O(n log h) 凸包算法及其实现

• 下载可执行文件 64 bits.zip - 210.4 KB
• 下载源代码.zip - 2.7 MB

2017-10-13：一篇包含更多额外比较、一种新的凸包点存储方式以及更多内容的更新文章：快速改进的二维凸包算法及其在 O(n log h) 中的实现

引言

本文介绍了一种用于寻找平面点集的凸包的极快算法。它还展示了其实现以及与其他许多实现的比较。

本文是系列文章三篇中的第一篇。

#	Ouellet算法文章链接	摘要
1	O(n log h) 凸包算法及其实现	本文。 算法内部工作原理的描述。
2	快速改进的 2D 凸包算法及其 O(n log h) 的实现	展示 C++ 实现。描述并展示使用 AVL 树作为凸包点容器的新实现。描述了许多额外的优化。展示了不同凸包算法实现的多次比较结果。
3	第一个也是速度极快的在线 2D 凸包算法， 每点 O(Log h)	添加了“在线”功能。还添加了辅助函数，使算法更灵活易用，且不影响原始性能。

什么是凸包

根据 维基百科：在数学中，欧几里得平面或欧几里得空间中点集 X 的**凸包**或**凸包络**是包含 X 的最小凸集。例如，当 X 是平面的有界子集时，凸包可以形象地理解为围绕 X 拉伸的橡皮筋形成的形状。

您可以在图 1 中看到一个简单凸包的示例。红线是凸包。

存在许多算法可以找到二维或三维的凸包。维基百科列举了其中的许多算法：http://en.wikipedia.org/wiki/Convex_hull_algorithms。

许多人多年来一直试图找到一种快速算法。许多人发现了出色的算法。最近，性能已达到 O(n log h)，其中 h 是构成凸包的点的数量。今天，我提出了一种这种量级的算法，事实上，我以另一种方式重新解释了 Liu 和 Chen 在 2007 年发现的算法。我还展示了它的实现，并将其与其他几种算法进行了比较。我将在此解释它的工作原理以及为什么它非常快。

动机

我最近需要为一个大型点集找到凸包。C# 中发现的简单实现非常慢，并且在处理大量数据时会崩溃。也有一些不是用 C# 编写的代码可以使用。但我想要一个快速可靠的 C# 实现。我没有理解网上找到的算法的每一个方面，或者太懒了不想去理解它们。我以为我有一个好主意，想验证一下。我决定编写自己的算法。此外，我还有一些其他的需求，想同时满足：保持原始点顺序不变，无需复制它们，并且能够进行多线程处理。

背景

本文涉及一些基本的数学和几何知识，如象限和斜率计算。但即使您不记得这些，也能理解主要概念。

对“二分查找”的了解也有助于理解所提供的概念和代码。

还有一个多线程部分可以跳过，而不会影响主要理解。

刘与陈凸包算法

另一种凸包算法。这没有初始排序，没有切线计算，它的工作方式不同。根据测试，它似乎非常快，并且有一些额外的技巧/优点......

速度

直到今天，“Chan”算法是最新的一种 O(n log h) 凸包算法，其中 h 是构成凸包的顶点数。我原以为它的实现被认为是速度最快的。但我认为“刘与陈”算法要么更快，要么与 Chan 算法非常接近。实际上，我必须在同一种语言中测试这两种算法才能确保进行适当的比较，但我缺少时间。我将展示不同语言的结果，Chan 用“C”语言，而“刘与陈”用 C# 语言。

其他要求

我找到的“Chan”算法的现有实现会对点进行原地置换以快速找到凸包。这种技术会修改原始点集的顺序。我项目的要求是保持原始点集的顺序。为了使用像“Chan”这样的算法做到这一点，我们需要在调用之前复制完整的点集。所需时间非常快，但它会在内存中占用两倍的点数，这对于低内存系统中的超大型点集来说可能是不 desirable 的。

此外，我的要求还包括寻找点列表的凸包的可能性，这在 Chan 和 Hull 中没有直接实现。我实现了这种可能性，同时保留了使用列表或点数组将算法与列表或点数组结合的常用方式。

刘与陈凸包算法的特点

刘与陈凸包算法实现的优势

