如何根據點集和Delaunay三角剖分推導出Voronoi圖？

我正在製作一個遊戲，我創建了一個隨機的省份地圖（一個風險或外交）。爲了創建該地圖，我首先生成一系列半隨機點，然後計算這些點的Delaunay三角剖分。如何根據點集和Delaunay三角剖分推導出Voronoi圖？

這樣做，我現在正在創建一個Voronoi圖的點作爲省邊界的起點。我現在的數據（沒有雙關語意思）由原始的一系列點和Delaunay三角形的集合組成。

我見過很多方法可以在網上做到這一點，但其中大部分與德勞奈的派生方式有關。我很想找到一些不需要整合到德勞內的東西，但可以單獨依據數據進行工作。如果不這樣做，我正在尋找相對幾何新手可以理解的東西，而不是最佳速度。謝謝！

來源

2008-09-17 CommanderTso

Voronoi圖僅僅是Delaunay三角網的偶圖。

因此，Voronoi圖的邊緣沿着Delaunay三角剖分邊緣的垂直平分線，因此計算這些線。
然後，通過找到相鄰邊的交點來計算Voronoi圖的頂點。
最後，邊緣就是你計算的線條的子集，它們位於相應的頂點之間。

請注意，確切的代碼取決於您用於兩個圖表的內部表示。

來源

2008-09-17 16:59:59

+17

您還可以通過計算所有三角形的外圍中心，並連接任意兩個三角形共享邊緣的外圍中心來找到對偶（即Voronoi圖）。 – batty 2009-05-01 03:22:06

正如上面的評論所建議的那樣，我會分兩步做： 1.計算每個Delaunay三角形的外心 - >這些是Voronoi頂點。請參閱http://en.wikipedia.org/wiki/Circumscribed_circle#Circumscribed_circles_of_triangles 2.對於每個Delaunay邊緣，計算Voronoi邊緣：連接兩個相鄰Delaunay三角形的外圍中心的線段。 – 2009-07-10 12:43:28

@ balint.miklos如何處理外部網站/三角形？ – Orient 2016-05-03 12:20:28

我敢肯定，「三角」 http://www.cs.cmu.edu/~quake/triangle.html可以生成沃羅諾伊

來源

2008-09-17 16:58:52

那麼事物之所以連在一起的原因是因爲Delaunay三角測量和Voronoi圖是雙重結構。意味着從voronoi到delaunay，反之亦然。

這意味着如果你有一個voronoi圖，你需要做的就是連接共享一個邊的點，然後你將有delaunay三角測量（反之亦然）。

來源

2008-09-17 17:05:49

如果你只是連接（即，添加一個邊緣）共享一個邊緣的點，你會得到原始圖形，呃？ – 2008-09-17 17:08:57

如果最佳速度是不考慮，下面的僞代碼將生成Voronoi圖艱辛的道路：

for yloop = 0 to height-1 
    for xloop = 0 to width-1 

    // Generate maximal value 
    closest_distance = width * height 

    for point = 0 to number_of_points-1 
     // calls function to calc distance 
     point_distance = distance(point, xloop, yloop) 

     if point_distance < closest_distance 
     closest_point = point 
     end if 
    next 

    // place result in array of point types 
    points[xloop, yloop] = point 

    next 
next

假設你有一個「點」類或結構，如果將它們分配隨機顏色，那麼當你顯示輸出時你會看到熟悉的voronoi模式。

來源

2008-09-17 17:13:42

您的每個Delaunay三角形都包含Voronoi圖的單個點。

您可以通過找到每個三角形的三個perpendicular bisectors的交點來計算此點。

您的Voronoi圖將連接這組點，每個點都與它最近的三個鄰居有關。（每個鄰居共享Delaunay三角形的一側）

您如何計劃接近邊緣案例？

來源

2008-09-17 17:14:04

在嘗試將此線程用作我自己類似問題的答案的源代碼之後，我發現Fortune的算法 - 可能是因爲它是最受歡迎的&因此最容易理解。

The Wikipedia article on Fortune's algorithm保持與C，C＃和Javascript中源代碼的新鏈接。他們都是頂尖的，並帶有美麗的例子。

來源

2012-10-02 14:58:15

如何根據點集和Delaunay三角剖分推導出Voronoi圖？

回答

相關問題