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

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

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

引言

本文是3部分系列文章中的第2篇。

#	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. 最初的目的是展示用C++开发的新Ouellet算法实现。根据提供的性能测试，新实现比C语言的Chan实现（也已提供）快约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算法内部工作原理的最详细描述可以在以下地方找到：

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

更多信息可在后面的章节找到：Ouellet 与 刘陈凸包算法的差异

算法主旨

这是一个快速摘要。更多信息可在O(n log h) 的凸包算法及其实现中找到。

算法包含3个按顺序进行的主要步骤：

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

Ouellet 与 刘陈凸包算法的差异

在深入研究凸包优化之前，应该清楚的是，刘陈凸包算法和Ouellet算法都基于相同的原理：虚拟象限，至少根据我从刘陈的文章中的理解：《计算平面点集凸壳的新算法》。刘陈的文章没有代码或实现细节以及/或任何相关链接。因此，我决定重新命名我的第一个实现代码：刘陈。此后，已添加了许多优化，提高了性能。包含的基准测试结果显示了这些差异。

根据出版日期：2007-07-01，刘陈是第一个发现使用虚拟象限原理的人。优化可以说是“刘陈”和“Ouellet”之间的区别。

优化

以下是可选的优化，可以应用于Ouellet凸包算法的一个或多个版本。有些仅用于Ouellet C++版本，而大多数则应用于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。在糟糕的情况下（丢弃点随机生成器），QD只是稍微慢一点（可忽略不计），并且对于任何数量的输入点都相当稳定。在好的情况下（圆形点随机生成器），对于100,000个点，QD快1.2倍，并且随着点数的增加，性能缓慢增加。没有QD可能会更糟，但只是稍微差一点，它是一个不错的补充，并且通常应该能提高性能。可以使用提供的基准测试轻松进行相同的测试。

对向象限检查 (OQC)

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

在算法的早期版本中，点象限归属是基于象限根点计算的。对向象限可以有一个重叠区域（见下例）。因此，算法应该对重叠区域中的任何点执行对向象限检查（OQC）。OQC源于在点已被识别为属于某个象限的情况下，仍需要检查其对向象限的必要性。这种情况主要发生在某些特定的点分布中，但应予以考虑。

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

这里我们有虚拟的Q1（粉色）和Q3（绿色），每个象限的根点为相同颜色的菱形。可以看出，P1（黄色点），本应评估其是否属于凸包，却被包含在Q1（粉色区域）和Q3（绿色区域）中。但是，如果我们评估P1对于Q1并且在不检查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))

算法实现信息

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

算法名称	实现名称	实现			参考/说明
		语言	#线程	作者
单调链	单调链	C#	1	David Piepgrass	Loyc – C#中的二维凸包：40行代码
Graham扫描	HeapHull	C	1	Pat Morin	在我告知Pat Morin其Chan算法实现中存在一个小bug后，指向Pat Morin代码的链接已被删除。本文源代码提供了该代码的副本。
Delaunay/Voronoi	MI Convex Hull	C#	1	Design Engineering Lab	GitHub，虽然不是O(n log h)。我将其包含是因为代码是公开的，在3D世界中广为人知，并且我想展示复杂度（大O）对性能的重要性。
Chan*	Chan	C	1	Pat Morin	在我告知Pat Morin其Chan算法实现中存在一个小bug后，指向Pat Morin代码的链接已被删除。本文源代码提供了该代码的副本。
刘陈	刘陈	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 multi	C#	M, 4, 1	Eric Ouellet	与4线程相同，但第一次遍历使用所有可用线程进行多线程处理。
	Ouellet AVL	C#	1	Eric Ouellet	AVL实现的代码源自Bitlush

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

Ouellet凸包算法实现比较

名称	实现描述	语言	线程（每步）	容器	优化						注释
					QD	OQC	OQCB	DQC	PCZPI	PQ
