Voronoi图及相关第三方库概述

Voronoi图简介

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

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

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

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

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

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

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

生成Voronoi图的算法

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

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

LGLP

Commerical & Academic

第三方库备注：

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

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

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

参考链接

[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/

运筹优化 EI企业智能 EI创新孵化Lab

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。