不使用Fortune算法生成Voronoi圖

我希望能在C＃中創建一個Voronoi風景。我查看了許多Unity Project文件，但它們都實現了Fortune的算法，這完全在我的頭上。有沒有其他生成Voronoi圖的方法（這更容易理解）？性能下降對我來說是完全沒問題的。非常感謝！不使用Fortune算法生成Voronoi圖

旁註：由於我在團結工作，需要從生成Voronoi圖的2D/3D網格，每個像素的距離檢查將無法正常工作：（關於第二個想法，也許我可以用一個二維的Vector2s陣列，而不是像素，它們在x軸和z軸上有1.0個單位的間隔

來源

2017-07-27 Komm

所以，做你真正需要的幾何精確Voronoi圖或者是像素近似正常，因爲你提到的‘風景’？ – gue

的近似絕對是好的。雖然這將是不錯的頂點或邊的數據，這樣我就可以用它來生成一個網格。謝謝GUE！ – Komm

的可能的複製[最簡單的Voronoi圖的算法來實現？（https://stackoverflow.com/questions/973094/easiest-algorithm-的-維諾 - 圖對實施） – Bytemain

有一種非常簡單的方法可以創建一個近似的Voronoi圖VD對於每個需要在VD中定義一個單元的s （二維平面），你在一個圓錐體的s處以恆定的斜率和一定的高度作爲中心，然後你從上面看到圓錐體（所有尖峯都是可見的）景觀。滿足（投影到2D平面）是（近似的）Voronoi圖。

（Image Source）

當您在意見中的要求，以獲得實際的邊緣數據似乎不那麼容易。但是可能有一些圖形例程通過相交圓錐來生成它們。

另一種方法是計算給定點集的Delaunay三角剖分。這個related post中引用了一些實現（也提到了簡單的近似值）。然後你計算你的三角測量的雙重圖，你就得到了Voronoi圖。（雙圖表示對於三角剖分中的每個邊緣AB的每一個邊緣，VD中存在一個邊緣，平分兩個頂點A和B之間的空間，並且對於每個三角形，在雙邊相遇的VD處存在頂點。） Othwerwise還有許多C# Voronoi實現：Unity-delaunay，但正如你所提到的使用Fortune方法。

如果你想自己的代碼都可能在O(n^2)時間計算點用蠻力三角爲n點。然後應用圈內測試和edge flips。也就是說，對於每個三角形t(abc)創建一個由t三個頂點定義的圓C。然後檢查你的點的另一點d是否在C內。如果是，則翻轉t中的邊緣，並在d的三角形中形成邊緣。該翻轉完成，直到所有三角形滿足空圓屬性（德勞內條件）。再次以蠻力將需要O(n^2)時間。然後你可以計算上面提到的雙圖。

（Image Source）

來源

2017-07-27 06:38:51 gue

這是如何工作 – Bytemain

@gui：你是一個博士哇 – Bytemain

：？！？它是否也工作，當你從底部看 – Bytemain

「最簡單的那蠻力方法：對於在輸出的每個像素，遍歷所有的點，計算距離，使用最接近慢的可以，但很簡單，如果表現不重要，它就可以完成這項工作。「

[1] Easiest algorithm of Voronoi diagram to implement?

來源

2017-07-27 07:18:24 Bytemain

引用的算法是鮑耶 - 沃森這無關你的答案描述像素近似。 – gue

@gue：你在說什麼？你是博士嗎？哇？ – Bytemain

我不是博士學位。我看到的錯誤，你所使用的裁判是不是你引用一個，你引用（https://stackoverflow.com/a/10848478/4462067），但引用（https://stackoverflow.com/questions/973094/easiest-算法-的-沃羅諾伊-圖對實施/ 18084287＃18084287）。那是我的困惑來自的地方。 – gue

不使用Fortune算法生成Voronoi圖

回答

相關問題