刘陈	首次实现	C#	1-1-1	List（数组）							我将我的第一次实现重命名为刘陈。
Ouellet ST	首次实现，增加了QD优化	C#	1-1-1	List（数组）	x						快速，简单。见数组问题
Ouellet 4T	第二次实现以提高速度	C#	1-4-1	List（数组）	x						比1T快
Ouellet MT	第三次实现	C#	M-4-1	List（数组）	x						比4T稍快
Ouellet C++	第四次实现	C++	1-1-1	数组	x	x					在一般情况下最快。许多“goto”，代码冗余…为了速度，代码看起来很糟糕。
Ouellet AVL	第五次实现	C#	1-1-1	AVL树	x						不受“h”大的影响（因为凸包点的底层容器是AVL树）。它不预先保留更多空间以最小化堆分配器请求。由于算法的性质，树似乎是自然容器（最近发现）。
Ouellet Array	第六次实现（几次复制数组数据的测试）	C#	1-1-1	数组	x						进行一些测试，看看通过使用数组而不是“List”能否获得更好的性能。另外，当使用数组时，是否有方法可以更快地移动数据。
Ouellet Array Immu	第七次实现	C#	1-1-1	数组，但不可变	x						与其仅在插入点后复制重叠数据（为新点腾出空间或移除），不如复制整个数组。这使得我能够在多线程中保持数据一致性。
Ouellet MT	第八次实现（此处未展示）	C#	M-M-1	List（数组）	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

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

数组与树

除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个点，在所有正常随机生成器（非“Arc”生成器）下，结果几乎总是保持在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 - 尝试插入由线程1过滤的潜在凸包点。这以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)内找到凸包点的一切都需要证明，而且本应非常有趣，但时间和金钱统治着世界，我身处其中。由于性能不佳以及我认为我应该改进算法，我更愿意不发布这部分内容。

C# vs C++

尽管我没有以相同的方式实现C++和C#版本，但很容易看出C++的灵活性或接近机器语言的特性在性能方面优于C#。但C++实现有几点需要注意：

• 代码很糟糕。
• 有一个非常大的函数，代码重复。
• 有许多“goto”语句。

C++代码难以维护。C#实现的阅读和理解难度要大得多。基类中也有更多的通用函数，代码重复性更少。仍然有一些改进的空间，但大多数人应该比C++更容易理解C#实现。

C++中的每一个选择都是故意的，目的是超越“Chan”。根据测试结果，在大多数一般情况下，至少基于我的4个通用生成器（圆形、5个圆形、矩形、丢弃点），对于一百万个点，Ouellet CPP实现比Chan快约4倍。结果来自我的基准测试，可在：“深度性能测试”结果找到。

多线程

根据基准测试结果，很容易看出多线程版本比单线程版本快一倍多。由于Ouellet凸包算法的性质，它很容易实现多线程，至少对于前两个步骤（共三个）。前两个步骤依赖于“n”，而第三个步骤仅依赖于“h”。在三个步骤中，第一个步骤可以轻松地完全多线程化，第二个步骤可以轻松地实现为4个完全独立的线程（不需要同步机制），而第三个步骤将稍微难以多线程化，但它不受“n”的影响，只受“h”的影响。

虽然多线程的使用不如算法的复杂度（大O）重要，但它可以带来显著的性能提升。在Ouellet算法的情况下，很容易添加多线程并保持线程完全独立，这是一个额外的奖励。

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

使用非安全代码而不是安全代码可能会带来更好的性能。但是非安全代码需要很多人工处理。已决定非安全代码的潜在速度提升不足以抵消其在阅读和维护代码方面增加的难度。

容器使用说明

使用了2种不同类型的容器：

• 数组（或底层使用数组的List）
• 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)不能用于泛型类型，因为对象的大小在编译时无法确定。我想知道是否不能在编译时知道对象的大小，例如对于简单类型和简单类型的结构？是否无法使用指定“SimpleType”的“where”子句应用于T？如果可行，我认为拥有使用“sizeof”对T的能力将是C#语言的一个很好的补充。

编译/运行代码

