從邊界切割矩形

從邊界提取矩形的好方法是什麼？我已經有一些工作，但它有一些錯誤，有些事情處理更先進，然後需要，所以我想重新開始。從邊界切割矩形

這裏是我想要的東西：

enter image description here

注意右側邊界得到的切成多種形狀。

我的邊界與[nOfPoints] [xy]中的float[][]一樣。舉例：

[0][0] = 10; 
[0][1] = 10; 
[1][0] = 100; 
[1][1] = 10; 
[2][0] = 100; 
[2][1] = 100; 
[3][0] = 10; 
[3][1] = 100; 
[4][0] = 10; 
[4][1] = 10;

會形成一個矩形。如果任何其他格式更適合，那麼我可以改變它。無論如何，我對抽象方法更感興趣，然後詳細描述它。

請大家幫忙。

來源

2015-02-09 clankill3r

您的矩形是否始終與軸對齊？ – 2015-02-09 14:54:34

是的，他們是！ – clankill3r 2015-02-09 15:08:16

我打算在這一天給出一些想法，但我不確定你可以做得比做2d布爾更好。我已經爲交叉點撰寫了此摘要：http://stackoverflow.com/questions/8011267/area-of-rectangle-rectangle-intersection/8011422#8011422。減法的方法是類似的，但是存在結果可能不是單個多邊形的複雜情況，例如，如果你從一個大的中心減去一個小方格。 – 2015-02-09 15:39:28

具有軸對齊的矩形將使一些細節更容易，但不會影響一般算法，所以我將不會做出關於軸對齊的進一步假設。

用於減去簡單多邊形的方法的工作原理與查找here中描述的具有一個小變化的多邊形的交點相同。此外，該答案假設多邊形是凸的（實際上是矩形），所以最多隻有一個由交點產生的多邊形。在當前情況下可能會導致多個多邊形。但是，找到多個多邊形並不難，請參閱下面的註釋。

在相交問題中，多邊形都是逆時針方向的，這是一種指定（按照慣例）線的哪一側在多邊形內的方式。如果我們反轉要減去的矩形的方向，那麼按照約定，平面的所有都在多邊形「內部」，除了邊緣右側的一個小區域。因此，減去多邊形實際上是多邊形的交點，其中將要減去的多邊形從裏面翻出來！

評論：

從非凸多邊形減去一個凸多邊形可能導致多個多邊形。找到哪個多邊形取決於起始交點。如果跟蹤在追蹤一個合成多邊形時消耗的交點，則可以對未消耗的交點重複該過程，每次找到更多結果。
在交叉點發生在角落的情況下，事情會變得混亂。一種方法是從邏輯上將交叉點分成多個邏輯交點，每個邏輯交點代表一次合法遍歷。
兩個多邊形的分段可能是併發的，特別是在OP的情況下。這些細分市場可能會被視爲預處理的一部分。如果方向相反，則表示由外部環繞的無限薄的內部件，如果它們在相同的方向上則代表內部環繞的無限薄的外部。無論哪種方式，他們可能會被丟棄。
以前的評論可能看起來很奇怪，因爲丟棄重疊的片段後，布爾不再位於多邊形之間，但算法只需要實體正確定向。因此，這種通用方法可用於用曲線對多邊形進行切片，從而將切片保留在一側或另一側。
減去多邊形可能會導致物體不是簡單的多邊形。如果要減去的多邊形完全位於另一個多邊形的內部，則結果可能是其中有孔的區域。如果這是擔心的問題，那麼可以考慮使用稍微複雜的結構來表示使用多個循環來定義邊界的區域。區域的外環應該逆時針方向，內環應該順時針方向。

來源

2015-02-10 19:08:02

感謝您的巨大回答。我沒有時間閱讀，但我現在非常感謝！ – clankill3r 2015-02-16 11:37:40

從邊界切割矩形

回答

相關問題