第一个也是速度极快的在线 2D 凸包算法， 每点 O(Log h)

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

引言

本文主要有两个目的：解释 Ouellet 凸包算法新开发的“在线”（动态逐点添加）部分，并展示其用法和灵活性。

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

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

什么是凸包？

一个快速定义：当平面中的一个有界子集 X 时，凸包可以想象成围绕 X 拉伸的橡皮筋所包围的形状。

更详细的定义可以在我的第一篇文章中找到：一个凸包算法及其在 O(n log h) 中的实现，或者直接在维基百科中查找：凸包 和/或 凸包算法。

 

绿色的钉子是凸包或所有钉子
图片来源：Brilliant.org

Ouellet 算法历史

寻找凸包是一个古老的问题，始于60年代。自那时起，出现了许多寻找凸包的算法。Ouellet 凸包是一个相当新的凸包算法。它的首次发表是在2007年，由 Liu 和 Chen 在浙江大学学报A辑上发表的一种计算平面点集凸包的新算法。Liu 和 Chen 的文章相当隐蔽，很少有文章提及它，至少在2014年是这样。Liu 和 Chen 的文章不包含任何代码或其实现的任何细节。没有可用的比较测试来证明其真实效率，也没有人似乎发现了它的真正威力。

尽管不是第一个，我完全是独立创建的，完全不知道刘和陈论文的存在。我独自发现了相同的算法并创建了一个实现。然后我将其与 Chan 算法进行了测试，因为它当时似乎是最好的。在2014年，Ouellet 用“C#”实现，Chan 用“C”语言实现，两者性能非常接近。“C”语言以速度快于“C#”而闻名。为了了解其确切的性能优势，我决定用“C”语言编写我的算法。最终的“C”语言 Ouellet 算法在一般情况下（圆形和随机抛弃生成器）比 Chan 算法快约4倍。但最近发现了一个主要缺点。问题是在“h”接近“n”的特定情况下存在性能问题。尽管这种情况应该很少发生，但这使得算法在所有情况下都不稳定。问题出在用于存储凸包点的集合容器。该容器是一个使用数组作为其内部容器的列表。在 Ouellet 算法中，凸包点应始终保持有序。为了插入到数组中并保持有序，点需要移动到插入点的一侧，通常是右侧。当凸包点（命名为“h”）保持非常低时，即使源点（命名为“n”）数量极高，该算法也能正常工作。但当“h”变得太大，大约100,000个点时，性能迅速下降。为了解决这个问题，“List”已被 AVL 树替换。同时，还添加了许多优化。已经撰写了一篇文章来解释这些新实现和优化（参见快速改进的二维凸包算法及其在 O(n log h) 中的实现）。

今天的文章是为了解释算法中最新主要添加的功能：能够动态地逐点添加。能够一次处理一个点指的是“在线”，根据维基百科/Preparata 和 Shamos。该算法不仅可以一次处理一个点，而且可以以O(log h)每点的复杂度完成。它也可以在逐点添加之前通过批量调用（像大多数标准凸包用法一样）进行初始化。

词汇表

“h”	在谈论性能/复杂性时，“h”指结果计数，即凸包点。
“n”	在谈及性能/复杂度时，“n”指的是输入点的数量。
批处理	这是调用凸包算法的传统方式，即向算法提供一堆源点，然后一次性计算凸包。在本文中，它通常与“在线”相对使用。
凸包	请参阅：维基百科 – 凸包 或 Brilliant – 凸包 或 格拉斯哥大学 – pdf 文档，以获取出色的定义
一般用途 （一般情况）	“一般用途”在本文中经常使用。这意味着在大多数测试案例中，“h”保持极低。在代码中，主要使用2个随机生成器来表示真实案例：圆形和抛弃。作为参考，在这两种情况下，当“n”= 10,000,000点时，“h”通常保持在1000点以下。
在线	“在线”表示动态地逐点添加，在任何迭代中都拥有一个有效的凸包。它与“批处理”相对，批处理应用于点集合并一次性计算凸包。维基百科 - “凸包算法”对“在线”凸包有很好的定义。

