計算爲平面的Voronoi圖在3D

是否有一個代碼，/庫，可以計算出在3D平面（平行四邊形）Voronoi圖？我檢查了Qhull，看起來它只能使用點，在它的例子中，Voro ++可以處理不同大小的球體，但我找不到任何多邊形。計算爲平面的Voronoi圖在3D

在此圖像中(sample planes in 3d)的平行四邊形是3D，因爲它們的厚度，但在這種情況下，厚度將是零！

2012-02-10 zamazalotta

Voronoi細胞不是平行四邊形。你在這裏發佈的圖片讓你感到困惑。 Voronoi單元邊界是超平面的一部分，這些超平面將各個單元分開。

看看這個網站討論和可視化3D Voronoi圖：

http://www.wblut.com/2009/04/28/ooh-ooh-ooh-3d-voronoi/

爲了計算沃羅諾伊細胞，常見的方法是先建立德洛內三角。在2D中有很多算法可以做到這一點，而在3D中它變得更加複雜。但你仍然應該能夠找到一些東西。 qhull可能是正確的選擇。

當你有Delaunay三角，計算每個tetraeder的中心。這些是您需要繪製的多邊形的角點。對於Delaunay三角測量中的任何邊緣，繪製連接相鄰中心的多邊形。這應該是一個超平面。現在，您所需要做的就是繪製超平面作爲凸包的一部分。爲此，您需要繼續從內部到外部無限的超平面。

我強烈建議最初開始2D。一旦你有2D的工作代碼，看看如何在3D中做同樣的事情。如果你希望速度很快，這在2D中已經非常棘手。

這是來自維基百科可視化兩個德洛奈和Voronoi圖的圖形： Delaunay and Voronoi in 2D

黑線是的Delaunay三角剖分。棕色線與此正交，並形成Voronoi圖。 Delaunay三角剖分可以用於各種很酷的可視化事物：計算凸包，voronoi圖和alpha形狀：http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Alpha_shapes_3/Chapter_main.html

來源

2012-02-11 12:14:01

我想我的問題是不夠清楚。讓我試着澄清它。當你做一個點的Voronoi圖時，你得到的單元格是最靠近某個點的區域。我想要做的是對這些平行四邊形進行Voronoi，並且使每個Voronoi單元定義最接近其對應平行四邊形的區域。我可以弄清楚如何在二維中做到這一點（將點定義爲矩形的頂點，然後將所有四個點相加得到一個整體區域，等等......）但是3D非常複雜，所以我不能相信自己。這就是爲什麼我正在尋找一個強大的/經過測試的代碼/紙張/算法 – zamazalotta 2012-02-11 19:32:02

即使在2D中，角落也不會起作用。當你走彎路時，我可以很容易地畫出你失敗的情況。說R1是0,0,0,1 1,1 1,0，R2是-50,50 50，-51 50，-52 -51,49。你需要的是每對物體邊緣上最接近的一組點。當一組邊/平行平行時，您需要最小值和最大值（三維，四對）。 – 2012-02-11 21:27:16

Bowyer-Watson通常是推薦的算法。大多數論文/算法的問題在於，它們沒有解決當點在空間上彼此接近時（所以四面體很薄）時產生的棘手情況，當voronoi單元最終應該平坦並且當多點是在同一個球體上。再加上處理不準確的數學和舍入的數字複雜性，你有自己的無盡調試的祕訣。我的建議是，如果可以接受，請先過濾數據。否則，你最終會在你的算法中編寫大量的特殊情況。

前段時間，還有一篇日文論文聲稱有一種不同的方法來解決這些情況，從delaunay三角測量開始，並從中找出voronoi細胞，但它也是有缺陷的。它必須是很好的研究員，未來與算法的廣泛線，讓研究助理擔心細節...

來源

2012-06-04 15:07:02

計算爲平面的Voronoi圖在3D

回答

相關問題