Voronoi图的简单方法

我们使用标准容器和算法讨论Voronoi图的简单变体，这些容器和算法提供的性能比暴力法更好。

布局

介绍

基于边界的Voronoi图

点位置查询

简单变体的想法

蛮力法

网格法

倒排列表

计算复杂度

更新操作

Voronoi图的更高级的变体

C ++实现

Voronoi图的可视化和距离变换

性能测试

使用C ++代码

与C＃实现的比较

德劳内三角剖分

参考文献

介绍

Voronoi图（参见图1）是具有许多应用程序的基本几何结构。有关更详细的描述，请参见Wikipedia [1]中的文章及其参考。

图1：平面中一组点的Voronoi图。

不幸的是，Voronoi图的有效编程表示需要相当复杂的数据结构。开发和维护这些数据结构的高成本是在实践中充分利用这一强大的数学概念的严重障碍。

在这里，我们讨论使用可互换STL容器的可负担且有效的Voronoi图。这种方法的主要优点是表示简单，开发和维护成本低以及对各种用户算法的适应性。好处是以性能为代价的，但是，它比暴力方法要好得多。Voronoi图的建议变体对于快速开发需要Voronoi图功能的算法，以及开发Voronoi图的高级和高效表示形式应该是有用的。

基于边界的Voronoi图

根据定义，Voronoi图表示将二维空间细分为由一组输入点诱导的区域，这些点在传统术语中称为站点。每个区域都有一个多边形边界，其中包含最接近该区域站点的平面的所有点。这些区域也称为Voronoi细胞。

图2： Voronoi图的基于边界的表示图。两个相邻单元格的公共边界元素用红色绘制。

Voronoi图的广泛使用的基于边界的表示形式，如图2所示，存储了位置，单元，边缘和顶点的集合。这些表示的复杂性不仅与数据集相关，而且与支持不同类型表示形式的元素之间的邻接关系的需求有关。例如，边缘必须链接到单元格边界中的上一条和下一条边缘，此外，该边缘必须存储到该边界所包围的单元格的至少一个链接。这些表示形式对于有效遍历Voronoi图和计算Voronoi单元的参数（例如面积和周长）很有用。

点位置查询

应用程序中所需的Voronoi图的主要功能之一是平面点定位算法，该算法针对给定的查询点查找包含该点的像元。点位置问题非常重要。在实践中出现的许多类型的特定问题可以简化为点位置问题。一个典型的示例是涉及计算居住在购物中心区域内的客户数量的任务。

尽管有丰富的数据集，但是基于边界的表示方法没有提供比具有线性运行时间的搜索更好的功能。一种方法是将多边形中的测试点应用于Voronoi单元。另一种方法是通过计算从查询点到每个站点的距离来找到最近的站点。为了使用对数运行时间进行有效的搜索操作，Voronoi图的表示应使用基于R树或有向无环图（DAG）的空间索引。另一个高级数据结构的开发和集成使有效的Voronoi图的实现和维护变得颇具挑战性，并且成本很高。

简单变体的想法

Voronoi图的实际变体的想法是通过存储和使用尽可能少的数据集来降低表示的复杂性。在建议的最小变体中，Voronoi图仅由一组站点表示。该表示的第二个元素是最近邻居搜索的算法。该算法旨在支持Voronoi图的功能：点位置，查找站点的邻居以及构建单元格边界。如果最近邻居搜索的实现简单，则此方法可提供这种Voronoi图表示的主要优点-降低开发和维护成本。该变体的另一个好处是最小的空间需求。

蛮力法

在开发的早期阶段，考虑并实施Voronoi图的蛮力变体是合理的。它基于简单的算法，该算法计算查询点与每个Voronoi站点之间的距离，并找到具有第一个最小距离的站点。实施蛮力变体的简便性以牺牲用户算法所需的操作效率为代价。该方法具有线性运行时间。对于大型数据集来说太慢了。

Voronoi图的简单表示的主要问题是，是否有可能在不开发点位置查询所需的复杂空间数据结构的情况下提高最近邻居搜索的效率。

网格法