• O(n log h)，与目前最好的算法复杂度相同
• 结果集与原始点集分离。输入保持不变。
• 保持较小的内存使用。
• 可以轻松进行多线程处理（所有线程进行第一次遍历，至少 4 个线程进行第二次遍历）。提供的代码使用两种方式（单线程和多线程）。
• 没有昂贵的计算（没有正弦、没有余弦、没有切线等）。只有斜率计算（减法和除法）及其使用被高度最小化。
• 可以从任何 IReadOnlyList<Point> (Point[]、list<Point> 等) 或任何 IReadOnlyList< IReadOnlyList<Point>> 调用。示例：点数组或点数组的数组。

其他优点，源于前述优点

• 输出敏感算法。我在这里提及它，仅仅是因为其他作者已在自己的文章中写过。在我看来，我认为任何在其复杂度中提及“h”的算法（例如：“O(n log h)”）都应该默认是“输出敏感的”。

刘与陈凸包算法该实现的缺点

• 非原地操作。结果集与原始点集分离，在点重新排序不是问题的情况下，这将占用不必要的额外内存。

刘与陈算法验证（结果：5个圆）

我将我的算法与卡尔顿大学 Pat Morin 在互联网上找到的 Chan Hull 实现进行了验证。这段代码对我修复错误帮助很大。我非常感谢 Pat Morin 分享了他的代码。在测试结束时，我发现 Pat Morin 的算法实现有一个小错误，当点数很少时会发生。

所有这些测试都是在单线程实现算法的情况下进行的。但我也将我的算法实现为多线程，固定为 4 个线程（Ouellet4），比我的单线程算法快大约 4 倍。我还做了另一个实现，其中我用所有线程进行第一次遍历，用 4 个线程进行第二次遍历（OuelletAll）。

图 2 显示了 3 种不同算法的 5 种实现的比较图表。所使用的点是从 5 个圆圈计算出来的，圆心随机，点数随机。每个圆圈都有一个固定但随机的半径。我宁愿使用这个测试而不是单个圆圈，因为我认为我的算法在这些情况下效率可能会低一点。所有使用的代码都在下载中提供。

刘与陈算法原理

“刘与陈”算法是为二维坐标开发的。它可能也适用于更多维度，但我不确定它是否能像在二维中那样可行和高效。

注意：查看示例部分将有助于理解以下文本。

算法分为三个主要部分，按顺序发生

• 第一遍 - 象限定义（查找左、上、右和下）
• 第二遍 - 为每个象限设置每个凸包点
• 组合 - 组合每个凸包点象限

该算法基于一个具有 4 个虚拟象限的 X 和 Y 平面。每个象限都有一个根点（参见图 3）。在学校我们学习到象限从 (0,0) 开始并覆盖平面的四分之一。但这里有所不同。您可以将我的“虚拟”象限视为相同，只是它们不从原点 (0,0) 开始，而是从我称之为“根点”开始。每个根点特定于每个象限。它们可以全部相同，但通常是 4 个不同的点。两个相对的象限可以重叠，或者象限之间可以存在孔洞。象限边界与 4 个点相关：最右、最上、最左和最右。这 4 个值是从所有点的完整迭代中提取的。这是第一遍。每个根点由其 2 个相关值（一个在 X 中，一个在 Y 中）及其 2 个相关点确定。象限的边界由其最小或最大 Y 坐标的 X 和其最小/最大 X 坐标的 Y 确定。例如，象限 1 (Q1) 由“上”的 X 和“右”的 Y 点确定。这 2 个坐标定义了象限根点。象限根点用于确定一个点是否属于该象限。下一节中的示例应该有助于理解这个原理。在尝试确定适当象限时可能会出现一种特殊情况，即当两个或更多点具有相同的最大 X 或 Y 坐标时，例如两个或更多“顶部”点。请参见 Q1 和 Q2 的适用示例。保留的 2 个点是彼此距离最远且最靠近每个相关象限侧边的 2 个点。这应该在 2 个象限之间创建一个孔洞，其中不可能有任何凸包点。

确定每个虚拟象限后，我再次遍历每个点，进行第二次也是最后一次遍历，尝试将每个点插入到其适当象限的适当位置。通过对照每个象限根点进行验证，可以轻松确定适当的象限。然后，我使用二分法查找插入新候选点的正确位置。搜索仅比较 X 坐标，但我也可以使用 Y 轴。为了知道是否应该插入新候选点，我们必须比较两个斜率：