“在线”Ouellet 凸包是什么？

简而言之

一种极快的凸包算法，支持批量或逐点插入。

- 或者 -

Ouellet 凸包在线 = Ouellet 凸包 Avl v2 + 在线功能 = Ouellet 凸包 Avl v3

详细信息

Ouellet 凸包“在线”算法是基于“AVL v2”版本的“Ouellet 凸包”算法，增加了在线功能和一些额外功能。它被称为“Ouellet 凸包 AVL v3”。

Ouellet 凸包算法（基础、第一版，非 AVL，非在线）在以下文章中解释得很好

• O(n log h) 凸包算法及其实现
• 一种计算平面点集凸包的新算法

Ouellet 凸包 AVL 和 AVL v2 在以下文章中解释得很好

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

Ouellet 凸包 AVL v3 基于 Ouellet 凸包 AVL v2。区别在于增加了在线功能和辅助函数，以简化在某些情况下的结果查询。这些新增功能可以帮助在某些场景下更快地获取结果。

新增函数列于在线凸包源代码 - 新增函数部分。

为了添加这些功能，进行了一些小的调整，但对性能的影响微乎其微。

“在线”添加部分的工作原理

为了理解，你需要了解 Ouellet 凸包的内部工作原理。请参阅Ouellet 凸包“在线”是什么。

“在线”功能按顺序执行3个步骤

1. 它检查“初始化”是否已完成，如果未完成，则只进行初始化，否则继续。“初始化”用第一个点初始化每个象限并返回。“初始化”在每个凸包计算中只在第一次调用时（无论是在线还是批处理）执行一次。
2. 它验证新点是否成为现有凸包点的新边界（最小/最大 X 或最小/最大 Y）。如果是，它会更新边界或每个受影响的象限，然后使相应的邻近点无效，最后返回。
3. 如果新点没有定义新边界，它会执行常规的添加点操作，就像以标准方式调用一样。我们添加点的方式就好像象限不是不相交的，因为这是最一般的情况——这意味着在象限不相交的情况下，我们会损失一点潜在的性能。但是，评估象限是否不相交比简单地调用不相交象限的函数更耗时。

性能

• O(log h) 每点

空间

• 当点是凸包点时，每点 O(1)，否则 O(0)。可以认为是 ~O(h)。

标准/批处理模式 vs “在线”模式用法

使用“标准/批处理”模式而不是“在线”模式有一些优势，因为一些优化只能在该模式下实现，而“在线”模式下执行不相交象限检查成本太高。不相交象限检查具有以下2个优点（适用时）

• 一项优化可以更快地验证象限归属。
• 一项优化可以跳过更多象限归属验证。

“在线”Ouellet 凸包的优缺点

优点