蛮力方法的低效率可以通过流行的网格方法解决。此方法的最简单变体是构建大小相等的方形单元。每个网格单元均存储其包含的点的列表。

图3：网格方法的图示。最近邻居搜索算法计算查询点（红色）和灰色单元中的点之间的距离。

搜索从包含查询点的单元格开始，然后在与访问的单元格相邻的单元格中继续进行搜索（参见图3）。当查询点与最接近的未访问单元格之间的距离大于查询点与已处理数据子集中的点之间的最小距离时，搜索将停止。

网格方法比基于空间数据结构的方法简单得多，但是它并不完全琐碎，并且有许多限制。当空间数据的分布均匀时，此方法可提供最佳性能。像元的最佳大小取决于数据的密度。当网格中有太多的空单元格或一个单元格中的平均点数太大时，此方法的性能会降低。即使空间数据的分布是均匀的，也必须重建网格单元，以避免由于空间数据集中的点数变化而导致性能损失。重建操作是网格方法的主要缺点。它使实现复杂化，并可能导致用户算法的性能下降。

倒排列表

在本文中，我们将重点介绍具有许多吸引人的功能的“反向列表”或“反向文件”方法。从实现的角度来看，这是最简单的方法之一。它比蛮力法稍难，但比网格法和空间索引更简单。在性能方面，尽管不能与使用空间索引结构的方法竞争，但与强力方法相比，该方法提供了相当合理的改进。与网格方法不同，此方法不需要重新构建操作，因为空间数据集会增加或缩小。

The method of inverted list is based on an ordered data set. It imposes an order on elements using the values of one of the attributes. For a set of two dimensional points, this requirement implies that the set of Voronoi sites can be sorted by X-coordinate (or Y-coordinate) of a point. However, in computational geometry, a more suitable option is to use lexicographic ordering.

帮助开发新的更有效的最近邻搜索算法的关键发现是站点的字典顺序显着减小了搜索范围。如下图4所示，该顺序使算法避免在距查询点很远的区域中进行搜索。因此，与无序集合不同，无需计算查询点与每个站点之间的距离。这个事实说明了通过暴力方法获得的性能提升。

图4：在一组有序点中的最近邻居搜索。查询点的X坐标（红色）与向前和向后顺序搜索的两个起点之间的红线段相交。灰色区域包含该算法要访问的点的最小子集。

改进的最近邻搜索算法具有两个阶段。首先，该算法为给定的查询点找到站点集中的初始位置。此位置提供两个站点，它们的X坐标构成范围，其中包含查询点的X坐标。然后，使用初始位置以按站点的升序和降序的顺序开始两个连续搜索。搜索向前或向后移动，并计算查询点与当前站点之间的距离。当查询点和当前站点的X坐标之间的差的绝对值大于所计算的从查询点到已处理子集中站点的最小距离时，每次搜索都会停止。

以下C ++代码说明了使用此算法的正向搜索来计算最小距离：

while ( it_cur != it_end ) {
dist_cur = Distance ( *it_cur , pnt ) ;
dist_x = fabs( it_cur->X() - pnt.X() ) ;

if ( dist_cur < dist_min )
dist_min = dist_cur ;

if ( dist_x > dist_min )
break ;

++it_cur ; }12345678910111213

这段代码仅比蛮力方法中的典型实现稍长：

for ( ; it_cur != it_end ; ++it_cur ) {
dist_cur = Distance ( *it_cur , pnt ) ;

if ( dist_cur < dist_min )
dist_min = dist_cur ; }1234567

计算复杂度

该算法的性能由处理的第二阶段决定。平均而言，每个顺序搜索的运行时间与站点数的平方根成正比。搜索初始位置更加有效。在有序容器中，最坏情况下的运行时间为对数。

从理论上讲，平方根运行时间看起来并不令人印象深刻。但是，与蛮力搜索相比，所讨论的算法的性能提高了几个数量级。例如，当Voronoi站点的数量为10,000时，该算法比线性搜索快100倍。

在Voronoi图的上下文中，讨论的最近邻搜索算法的重要优点之一是对矩形范围查询的有效支持。它可以用于查找站点的所有邻居，并在一遍算法中构造其单元。