• 要插入的候选点与其前一个点的斜率
• 候选点的前一个点与候选点的后一个点的斜率。

两个斜率的比较决定了该点是否应该被插入。是否包含它的决定取决于两件事：1- 比较结果（大于或小于），2- 象限本身。

要在两个点之间插入一个点，我们只需验证它的斜率是否介于其两个相邻点的斜率之间。插入一个新点也可能使一个或多个现有点失效，我们必须对每个新添加的点进行验证。潜在新失效点的验证应该从该新插入的点开始，并向上和向下移动，直到我们找到一个仍然是凸包一部分的有效点。

最后，我将每个象限的凸包点向量组合成一个向量，以形成完整的凸包结果集。

象限提供了巨大的优势。我们可以提前知道预期的斜率方向。知道了这一点，我们就可以轻松快速地：放弃一个候选点，改变一个现有点或添加一个新点。当点变得非常大时，要放弃的点的数量变得非常重要。能够快速放弃它们有助于提高效率。因为所有点都按象限组织和排序，所以我们可以在进行二分搜索的同时验证并潜在地快速拒绝坏的候选点。

示例

此示例针对以下 12 个点定义

(1,2) (5,3) (3,6) (2,2) (3,4) (6,1) (1,7) (-3,5) (-5, -2) (-4,-3) (2, -6) (-1, 7), (0, 7)

步骤 1 - 第一次遍历

我们遍历每个点，找到 4 个点：最右、最上、最左和最右点。我们通过这些点确定象限。您可以在图 3 中看到它们。这里我们有一个需要考虑的特殊情况，3 个点具有相同的 Y 值：(1,7)、(0,7) 和 (-1,7)。这些点都具有相同的 Y 值，这也定义了顶部。在这种情况下，我们只保留最远的点。这里我们保留 (-1,7) 和 (1,7)。(0,7) 将不用于定义象限限制。

步骤 2 - 第二次遍历

第二次遍历每个点，并将其作为凸包点插入或丢弃。在图 4 中，点“A”和点“B”分别在步骤 1 中被发现为象限 1 的起点和终点。我们已经插入了点“C”。我们想添加点“D”。CD 的斜率 (-3/2) 小于 BC 的斜率 (-1) => 我们应该保留“D”。我们将“D”插入为凸包点。现在，我们应该从“D”向两侧迭代，以丢弃因插入“D”而失效的任何点。在我们的例子中，“C”保留，因为它仍然是凸包的一部分 => AC 的斜率小于“CD”的斜率。如果我们想插入一个新点 (4,6)，这个插入将使“C”和“D”失效，它们将被移除以保持凸性。

接下来，是步骤 2 完成后的结果。图 5 显示了第二次遍历的结果。我们有 4 个不同的点向量，每个向量构成了完整凸包的一个象限部分。它们以不同的颜色显示。

步骤 3 - 组合

将每个象限结果组合成一个单一结果。图 6 显示了最终结果，其中每个象限结果都已组合在一起。您可以看到点 (-1,7) 和点 (1,7) 已连接。每个相邻象限中相同的点都已合并为一个点。

优化

预分配内存

在开始时，我使用以下公式计算了点数并分配了初始内存：点数平方根。这只是一个估计。在我的测试中，它与结果数量非常接近。但它不一定能满足所有需求。如果此优化不符合您的要求，没有什么能阻止您计算内存结果的初始大小，或者让它根据需要自行增长。但请记住，当列表需要增长其内部数组时，会产生开销。在我的测试用例中，这是一个非常好的估计，我宁愿选择这种方式，而不是让列表自行增长或预留总点数。

无需计算即可丢弃点

由于象限的使用，在大多数情况下（当有大量随机点时），我可以通过仅比较其 Y 坐标与其前一个或后一个 Y 坐标来丢弃一个点，而无需进行任何计算。这种快速测试是因为我们已经在 X 轴上使用了二分法，因此我们知道新候选点应该位于其两个“X”坐标相邻点之间。如下例图 7 所示，如果“B”和“C”已经作为凸包点插入。如果“E”和“F”的 X 坐标位于“B”和“C”的 X 坐标之间，则“E”和“F”将成为“B”和“C”的潜在新邻居候选点。但是我们不需要验证这两个点的斜率，因为这两个点的 Y 坐标都小于“C”的 Y 坐标。我们可以立即丢弃它们，而无需计算斜率。

