快速改进的 2D 凸包算法及其 O(n log h) 的实现

源代码可在 GitHub 获取，二进制文件（可执行文件）可在此处下载：下载 OuelletOnlineConvexHull.zip

注意：选择横向打印比纵向打印效果更好。

引言

本文是三篇系列文章中的第二篇

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

一个小请求

在阅读完本文后，如果您认为这个算法足够优秀，可以被收录到维基百科 – 凸包算法中，我将不胜感激您能添加一个指向刘和陈的文章（或我写的两篇文章中的任何一篇，即本文和/或凸包算法及其 O(n log h) 实现）的链接。但请务必先阅读这一节：附录 B – 我在维基百科的经历。

再次撰写关于几乎相同算法的新文章的原因

本文是第一篇文章的延续：凸包算法及其 O(n log h) 实现。新文章的动机是：

1. 最初的原因是展示一个新开发的 Ouellet 算法的 C++ 实现。根据提供的性能测试，这个新实现比 Chan 算法的 C 语言实现（也已提供）快大约 4 倍。
2. 添加并展示 Ouellet 算法的另一个实现，该实现使用 AVL 树作为凸包点的容器，而不是基于数组的容器。基于 AVL 树的实现有两个版本：一个简单版本和一个效率更高、增加了许多优化的版本。
3. 解释 AVL 版本中增加了哪些优化以获得更好的性能（Ouellet AVL v2 vs Ouellet AVL）。
4. 分享我的工作台工具，以便轻松比较使用点的二维算法，如凸包算法或任何其他以点为输入并以点为输出的算法。例如，该工作台也可用于测试最小包围圆算法（代码已提供）。
5. 展示并记录对我算法第一版的一些改进，这些改进使我的 C# 凸包实现现在比 Pat Morin 用 C 语言编写的 Chan 算法实现更快（至少在我用于测试的所有“正常”随机点生成器上是这样）。
6. 展示许多现实生活中的凸包算法实现，并比较它们的性能。
7. 展示一个生成点集所有排列可能性的最快实现（代码已提供）。
8. 分享其他想法/发现（多线程、维基百科、最小包围圆等）。

什么是凸包

定义

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

图 1：凸包示例（红色部分），来自所提供的工作台

凸包在二维和三维中的应用

凸包算法是计算几何中的一个基础算法，许多计算几何算法都基于它。此外，还有很多应用使用了凸包算法。

凸包被用于许多领域，在这些领域中，环绕所有点所占空间路径的信息变得很有价值。以下是一些例子：

• 确定电力公司网络模拟的阻抗区域（IEEE）。这就是我几年前接触到凸包的原因。
• 它可以作为其他算法的输入，以提高其性能。例如，一个常见的最小包围圆算法可以通过快速凸包算法实现对点进行预处理，从而大大提高性能。性能差异可以在提供的基准测试中看到。
• 凸包可用于图像处理。
• 用于GIS 系统中，创建一个包含多边形的要素类，这些多边形代表包围每个输入要素或每组输入要素的指定最小边界几何体。
• 还有许多其他应用……Quora 上的 11 个应用

凸包的寻找也在大学里被广泛使用和研究。

凸包算法的性能和复杂度

有许多具有不同复杂度的凸包算法。维基百科 - 凸包算法列出了其中许多。Ouellet 凸包（或刘和陈）算法不在维基百科中。有关原因的更多信息，请阅读本文末尾的附录 B – 维基百科。算法性能的一个好指标通常与其复杂度有关。建议选择复杂度最低的算法。在凸包的情况下，速度测试结果证实了这条经验法则。目前，已知的凸包算法的最佳复杂度为 O(n log h)，其中：

• “n”是所有源点的数量
• “h”是在所有源点中，构成凸包路径的结果点集。

根据测试和个人经验，在一般用例中，“h”远小于“n”。例如，在我的测试中，对于一个圆内的 20,000,000 个随机点集，对于常规的随机生成器（圆形或抛弃型），凸包通常由 200 到 600 个点组成。考虑到存在复杂度为 O(n²)、O(n log n) 和 O(n log h) 的算法，很容易意识到，将复杂度基于“log h”而不是“log n”会极大地提高性能。但也有可能两个算法具有相同的复杂度，其中一个却比另一个快得多。这就是本文的主要原因。但正如您将看到的，并且可以用提供的代码自己测试，一般情况下的结果表明，Ouellet 算法是最快的，并且优势相当明显。根据您的需求，它还有其他优点。在比较时，您还应该考虑算法实现的语言。在实际测试结果中，您必须考虑到 C# 的声誉是比 C 慢。我个人的测试似乎与 C# 比 C++ 慢得多的事实相符，至少对于这个算法的实现是这样。

Ouellet 凸包算法

工作原理

关于 Ouellet 算法内部工作原理最详细的描述可以在以下地方找到：

• 我的第一篇关于它的 CodeProject 文章：凸包算法及其 O(n log h) 实现
• 刘和陈的原始科学论文：一种计算平面点集凸包的新算法。

更多信息可以在后面的章节中找到：Ouellet VS. 刘和陈凸包算法的差异

算法主要思想

这是一个简要总结。更多信息可以在凸包算法及其 O(n log h) 实现中找到。

该算法有 3 个按顺序发生的主要步骤

• 步骤 1 - 确定虚拟象限边界
  • 我们找到所有输入点的边界（左、上、右、下）（对所有输入点进行第一次遍历）。
  • 我们根据边界点定义 4 个虚拟象限（Q1 基于最上和最右的点，其根点基于最上点的 x 坐标和最右点的 y 坐标）。每个象限都采用相同的方法。
  • 每个凸包点将按象限（虚拟象限）保存，并始终保持有序。注意：在所有提供的实现中，每个象限的所有点都按逆时针顺序存储。
• 步骤 2 - 寻找凸包点
  • 对于每个输入点，我们判断它是否属于某个象限，如果是，则将其作为凸包点插入。
    • 使用二分法，我们搜索一个输入点如果适用应该插入的位置。
    • 如果输入点是凸包的一部分，我们插入它。如果是这种情况，我们还会移除任何因为新凸包点而失效的邻近点。
• 步骤 3 - 合并象限结果
  • 合并 4 个象限的凸包点结果，移除象限边界处的任何重复点

Ouellet VS. 刘和陈凸包算法的差异

在深入探讨凸包优化之前，应该明确的是，刘和陈的凸包算法与 Ouellet 算法基于相同的原理：虚拟象限，至少根据我从刘和陈的文章《一种计算平面点集凸包的新算法》中理解是这样的。刘和陈的文章没有提供任何代码、实现细节或相关链接。因此，我决定将我的第一个实现代码重命名为：刘和陈。自那时以来，已经添加了许多优化，提高了性能。附带的基准测试结果显示了这些差异。

根据发表日期：2007-07-01，刘和陈是第一个发现使用虚拟象限原理的人。优化可以被视为“刘和陈”与“Ouellet”之间的差异。

优化

以下优化是可选的，可以应用于 Ouellet 凸包算法的一个或多个版本。有些仅用于 Ouellet CPP 版本，而大多数则应用于 Ouellet AVL v2 版本。刘和陈的实现中不包含这些优化。

斜率 VS 叉积

在 Ouellet 凸包算法中，要将一个新点作为潜在的凸包点插入，需要知道它位于其应插入位置的两个相邻点的左侧还是右侧。这可以通过两种方式完成：