• 该算法的复杂度为 O(n log h)，这是目前已知最佳的性能。
• 根据我们的测试，它实际上是速度最快的凸包算法。
• 基于 Ouellet 凸包 AVL v2，该版本已得到很好的优化和测试。
• 同一个算法可以用于两种用途：“标准/批处理”和“在线”。同一个算法允许使用标准/批处理调用，然后进行任何“在线”调用。它也可以从一开始就专门用作“在线”算法。
• 性能与标准/批处理 Ouellet 凸包相似，尽管略慢。
• 标准/批处理功能的输入可以是任何 IEnumerable。这意味着它比任何需要数组作为输入的算法限制要少得多。它们中的大多数都能够被 C# 中的 IList 馈送。但 IList 仍然比 IEnumerable 限制更多。
• IEnumerable 对输入要求较低的另一个积极的副作用是，您可以使用任何对象，或许多对象的组合。如果它们支持 IEnumerable，那就足够了。迭代器-适配器辅助类将提供一个迭代多个不同 IEnumerable 对象的单一 IEnumerable 接口。
• 结果凸包不是原地生成。这意味着原始点顺序保持不变。在某些情况下，保持原始源点有序可能是一个要求。对于原地算法，如果原始源顺序必须保持不变，则在调用算法之前必须完整复制源点。
• 存储凸包点所需的空间约为“h”。在一般使用中，由于新添加的凸包点可能导致邻近点失效，因此空间可能会稍微高一些，但应该非常接近“h”。在最坏情况下，即使“h”极低，空间也可能接近“n”。最坏情况可能发生在“h”约等于“n”时，但最后添加到凸包的4个点是凸包点，每个象限一个，这将使所有之前的点失效。在一般情况下，这种情况几乎不可能发生。
• 该算法分为三部分。第二部分耗时最多。但它也是最容易多线程化的部分。
• 算法的第三部分是将单个象限结果合并到数组中。根据场景需求，可以避免这一部分。
• 所需空间保持在 O(h)。虽然不是原地算法，但在一般使用中，占用空间应保持非常低。
• 它似乎是在任何情况下都最可靠的算法/实现。在一般使用中性能最佳，即使 h ~= n 时也能提供出色的性能。下面的图形结果展示了这种稳定性。

缺点

• 它不是“原地”算法。用于存储凸包点的空间位于源点之外，这意味着它需要额外的空间。所需空间始终为 O(h)。

性能比较，Ouellet 在线版 vs Chan 版

目前，已知有3种凸包算法的时间复杂度为 O(n log h)：Chan 算法、最终的平面凸包算法 和 Ouellet 凸包算法。

最终凸包算法未包含在内，也未进行测试。没有找到任何实现。但其速度很可能相当慢，因为它需要计算中位数。Chan 算法实现已被用作性能测试的参考。性能结果来自GitHub 上提供的代码。Chan 和 Ouellet 算法都应该是性能最好的两个算法。这就是为什么在下面大多数性能图中只显示这两个算法。

本节中显示的图表是从所提供的基准测试中获得的。对于每次计算凸包结果的调用，其所花费的时间用一个点表示。对于每个算法的每个计时结果，绘制一条线来表示每个算法的线性回归。它有助于观察趋势，看它是否保持线性。

用于测试“Ouellet C# Avl v3”的3种基准测试类型

Ouellet 算法后缀 （Ouellet C# Avl v3…）	适用于	描述
（标准/批处理）	所有速度和 有效性测试	常规/批处理算法用法。输入：数组，输出：数组
（逐个循环）	所有速度和 有效性测试	模拟常规/批处理算法用法。 它接收一个数组并遍历所有点，将它们传递给算法，就像它被用作常规/批处理算法一样。最终的凸包结果只在所有点插入后查询一次。它演示了在线算法可以有多快。实际上，Ouellet 在线算法的速度几乎与 Ouellet 算法的常规/批处理部分一样快。
（**仅用于在线性能测试）	仅用于：在线速度测试	此选项应仅在“在线”速度测试中选择。其目的是查看能够动态添加点相对于非“在线”算法的优势。

测试类型

类型	描述
速度测试	标准/批处理模式。调用算法，传入点数组，并获取凸包点数组作为结果。
“在线”速度测试	对于“在线”算法（目前仅 Ouellet Avl v3 支持），一次调用算法一个点。 对于所有其他算法，将先前的凸包结果调整大小（数组扩大一个），并将要评估的新点添加到这个扩大的副本的末尾。因为每次迭代数组都会增长一个，这意味着必须创建一个新的数组的完整副本。然后再次使用新扩大的数组调用算法。循环直到所有点都被处理。 注意：此测试有一个特殊参数，仅适用于 Ouellet Avl v3。它可以通过避免每次都要求完整复制结果（常规/批处理算法需要）来节省一些时间。有时，上下文可能只需要知道该点是否已作为凸包点添加。有时，只知道已添加点的邻居就足够了。

 

测试结果

图 1

图1描述