代码使用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）检查每个点是否属于象限，处理第四象限的点比其他象限稍微困难一些。此外，将每个点保留为凸包点让我意识到，在凸包点数非常多的情况下，使用列表是一个主要缺点。它显示了使用基于数组的容器在这些情况下非常糟糕的性能。在这些情况下，树容器要好得多。有关更多详细信息，请参阅*数组与树*。

用于测试的硬件

仅作为附加信息，这是我的机器配置：

操作系统名称	Microsoft Windows 7 企业版 版本 6.1.7601 Service Pack 1 Build 7601
系统制造商	Hewlett-Packard
系统型号	HP Z620 Workstation
系统类型	x64-based 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受“h”的影响比Chan更大。通过比较“Arc生成器”与其他任何生成器的结果可以看出。这可能是由于堆分配延迟和/或重新平衡树所致。
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. 不可变数组复制比使用重叠复制（正常使用，例如在List中）的数组受大量点的影响更快。
15. 尽管Ouellet CPP在正常使用中明显获胜，但当“h”因使用基于数组存储凸包点而变大时，其性能会很差。
16. Ouellet AVL与Chan之间的差异在Arc生成器（n=h）上相当大。但当点数增加（变得非常大）时，这种差异会减小。请参阅“深度性能测试”结果。
17. 对于Ouellet，AVL树似乎是确保所有情况下性能良好的最佳容器。虽然在一般情况下比数组慢一点，但当“h”变得非常大时，它的行为更加恒定。

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

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

推导出的结论

根据结果，我们可以推断出，有可能实现一个比Ouellet CPP更快的Ouellet AVL v2 C++实现。该实现将不会有影响所有基于数组的Ouellet实现的“数组”容器效应。但由于每次插入潜在凸包点候选点都需要使用堆分配器，因此速度提升可能不如Ouellet ST和Ouellet CPP之间的差距大。

“深度性能测试”结果

此测试主要显示算法速度的比较。结果分为两个部分：

1. 第一个表显示原始速度结果。
2. 第二个表显示与同一行中最快算法相比的比率。

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

• 对于每个点数（列：Points）
  • 进行10次测试
    • 创建一个随机数量的点（ptsCount）
    • 执行每个算法，计算其耗时
  • 对每个算法，基于10次测试进行平均（以获得更好的标准化平均值）

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

一些样本结果

Circle生成器
Points	Heap	MI ConvexHull	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
Circle生成器比率
Points	Heap	MI ConvexHull	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 Circles生成器
Points	Heap	MI ConvexHUll	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 Circles生成器比率
Points	Heap	MI ConvexHUll	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
Rectangle生成器
Points	Heap	MI ConvexHUll	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
Rectangle生成器比率
Points	Heap	MI ConvexHUll	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
Throw away生成器
Points	Heap	MI ConvexHUll	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
Throw away生成器比率
Points	Heap	MI ConvexHUll	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

 

Arc生成器
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
Arc生成器比率
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编写的）。

剩余内容

还有许多内容待完成：

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

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

-附录A - Ouellet凸包算法历史

日期	事件	注释
2013年 - 春季	-  Got a task to implement a convex hull functionality into a software developed for electric network simulation called EMTP.-  Bought ceometric libray.	Ceometric library was slow and crashed for millions of points.
2013 – Summer	-  Found Pat Morin code implementation of Chan algorithm.	Pat Morin implantation is coded in "C" but I preferred to stay in C#. Also, I found it difficult to switch between 32bits/64 bits.
2014- Spring	-  An idea sprout in my mind about a new way to find the convex hull. I tested it quickly and came to the conclusion that it should work.-  I created a benchmark, tested the algorithm and debugged it
2014-05-20	-  Initial post at code project about the new algorithm
2014-06-17	-  Attempt of adding a reference to my algorithm into Wikipedia – Convex Hull algorithms.	It stays there one day. David Eppstein removed it, see Wikipedia webpage history for details.
2015 – Summer	-  I decided to try to publish in a "True" scientific journal. I communicate with teachers here in Quebec to help me and I tried to find an appropriate journal to publish. -  I found a convex hull article from Liu and Chen article "A new algorithm for computing the convex hull of a planar point set" for which appears to me to be the exact same algorithm as mine, or I should say that my algorithm is the same as them.	Liu and Chen article discovery was a real choc to me.
2015-07-25	-  Attempt to add a reference to Liu and Chen article into Wikipedia.	David Eppstein, "The Wikipedia Guardian of the Convex Hull algorithms pages", evaluated that Liu And Chen article was not published in an appropriate journal. The journal was too obscure for him, for Wikipedia (details in history of Wikipedia - convex hull algorithms).
2017 – September	-  This article	Hoping it will be useful and appreciated by readers.

