線裁剪爲任意二維多邊形

Question

如果我得到一段足夠長的線段可以穿過給定的多邊形，這可能是凹面或凸多邊形。我如何找到包含在多邊形中的所有相交的光段？

如果目標區域不是多邊形，但隱含的曲線函數或樣條曲線，怎麼辦呢？

謝謝！

Answer 1

真的沒有一個簡單的解決方案來解決您的問題，特別是曲線（貝塞爾曲線和樣條曲線）。除了多邊形裁剪的複雜性之外，重構修剪曲線還有相當大的挑戰（假設您希望裁剪結果保持爲貝塞爾曲線和樣條曲線，而不僅僅是「平展」線條近似）。

我最近發佈了一個測試更新*到我的多邊形剪裁庫'Clipper'，它可以做線多邊形和線條剪裁（線條也可以是曲線）。然而，雖然主要的庫是用Delphi編寫的，但是C＃& C＃，新的beta代碼到目前爲止只在Delphi中可能不會幫助你。不過，如果你看看代碼，你會明白爲什麼我說沒有'簡單'的解決方案。

• 編輯2011年7月15日： 此「更新」從來沒有超過這個beta版本，現在簡單的「證明了概念」。它現在基於我的Clipper庫的舊版本，並且需要進行重大修改才能維護和擴展。 （在某個階段，我可以重溫它，但我目前正在進一步完善核心庫的意圖。）不過，這個「證明了概念」 Delphi代碼可以下載here

Answer 2

• 第一步：以任意順序查找所有交點 分。對於多邊形， 您需要找到每個線段和線段的紅線 的交集。只需求解兩個線性方程組。如果解決方案受限於多邊形分段限制，則您有 有交集。
• 第二步：按照紅線對 的位置排序找到的點。你知道第一個和最後一個點是外部的。 「外部」隨每個點翻轉 - 外部 - 內部 - 外部等等。在兩個相鄰的外部點之間有內部線段（綠色）。編輯：不是真的......從＃0號開始，＃0號段 - ＃1號是內部，下一個是外部，下一個是內部，等等。

如果區域不是多邊形，但是由某個隱式函數給出，則需要找到該函數等於紅線的位置（當然，方法取決於函數）。