基准测试中包含的许多凸包实现的一般性能概览。所有 O(n log h) 算法都比 MI 凸包（Delaunay/Voronoi）快。它们都被分组并位于 MI 凸包（Delaunay/Voronoi）之下。

图1观察

它显示了 O(n log h) 算法相对于其他算法的性能优势。

图 2

图 3

 

图2和图3描述

为了比较最快的算法，只选择了 O(n log h) 的算法。

这些图表显示了以标准批处理方式调用凸包算法实现的性能。这两个测试都显示了算法在一般使用中的速度。两张图片之间的区别是所使用的随机生成器类型（显示在图表标题中）。

图2（圆形生成器）显示了在圆形中随机生成的点的结果。

图3（抛弃）显示了从一个点开始，以随机方向和随机距离生成下一个点的生成器的结果。这通常会创建许多不同的点簇。

图2和图3的观察

逐点添加的性能与批处理模式下执行相同操作的性能相似。

两张图片之间存在的主要差异是由随机数生成器引起的。“抛弃”随机生成器的点分布有许多更接近的邻居，而“圆形”的点分布完全是随机的。拥有“抛弃”生成器分布确实使一项性能优化非常高效。这种优化只存在于批处理模式中。这就是为什么“Ouellet C# Avl v3 standard/batch”（批处理添加所有点）与“Ouellet C# Avl v3（逐个循环）”在“抛弃”生成器下具有更大的差异。

“Ouellet C# Avl v2”略慢于“Ouellet C# Avl v3”（即使两者都在批处理模式下），尽管后者是基于前者，它们应该非常接近。这归因于两个原因：

1. 我将“v2”中很久以前注释掉的优化重新放回了“v3”版本。我更喜欢在“v2”中保留优化注释掉，因为这样比较更容易。该优化是“快速丢弃”（有关更多详细信息，请参阅此处）。
2. 第二个影响则相反，它使“v3”变慢。这是对在线版本（“v3”）进行的小改动，它使其变慢，但非常微小，很难察觉。这个改动是为了获得添加一个点的结果：“已添加”或“未添加”作为凸包的一部分。这个修改意味着代码为“在线”版本增加了非常轻微的延迟。为了防止这种新的延迟，我本可以复制这两个函数（一个用于标准/批处理，保持不变，另一个用于在线），它们执行完全相同的功能，但由于时间差异非常小，我只保留了一个函数，以使代码更小且更易于维护。

 

图 4

图 5

图4和图5描述

图4和图5显示了“在线速度测试”的性能测试。该测试与常规“速度测试”相同，但它一次添加一个点。对于在线算法，它像接口设计的那样，正常逐点添加。对于所有其他非“在线”实现的算法，将先前计算的凸包结果扩大一个，然后将要评估的新点作为新扩大数组中的最后一个点存储。然后使用包含附加点的新扩大数组再次调用算法。然后循环直到所有点都添加完毕。

在图 5 中，为了更好地展示其他 4 个实现的分辨率，移除了 2 个较慢的实现（多线程）。

图4和图5观察

如图4所示，可以观察到多线程版本（主要是“MT”，也包括“4T”）具有相当长的稳定偏移。这种偏移是由于它们启动线程并等待其完成再继续，但与插入一个点所需的极短时间相比，这一步需要相当长的时间。当涉及线程同步（等待线程完成再继续）时，这意味着主线程等待其他线程完成时会发生线程切换。该线程必须等待操作系统重新调度CPU才能继续工作。

我们可以看到，Chan 实现与任何在批处理模式下使用的 Ouellet（除了蓝色曲线）的速度差异相当小。这种差异可能来自于它是在“C”语言中完成的，不需要对象实例化。

Ouellet C# Avl v3 在“在线”模式下使用（蓝色曲线）具有明显的优势，因为它的实例和状态始终保持活跃。无需重新创建其对象及其依赖对象。此外，由于 Ouellet 算法的设计基于象限，在线版本受益于大量信息，这些信息能够非常快速地评估和插入凸包点。