确定一个点相对于另外两个点的位置的方法	斜率	叉乘
公式
描述	通过比较两个斜率。对于 A、B、C 三个点，其中 A 和 B 是待比较的新点 C 两侧的点。比较 (AB) 的斜率和 (AC) 的斜率。 注意：斜率 (AB) 可以很容易地被缓存，以便下次节省一些计算。	直接使用叉积。在前面的 A, B, C 公式中 如果 (d>0) 则 C 在左侧 如果 (d=0) 则 C 在同一条线上 如果 (d<0) 则 C 在右侧。
所需计算	2 x (2 次减法和 1 次除法) = 4 次减法和 2 次除法 **	5 次减法和 2 次乘法
算法中的最终结果	稍慢	稍快

算法中的结果

在算法中使用叉积带来了轻微的性能提升。刚好足以在某些情况下击败 Chan 算法。但它也简化了潜在凸包候选点的选择。叉积可以完全相同地用于所有象限，这实现了三件事：

• 通过将点选择提升到每个象限的基类，简化并改进了代码架构（更通用）。
• 通过移除点结构中斜率的缓存管理来简化代码
• 通过从点结构中移除缓存的斜率，减少了内存占用。可以使用框架中已定义的点结构。

乘法 VS. 除法

基准测试结果

根据附带的基准测试，乘法比除法快 1.14 倍。要了解更多关于测试条件的信息，请参见用于测试的硬件。两者速度的差异部分解释了为什么叉积稍快一些。还应考虑许多其他变量，如 CPU 流水线、内存邻近性等。

快速丢弃 (QD)

快速丢弃是“刘和陈”算法与 Ouellet 算法之间存在的第一个差异。它是在 Ouellet 算法中添加的一个简单检查，在二分搜索的每次迭代中进行，在大多数情况下，会因为点被拒绝而快速停止搜索，而无需进一步深入二分搜索。检查是否可以拒绝当前评估的点的操作不需要任何计算，只需要与二分搜索路径上的每个点进行一次简单比较。这个优势来自于我们使用象限，并且象限的凸包点总是排序的。通常，进行这个简单测试所花费的时间将节省执行所有二分步骤的时间，因为一个点可以在最初的几步中被快速丢弃。快速丢弃之所以成为可能，是因为二分法正在向其插入点合并。如果我们考虑到“h”（凸包点的数量）通常远小于“n”（输入点的数量），那么在大多数情况下应该能节省时间。换句话说，有大量的点应该被丢弃，快速丢弃一个点的机会很高。

在刘和陈算法和 Ouellet 算法之间，使用了两种最有价值的（更接近现实生活）随机生成器进行了测试：抛弃型和圆形。刘和陈算法没有 QD，而 Ouellet 算法有。在坏情况下（抛弃型点随机生成器），QD 只是稍微慢一点（可忽略不计），并且对于任何数量的输入点都相当稳定。在好情况下（圆形点随机生成器），对于 100,000 个点，QD 快 1.2 倍，并且性能随着点数的增加而缓慢提升。没有 QD 可能会更糟，但差别非常小，所以这是一个很好的补充，应该能在一般使用中提高性能。同样的测试可以很容易地用提供的基准测试来完成。

对象限检查 (OQC)

在 Ouellet 算法中，由于象限的定义方式，两个相邻的象限不能有任何相交区域。奇数和偶数象限是互斥的，而两个相对的象限可以共享一个区域。

在算法的早期版本中，点的象限归属是根据象限根点计算的。对象限可能有一个相交区域（见下例）。因此，算法应该对相交区域中的任何点进行对象限检查（OQC）。OQC 的必要性来自于，即使一个点已被识别为属于特定象限，也需要检查它是否在它的对象限中。这种情况只在某些特定的点分布中发生，但应予以考虑。

下面的例子展示了一种情况，其中点的分布迫使算法进行对象限检查。在这个例子中，根据每个象限的根点，P1 同时属于两个象限（Q1 和 Q3）。这种情况主要发生在点分布为一条狭窄的对角线时。

这里我们有粉色的虚拟 Q1 和绿色的 Q3，每个象限的根点为菱形，颜色与其象限相同。如您所见，黄色的点 P1，应该被评估以确定它是否是凸包的一部分，它被包含在 Q1（粉色区域）和 Q3（绿色区域）中。但是，如果我们只为 Q1 评估 P1 并丢弃它，而不去核对 Q3，那么我们就会丢弃一个好的候选点。为了确保不错过任何象限检查，最懒惰的方法是检查每个点与每个象限的关系。但这可以很容易地通过仅在点被识别为属于某个象限时，对其对象限进行验证来优化。在大多数算法实现中，每个点都会与所有可能的象限进行检查，以确保不会错过任何象限中的任何点。但在 Ouellet CPP 和 Ouellet AVL v2 中，添加了一些优化（参见关于 Ouellet 凸包每个实现的具体信息）。我们可以很容易地看到奇数和偶数象限是互斥的。换句话说，如果一个点属于 Q1 或 Q3，它就不可能属于 Q2 或 Q4，反之亦然。

对象限检查旁路 (OQCB)

另一个优化是，一旦一个点在任何二分步骤中被估计为凸包点（而不仅仅是属于某个象限），就不需要再对它进行任何其他象限的检查，包括它的对象限。它不能同时属于两个象限的凸包点。对象限的检查仅对于已被识别为属于某个象限但未被识别为潜在凸包点的点是强制性的。只有象限边界点可以同时在两个象限中，这些点将在算法的第三步合并成一个点。这个优化只在 Ouellet CPP 和 Ouellet AVL v2 中实现。

不相交象限检查 (DQC)

PCZ

每个象限的第一个和最后一个点总是按逆时针定义的。PCZ 是“潜在候选区”，由象限的第一个和最后一个点定义。它是象限第一个和最后一个点右侧的区域。这个区域对于每个象限都是唯一的，并定义了可以添加的潜在候选点的区域。该区域之外的任何其他地方都不可能包含该象限的任何有效凸包点。

使用 PCZ 的 DQC

还有一个很好的优化，只在 Ouellet AVL v2 中使用。它是在开始时验证所有象限是否不相交。要验证这一点，我们只需要检查一个象限的根点是否在其对象限的 PCZ 之外。如果所有象限都满足这个条件，那么如果一个输入点落入一个象限，我们就可以跳过任何其他象限的检查，包括它的对象限。

该优化需要两件事：

1. 在算法的第二步之前进行一次验证，以确定象限是否不相交。
2. 根据象限是否不相交，为算法的第二步提供不同的代码
   • 如果不相交，使用 DQZ
   • 如果不相交，使用原始算法代码

     

     Q3 是 Q1 PCZ（黄色）的一部分。象限不相交，因为至少有一个根点（菱形）在其对象限的 PCZ 内。

     

     所有根点（菱形）都不在其任何对象限的 PCZ（黄色）内。可以使用 DQC 优化。

PCZ 点归属 (PCZB)

PCZ 在不相交象限检查的开头有解释。使用象限的 PCZ 来确定当前点的象限归属。

为了快速保留/丢弃潜在的候选点，我们可以首先通过使用叉积来检查它是否属于目标象限的 PCZ，而不是使用象限的根点。进行叉积计算有成本，但使用它可以避免我们进行许多二分迭代。它还有一个优点，即位于一个象限的 PCZ 内的点，不可能是任何其他象限的凸包点。Ouellet AVL v2 使用了这种优化。

前一象限 (PQ)