特殊情况

存在一些特殊情况，需要注意或至少进行验证以确保正确的结果。

输入集合中没有点

当集合中没有点时，我们不应做任何事情，并返回一个空集合。

仅一个点

当集合中只有一个点时，我们只返回包含该一个点的集合。尽管我们要求闭合图形，但我们只应返回该单个点。

2 个点

当集合中有 2 个点时，我们返回包含 2 个点的集合，或者当 2 个点相同时返回包含 1 个点的集合。我们还必须验证闭合图形是否按预期工作。我们还应该验证当 2 个点与 X 轴或 Y 轴对齐时是否具有正确的行为。

任意点成线

2 个或更多点具有相同的顶部、左侧、右侧或底部。

重叠象限

它只能同时发生在两个相对的象限上。这是一个非常特殊的情况，需要注意。当使用大量随机放置在圆中的点进行测试时，它不会（极不可能）发生。但在点沿对角线形状放置或点呈三角形形状的任何情况下都可能发生。例如，在图 8 中，点“A”属于红色象限 (Q1) 和橙色象限 (Q3)。如果我们只验证点是否适合第一个象限，这可能是一个问题。在这种情况下，点“A”是 Q1 的一部分，但不参与 Q1 的凸值。它只能作为 Q3 的凸值参与。但如果我们在 Q1 中首先测试了“A”，然后立即切换到下一个点进行评估，那么我们就会错过该点作为凸包点。当存在重叠象限时，我们应该与它的对立象限进行验证，以确保不会丢失任何可能的凸包点。

另外，值得注意的是，根据实现方式，当点集呈三角形或对角线形状时，算法可能会失去性能。它仍然是 O(n log h)，但在这些最坏情况下，一个点需要针对两个不同的对立象限进行验证，这可能会使其运行时间接近两倍。

 

图 8：重叠象限

所提供的代码

所提供的代码很好地近似了在几种算法中找到凸包所需的时间。用于测试的算法是 Chan 和“刘与陈”。请务必在“Release”模式下运行，而不是“Debug”模式，以获得正确的性能比较结果。比较结果显示在输出窗口中并保存到临时文件夹中。在评估性能结果时，您需要了解并考虑以下几点：

• “Chan”算法及其变体是用“C”语言实现的，而所有“刘与陈”实现都是用“C#”语言实现的。
• “Chan”是原地算法，而“刘与陈”创建另一组点作为结果。
• 我编译的实际“Chan”实现是 32 位的。由于是 32 位，这迫使我运行最大约 400 万个点。请注意，我找不到用于创建 DLL 的项目。我有源代码，但我对“C”语言不够精通，无法将其重新编译为 64 位。
• 卡尔顿大学的代码详情包含在 zip 文件中。
• 我还包含了一个只能在 64 位环境下测试的小应用程序。它使用非常大的点集测试了“刘与陈”凸包的每种实现。它表明，当点数巨大时，在第一次遍历中使用所有核心可能会变得很有趣。但总的来说，我不会介意使用强制的 4 个独立线程，它提供了出色的性能。
• 性能比较是按顺序进行的。

几乎相同的“刘与陈”算法可以以 3 种不同的配置使用：

• 单线程：算法的每个 3 个步骤只使用一个线程。
• 4 个线程：第 1 步使用 1 个线程。第 2 步使用 4 个线程，第 3 步（组合每个象限结果）使用 1 个线程。
• “所有线程：使用所有核心评估象限限制（第一步），然后第二步与“4 个线程”相同，最后使用 1 个线程组合每个象限的结果。

摘要

• 请注意：“错误的图像格式”错误可能会在您尝试在 64 位下编译项目“ConvexHullTest”时发生。但“ConvexHullPerfTest”
• 仅”项目旨在以 64 位编译和运行。
• 使用的图形控件是 DynamicDataDisplay。它免费且美观，但速度慢。避免在超过 10000 个点时使用它。
• 您也可以使用点集合的集合来调用我的算法，这是我们项目的要求。接口使用 IReadOnlyList，我认为这是我的算法所需的最开放的接口。数组或“List”都可以完美工作。
• 代码旨在在 Framework 4.5 或更高版本中运行。请注意，“IReadOnlyList<T>”始于 .Net 4.5。

未来 - 潜在发展