Appendix B – Wikipedia

On Wikipedia history page of the "Convex hull algorithms", you can see a trial, by myself, to add a reference to my first Code Project article and Liu and Chen article. Both attempt has been removed by David Eppstein. Up to now, there is no reference to this algorithm in Wikipedia which makes it harder to discover.

Appendix C - WPF Chart Control

In the included code, the graphic control used is OxyPlot. This control works fine and it is simple to use. But its performance is on the slow side. In fact, I never saw any WPF only graph control that could handle many thousands of points smoothly. There is one control that I use at work that deliver proper performance and it has a nice API too: "LightningChart" from Arction. I also think that SciChart make a really good control too. LightningChart uses DirectX under the hood and I think SciChart is also using DirectX to ensure acceptable performance. Both have C# control and are very easy to use.

Arction offer exceptional support and SciChart seems to offer something similar.

My experience of C# Chart control

Company	Arction	SciChart	National Instrument	Oystein Bjorke (objorke on GitHub)	Microsoft Research
Control	LightningChart	WPF Charts	Measurement Studio WPF Graph Control	OxyPlot	DynamicDataDisplay
API (quality of design)	Excellent	So-so in the past. Didn’t try a recent one but I heard good words.	Good. Based on GDI32.dll. Need some tweaks to ensure proper usage with WPF.	Good	Good
价格	Expensive	?	Expensive	免费	免费
性能	Great	? Expecting great performance because it uses Direct X	Good	Slow	Slow
源代码	Available $$$	?	否	是	是
备注	Excellent. Easy to recommend.	?	I would avoid it. Bad support.C++ COM control adapted to WPF. Not used for 2-3 years now.	GitHub project. Very nice graph if performance is not an issue.	Very old and not supported for many years now

Appendix D - Excel

Just as a side note, I used ClosedXML as the library to create my excel report. I really liked it. It was easy to learn and use and it’s free.

In our company, we are using SpreadSheetGear which I prefer but it cost money.

Appendix E - Smallest Enclosing Circle

Also called the minimum enclosing circle, the smallest enclosing circle is, as its name implies, the smallest circle of a set "S" of points that include all "S" points in it. A good definition could be found in Wikipedia: Smallest-circle problem. I added the code from Rod Stephens web page: Find a minimal bounding circle of a set of points in C# as an available algorithm. The smallest enclosing circle takes a set of points as its source and produce a result compose of a point, the center, and a length, the ray of the circle. By adding a small, and easy to do algorithm, we can transform the center point and the ray into a circle. In fact the circle is represented as an array of consecutive points forming that circle. The count of points should be enough to give the illusion of a circle. We then can use that algorithm with the workbench exactly the same as we use for the convex hull. The actual implementation code from Rod Stephens works well, but it is quite slow. I also added another available algorithm which is based on Rod algorithm. The difference is that "S" points are pre-filtered with Ouellet convex hull algorithm. The result of the convex hull is then used as a source for Rod algorithm. The algorithm become a lot faster because it drastically reduce the number of source points. This is another advantage of having an efficient convex hull algorithm. Please note that Rod algorithm seems to be in O(n²). You can easily test performance with the provided test workbench where I included both implementation. I recommend to stay under ~1000 points because of the complexity of the original Rod algorithm. See a quick sample of a benchmark test results between the 2 algorithms