另一个仅在“Ouellet AVL v2”中完成的优化是，总是从上一个添加了点的象限开始检查，然后按顺序循环检查剩余的象限。这种优化在某些情况下可能很有用，即连续待评估的输入点很有可能彼此相邻，从而属于同一个象限。这样做也可以让我们跳过不必要的其他象限检查，从而提高性能。尽管这种优化在随机点放置中没有任何优势，但它也不会带来任何坏处。这是一种在某些情况下可能很好，而在所有其他情况下没有影响的优化。

算法

算法比较

总体描述

算法名称	作者	支持的维度	原地*	参考资料
单调链	M. Andrew	2	是	算法实现/几何/凸包/单调链
Graham扫描	Ronald Graham	2 (3?)	?	Graham扫描
Delaunay/Voronoi	Boris Delaunay 和 Georgy Voronoi	任意	?	Delaunay 三角剖分 和 Voronoi 图
Chan	Timothy M. Chan	3 (根据维基百科)	是	Chan 算法
刘和陈 / Ouellet	刘和陈 / Ouellet	2（很可能：任何维度，但有待证明）	否	一种计算平面点集凸包的新算法 (Springer) 或 Code Project 或本文

*原地意味着点直接在其源容器中移动，影响原始顺序。如果您不能接受这一点，应在调用算法之前复制源点。

复杂性

算法名称	复杂性
	速度			内存
	最佳	典型	最坏	典型	最坏
单调链	?	O(n log n)	?	O(n)	O(n)
Graham扫描	?	O(n log n)	?	?	?
Delaunay/Voronoi	O(n log log n)	O(n log n)	O(n log n)	O(n)	?
Chan	O(n log h)	O(n log h)	O(n log h)	O(n)	O(n)
刘和陈 / Ouellet	O(n log h)	O(n log h)	O(n log h)	O(n) *	O(n) *

* 针对 AVL 实现给出。精确值为：n+(h*2)+(h*2*sizeof(pointer))

算法实现信息

这是一个实现细节列表，以便更好地理解任何差异。

算法名称	实现名称	实现			参考/说明
		语言	#线程	作者
单调链	MonotoneChain	C#	1	David Piepgrass	Loyc – C# 中的二维凸包：40 行代码
Graham扫描	HeapHull	C	1	Pat Morin	在我告知 Pat Morin 其 Chan 算法实现中有一个小 bug 后，指向他代码的链接已被移除。本文源代码中提供了该代码的副本。
Delaynay/Voronoi	MI 凸包	C#	1	设计工程实验室	GitHub，虽然不是 O(n log h)。我之所以包含它，是因为代码是公开的，在 3D 世界中广为人知，并且我想展示算法复杂度（大 O 表示法）在性能上的重要性。
Chan*	Chan	C	1	Pat Morin	在我告知 Pat Morin 其 Chan 算法实现中有一个小 bug 后，指向他代码的链接已被移除。本文源代码中提供了该代码的副本。
刘和陈	刘和陈	C#	1	Eric Ouellet	Ouellet (刘和陈) 算法的原始首次实现
Ouellet	Ouellet C++	C++	1	Eric Ouellet	虽然它与“Ouellet 1”是几乎相同的算法，但不能直接用来比较语言，因为我在 C++ 中做了一些 C# 版本中没有的优化。
	Ouellet 1	C#	1	Eric Ouellet	单线程（名称基于算法的第二遍）
	Ouellet 4	C#	4, 4, 1	Eric Ouellet	算法的 3 个过程分别在 4 个、4 个和 1 个线程中完成。
	Ouellet 多线程	C#	M, 4, 1	Eric Ouellet	与 4 线程相同，但第一遍是使用所有可用线程进行多线程处理。
	Ouellet AVL	C#	1	Eric Ouellet	AVL 实现的代码派生自 Bitlush

* 当前的实现有一个非常小的 bug，它很少出现，主要是在点数很少的时候。这个 bug 可以通过工作台很容易地显示出来，但它是随机的（我不知道原因）。提供的代码由卡尔顿大学的 Pat Morin 编写。
 

Ouellet 凸包算法实现比较

名称	实现描述	语言	线程（每步）	容器	优化						注释
					QD	OQC	OQCB	DQC	PCZPI	PQ
刘 & 陈	首次实现	C#	1-1-1	列表 (数组)							我将我的第一个实现重命名为刘和陈
Ouellet ST	第一个实现，增加了 QD 优化	C#	1-1-1	列表 (数组)	x						快速、简单。参见数组问题
Ouellet 4T	为提高速度的第二次实现	C#	1-4-1	列表 (数组)	x						比 1T 快
Ouellet MT	第三次实现	C#	M-4-1	列表 (数组)	x						比 4T 稍快
Ouellet C++	第四次实现	C++	1-1-1	数组	x	x					在一般情况下最快。许多“goto”，代码冗余……以速度为重，代码看起来很糟糕。
Ouellet AVL	第五次实现	C#	1-1-1	AVL 树	x						不受大的“h”（凸包点）影响，因为凸包点的底层容器是 AVL 树。它不会预先保留更多空间以减少堆分配器请求。由于算法的性质，树似乎是天然的容器（最近发现的）。
Ouellet 数组	第六次实现（对复制数组数据的几种方式进行了少量测试）	C#	1-1-1	数组	x						一些测试，看是否可以通过使用数组而不是“List”来获得更好的性能。此外，当使用数组时，是否有更快移动数据的方法。
Ouellet 数组 Immu	第七次实现	C#	1-1-1	数组但不可变	x						我不是只复制数组插入点后的重叠数据（为新点腾出空间或移除任何点），而是复制整个数组。这使我能够在多线程中保持数据一致。
Ouellet MT	第八次实现（此处未展示）	C#	M-M-1	列表 (数组)	x						尝试产生一个 O(n) 的算法。见下注：O(n) 的凸包
Ouellet AVL v2	第九次实现	C#	1-1-1	AVL 树	x	x	x	x	x	x	Ouellet AVL 的一个分支。我主要改变了检查一个点是否属于一个象限的方式，以节省更多一点时间。许多优化仅包含在此实现中。

代码

该基准测试是使用 Visual Studio 2017 制作的。框架是 WPF，带有一些 MVVM。算法全部用 C# 制作，除了少数明确说明是用 C/C++ 制作的，详情请见算法实现信息。所有测试都是在优化代码并编译为“Release”模式下进行的。

注意：唯一缺失的 O(n log h) 算法是“终极平面凸包算法”。因为需要计算中位数，所以它很有可能比任何其他现有的 O(n log h) 算法慢。如果我找到了任何实现，我会把它包含在这里。

实现选择

数组 VS. 列表

“List”类是 C# 的一个集合，它使用数组作为其底层容器。使用“List”而不是数组应该有相似的性能。测试证实，直接管理数组在性能上有非常小的提升。这种差异非常小，以至于很难证明使用数组带来的清晰度损失是值得的。两种集合已在不同的实现中使用，可以相互比较。

数组 vs 树

除了 Ouellet AVL 版本，所有 Ouellet（以及刘和陈）的实现都使用了基于数组的容器。Ouellet AVL 和 Ouellet AVL v2 使用 AVL 树来存储潜在候选点，而不是基于数组的容器。使用基于数组的容器意味着需要手动管理二分查找。而树，由于其性质，内部实现了二分查找。使用二分查找来获取合适的插入点可以确保良好的性能，并且是保持 O(n log h) 复杂度的关键。根据我的测试和一次实际使用经验，我怀疑“h”在大多数情况下会保持在 1000 以下，这使得使用数组或树没有太大区别。但对于“h”可能非常大的情况（在我的测试中约超过 500,000 个点），使用树会更安全。否则，在基于数组的容器中，插入/删除时发生的项目移动会变得过于突出，并对性能产生太大影响。