图 6

图7

图8

图9

图 10

图6-10描述

这些图显示了使用不同方法获取在线 Ouellet 凸包算法结果时的差异。用法在每个图的标题中描述。请注意图 9，由于响应时间非常低，点的数量减少了 10 倍。图 9 和图 10 使用“弧”随机生成器，其中所有点都是凸包点。

图6-10观察

当需要“在线”上下文时，有多种方法可以从 Ouellet Convex Hull Avl v3 获取凸包结果。为您的上下文选择最佳策略可能会在超快和慢速之间，在毫秒和小时之间产生差异。一些经验法则：

1. 如果您只想知道新评估的点是否是凸包的一部分，则无需询问任何凸包信息。
2. 如果您的上下文足够，则只要求新添加的凸包点的邻居。
3. 只有当评估点已添加到凸包中时，才请求完整的凸包点数组。

当上下文允许时，查询新添加点的邻居比获取完整的凸包结果要快得多。查看图6-10的 Y 轴清楚地表明，不请求凸包点完整副本可以节省大量时间。选择合适的函数，对性能影响最小，可以节省大量时间，尤其是在凸包由大量点组成时。

图9和图10的目的是展示查询凸包信息的函数对结果的影响，这种影响在图7和图8之间没有显现。实际上，令人惊讶的是，请求凸包点的完整副本所需的时间比请求邻居的时间要少（图7对比图8）。这种奇怪的结果应该归因于凸包结果点数非常少。但当构成凸包的点数非常多时，仅查询邻居的优势就变得非常明显（图9和图10）。尽管查询新添加凸包点的邻居并不总是足够的，但当上下文允许时，强烈建议这样做。

图 11

图12

图13

图11-13描述

所有图表均基于“弧形”点生成器，其中凸包结果满足“h”=“n”。这意味着所有凸包结果都由所有源点组成。图11耗时数天完成。

在图11中，Ouellet v3以两种不同的方式使用

• 作为标准/批处理算法
• 作为在线算法

图12和图13仅包含 Ouellet Convex Hull Online，以更详细地展示其自身结果。

图 13 的测试与图 12 相同，但不是查询完整结果，而是只查询添加点的邻居。图 12 基于 100,000 个点（太慢），而图 13 基于 1,000,000 个点。

图11-13观察

当“h”=“n”时，极大地放大了在线算法的优势。但主要目的是展示这种差异，根据结果，目标已实现。

尽管在现实生活中发生的风险很低，但所有这些测试都清楚地展示了当凸包点数变得非常大时，拥有“在线”凸包算法的主要优势。

图12很可能变为 O(n²)，因为在本次测试中，对于“n”，我们查询的是完整的“n”个结果。在100万点或更多点的情况下，需要数天才能获得所有结果。

图13基本上保持线性且速度极快。实际上，它保持在 O(n log n)，因为我们只获取有关添加点的邻居信息。

所有图的结论

“Ouellet 凸包 AVL v3”在大多数情况下表现出相当稳定的行为。当“h”=“n”时，它比任何其他算法都高效得多。它在所有一般情况下（常规/批处理使用）以及需要“在线”使用时都提供最佳性能*。根据目前的测试，Ouellet 凸包 AVL v3 提供出色的性能，并且在任何情况下都非常稳定。它也是最灵活的算法，支持“在线”使用，无论是否之前通过常规/批处理使用进行初始化。

*这里，Ouellet CPP 和所有基于数组容器的 Ouellet 算法都没有考虑在内，因为它们在“h”接近“n”时存在问题。

提供代码：实现和测试平台

代码摘要

代码包含

• 3项性能测试，用于比较算法速度。
• 3项有效性测试，以确保凸包算法返回正确的结果。
• 许多不同的算法实现（凸包和最小封闭圆），可在网络上找到。
• 许多 Ouellet 凸包算法实现，以观察演变并比较实现细节，例如优化、语言等。

可执行文件

