65.9K
CodeProject 正在变化。 阅读更多。
Home

Voronoi 图的简单方法

Vadim Stadnik
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.99/5 (42投票s)

2015年3月4日

CPOL

22分钟阅读

viewsIcon

100920

downloadIcon

2465

讨论 Voronoi 图的简单变体。

布局

引言

Voronoi 图（参见图1）是一种基本几何结构，具有众多应用。更详细的描述请参见维基百科文章 [1] 及其参考文献。

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

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

在这里，我们讨论一种经济高效的 Voronoi 图，它使用可互换的 STL 容器。这种方法的主要优点是表示简单、开发和维护成本低以及适应范围广泛的用户算法。这些优点是以性能为代价的，但其性能仍远优于暴力法。所建议的 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）。当查询点与最近的未访问单元格之间的距离大于查询点与已处理数据子集中的点之间的最小距离时，搜索停止。

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

倒排列表

在本文中，我们将重点讨论“倒排列表”或“倒排文件”方法，它具有许多吸引人的特性。从实现角度来看，这是最简单的方法之一。它比暴力法略难，但比网格法和空间索引更简单。在性能方面，与暴力法相比，该方法提供了相当合理的改进，尽管它无法与使用空间索引结构的方法竞争。与网格法不同，随着空间数据集的增长或缩小，该方法不需要重建操作。

倒排列表方法基于有序数据集。它使用其中一个属性的值对元素施加顺序。对于一组二维点，此要求意味着 Voronoi 站点的集合可以按点的 X 坐标（或 Y 坐标）排序。然而，在计算几何中，更合适的选项是使用词典排序。

有助于开发新的更高效的最近邻搜索算法的关键观察是，站点的字典序显着缩小了搜索范围。如下图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 ; 
}

这段代码仅比暴力法中的典型实现稍长一点。

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

    if ( dist_cur < dist_min ) 
        dist_min = dist_cur ; 
}

计算复杂度

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

理论上，平方根运行时间看起来并不那么令人印象深刻。然而，与暴力搜索相比，所讨论的算法提供了数量级的性能提升。例如，当 Voronoi 站点的数量为 10,000 时，该算法比线性搜索快 100 倍。

在 Voronoi 图的背景下，所讨论的最近邻搜索算法的一个重要优点是高效支持矩形范围查询。它可用于在算法的一次遍历中找到站点所有邻居并构建其单元格。

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

更新操作

到目前为止，我们讨论了不修改 Voronoi 图的简单算法。许多实际应用不仅需要遍历和搜索，还需要插入和删除操作来改变站点和单元格的数量，并修改单元格的边界。更新操作的性能和实现简易性在这些应用中非常重要。

在计算几何中，空间数据结构上的高效更新操作特别具有挑战性。它们仅在特定输入下才能良好工作，这假设了特定类型的数据分布以及插入和删除的顺序。任何偏离理想输入的情况都会导致平衡和性能问题。更新操作使不变量失效，并且算法必须重建表示的数据集，这种情况并不少见。

所提出的 Voronoi 图简单变体的优点在于它完全避免了所有这些困难。为了获得所需的高效更新操作，只需选择合适的表示站点集的数据结构。平衡搜索树是此任务的良好候选者。除了高效的搜索和遍历外，它们还支持对数运行时间的插入和删除。

更高级的 Voronoi 图变体

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

另一个合理的选择是在基于边界的 Voronoi 图表示中使用所讨论的最近邻搜索。这种简单算法为使用复杂数据结构（例如树或 DAG）的空间索引方法提供了一种替代方案。然而，它要求站点集存储在有序容器中。

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 系统上，对于 std::vector 中的 N = 100 个点，运行时间提高了 2.9 倍；对于 N = 10,000 个点，运行时间提高了 28 倍。因此，当 N 增加 100 倍时，性能增益大约增加 10 倍。该结果与这两个算法的渐近计算复杂度得出的平方根估计值一致。

使用 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++ 中 std::lower_bound() 等效的函数 AlgoOrderedList.LowerBound() 来解决此问题。在其他方面，C# 实现比 C++ 更简单。特别是，它不针对容器类型进行参数化。它仅针对 List 编写，这意味着此演示不直接适用于数学集合的表示。此 C# 变体的优点是它允许我们将运行时间与基于 std::vector 的最快 C++ 变体进行比较。

C++ 和 C# 算法在同一台台式电脑上进行了测试，该电脑配备 AMD Ryzen 7 PRO 3700 处理器、16GB 内存和 Windows 10 专业版操作系统。附件代码支持使用 C# 中的 Stopwatch 和 C++ 中的 chrono::high_resolution_clock 测量计算时间（以毫秒为单位）。可执行代码是在 Visual Studio 2019 中使用默认项目设置的控制台应用程序生成的。

对暴力算法的测试证实其具有线性计算复杂度（参考下表）。C++ 算法比 C# 算法快约 3 倍。

N 100 1,000 10,000
C++ 88 830 8,180
C# 270 2,900 28,700

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

N 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 三角剖分超出了本文的范围，以及为什么在本文的第一个版本中省略了对其的讨论。

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

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

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

参考文献

  1. http://zh.wikipedia.org/wiki/Voronoi_diagram
  2. http://zh.wikipedia.org/wiki/Distance_transform
  3. http://zh.wikipedia.org/wiki/Delaunay_triangulation

历史

  • 2015年3月4日：初始版本
© . All rights reserved.