数组的优点是（与树结构相比）：

1. 数据是连续的，可以实现更高的 CPU 缓存命中率。
2. 在大多数情况下，只需要一次对堆分配器的调用就可以获得一个足够大的数组来容纳所有凸包点。这是基于使用随机点生成器作为输入点源的多次测试得出的，如这里的基准测试所述。当前的实现在开始时保留 1000 个点的空间，以减少堆分配器请求。对于 1,000,000 个点，使用所有正常的随机生成器（非“弧形”生成器），结果几乎总是保持在 800 个凸包点以下。
3. 可以使用索引，这使得可以直接访问点。实际上，直接访问可以在多线程算法中实现 O(n) 的性能，但一些测试显示结果比当前实现慢。性能较慢的原因似乎是多线程锁定机制。关于我做的一个没有达到预期效果的快速测试的更多信息，请参见O(n) 凸包。此外，由于“h”在大多数情况下非常小，应用于“n”的多线程机制的开销应该非常低，以免比与“h”相关的时间更显著。O(n) 测试不包含在提供的代码中。

使用数组相对于树结构的主要缺点是：

当“h”的数量变得很大时，大约超过 500,000（Ouellet C# 实现），数组容器解决方案会因为两个原因而变得昂贵：

1. 主要原因是我们每次插入或删除候选点时都必须移动点。
2. 此外，每当我们达到预留空间边界时，都必须分配一个新数组，并将所有数据复制到新数组中。

树解决方案（在代码中使用 AVL 树）是较新的。我的意思是，使用 AVL 树而不是数组是最近做的主要实现更改。AVL 树实现似乎是一个很好的选择，可以得到一个直接依赖于其输出大小而不是更高的算法。这将确保在所有情况下性能更稳定。但在一般用例中应该不需要，因为在所有测试用例中，“h”（凸包点）远小于“n”（源点）。C++ 实现不使用树的原因是，我最近才意识到当“h”变得太大时数组的负面影响，并且我没有时间在 C++ 中编写另一个实现。

平衡树有两种最流行的树管理算法：AVL 和“红黑”树。我选择 AVL 而不是“红黑”树有两个原因：

1. 懒惰，对我来说实现 AVL 树似乎比红黑树更容易。
2. 根据我的测试，由于“h”相对于“n”保持极小，树中的读取操作应该远多于插入操作，这应该有利于 AVL 树以获得最佳性能，而不是红黑树。

O(n) 的凸包

我曾尝试创建一个 O(n) 而不是 O(n log h) 的算法。我认为借助线程、数组作为容器和良好的设计是可能的。至少需要两个线程来实现这个目标。一个线程快速过滤潜在候选点，另一个线程将潜在候选点插入到结果凸包容器——一个数组中。

• 线程 1 - 以 O(1) 的时间复杂度过滤每个候选点。该线程拒绝不合格的候选点，并将合格的候选点放入一个栈中。为了在已找到的候选凸包点数组中获得近似的插入位置，算法应使用第一个和最后一个点之间的线性定位。这可能不会给出精确的插入位置（圆弧的线性化），但应该足以快速拒绝大多数点。这样，就不再有二分法，这对应于去除了“log h”。该线程以 O(n) 的时间复杂度完成其工作。
• 线程 2 - 尝试插入由线程一过滤出的潜在凸包点。这在 O(~h++ log h) 时间内完成。随着接近 n 个点和/或接近解，插入的频率应该会越来越低。这应该能给清空待插入点栈足够的时间。

如果线程 1 总是在线程 2 之前完成，或者非常接近（常数时间），那么我们可以说我们有一个 O(n) 的凸包算法。

两个线程之间首选的容器是栈，因为最近评估的点有更高的风险成为更好的凸包候选点。

事实上，它确实能工作，但完成任务的时间是 Ouellet 单线程版本的两倍。请注意，在大多数情况下，线程 1 完成时，潜在候选点的栈中没有点，这应该表明至少在一般情况下，达到了 O(n) 的成功。

此外，该算法在两个不可变数组的副本之间交替，以保持一致性，并且不减慢过滤候选点的线程。这并没有取得真正的成功，原因有以下几点：

• 在一般情况下，它比我的任何其他实现慢两倍，可能是因为访问共享的已过滤候选点栈需要锁定机制。尽管我使用了“SpinLock”而不是标准的“Lock”，这应该更快，但我感觉有太多的阻塞情况增加了延迟。我应该找到一种非阻塞的方式来插入潜在的候选点。
• 它高度依赖于点的良好随机分布。否则可能会很糟糕，因为过滤可能会有很差的丢弃命中率，至少在我实现算法的方式上是这样。我必须重新设计一切，以使其更有效，更少地依赖于数据……如果可能的话。
• 我为每个象限固定了线程数量，这些线程在完成其初始象限/工作后会休眠，而不是帮助其他象限完成任务。看到结果后，我决定不再梦想在现实世界中使用 O(n) 算法。由于常规算法中每一步的简单性和速度，添加锁定机制会使事情变慢太多。也许在很多年后，当数千万个点变成少数几个点，并且线程数量更多时，它可能会被更多地关注和使用。
• 我认为，简而言之，速度慢的问题来自于小的“h”，它通常保持在 1000 以下，这是一个 8-10 级的树。进行 10 次迭代是如此之快，以至于它能与任何锁定机制很好地竞争。

附注：由于我知识有限，我不确定如果一个算法需要多个线程才能达到“O(n)”的性能，我是否有权说它是在“O(n)”中？我也需要研究一下这个问题。关于在 O(n) 中找到凸包点的一切都需要被证明，而且做起来会非常有趣，但时间和金钱统治着世界，而我也是其中的一部分。由于性能不佳，并且我认为我应该改进这个算法，我倾向于不发表那部分内容。

C# vs C++

虽然我没有用相同的方式实现 C++ 和 C# 版本，但很容易看出 C++ 的灵活性，或者说它与机器语言的接近程度，在性能方面比 C# 有优势。但关于 C++ 实现，有几点需要注意：

• 代码很糟糕。
• 它有一个非常大的函数，里面有重复的代码。
• 有很多 "goto"。

C++ 代码难以维护。C# 实现更容易阅读和理解。在基类中也有更多通用的函数，重复的代码更少。虽然还有改进的空间，但大多数人应该更容易理解 C# 的实现而不是 C++ 的。

在 C++ 中做出的每一个选择都是为了击败“Chan”而有意为之的。根据测试结果，在大多数一般情况下，至少基于我的 4 个通用生成器（圆形、5 个圆形、矩形、抛弃型），对于一百万个点，Ouellet CPP 实现比 Chan 快大约 4 倍。结果来自我的基准测试，可在以下位置找到：“深度性能测试”结果。

多线程

根据基准测试结果，很容易看出多线程版本比单线程版本快两倍以上。由于 Ouellet Hull 算法的性质，它使其成为一个易于实现多线程的良好候选者，至少对于 3 个步骤中的前 2 个是这样。前 2 个步骤依赖于“n”，而第 3 个步骤仅依赖于“h”。在这 3 个步骤中，第一个可以很容易地完全多线程化，第二个可以很容易地在 4 个完全独立的线程上实现（不需要同步机制），而第 3 个步骤多线程化会 थोड़ा 困难一些，但它不受“n”的影响，只受“h”的影响。