可执行文件（二进制文件）在此提供。本文顶部也提供了一个链接。

该可执行文件提供了许多测试，用于性能评估或算法有效性测试。每个测试都在用户界面中自解释。

源代码

源代码在GitHub上提供。它包含了构建可执行文件所需的一切。它还包括GUI中作为可能测试的每个算法实现的源代码。它还包含一个小的示例，展示了调用算法的不同方式，这在下一节中也会有少量描述。

使用代码

在线使用新增功能（函数）

新增功能	描述
EnumConvexHullPoint	调用“Evaluate”或“TryAddOnePoint”函数的结果枚举类型。可能的值为： （非凸包点、已存在、凸包点）
bool IsExists(Point pt)	验证一个点是否已经是凸包的一部分。
EnumConvexHullPoint Evaluate(Point pt)	评估一个点是否会成为凸包点，如果尝试添加它，但不实际添加它。
EnumConvexHullPoint TryAddOnePoint(Point pt)	尝试将一个点添加为凸包点。
Point GetNextPoint(Point pt)	返回一个点的下一个点
Point GetPreviousPoint(Point pt)	返回一个点的上一个点
Tuple<Point, Point> GetNeighbors(Point pt)	返回一个点的上一个点和下一个点

调用示例

public void CallOnlineConvexHullDifferentWays()
{
	GeneratePoints(); // Points are generated in "Point[] _points";
 
	ConvexHull convexHull = new ConvexHull();
 
	// First way to call: Standard way to call (standard/batch)
	convexHull.CalcConvexHull(_points);
 
	// Usage of IEnumerable wrapper to loop over each convex hull points 
	// that are node in avl tree of each quadrant.
	foreach (Point pt in convexHull) { Debug.Print(pt.ToString()); }
 
	//Or can get an array copy of the convex hull points
	Point[] pointsStandardCall = convexHull.GetResultsAsArrayOfPoint();
 
	convexHull = new ConvexHull();
 
	// Second way to call: Adding one point at a time (online).
	foreach (Point pt in _points)
	{
		convexHull.TryAddOnePoint(pt);
	}
 
	Point[] pointsOnlineCall = convexHull.GetResultsAsArrayOfPoint();
 
	DifferencesInPath diffs = ConvexHullUtil.GetPathDifferences(nameof(ConvexHull), _points, pointsStandardCall, pointsOnlineCall);
	Debug.Assert(diffs.HasErrors == false);
 
	convexHull = new ConvexHull();
	Point[] allPoints = new Point[_points.Length * 2];
	Array.Copy(_points, allPoints, _points.Length);
 
	// Third way to call: Standard/Batch then Online
	convexHull.CalcConvexHull(_points);
 
	GeneratePoints(_points.Length); // Points are generated in "Point[] _points";
	Array.Copy(_points, 0, allPoints, _points.Length, _points.Length);
 
	foreach (Point pt in _points)
	{
		if (convexHull.TryAddOnePoint(pt) == EnumConvexHullPoint.ConvexHullPoint)
		{
			// Do nothing if only knowing if Hull point or not is enough
 
			// Get Only neighbors if enough
			var neighbors = convexHull.GetNeighbors(pt);
 
			// Query full result as an array
			var convexHullPoints = convexHull.GetResultsAsArrayOfPoint();
		}
	}
 
	// HERE: Verifying previous result
	OuelletConvexHull.ConvexHull convexHullOnline2 = new OuelletConvexHull.ConvexHull(allPoints); // Original First Convex Hull (highly tested)
	convexHullOnline2.CalcConvexHull();
 
	diffs = ConvexHullUtil.GetPathDifferences(nameof(ConvexHull), _points,
		convexHull.GetResultsAsArrayOfPoint(), convexHullOnline2.GetResultsAsArrayOfPoint());
 
	Debug.Assert(diffs.HasErrors == false);
}

未来

完全动态凸包（逐点添加和删除）

在Ouellet凸包中添加完全动态功能（管理添加/移除）的要求