该算法的另一个优点是可以通过各种方法和比较操作对一组二维点进行排序。这个事实对于优化特定应用程序中最近邻居搜索的性能很有用。可以通过使用到线上的预计距离对点站点进行排序来实现优化，这最适合给定的站点分布。

更新操作

到目前为止，我们已经讨论了不会修改Voronoi图的简单算法。许多现实世界的应用程序不仅需要遍历和搜索，还需要插入和擦除操作，这些操作会更改站点和单元的数量并修改单元的边界。在此类应用程序中，执行更新操作的性能和简便性很重要。

在计算几何中，对空间数据结构的有效更新操作尤其具有挑战性。它们仅适用于特定的输入，假定特定的数据分布类型以及插入和删除的顺序。与理想输入的任何偏差都会导致平衡和性能问题。更新操作会使不变式无效并且算法必须重新构建表示形式的数据集的情况并不罕见。

拟议的Voronoi图的简单变体的优点在于，它完全避免了所有这些困难。为了获得所需的有效更新操作，选择代表一组站点的合适数据结构就足够了。平衡的搜索树是此任务的理想选择。除了有效的搜索和遍历之外，它们还支持对数运行时间的插入和擦除。

Voronoi图的更高级的变体

尽管Voronoi图的简单变体不存储单元和边的详细空间分区数据集，但可以在此几何结构的许多应用中使用。最近邻居搜索通过查找其站点的所有邻居，可以构造Voronoi单元的边界。显然，与基于边界的Voronoi图相比，计算单元的周长和面积效率较低，但是此方法的性能对于某些应用程序可以接受。

另一个合理的选择是在Voronoi图的基于边界的表示中使用讨论的最近邻居搜索。这种简单的算法为使用复杂数据结构（例如https://www.xiaoyuani.com/）的空间索引方法提供了一种替代方法。但是，它要求将一组站点存储在有序容器中。

C ++实现

Voronoi图的简单变体可以用多种编程语言实现。C ++标准库提供了强大的功能，使您能够以最小的努力开发许多编程解决方案。我们将利用STL容器和算法来实现所讨论的思想。

Voronoi图的简单变体的性能主要取决于代表一组站点的数据结构。STL具有几种类型的基本数据结构，它们支持容器和迭代器的统一接口。这一事实表明，最佳编程解决方案应利用通用算法形式的可互换标准容器。可以根据容器的类型，迭代器和支持算法对其进行参数化。

Voronoi图的每个变体都有特定的要求，这些要求决定了实现的简便性。讨论的Voronoi图的简单变体在网站如何存储在集合中以及如何访问它们方面有所不同。

由于要求极少，Voronoi图的蛮力变型特别有吸引力。此变体对容器中数据的存储方式没有任何限制。它只要求容器提供对每个元素的访问。在C ++ 11中，任何提供正向迭代器的标准容器都满足这些要求。因此，下列所有的容器都适合Voronoi图的蛮力变体：set，unordered_set，vector，deque，list和forward_list。

基于倒排列表的Voronoi图的表示形式显得微不足道。此变型具有以下要求。它假定一个代表一组Voronoi站点的容器以字典顺序或排序顺序存储数据。容器必须提供一种有效的算法来查找站点集中的初始搜索位置，并且必须支持向前和向后顺序搜索。

当性能很重要时，与蛮力版本相比，合适的STL容器的种类大大减少了。这是为什么特定的STL容器不适合实施Voronoi图的改进变体的一些原因。单链接列表（std::forward_list）无法提供对前一个元素的有效访问。双向链表（std::list）对于查找初始搜索位置效率不高。基于哈希表（std::unordered_set）的容器不维护站点的词典编排或排序顺序。

可接受的有效容器的选择基本上由最近邻居搜索的第一阶段确定，该搜索在有序站点集中找到初始位置。有两种类型的数据结构可有效支持所需的操作。数组和基于数组的容器提供二进制搜索，运行时间为对数。在C ++标准库中，这种类型的最合适的容器是std::vector。库函数std::lower_bound()使用随机访问迭代器在有序容器中实现了对初始位置的有效搜索。平衡的搜索树可以获得相同的对数运行时间。所述std::set容器通常是基于一个红黑树和支持通过成员函数所需要的搜索std::set::lower_bound()。