虽然多线程的使用不如算法的复杂度（大 O 表示法）重要，但它可以帮助获得不错的性能提升。在 Ouellet 算法的情况下，添加多线程并保持线程完全独立非常容易，这是一个额外的优势。

C# - 安全代码 VS. 非托管代码

使用非安全代码代替安全代码可能会带来更好的性能。但非安全代码需要大量的附加操作。我们决定，非安全代码潜在的速度增益不足以弥补它给代码阅读和维护带来的困难。

容器使用说明

使用了两种不同类型的容器

• 数组（或在其底层使用数组的列表）
• AVL 树

两种容器在一般情况下速度相当。我开始时使用“List”，因为它对我来说更简单。但基于数组的容器有一个主要缺点：当“h”（凸包点的数量）变得太大时，其性能会迅速下降。数组性能出现真正问题的点数大约在 100,000 到 500,000 之间。这就是为什么我决定为那些非常罕见的情况创建一个使用 AVL 树的新版本。就其本质而言，AVL 树是单线程 Ouellet 算法的完美容器。它不像数组那样受“h”的影响。主要区别在于：

• 数组：二分查找是外部完成的。插入和删除需要移动靠近相关索引的对象（靠近是因为有失效的邻居）。
• AVL 树：二分查找源于树的内部实现方式。我们需要重新平衡树以保持在 O(n log h) 的复杂度。

当结果点（凸包点）的数量变得太大时，很明显 AVL 树会轻松获胜。

C# Array.Copy vs MSVCRT memmove vs MSVCRT memcpy (对于不可变)

如果你需要快速复制数据数组，并且知道内部数组对象的类型是简单类型（或简单类型的结构体），那么你可以使用 MSVCRT memcpy（非重叠复制）或 memmove（重叠复制）。MSVCRT - memcpy 函数最快，但根据 MSDN，它不能用于重叠数据。否则，Array.Copy 和 memmove 是相同的，memmove 有一个非常一致但微不足道的时间优势。要使用 memcpy，我们需要每次复制整个数组（与使用不可变数组相同）。

请注意，在有垃圾回收器的语言中，移动任何对象（非简单类型或包含简单类型的结构体）都需要将该对象固定在内存中，以防止在被非托管代码移动时被垃圾回收器移动。数组是一个对象。数组本身在从非 GC 感知代码中使用时应该被固定。

C# Buffer.Copy

我不能使用 Buffer.Copy 来移动点。Buffer.Copy 不支持结构体，即使它们只由简单类型组成。见下面的异常：

如果有人能清楚地解释为什么会这样，我将不胜感激。

C# sizeof(T)

C# sizeof(T) 不能用于泛型类型，因为对象的大小在编译时无法确定。我想知道是否有可能在编译时知道对象的大小，例如对于简单类型和简单类型的结构体？是否可以有一个应用于 T 的“where”子句，指定“SimpleType”？如果可行，我认为让 C# 语言能够在 T 上使用“sizeof”将是一个很好的补充。

编译/运行代码

该代码是使用 Visual Studio 2013 完成的，并已移植到 Visual Studio 2015，然后是 Visual Studio 2017。它目前使用 VS 2017 的一些功能。建议使用该版本。如果您无法这样做，您可能会在 C++ 代码上遇到一些问题，因为它与 Visual Studio 2017 附带的 MSVCRT.dll 的特定版本绑定。

如果您遇到 BadImageFormat 异常，应确保在 64 位模式下运行。问题是错误的映像 CPU 目标（64 位 vs 32 位）。C++ 代码仅为 64 位。如果您移除 C++ 代码，则可以使用“AnyCPU”设置进行构建。

算法基准测试

所有基准测试结果都是使用提供的代码得出的。一切都是可测试和可验证的。

随机生成器

该基准测试有五种不同类型的点生成器：

生成器	描述
圆	圆内的随机点。
5 个圆	5 个随机圆，其中包含随机点。圆可以重叠或不重叠。
矩形	矩形内的随机点。
抛弃法	设置一个随机点，向任意随机方向移动一个随机距离，然后设置一个新点，从这个新点开始迭代。
第四象限的弧	所有点都位于弧的边缘上，使它们都成为有效的凸包点。所有点都在第四象限的弧内。这个生成器非常特殊。它完全是为了检查 Ouellet 算法的最坏情况而制作的，不应反映任何可能的实际使用情况。因为我的单线程算法是按顺序（1、2、3、4）检查每个点的象限，所以处理第四象限的点比任何其他象限都要差一些。此外，将每个点都保留为凸包点让我意识到，在构成凸包的点数非常多的情况下，使用列表是一个主要的缺点。在使用基于数组的容器时，它显示出非常糟糕的性能。在这些情况下，树容器要好得多。更多细节请参见数组 vs 树。

用于测试的硬件

仅作为补充信息，这是我的机器规格：

操作系统名称	Microsoft Windows 7 企业版 6.1.7601 Service Pack 1 Build 7601
系统制造商	Hewlett-Packard
系统型号	HP Z620 Workstation
系统类型	基于 x64 的 PC
Processor	Intel(R) Xeon(R) CPU E5-1660 0 @ 3.30GHz, 6 核, 12 逻辑处理器
BIOS 版本/日期	Hewlett-Packard J61 v03.50, 2013-08-15
已安装物理内存 (RAM)	16 GB

“速度测试”结果

呈现的大多数结果是针对 O(n log h) 的算法，以便更好地比较最快算法的性能。大多数测试是使用两种生成器“Circle”和“Throw away”完成的，这两种生成器应该更接近实际使用情况。任何其他算法和随机生成器的组合都可以使用提供的代码轻松测试。如果您愿意，也可以添加自己的生成器或算法。

用 C/C++ 实现的结果是在原生语言内部获取的，而不是在 C# 代码中，以防止将结果转换时间计算在内。这应该能更好地反映每个算法/实现所花费的实际时间。

还直接基于结果点添加了线性回归，以观察趋势以及它是否是线性的。

 

 

 

 

 

 

 

 

 

关于“速度测试”结果的结论

观察

1. O(n log h) 的优势是显而易见的。
2. 单调链算法是评估的算法实现中最慢的
3. 虽然 MiConvexHull 和 Heap 算法都是 O(n log n)，但 Heap 算法要慢得多。
4. 速度取决于源点、它们的位置和顺序。速度结果可能因点排列（随机生成器）而异。
5. 所有 O(n log h) 的凸包算法都更快，但它们之间存在明显的差异。
6. 与刘和陈相比，Ouellet 中所做的优化带来了更好的性能。
7. 基于数组的容器实现依赖于非常大的“h”。当“h”达到约 500,000 个点时，问题就会出现。
8. Chan 算法比 Ouellet 算法更独立于随机生成器的类型。在比较不同随机生成器的结果时，可以看到这种差异。
9. Ouellet AVL 和 Ouellet AVL v2 比 Chan 更受“h”的影响。通过将“Arc generator”的结果与任何其他生成器进行比较，可以看出这一点。这应该是由于堆分配器延迟和/或重新平衡树造成的。
10. 多线程是一个真正的优势。
11. C++ 比 C# 快得多。虽然不是完全相同的算法，但差异比预期的要大得多。我认为这可以归因于大量的内存读/写，这在 C++ 中可能有更少的间接寻址，也归因于数组边界检查，这在 C# 中为了安全会自动发生，但在 C++ 中则不会。
12. C# 单线程与 Chan 的比较因生成器类型而异。对于“Circle”点生成器，C# 比 C 中的 Chan 更快。而当使用“Throw away”点生成器时，Chan 轻松获胜。
13. Ouellet CPP 比 Chan 快 4 倍，两者都是用同一种语言（C/CPP）编写的。这适用于点数大于 100,000 的情况。
14. 不可变数组复制受大量点的影响比使用重叠复制（正常使用，如在列表中）的数组快得多。
15. 尽管 Ouellet CPP 在正常使用中明显胜出，但当“h”变得太大时，由于使用基于数组的方式存储凸包点，其性能会很差。
16. 对于弧形生成器（其中 n=h），Ouellet AVL 与 Chan 之间的差异相当大。但随着点数的增加（变得巨大），这种差异正在缩小。参见“深度性能测试”的结果。
17. 对于 Ouellet，AVL 树似乎是确保在所有情况下都具有良好性能的最佳容器。虽然在一般情况下比数组稍慢，但当“h”变得非常大时，它具有更稳定的行为。

