Voronoi圖的凸殼

我需要一個算法來計算O（n）中點的Voronoi圖的一組點的凸包。 Voronoi圖包含在邊界框中並存儲爲雙向連接的邊界列表。輸入是原點位於邊界框上的半邊。Voronoi圖的凸殼

我知道這兩點是相鄰的上凸包當且僅當它們共享一個無限長維諾邊緣......

2010-11-23 wallacer

爲什麼你不能從一個無限邊緣繞到凸包？我想你可能想更多地談一談這個問題是如何表現出來的，以便我們能夠理解這個難題。 – 2010-11-25 14:09:04

我想這個問題的難度更大的部分是測試voronoi圖上的特定邊是否確實會持續無窮大，如果它沒有在邊界框中定界。此外，由於voronoi圖和邊界框存儲爲雙向連接的邊列表，另一個具有挑戰性的部分是確定如何正確地遍歷DCEL。無論哪種方式，我想出了一個有效的解決方案。也許我會很快在這裏寫下它。 – wallacer 2010-11-26 00:19:50

如果你有一個邊界框足夠大，這樣只有無限的細胞具有界限邊緣，任務沒有按看起來很難。遍歷邊界邊界，對於它們中的每一個，向前和向後遍歷它以找到第一個非邊界邊界F和B。將遍歷期間發現的當前和所有邊界標記爲used。如果該框不存在，則邊線F和B將是無限的。因此，他們接觸面（fF和fB），他們的「中心」是凸包的一部分（當前面是C），而橫向C-to-F是凸包的一部分。採取面子fF並從F的雙胞胎向前迭代找到下一個非邊界邊緣，比如F1。如果它等於'B'-twin（或者它的邊界是used），我們就完成了。如果不是，遍歷下一個鄰居（'fF1'）。

來源

2011-01-27 22:28:27 mbaitoff

-1

我相信可以在O（n）時間內計算Voronoi圖的凸包。

如果給定的Voronoi圖和一個頂點應該位於CH中，那麼您可以遍歷Voronoi圖的單元格，並像Graham掃描算法中那樣使用不同的方式來擴展凸包。

只有一個理論缺少在這裏，看接下來...

根據計算幾何由Springer的M4書，定理7.4：Q點是渦（P）的頂點當且僅當其最大的空圓C_p（q）在其邊界上包含三個或更多個位置。這意味着每次迭代需要檢查的站點都在O（1）中完成，這意味着您只需要遍歷O（n）個站點。

根據定理7.3，n的點的Voronoi圖中頂點的數目指向最多2n-5（線性次序）的平面上的點。

因此，可以計算O（n）時間內Voronoi圖的CH。

來源

2014-07-13 18:57:35 TripleS

Voronoi圖的凸殼

回答

相關問題