未来有一些潜在的开发方向……乐趣从此开始。

算法性能

该实现在算法本身的单线程方面仍有改进空间。例如，可以利用候选点与其象限根点的角度来提高正确插入点的性能（二分查找与非常接近精确插入点）。它能否达到 O(n) 或接近 O(n)？

多线程性能

多线程性能也存在许多可能性。我本应将第二次遍历完全多线程化，但我当时没有时间。我认为，每个象限一个主线程，带有只提取有效候选点的从属线程，会非常棒。主线程将是唯一一个在其象限中插入点的线程。主线程和从属线程之间有一个只包含可能候选点的并发栈。主线程将优先清理栈，然后执行与从属线程相同的操作。这样做仍然可以继续利用第一次遍历（确定左、上、右和下）的全部潜力。

此外，将点分离成桶将使每个线程完全独立（除了并发栈），并最大限度地利用所有线程的时间。桶分离也可以不均匀，开始时几个大桶，结束时许多小桶。还可以做的一件事是快速验证一个象限是否没有点（如果其形成边界的两个点相同），然后完全跳过该象限。

3个或更多维度

它也可能在 3 个或更多维度中实现，但复杂性可能会成为一个问题。为了消除这种潜在的复杂性，我们可以精确地分离每个象限的特殊性，然后只进行一次通用实现。但这可能会由于每个特定象限需求所需的调用而降低性能，或许模板可以解决这个问题？

重要说明

2014-08-11

在尝试将我的文章发表到算法期刊后，我必须改进我的测试，并使用相同的语言并在“release”模式下编译，而之前并非如此。最初的测试是在“C”32位-“Debug”模式下对 Chan 算法代码进行的，而“Liu and Chen”则在 C# 64位-“Release”模式下进行。我花时间重新编译了 Chan 的“C”实现，使其在 64 位-“Release”模式下运行。随后的结果使原始文章中显示的所有统计数据失效。Chan 在“C”中变得比我的 C# 实现快两倍，而不是相反。两者都在 64 位发布版本中编译。

我更新了图表和部分文本。这花了我一些时间，因为我试图将我的代码转换为 C++，这比我最初想象的要长。我还没有完成，但我希望更新这篇文章，以确保不会将错误的结果流传太久。

致歉：我想向所有人道歉，我误导了大家。我的算法仍然可能是最快的，但这不确定，而且我认为可能不是。如果我能有足够的时间完成 C++ 的转换，我会告诉大家结果。

2014-07-25

2014年7月25日14时，我偶然发现了一篇旧文章，其中包含了我所介绍的算法的主要概念。

这篇文章来自广辉·刘和传波·陈：一种计算平面点集凸包的新算法。它于 2007 年在 Springer 出版。

因为为我并非第一个创建的算法邀功是不公平的，我将凸包算法从“Ouellet”凸包算法更名为“Liu and Chen”凸包算法。但请放心，我是完全独立创建的。您在这里看到的一切都源于我……我并非第一个。

您可以将本文视为 Liu 和 Chen 凸包算法的一种实现。

参考文献

• Hervé Brönnimann、John Iacono、Jyrki Katajainen、Pat Morin、Jason Morrison、Godfield Toussaint 合著的《空间效率的平面凸包算法》。此参考文献来自一份 PDF 论文“insitu-tcs.pdf”，我已无法在网上找到，但已包含在我的下载中。Chan 实现的“C”代码也来自同一来源。代码作者是卡尔顿大学的 Pat Morin。我也将源代码作为参考包含在内。尽管该实现存在一个错误，但它确实对我发现所有错误提供了很大帮助。我怀疑这只是“<”而不是“<=”或类似问题。
• 这是一个链接，指向一篇文章，该文章很好地解释了许多流行的二维凸包评估算法：http://www.tcs.fudan.edu.cn/rudolf/Courses/Algorithms/Alg_cs_07w/Webprojects/Zhaobo_hull/（2017-09-05，此链接已失效，抱歉）

致谢

• 感谢我的项目经理 Omar Saad 给我解释了什么是凸包，并让我有时间撰写这篇文章和代码。
• 感谢我的同事 Paul Labbé 向我展示了向量乘法。
• 感谢 Pat Morin 提供的免费“C”语言 Chan 算法实现代码。
• 感谢 Henri de Feraudy 审阅我的文章，并给了我大约一百条语法和语法修改建议，使其变得更好（2017 年 11 月）。

