Voronoi图简介

Voronoi图刻画了特定站点集的影响区域。举例来说，通常情况下119急救电话都会将急救任务指派给距求救地点最近的医院，那么根据各医院的急救响应范围构成的空间划分就是以医院为站点的Voronoi图。具体来说，Voronoi图是指根据点集（称为站点）对二维平面的划分，使得划分出的每个区域内的点都具有相同的最近站点。

除了平面上的点之外，Voronoi图的站点也可以是平面上的直线或线段，其中最典型的例子就是以多边形的边为站点集的Voronoi图。更一般的，Voronoi图的站点还可以扩展为平面上的弧线。下图包含了平面上可能站点类型以及由这些站点生成的Voronoi图。

Voronoi图有着广泛的应用[1]，经典的应用场景例如：

1. 最近邻搜索：给定平面上的点集，通过该点集的Voronoi图可将平面上的最近邻搜索转化为判断待查询点所在的Voronoi区域的问题。

2. 设施选址：连锁品牌在开设新的分店时会希望新店的地址距离已有店铺尽可能的远，从而降低对现有店铺客流的影响。根据Vornoi图的性质，新店应该开设在以现有店铺为站点的voronoi图的顶点上。

3. 自动避障：假如站点代表了区域内的一系列的障碍物，我们希望具有自主寻路能力的机器人在穿过该区域时尽可能的远离障碍物，那么沿着以障碍物为站点所生成的Voronoi图的边行进就是最安全的路线。

此外，Voronoi图的概念还可以被拓展到更高维的空间，其中三维空间的Vornoi图在计算机图形学上有重要的应用。

生成Voronoi图的算法

  直接生成Voronoi图的经典算法有 Fortune(1987)的扫描线算法[2]和Imai (1996)基于拓扑的生成算法[3]，这两种算法的时间复杂度都为O(n log n)。Fortune算法和Imai算法都可用于处理站点为点或直段的情况，Imai算法还可以被拓展到处理站点为弧形边的情况。Fortune算法的优点在于算法直观，较容易实现，可参考算法作者提供的是实现方式[4]。保证数值稳健性是计算Voronoi图的一大难点。Fortune算法假设计算过程中的数据是完全精确的，因此基于该算法的实现方案，如boost::voronoi，需要将输入数据的类型限制为整形。Imai算法则使用浮点数表示输入、输出结果的坐标，并通过保持Voronoi对象间的拓扑关系来消除浮点误差的影响，因此数值稳定性更好。此外，由于点集的Voronoi图与Delaunay三角化之间存在对偶关系，所以生成Delaunay三角化的算法也可以被用来间接的生成Voronoi图。

生成二维Voronoi图的第三方库概览

     本节将对常见的生成二维Voronoi图的第三方库进行了梳理，信息主要来自库文档及第三方测试报告。

第三方库备注：

1. Boost Voronoi是目前唯一能对输出结果的精度进行控制的第三方库，但代价是输入坐标类型只能是整型。默认的输入数据类型是int32，作者提供了扩展数据范围的方法，但经测试在站点集规模较大时该方法可能存在bug。

2.  经测试Boost Voronoi的voronoi_edge.is_primary()函数存在bug，使用该功能时需注意。

3.  Boost Voronoi有用python封装的接口，使用方法与Boost Voronoi基本一致。

4.  在站点数为10E6以内随机数据集上，CGAL的计算速度与Boost Voronoi相近。CGAL在纯点集上的效率更高，Boost Voronoi在站点集包含边的数据更具优势。

5.  VRONI是目前唯一可处理弧形站点的第三方库，但该库并不开源。商业版本在CNC领域有较成熟的应用，单个licenses的价格为数千美金；学术版本可通过给作者发邮件进行申请。

参考链接

[1] Aurenhammer, F., "Voronoi diagrams -- A survey of a fundamental geometric data structure," ACM Computing Surveys, 1991, 23:345-405.

[2] S. Fortune, "A Sweepline Algorithm for Voronoi Diagrams," Algorithmica, 2, 1987 pp. 153–174. www.wias-berlin.de/people/si/course/files/Fortune87-SweepLine-Voronoi.pdf.

[3] Imai (1996), "A Topology-Oriented Algorithm for the Voronoi Diagram of Polygons" http://www.cccg.ca/proceedings/1996/cccg1996_0019.pdf

[4] Fortune算法C语言实现：https://netlib.sandia.gov/voronoi/index.html

[5] Menelaos I. Karavelas. A robust and efficient implementation for the segment Voronoi diagram. In Proc. Internat. Symp. on Voronoi diagrams in Science and Engineering (VD2004), pages 51–62, 2004.

[6] M. Held, S. Huber (2009), "Topology-Oriented Incremental Computation of Voronoi Diagrams of Circular Arcs and Straight Line-Segments".
Computer-Aided Design,41(5):327--338, May 2009.

[7] http://www.anderswallin.net/category/cnc/cam/openvoronoi/