驗證非相交形狀的自由多邊形頂點的算法

我的任務是允許用戶在畫布上輸入任意數量的任意點，並按指定的順序將它們鏈接在一起以繪製多邊形。驗證非相交形狀的自由多邊形頂點的算法

但是，每次用戶嘗試添加一個點時，我都必須驗證該多邊形是否仍然可以被繪製而不會相交。

我已經搜索過，發現只有this post這不會幫助我。

每次將新點添加到畫布時，我都需要形成約束，並檢查下一個點是否未驗證這些約束。

我已經添加了一些我試圖在下面實現的很差的插圖。這可能有助於定義我正在使用的座標系：點1是原點(0,0),x是正向右側，而y是向上的正向。

加點3個

前兩個點只具有約束1 != 2，添加點3我必須確保它不會在任何地方坐，通過兩個1和2傳遞行。

Adding point 4

黃色區域由線約束：

adding point 3

加入點4

現在，如下圖所示具有添加的點3，點4被阻止了1-2和綠地受限於2-3。在相當不可讀標記（沒有MathJax或任何東西），我想通了約束4是：

Y_4 < ((Y_2 - Y_1)/(X_2 - X_1))*X_4 + Y_1 

Y_3 < ((Y_2 - Y_1)/(X_2 - X_1))*X_3 ? Y_4 > ((Y_3 - Y_2)/(X_3 - X_2))*X_4 + Y_2 : Y_4 < ((Y_3 - Y_2)/(X_3 - X_2))*X_4 + Y_2 

Y_4 =/= ((Y_3 - Y_1)/(X_3 - X_1))*X_4 + Y_1

加入點5

現在添加在5點的狹窄的區域是：

Adding point 4

而且開始變得複雜起來。

我想知道如果有這些類型的東西的任何已建立的算法，或者如果有一般方程頂點n生成約束方程。如果不是幾百個點，可能有數十個，所以通過暴力和手工編碼來解決似乎不是一種選擇。

來源

2014-10-03 James

你想達到什麼稱爲多邊形簡單測試。您將在本文中找到相關信息：「平面多邊形的定位，簡化和包含測試」，F. FEITO，J. C. TORRES和A. URENA。

來源

2014-10-03 19:20:21

謝謝你，這是一個非常好的算法，他們還參考了一篇由Balbes和Siegel撰寫的論文：「一種用於計算平面多邊形簡單性和方向性的可靠方法」，1991年，值得一讀。 – James 2014-10-08 12:49:18

感謝您的反饋。魯棒性確實是一個重要的話題，因爲在實踐中，你經常會遇到退化或準退化的情況。 – 2014-10-08 13:18:32

你可以那樣做：

添加一個新的起點。
添加兩個與此點相鄰的新邊。
檢查是否存在一對相交的邊，通過迭代所有邊對並檢查它們是否相交。

該算法具有每增加一個新點的時間複雜度O(n^2)。如果速度太慢，可以使用以下觀察結果使其成線性：
如果在添加新點之前多邊形是有效的，則不會有邊相交。這就是爲什麼不需要遍歷所有邊對。因此，您只能在對<new, any>進行迭代，其中new是新創建的邊，any是多邊形的任意邊。有2 * n = O(n)這樣的對（因爲增加一個點只會產生2個新的邊緣）。

該算法每個點具有O(n)時間複雜度，所以它應該足夠快到幾十個或幾百個點。

檢查兩條邊相交是否簡單：邊只是一條線段，檢查兩條線是否相交是一個衆所周知的問題。

來源

2014-10-03 15:59:18 kraskevich

驗證非相交形狀的自由多邊形頂點的算法

回答

相關問題