在C ++中，std::vector它是默认的标准容器，因为它为许多类型的应用程序提供了最佳性能。但是，对于需要对Voronoi图进行频繁更新操作的用户算法而言，它并不总是最佳选择。由于插入和擦除操作的线性运行时间，此类算法的性能可能会大大下降，这比最近邻居搜索的平方根运行时间明显差。std::set提供具有对数运行时间的更新操作的容器可以提供更好的性能。

在复杂的用户算法中，最有效的标准容器的选择并不明显。运算的计算成本分析非常困难且无效。使用可互换STL容器的通用算法为调整性能和选择容器提供了一种简单实用的方法。对每个可接受容器的用户算法运行时间的度量使人们能够找到合适的容器。

鉴于STL仅是一个通用库，使用标准容器简单表示Voronoi图所提供的功能令人印象深刻。特别有趣的是，基本上免费获得对更新操作的有效支持。使用参数化解决方案时，只需std::vector要将模板参数从更改为即可std::set。这种优势来自关键的设计原则，即标准库提供了各种各样的可互换容器，这些容器对接口操作具有不同的性能保证。

同时，使用基本数据结构的标准容器不可能在所有类型的应用程序中提供最佳性能。例如，STL对要求高效随机访问元素和更新操作的问题的解决方案提供了有限的支持。具有随机访问迭代器的标准容器具有插入和擦除操作的线性运行时间，而具有快速更新操作的容器仅支持双向迭代器。这些限制可以通过应用前面提到的关键STL设计原则来解决。可以通过新的高效数据结构来提高算法的性能。在通用算法中，这些数据结构应用作STL扩展，以支持标准容器和迭代器的接口。

Voronoi图的可视化和距离变换

Voronoi图的可视化在实际应用中很重要。尽管所讨论的简单表示不提供单元的边界，但是它允许人们轻松地在位图上绘制Voronoi图。这是Voronoi分配模型的应用示例。绘制方法为每个站点分配唯一的颜色，然后应用最近的邻居搜索算法以设置每个像素的颜色。使用此方法已获得图1所示的Voronoi图的图像。

距离变换[2]与Voronoi图密切相关（请参见图5）。它计算查询点与其最近站点之间的距离。可以通过将距离值映射到用作查询点的每个像素的亮度来可视化距离转换。

图5：图1和2中使用的同一组点的距离变换。像素的亮度与像素与其最近位置之间的距离的平方成正比。

性能测试

所讨论的Voronoi图表示的性能已使用模拟距离变换计算的算法进行了测量。与Voronoi图相比，距离变换的实现更为简单，从而说明了这一选择。该测试将生成一个随机的二维点集，这些二维点代表Voronoi图的位置并填充指定的矩形。每个容器按字典顺序存储站点，以确保最近邻搜索的平方根计算复杂性。该测试测量计算从指定矩形内的每个点到其最近位置的距离所需的总运行时间。

该测试的运行时间表明std::vector具有最佳性能。这是因为该容器中元素的连续排列提供了对测试所需元素的快速随机和顺序访问。与蛮力算法相比，距离变换的计算使我们能够测量有序集合中搜索提供的性能增益。在Windows 7系统上，对于N = 100 ，运行时间缩短2.9倍，对于N = 10,000点，运行时间缩短28倍std::vector。因此，当N时，性能增益将增加约10倍。 增加了100倍。此结果与这两种算法的渐近计算复杂度得出的平方根估计一致。

使用C ++代码

该代码已为C ++ 03编译器开发。在C ++ 11编译器中，boost::chrono可以替换为std::chrono。