关于“Arc”点生成器的警告

一些测试是使用“Arc”随机生成器完成的。该生成器的输出是可用于提供给 Ouellet 算法的最坏情况数据生成器，当该算法基于数组容器（数组或列表）时。由“Arc”点生成器生成的点将全部成为凸包的一部分，无一例外。所有点形成一个弧，即第四象限中椭圆的边界。这在现实生活中不应该发生，但在这里测试 Ouellet 算法的最坏情况以及它如何影响其某些实现是很有趣的。

衍生结论

根据结果，我们可以推断出，有可能得到一个比 Ouellet CPP 更快的 Ouellet AVL v2 “CPP” 实现。该实现不会有影响所有基于数组的 Ouellet 实现的“数组”容器效应。但由于每次插入潜在凸包点候选者时都使用堆分配器，速度提升可能不会像 Ouellet ST 和 Ouellet CPP 之间那样好。

“深度性能测试”结果

该测试主要展示了算法速度的比较。结果分为两部分：

1. 第一个表显示原始速度结果
2. 第二个表显示相同的信息，但以相对于同一行中最快算法的比率表示

“深度性能测试”如何实现

• 对于每个点数（列：Points）
  • 每个测试重复 10 次
    • 创建随机数量的点 (ptsCount)
    • 执行每个算法，计算其所用时间
  • 对于每个算法，基于 10 次测试取平均值（以获得每个算法更好的归一化平均值）

这种测试的一个优点是，它是在特定数量的点上进行的，但对于每个数量，都会对 10 组不同的随机点取平均值，每个算法都会针对同一组点进行测试。对 10 次测试取平均值有助于获得更可靠的结果，更好地反映现实情况。它降低了算法计算性能可能出现的波动。

一些示例结果

圆形生成器
Points	Heap	MI 凸包	Chan	Ouellet C# ST	Ouellet C# Avl v2	Ouellet C# 4T	Ouellet C# MT	Ouellet CPP ST
10	0,00108	1,87276	0,01983	1,68595	2,23541	2,31733	0,06784	0,00442
100	0,00928	0,07411	0,01553	0,01491	0,05198	0,04098	0,67324	0,00811
1000	0,12542	0,41404	0,12634	0,10726	0,19491	0,10209	0,09456	0,03884
10000	1,59029	1,4313	0,92123	0,88127	0,8602	0,47758	0,40407	0,20166
100000	22,79887	27,42013	8,81501	8,46962	7,20517	3,78218	11,55244	2,95017
1000000	541,474	456,7736	106,1159	86,48805	72,61888	32,67093	32,60175	19,12635
10000000	9704,916	3494,845	1123,966	904,2915	753,2944	429,324	321,1153	195,4884
50000000	59832,37	90730,66	5648,566	4321,777	3625,627	1858,696	1611,791	975,5726
圆形生成器比率
Points	Heap	MI 凸包	Chan	Ouellet C# ST	Ouellet C# Avl v2	Ouellet C# 4T	Ouellet C# MT	Ouellet CPP ST
10	1	1734,037	18,36111	1561,065	2069,824	2145,676	62,81481	4,092593
100	1,144266	9,138101	1,91492	1,838471	6,409371	5,053021	83,01356	1
1000	3,229145	10,66014	3,252832	2,761586	5,01828	2,628476	2,434604	1
10000	7,885996	7,09759	4,568234	4,370078	4,265596	2,368244	2,003719	1
100000	7,727985	9,294424	2,987967	2,870892	2,44229	1,282021	3,915856	1
1000000	28,31037	23,8819	5,548151	4,521932	3,796798	1,708163	1,704546	1
10000000	49,64446	17,8775	5,749527	4,625806	3,853397	2,196161	1,642631	1
50000000	61,33052	93,00247	5,790001	4,42999	3,71641	1,905236	1,652149	1
5 个圆形生成器
Points	Heap	MI 凸包	Chan	Ouellet C# ST	Ouellet C# Avl v2	Ouellet C# 4T	Ouellet C# MT	Ouellet CPP ST
10	0,00114	0,06827	0,00182	0,00555	0,03001	0,05306	3,65214	1,56142
100	0,00972	1,4628	0,01716	0,01725	0,06456	0,03631	0,07146	0,00804
1000	0,12014	0,37807	0,1058	0,10401	0,15686	0,10403	0,23345	0,03499
10000	1,51341	2,6314	0,8092	0,84836	0,60956	0,48868	3,96307	0,98666
100000	24,82565	42,64931	8,4731	8,68809	12,91215	4,34475	3,96131	2,01127
1000000	566,718	381,0362	99,78135	84,84197	55,64279	38,98233	39,39097	21,28255
10000000	9823,763	2789,914	1124,163	883,7857	712,3286	500,4938	391,891	251,782
50000000	56538,56	14800,21	4875,033	4398,306	2597,754	1891,765	1937,045	1161,692
5 个圆形生成器比率
Points	Heap	MI 凸包	Chan	Ouellet C# ST	Ouellet C# Avl v2	Ouellet C# 4T	Ouellet C# MT	Ouellet CPP ST
10	1	59,88596	1,596491	4,868421	26,32456	46,54386	3203,632	1369,667
100	1,208955	181,9403	2,134328	2,145522	8,029851	4,516169	8,88806	1
1000	3,433552	10,80509	3,023721	2,972564	4,482995	2,973135	6,671906	1
10000	3,096935	5,38471	1,655889	1,736024	1,24736	1	8,109745	2,019031
100000	12,34327	21,20516	4,212811	4,319703	6,419899	2,160202	1,969557	1
1000000	26,62829	17,90369	4,688411	3,986457	2,614479	1,831657	1,850858	1
10000000	39,01694	11,08067	4,464827	3,510123	2,829148	1,987806	1,55647	1
50000000	48,66916	12,74023	4,196495	3,786122	2,236182	1,628457	1,667435	1
矩形生成器
Points	Heap	MI 凸包	Chan	Ouellet C# ST	Ouellet C# Avl v2	Ouellet C# 4T	Ouellet C# MT	Ouellet CPP ST
10	0,00102	7,4844	0,00263	0,00643	0,03033	0,0248	1,74169	0,00483
100	0,00997	0,07902	0,01451	0,02722	0,05932	0,03731	0,03714	0,01129
1000	0,12493	0,20427	0,09821	0,10101	0,17569	0,09951	0,09731	0,11553
10000	1,55069	3,7444	0,7152	0,81974	0,66621	0,47438	0,39172	0,18275
100000	22,27714	112,672	7,98381	9,76501	5,95338	3,21348	5,7474	1,53242
1000000	554,4348	406,3471	90,25243	83,9157	60,25598	46,47369	38,26555	16,35665
10000000	10041,87	2625,678	936,3977	834,0339	564,9664	375,76	297,6457	204,7239
50000000	56114,48	16609,91	14926,98	3645,529	2783,8	1483,013	1436,47	856,4593
矩形生成器比率
Points	Heap	MI 凸包	Chan	Ouellet C# ST	Ouellet C# Avl v2	Ouellet C# 4T	Ouellet C# MT	Ouellet CPP ST
10	1	7337,647	2,578431	6,303922	29,73529	24,31373	1707,539	4,735294
100	1	7,925777	1,455366	2,730191	5,94985	3,742227	3,725176	1,132397
1000	1,283835	2,099168	1,009249	1,038023	1,805467	1,022608	1	1,187237
10000	8,485308	20,48919	3,913543	4,485581	3,645472	2,595787	2,143475	1
100000	14,53723	73,5255	5,209936	6,37228	3,884953	2,096997	3,750538	1
1000000	33,8966	24,84293	5,517782	5,130372	3,683883	2,841272	2,339449	1
10000000	49,05078	12,82546	4,573954	4,073945	2,759651	1,835448	1,453888	1
50000000	65,51914	19,3937	17,42871	4,256511	3,250359	1,731562	1,677219	1
抛弃法生成器
Points	Heap	MI 凸包	Chan	Ouellet C# ST	Ouellet C# Avl v2	Ouellet C# 4T	Ouellet C# MT	Ouellet CPP ST
10	0,0012	0,06457	0,00163	0,00714	0,03473	0,03447	0,03586	0,00423
100	0,00915	0,07318	0,0149	0,01467	0,05557	0,03048	0,03261	0,00755
1000	0,13591	0,34241	0,0957	0,09783	0,66553	0,1031	0,08968	0,03367
10000	1,47477	1,19184	0,69639	0,8837	0,58769	0,48858	0,45522	0,20029
100000	20,05145	14,0944	6,9497	8,28934	4,80163	4,14814	6,55351	1,95432
1000000	352,7863	335,9496	90,7813	89,00771	48,50286	36,29886	39,43067	20,9981
10000000	5565,573	2037,657	900,9266	859,9736	560,264	357,0917	346,4088	242,5131
50000000	32520,03	22094,49	4213,683	4071,137	2194,05	1593,671	1605,114	872,252
抛弃法生成器比率
Points	Heap	MI 凸包	Chan	Ouellet C# ST	Ouellet C# Avl v2	Ouellet C# 4T	Ouellet C# MT	Ouellet CPP ST
10	1	53,80833	1,358333	5,95	28,94167	28,725	29,88333	3,525
100	1,211921	9,692715	1,97351	1,943046	7,360265	4,037086	4,319205	1
1000	4,036531	10,16959	2,842293	2,905554	19,76626	3,062073	2,663499	1
10000	7,363173	5,950572	3,476908	4,412102	2,934195	2,439363	2,272804	1
100000	10,26006	7,21192	3,556071	4,241547	2,456931	2,122549	3,353345	1
1000000	16,80087	15,99905	4,32331	4,238846	2,309869	1,728674	1,877821	1
10000000	22,94957	8,402252	3,71496	3,546091	2,310242	1,472463	1,428412	1
50000000	37,28284	25,3304	4,830809	4,667386	2,515385	1,827076	1,840195	1

 

