algorithm - 非凸多邊形內的最大圓




polygon computational-geometry (4)

一個O(n log X)算法,其中X取決於您想要的精度。

二進制搜索圓的最大半徑R:

在每次迭代中,對於給定的半徑r,將每個邊緣E“向內”推R,以得到E'。 對於每個邊E',將半平面H定義為多邊形“內部”的所有點的集合(使用E'作為邊界)。 現在,計算所有這些半平面E'的交集,這可以在O(n)時間內完成。 如果交點非空,則如果使用交點中的任意點作為中心繪製半徑為r的圓,則它將位於給定多邊形內。

如何找到可以放入凹多邊形內的最大圓?

只要能夠實時處理具有~50個頂點的多邊形,蠻力算法就可以了。


一個O(n log(n))算法:

  1. 構造P中邊緣的Voronoi圖 。這可以通過例如Fortunes算法來完成。
  2. 對於P內部的Voronoi節點(等距三個或更多邊緣的點);
  3. 找到P中邊緣距離最大的節點。此節點是最大內切圓的中心。

總結:理論上,這可以在O(n)時間內完成。 實際上,您可以在O(n log n)時間內完成。

廣義Voronoi圖。

如果您將多邊形的頂點和邊緣視為一組網站並將內部細分為“最近鄰居單元格”,那麼您將獲得所謂的(通用)Voronoi圖。 Voronoi圖由連接它們的節點和邊組成。 節點的間隙是到其定義的多邊形面的距離。


(這裡多邊形甚至有孔;原理仍然有效。)

現在關鍵的觀察是最大內切圓的中心接觸多邊形的三個面(頂點或邊),並且沒有其他面可以更接近。 因此,中心必須位於Voronoi節點上,即具有最大間隙的節點。

在上面的示例中,標記最大內切圓的中心的節點接觸多邊形的兩個邊和頂點。

順便說一下,內側軸是Voronoi圖,其中去除了從反射頂點發出的Voronoi邊緣。 因此,最大內切圓的中心也位於中軸上。

資料來源:我的博客文章 ,涉及某些點上最大內切圓的概括。 在那裡你可以找到更多關於Voronoi圖及其與最大內切圓的關係。

算法和實現。

您實際上可以計算Voronoi圖。 Fortune給出了點和段的最壞情況O(n log n) 算法,Voronoi圖的掃描線算法 ,SoCG'86。 Held發布了具有預期的O(n log n)時間複雜度的軟件包Vroni ,其實際上也計算了最大內切圓。 並且似乎也有一個實施boost

對於簡單的多邊形(即,沒有孔),在O(n)時間內運行的時間最優算法是由於Chin等人,1999年在線性時間中找到簡單多邊形的中間軸

蠻力。

但是,正如你所說的那樣你可以使用強力算法:如何簡單地嘗試所有三維網站(頂點和邊)。 對於每個三聯體,您可以找到候選Voronoi節點,即三個位點的等距基因座,並檢查是否有任何其他位點與候選最大內切圓相交。 如果有交叉路口,則解僱候選人。 你可以找到所有三胞胎中最大的一個。

請參閱我的碩士論文中的第3章,了解有關計算三個站點的等距基因座的更多詳細信息。


解決這個問題的關鍵是首先進行觀察:適合任意多邊形的最大圓的中心是:

  1. 在多邊形內; 和
  2. 離多邊形邊緣任意一點最遠。

為什麼? 因為圓的邊緣上的每個點都與該中心等距。 根據定義,最大的圓將具有最大的半徑,並且將在至少兩個點上觸摸多邊形,因此如果您發現距離多邊形最遠的點,則您找到了圓的中心。

此問題出現在地理位置,並以迭代方式解決為任意精度。 它被稱為無法接近的極點問題。 參見不可接近的極點:地球上最遠地方的計算算法

基本算法的工作方式如下:

  1. 將R定義為從(x min ,y min )到(x max ,y max )的直線區域;
  2. 將R除以任意數量的點。 本文使用21作為啟發式(意思是將高度和寬度除以20);
  3. 剪輯多邊形外的任何點;
  4. 對於其餘部分,找到距邊緣上任何點最遠的點;
  5. 從那時起,定義一個具有較小間隔和邊界的新R,並從步驟2重複以獲得任意精度答案。 本文將R減少了2的平方根。

一個注意事項,如何測試一個點是否在多邊形內部:這部分問題的最簡單的解決方案是將光線投射到該點的右側。 如果它穿過奇數個邊,則它在多邊形內。 如果它是偶數,它就在外面。

此外,只要測試到任何邊緣的距離,您需要考慮兩種情況:

  1. 該點垂直於該邊緣上的一個點(在兩個頂點的邊界內); 要么
  2. 事實並非如此。

(2)很容易。 到邊緣的距離是到兩個頂點的距離的最小值。 對於(1),該邊緣上的最近點將是從您正在測試的點開始以90度角與邊緣相交的點。 請參見點到光線或線段的距離







geometry