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小時內刪除侵權內容。