弧形生成器
Points	Chan	Ouellet C# Avl v2
10	0,00194	0,03007
100	0,02189	0,2406
1000	0,27112	4,38024
10000	3,33285	35,75693
100000	41,3635	490,43127
1000000	495,68418	4567,68341
10000000	5753,82461	36702,53548
50000000	31337,83897	111482,6417
弧形生成器比率
Points	Chan	Ouellet C# Avl v2
10	1	15,5
100	1	10,99132024
1000	1	16,15609324
10000	1	10,72863465
100000	1	11,85661924
1000000	1	9,214906576
10000000	1	6,378806788
50000000	1	3,557445099

关于“Arc”随机点生成器，请阅读：关于“Arc”点生成器的警告

请记住，大多数算法是用 C# 编写的，而 C# 语言的声誉是比 C 慢得多（Chan 和 Ouellet CPP 是用 C 编写的）。

还剩下什么

还剩下许多事情

• 用红黑树代替 Avl 树测试 Ouellet Avl 并比较性能
• 在 C++ 中实现 AVL 版本，以找出语言优势，并查看差异是否与 Ouellet ST 相同
• 在所有版本中添加部分或全部优化
• 在 C++ 中做一个多线程版本，就像在 C# 中用 AVL 树做的那两个一样
• 改进多线程版本，以便在每次传递中在所有情况下都使用所有线程。
• 在一个 O(n) 运行的算法上找到更好的实现选择并进行更多测试
• 通过使其更通用，将算法调整为可用于 3D 和/或任何维度。这应该是可行的。作为一个想法，我们可以使用位值作为象限。
• 结合上述任何一项，以获得有史以来最好的算法实现

谁有足够的勇气、时间、金钱和知识来完成其中任何一项或全部？

附录 A - Ouellet 凸包的历史

日期	事件	注释
2013年 – 春季	-  接到一项任务，在一个名为 EMTP 的电网仿真软件中实现凸包功能。-  购买了 ceometric 库。	Ceometric 库速度慢，处理数百万个点时会崩溃。
2013年 – 夏季	-  找到了 Pat Morin 的 Chan 算法代码实现。	Pat Morin 的实现是用“C”语言编写的，但我更倾向于使用 C#。此外，我发现在 32 位/64 位之间切换很困难。
2014年- 春季	-  我脑海中萌生了一个关于寻找凸包新方法的想法。我很快地测试了一下，得出的结论是它应该可行。-  我创建了一个基准测试，测试了算法并进行了调试。
2014-05-20	-  在 Code Project 上首次发布关于新算法的帖子
2014-06-17	-  尝试在维基百科 – 凸包算法中添加对我的算法的引用。	它在那里停留了一天。David Eppstein 将其删除，详情见维基百科网页历史。
2015年 – 夏季	-  我决定尝试在“真正的”科学期刊上发表。我联系了魁北克的老师来帮助我，并试图找到一个合适的期刊发表。-  我发现了一篇来自刘和陈的文章“一种计算平面点集凸包的新算法”，它在我看来与我的算法完全相同，或者我应该说我的算法和他们的一样。	刘和陈文章的发现对我来说是一个真正的冲击。
2015-07-25	-  尝试在维基百科中添加对刘和陈文章的引用。	David Eppstein，“维基百科凸包算法页面的守护者”，评估认为刘和陈的文章没有发表在合适的期刊上。对他来说，这个期刊太不知名了，不适合维基百科（详情见维基百科 - 凸包算法的历史）。
2017年 – 9月	-  本文	希望它对读者有用并受到赞赏。

附录 B – 维基百科

在维基百科“凸包算法”的历史页面上，您可以看到我曾尝试添加对我的第一篇 Code Project 文章和刘和陈的文章的引用。两次尝试都被 David Eppstein 删除了。到目前为止，维基百科中没有关于该算法的引用，这使得它更难被发现。