要求	原因
快速搜索（衍生要求：保持源点的排序副本）	删除一个现有凸包点可能会使任何现有源点成为可能的新的凸包点。当只删除一个实际凸包点时，多达所有源点中的任何点都可能成为新的凸包点。为了避免逐一查找每个源点，我们需要保持它们的排序状态。
快速插入/移除	添加或删除一个点需要更新点的排序副本。为了节省时间，使用快速访问的集合可以提高性能。

* 如果点只在一个象限中，其中一个点使所有点都失效，除了第一个和最后一个，那么几乎所有点都可能失效。

确保3个功能

1. 保持源点排序
2. 快速搜索
3. 支持快速插入/移除

树似乎是作为点管理集合的最佳折衷方案。由于在插入/删除和读取之间取得了良好的平衡，因此它似乎比 AVL 树具有红黑树的优势。

此外，为了保持源点和凸包点之间对点树节点的快速访问，每个节点可以包含对其对应节点的引用，或者如果可能的话，直接是同一个节点。这应该有助于保持更好的性能。

考虑到这里讨论的各个方面，可以推断出动态凸包算法的时间复杂度可以达到 O(log n + log h) = O(log n) 每点（添加或删除）。通过使用两个集合（所有点和凸包点）之间的交叉引用，我们可能会从方程中移除“log h”。尽管在最终的 Big O 中并不真正重要，但它可能有助于实现更好的性能。我怀疑这是找到动态凸包可能达到的最佳性能。听起来它可能比维基百科中写的要好

根据“Preparata, Shamos, 计算几何, 章"凸包: 基本算法”：“在线版本可以以O(log n)每点的复杂度处理，这是渐近最优的”。动态版本可以以O(log² n)每次操作的复杂度处理。”

根据我们的测试，Ouellet 凸包算法在线模式下每点时间复杂度为 O(Log h)，这优于 O(log n)。此外，Ouellet 凸包的未来动态版本很有可能通过使用与当前版本相同的原理并添加另一棵树来保持源点排序，从而实现 O(Log n + Log h) 每点的时间复杂度。这也将优于 O(log² n)。

常见问题解答

• 为什么不使用红黑树来保存凸包点？我选择 AVL 树而不是红黑树，因为在常规操作中，作为凸包点添加的点比读取操作少得多。对于 100 万个源点，在每次测试中，最终凸包结果中的点数都少于 1000 个。这意味着大多数点被拒绝，只有极小一部分点被添加为凸包点。这是基于特定的随机生成器，但我非常相信它应该能反映大多数一般用法。
• 为什么没有实现完全动态的凸包？这个问题在未来部分已部分回答。但主要原因是动态与在线的复杂性差异。虽然“在线”与初始批处理凸包兼容，但完全动态凸包要困难得多，并且需要花费更多时间进行编码/测试。做起来应该很有趣，但会耗费大量时间。
• 为什么获取凸包数组（GetResultsAsArrayOfPoint）的结果与迭代器不完全相同。迭代器只返回凸包点而不闭合路径。GetResultsAsArrayOfPoint 可以返回带或不带闭合点的路径。GetResultsAsArrayOfPoint 通常从 Q1 的第二个点开始，唯一的原因是为了性能。在迭代器方面，它从 Q1 的第一个元素开始，因为这样也更快。简而言之，是为了性能和/或保持代码更易读。
• 为什么不能直接访问树或树节点。这是因为这可能导致错误的利用，并且极易出错，因为需要对算法有很好的理解才能不犯任何错误。

本文历史

1. 2018年2月28日，本文创建
2. 2018年3月4日，更新了在线使用的新增功能，以反映最近的代码更改。更新代码以修复警告，修复C++编译/引用。在代码中添加了MSVCRT dll文件，以简化使用并使代码独立。修复、添加和更正了一些文本以提高理解。
3. 2018年5月14日，修正了关于算法文章首次出现的信息。增加了一些澄清。