計算任意多邊形的有符號距離變換

您將如何計算多邊形的有符號距離函數，由任意一組點描述。多邊形可以是凹形或凸形的。假設這些點以逆時針方向纏繞在std::vector中。計算任意多邊形的有符號距離變換

更新

讓我更具體。這不是網格上的採樣函數。我需要能夠檢測沿通過（不一定相交）多邊形繪製的任意線段的符號變化，而不檢查每個線段的單個交點。問題是，我可能有成千上萬的線段。

任何人都可以想到一個有效的方法嗎？

如果我可以參數化表達SDF，我可以計算一個導數來完成這個。

來源

2017-01-23 Jacques Nel

我會用數學。 – deW1

你現在做了什麼？ – max66

到目前爲止，我已經玩過使用set操作來創建來自不同線段的參數SDF。建設性實體幾何似乎是一個很好的起點。 https://en.wikipedia.org/wiki/Constructive_solid_geometry 問題是，最終會出現一堆來自'min'' max'操作的分段方程。也許我可以將邊界描述爲平滑插值的貝塞爾或其他東西。 –

首先旋轉所有點，使線與x軸平行。然後轉換，以便該線是x軸。然後作爲測試整合。直線x0y0 x1y1下的面積非常易於計算。您可以對所有表達式進行求和以得到不確定積分或有符號區域，該區域應獨立於軸（因爲曲線下的點相減）。現在要回答具體問題，按x排序，以便您可以在給定的x處找到點值。因此，創建兩個「事件」，節開始和節「結束」與指針或引用回到開始事件。然後爲了在任何時刻獲得距離變換，我們計算所有與x相關的事件。如果你想爲每個事件間隔分段函數，那實際上可以稍微簡單一些，因爲你可以從頭到尾遍歷隊列。

來源

2017-01-23 20:47:50

壞消息：在最壞的情況下，一條線段可以與N點中的多邊形相交，並且這可能對於所有M線段都會產生。因此，在最糟糕的情況下，細分與側面的詳盡比較是不可避免的。這有利於暴力方法。

幸運的是，輸出敏感的解決方案以使用掃描線方法的N線段交點問題而聞名。複雜度可降至O((N+K) log N)或O(N log N + K)其中K是找到的交點數。

來源

2017-01-24 13:28:34

計算任意多邊形的有符號距離變換

回答

相關問題