附录 C - WPF 图表控件

在附带的代码中，使用的图形控件是 OxyPlot。这个控件运行良好，使用简单。但它的性能偏慢。事实上，我从未见过任何仅使用 WPF 的图形控件能够流畅地处理数千个点。我在工作中使用的有一个控件能提供适当的性能，而且它的 API 也很好：“LightningChart” by Arction。我也认为 SciChart 做了一个非常好的控件。LightningChart 底层使用 DirectX，我认为 SciChart 也使用 DirectX 来确保可接受的性能。两者都有 C# 控件，并且非常易于使用。

Arction 提供卓越的支持，SciChart 似乎也提供类似的服务。

我的 C# 图表控件体验

Company	Arction	SciChart	National Instrument	Oystein Bjorke (GitHub 上的 objorke)	微软研究院
Control	LightningChart	WPF 图表	Measurement Studio WPF 图形控件	OxyPlot	DynamicDataDisplay
API（设计质量）	Excellent	过去一般。最近的没试过，但听说不错。	好。基于 GDI32.dll。需要一些调整以确保在 WPF 中正常使用。	Good	Good
价格	Expensive	?	Expensive	免费	免费
性能	很棒	？期待出色的性能，因为它使用 Direct X	Good	Slow	Slow
源代码	可用 $$$	?	否	是	是
备注	优秀。易于推荐。	?	我会避免使用它。支持差。C++ COM 控件适配到 WPF。现在已经 2-3 年没用了。	GitHub 项目。如果性能不是问题，这是非常好的图表。	非常老旧，多年未获支持

附录 D - Excel

顺便说一句，我使用 ClosedXML 作为创建我的 Excel 报告的库。我非常喜欢它。它易于学习和使用，而且是免费的。

在我们公司，我们使用 SpreadSheetGear，我更喜欢它，但它需要花钱。

附录 E - 最小包围圆

也称为最小包围圆，顾名思义，是包含点集“S”中所有点的最小圆。在维基百科可以找到一个很好的定义：最小圆问题。我添加了 Rod Stephens 网页上的代码：在 C# 中寻找点集的最小包围圆作为一种可用的算法。最小包围圆以一个点集作为其源，并产生一个由一个点（圆心）和一个长度（圆的半径）组成的结果。通过添加一个小的、易于实现的算法，我们可以将圆心点和半径转换成一个圆。实际上，这个圆是由形成该圆的一系列连续点表示的。点的数量应该足以给人一种圆的错觉。然后，我们可以像使用凸包一样，在工作台中使用该算法。Rod Stephens 的当前实现代码运行良好，但速度相当慢。我还添加了另一个基于 Rod 算法的可用算法。不同之处在于，“S”点经过 Ouellet 凸包算法的预过滤。然后将凸包的结果用作 Rod 算法的源。该算法变得快得多，因为它极大地减少了源点的数量。这是拥有一个高效凸包算法的另一个优势。请注意，Rod 算法似乎是 O(n²) 的。您可以使用提供的测试工作台轻松测试性能，我在其中包含了两种实现。由于原始 Rod 算法的复杂性，我建议点数保持在约 1000 以下。请看一个两种算法之间基准测试结果的简单示例。

附录 F - 生成一组项目所有可能排列的最快算法的通用实现。

附带一提。我认为我已经做出了生成一组项目所有可能排列的最快的 C# 实现。您可以在 StackOverflow 上的问题 生成一个集合的排列（最高效地）中查看我的答案，以了解其大概内容。我这样做是为了对凸包进行一些测试。所有代码都包含在本文提供的源代码中。

相对于找到的少数算法，主要优势在于：

• 堆算法（每次排列单次交换）
• 无乘法（不像网上看到的某些实现）
• 内联交换
• Generic
• 无不安全代码
• 原地（内存使用率非常低）
• 无取模（仅比较第一位）

附录 G – 基准测试

该基准测试代码是使用 Visual Studio 2017 在 C# 中完成的。它使用“.Net framework”4.5.2 及更高版本。提供了基准测试和每个算法实现的所有源代码。二进制文件也可以下载。除了两个凸包实现（Chan 由 Pat Morin 完成，Ouellet CPP 由我完成）外，所有代码都使用 C# 语言。

它不是完全的 MVVM，但使用了一些 MVVM 的特性。我不得不决定在某个地方停下来，它现在就是这个样子。我觉得它已经足够可用，并且很容易添加您自己的算法。

如何添加您自己的算法

请在项目“ConvexHullWorkbench”中查找类“AlgorithmManager”。只需在构造函数的末尾添加一行：“_algorithms.Add(...”。

截图

致谢

• 感谢我的项目经理 Omar Saad，他向我解释了什么是凸包，并给我时间来测试我的想法、撰写文章和编码。
• 感谢同事 Paul Labbé，他向我展示了叉积。这是我对算法做的最好改进之一。
• 感谢同事 Jacques Bherer 和 Chuma Francis Mugombozi 修订我的文章。如果我采纳了他们的每一条建议，我的文章会是一篇杀手级的文章！但我太懒了……

参考文献

• 维基百科，凸包算法
• Liu, G. & Chen, C. J. Zhejiang Univ. - Sci. A (2007) 8: 1210. 一种计算平面点集凸包的新算法 (https://rd.springer.com/article/10.1631%2Fjzus.2007.A1210)
• Eric Ouellet, IREQ, 凸包算法及其 O(n log h) 实现
• 维基百科，最小圆问题
• Rod Stephens, C# Helper, 2014-08-13, 在 C# 中寻找点集的最小包围圆
• 维基百科，堆算法
• SimpleVar, Stack Overflow 问题/回答, 生成一个集合的排列（最高效地）
• Qwertie (David Piepgrass)，在 GitHub 上的 Monotone Chain 实现以及在 Loyc.net 上的文章 《C# 实现二维凸包：40 行代码》
• Ceometric，.Net 库几何解决方案
• futura-sciences.com 论坛上 Tryss 关于叉积的回答
• bitlush，《C# 中的高效 AVL 树》

版本

提交版本时的日期。文章上线前可能会有延迟（一天或几天？）。 

1. 2017-10-13，本文初始版本。
2. 2017-10-18，修正了一些算法的复杂度。重新排列了凸包算法/复杂度表格，使其更易于阅读。增加了一些信息。进行了少量修正。 
3. 2017-10-28，更新了二进制可执行文件以包含 MSVCRT。这是为了确保 'C' 语言代码在任何 Windows 系统上都能正常运行。
4. 2017-11-17，少量语法修正或添加了少量超链接。
5. 2017-11-30，少量语法修正并增加了一些说明。更新了部分包含 Delaunay/Voronoi 信息的图表。增加了一张图表（包含圆生成器的结论部分）。
6. 2017-12-16，文本少量修正。
7. 2018-01-30，增加了对“在线”凸包（动态添加）的支持，每个点的时间复杂度为 O(log h)。同时增加了 Peek (IsHullPoint) 支持，以便在插入点之前判断该点是否会成为凸包上的点。所有这些目前仅在代码中实现，包含在 GitHub 的 OuelletConvexHullAvl2Online 项目中。移除了一些无效代码。略微改进（标准化）。增加了来自 Rod Stephens 的 Graham 扫描算法的修改版实现。
8. 2018-03-01，更新可执行文件以反映近期更改。添加了相关文章表格。

感谢您花时间让我知道您对本文的看法……