标准序列容器（std::vector，std::list和std::deque）已经被包含在示例算法来演示如何处理在通用算法的容器的特定代码，并允许用户比较各种数据结构的性能。这些容器在修改Voronoi图的应用程序中并不安全。更新操作违反了两个不变性：容器中元素的顺序和唯一性。可以使用STL扩展来解决此问题，例如基于数组的扩展Boost::flat_set，它们支持的接口std::set。这种容器将提高解决方案的安全性，并提供与相同的效率std::vector。

命名空间中的代码VoronoiDemo通过为二维点的X和Y坐标使用精确的整数类型，避免了与数字错误有关的问题。两点之间的距离的计算已被平方距离的计算所代替，该距离也利用了精确的整数类型。

与C＃实现的比较

用C ++开发的最近邻居搜索可为少量代码带来相当不错的性能提升。这一事实使该算法与其匹配的C＃实现进行比较很有趣。

将代码从C ++移植到C＃并不是很困难，但是有一个微妙的实现细节。C＃算法使用三态比较，而C ++中的标准算法假定容器数据类型支持严格的弱排序（简单放置，运算符较少）。附件中的C＃代码通过提供与C ++AlgoOrderedList.LowerBound()等效的功能解决了此问题std::lower_bound()。在其他方面，C＃实现比C ++更简单。特别是，它没有在容器的类型上参数化。它List仅用于编写，这意味着此演示不直接适合于数学集的表示。这个C＃变体的好处是它允许我们将其运行时间与基于的最快C ++变体进行比较std::vector。

C ++和C＃算法已经在装有AMD Ryzen 7 PRO 3700处理器，16GB RAM和Windows 10 Pro操作系统的台式计算机上进行了测试。附带的代码Stopwatch在C＃和chrono::high_resolution_clockC ++中支持以毫秒为单位的计算时间的度量。可执行代码是在Visual Studio 2019中使用具有默认项目设置的控制台应用程序生成的。

测试蛮力算法可以确认它具有线性计算复杂性（请参阅下表）。C ++算法比C＃算法快大约3倍。

ñ 100 1,000 10,000

C ++ 88 830 8,180

C＃ 270 2,900 28,700

对于基于有序数据集搜索的算法（请参见下表），渐近平方根复杂度达到N约10,000。

ñ 100 1,000 10,000 100,000

C ++ 22 58 146 430

C＃ 100 240 625 2,040

在此测试中，C ++的优势看起来更加令人印象深刻。它比C＃的性能高出将近5倍。尽管如此，在应用程序中选择此算法的C＃变体无疑是值得的。从比较N > = 1,000的运行时间可以看出，它比蛮力搜索（包括其C ++变体）要快得多。该测试是当数据集的大小可以增加几个数量级时应避免使用暴力算法的原理的另一说明。

德劳内三角剖分

本节说明了为什么Delaunay三角剖分超出了本文的范围，以及为什么在本文的第一个版本中省略了其讨论。

一组二维点的三角剖分表示将平面细分为一组三角形。对于给定的点集，存在许多三角剖分。在某些方面，Delaunay三角剖分是最完美的三角剖分，并且它是Voronoi图的对偶图（请参见图6）。Delaunay三角剖分的顶点对应于Voronoi细胞及其位置。Delaunay三角剖分中的顶点的连通性由Voronoi细胞的边界边缘定义。Delaunay三角剖分具有许多有趣的特性，使其在广泛的实际应用中有用[3]。

图6：一组点的Delaunay三角剖分（红色）和Voronoi图（灰色单元格边界）。通过在相邻Voronoi细胞的位点之间绘制线段来可视化Delaunay三角剖分。线段不一定与Voronoi单元的相应边界边缘相交。请注意，三角剖分仅覆盖输入点集的凸包内部的区域。

平面细分的相似性并不意味着对Voronoi图有效的方法可以直接应用于Delaunay三角剖分。在本文的上下文中，Delaunay三角剖分的主要显着特征是它是平面图。图的有效表示需要一个顶点存储到相邻边的列表。因此，Delaunay三角剖分的复杂度与Voronoi图的基于边界的变体相同。基于一组站点和最近邻居搜索的Voronoi图的讨论的简单表示不满足图形表示的这一要求。Delaunay三角剖分的几何结构比Voronoi图更复杂。