历史

1. 版本 1.0 - 2014-05-20 发布，初始发布
2. 版本 1.1 - 2014-05-21 发布，修复了代码中的一些小错误。文本略有修改。
3. 版本 1.2 - 2014-05-22 发布，根据同事的评论修复了部分图片和文本。
4. 版本 1.3 - 2014-06-17 发布，代码变更：使用 StopWatch 代替 DateTime，并添加了矩形性能测试。这两个建议都来自 Qwertie - 谢谢！
5. 版本 1.4 - 2014-07-24 发布，文本略有修改/改进。图 8：重叠象限的更正。
6. 版本 1.5 - 2014-07-25 发布，非常糟糕的一天...我意识到我不是第一个发现这个算法的人。我修改了我的算法，不再为我并非第一个发现的东西邀功。内容和代码仍然有效，但请阅读开头的勘误表以查找首次发表该算法的文章。我还会更新维基百科，因为它不在那里，这也是我写这一切的原因。
7. 版本 1.6 - 2014-08-11 发布，又是一个糟糕的日子，就在 2014-07-25 之后，我花了一些时间在 64 位发布版中找到/编译了 Pat Morin 的 C++ 版 Chan 算法（之前是 32 位调试版）。结果简直令人惊叹。该算法速度极快，比调试版快两倍多。我相应地更新了文章，也更新了比较图表。实际结果显示 Chan 算法在性能上具有明显优势。但要进行适当的比较，还有一些事情要做：将我的实现从 C# 转换为 C++... 我已经开始了，但我缺少时间。
8. 版本 1.7 - 2016-02-04，Smjert 提请我注意一个错误。非常感谢。错误在 Q4 中。
9. 版本 1.8 - 2016-02-13，修正了 Q2 和 Q3 中的两个小错误，当要检查插入的新值与已存在的 Hull 值具有相同的 X 值时。添加了一些测试以确保检测到这些情况。我还添加了 Pat Morin 的 64 位 Release 版 Chan Hull 实现（之前是 32 位 debug 版）。特别感谢 Smjert：在他提出问题后，我意识到我没有充分关注这种情况，并进行了一些检查以确保行为正确。
10. 版本 1.9 - 2016-02-17，最主要的改变是丢弃点的新方法。我不再使用斜率，而是使用向量乘法。我从 Tryss 的 http://forums.futura-sciences.com/mathematiques-college-lycee/510583-point-dun-cote-de-lautre-dune.html 中获取了公式。这个想法来自我的同事 Paul Labbé。他的想法带来了更好的性能和更清晰的代码，因为我可以将特定的象限代码转移到它们的基类中。它使用两次乘法而不是一次除法，但仍然更快。我添加了测试来证明这一点。它还使用更少的内存。我修复了一些在极少数情况下可能发生的错误。我重写了所有内容。它更简单，更容易理解。我添加了更多的测试，这让我认为我没有更多的错误了。附带一提，我知道我必须用这些相关的更改更新我的所有文章，我会在完成其他相关工作后尽快完成。我只是想尽快分享我的所有工作。我非常相信这是迄今为止最快的二维凸包算法 :)。希望您会喜欢。
11. 版本 1.9.1 - 重新排列段落，以避免文章以两个勘误表开头。我将它们移至“重要说明”部分。
12. 版本 1.9.2 - 删除了“复旦大学”的超链接，因为它已过时且找不到替代方案。抱歉。
13. 版本 1.9.3 - 2017-10-13 发布，添加了指向一篇关于相同算法的新文章的链接：快速改进的二维凸包算法及其在 O(n log h) 中的实现
14. 版本 1.9.4 - 2017-11-17 发布，应用了重大修正。非常感谢 Henri de Feraudy 对我文章的详细审阅。他是一位完美的陌生人，在自己的时间里免费完成了这项工作。您可以查看他的 Google+ 网站，了解他的一部分知识。他给我带来了大约一百条语法和语法修正。
15. 版本 1.9.5 - 2017-12-11 发布，修复了第一象限点数为 0 或 1 时的一个错误。该错误由 StackOverflow 上的“ephraim” 报告。非常感谢他！源代码和二进制文件已修复。注意：新文章 不受此错误影响（它已经修复）。