Appendix F - Generic implementation of the fastest algorithm generating all possible permutations of a set of items.

As a side note. I think I have made the quickest C# implementation for generating all possible permutations of a set of items. You can take a look at my answer at StackOverflow question generating permutations of a set (most efficiently) to have an idea of it. I did it in order to make some test on the Convex Hull. All the code is included in the provided source code of this article.

Main advantages over few algorithms found are

• Heap's algorithm (Single swap per permutation)
• No multiplication (like some implementations seen on the web)
• Inline swap
• Generic
• No unsafe code
• In place (very low memory usage)
• No modulo (only first bit compare)

Appendix G – The benchmark

The benchmark code has been made with Visual Studio 2017 in C#. It uses ".Net framework" 4.5.2 and newer version. All the source code for the benchmark and each algorithm implementation is provided. The binary could also be downloaded. The language is C# for all but 2 Convex Hull implementation, Chan done by Pat Morin and Ouellet CPP done by me.

It is not fully MVVM but uses some features of it. I had to decide to stop somewhere and it is like it is now. I feel it is working enough to be usable and easy to add your own algorithm.

How to Add Your Own Algorithm

Please look into the project "ConvexHullWorkbench" for the class "AlgorithmManager". Just add a line: "_algorithms.Add(..." at the end of the constructor.

Screenshots

Acknowledgment

• Thanks to Omar Saad, my project manager, for explaining to me what a convex Hull is and left me the time to test my idea, write articles and code.
• Thanks to Paul Labbé, a co-worker, for showing me Cross Product. It was one of the best improvements on my algorithm.
• Thanks to Jacques Bherer and Chuma Francis Mugombozi, co-workers, to revise my article. My article would have been a killer one if I would have followed each and every of their recommendations! But I'm too lazy...

References

• Wikipedia, Convex hull algorithms
• Liu, G. & Chen, C. J. Zhejiang Univ. - Sci. A (2007) 8: 1210. A new algorithm for computing the convex hull of a planar point set (https://rd.springer.com/article/10.1631%2Fjzus.2007.A1210)
• Eric Ouellet, IREQ, A Convex Hull Algorithm and its implementation in O(n log h)
• Wikipedia, Smallest-circle problem
• Rod Stephens, C# Helper, 2014-08-13, Find a minimal bounding circle of a set of points in C#
• Wikipedia, Heap's algorithm
• SimpleVar, Stack Overflow question/answer, Generating permutations of a set (most efficiently)
• Qwertie (David Piepgrass), Monotone Chain implementation at GitHub and 2D Convex hull in C#: 40 lines of code at Loyc.net
• Ceometric, .Net library geometry solutions
• futura-sciences.com forums for Tryss answer about Cross product
• bitlush, Efficient AVL Tree in C#

版本

Date of version submited. There could be a delay (day(s) ?) before the article become online. 

1. 2017-10-13, Initial version of this article.
2. 2017-10-18, Corrected some algorithm complexity. Re-arrange convex hull algorithm/complexity tables in order to make them easier to read. Added some information. Minor corrections. 
3. 2017-10-28, Updated binaries executable files to inlcude MSVCRT. This is to ensure 'C' code works fine on any Windows.
4. 2017-11-17, Minor syntax corrections or few hyperlinks added.
5. 2017-11-30, Minor syntax corrections and added some clarifications. Some updated graphics with Delaunay/Voronoi information. Added 1 graphic (conclusion with circle generator).
6. 2017-12-16, Minor corrections in text.
7. 2018-01-30, Added support for 'Online' Convex Hull (dynamic add) in O (log h) per point. Also added support for Peek (IsHullPoint) in order to know if a point would be a hull point before inserting it. All of that only in code for the moment, included in project OuelletConvexHullAvl2Online in GitHub. REmoved some dead code. Slight improvement (standardization). Added a Graham Scan modified version implementation , from Rod Stephens.
8. 2018-03-01, Update executable to reflect recent changes. Add table or related articles.

Thank you for taking time to let me know what you think about this article ...