定位邊界2D實體

Question

給定一個點，並且將任意2D實體（圓，多邊形，直線，折線，弧等），沒有人知道現有的戰略到：

1. 確定是否點是由任何實體組合包圍（界定）？我知道在封閉的形狀上進行'內部'測試是很容易的，但這並不總是給我想要的東西 - 特別是嵌套或相交的形狀。

2. 找到圍繞我的點形成閉合多邊形的最小（最接近？）線/實體集合？ （想想一個洪水填充，但不依靠顏色）

Answer 1

我已經解決了過去在商業產品中的這個問題。你已經問過關於分析曲線的問題，但是我會更一般性地討論至少兩次可微的曲線。將多邊形作爲一組單獨的線段處理。不需要對曲線進行分割，但是如果您想要，可以稍微調整算法。

此外，您可能希望在Graphics Gems V中查看我的論文10基於矩陣的橢圓幾何以找到您的省略號之間的交點。

基本思想：

1. 考慮從+ X方向測試點的射線。
2. 現在考慮一個螞蟻從測試點沿射線行走。
3. 當螞蟻碰到其中一條曲線的第一個交叉點時，它會使其最大限度地離開它，並在該交叉點留下一個箭頭指示其選擇的方向。 （如果沒有交點，那麼顯然這個點是沒有界限的。）
4. 如果涉及到曲線的末端，它會自己翻倍。
5. 如果在該點處有多條曲線相交，則會選擇最左邊的曲線。
6. 如果一條或多條曲線實際上與交叉處的射線相切，則可以使用更高的導數來決定選擇哪條曲線和方向。 （這隻螞蟻知道微積分）
7. 現在，當螞蟻沿着曲線漫步​​時，它總是會像上面那樣產生最大的左轉。如果在交叉點處曲線之間存在相切，請使用更高的導數來確定「最左邊」的曲線。 （細節留給螞蟻）。
8. 在旅途中，螞蟻可能會多次與光線出發。但是一旦它發現自己沿箭頭方向行進（它在步驟3中留下的箭頭），就會完成行程並穿過「輪廓」。問題被減少到決定點是否在該輪廓中。

「輪廓」是一個拓撲實體。它是在「頂點」連接的「分段」的閉環。

「段」是輪廓在特定方向中使用的一段曲線。

「頂點」是段之間的連接。頂點與平面上的（x，y）位置相關聯，但在同一位置可能有多個頂點，對於在該點處相交的輪廓中的每對分段，都有一個頂點。每個曲線終點（尖刺頂點）或螞蟻遇到的曲線曲線交點都有一個頂點。

輪廓（在此上下文中）不是幾何實體！不要把它看作是飛機上的簡單封閉的道路。螞蟻可能沿着一段，走到最後，並回到它來的方向 - 這被稱爲「刺激」，包括兩個輪廓段，一個用於任一方向。或者它可能沿着曲線段的一個方向，沿着其他曲線漫遊，並沿着該段的另一個方向返回。因此，即使你的曲線組中只有一行從A到B（假設你沒有無限長線），並且你的光線在P點擊了它，你仍然有輪廓V0（P ）-V1（A）-V2（P）-V3（B）-V0具有4段V0-V1，V1-V2，V2-V3，V3-V0。請注意，V0和V2是不同的頂點，都位於P.

現在測試您的點是否在輪廓中。

找到你的射線（任何射線源於你的測試點將與）輪廓的交點。我們只需要與輪廓交點的奇偶數（偶數或奇數）。如果奇偶校驗是奇數的，則該點由曲線限定，如果它甚至不是。

因爲雙重穿越的部分對平價沒有貢獻，我們可以忽略它們。這是因爲在雙線段上總是有偶數個交點，因爲它們在輪廓中是兩次。

示例：

考慮這個曲線集。我用的線，所以我不工作太辛苦：

案例1 - 點是無界。虛線箭頭表示輪廓對曲線段的使用。交叉口奇偶校驗的數量是偶數。

案例2 - 該點爲界。射線輪廓相交奇偶校驗是奇數。

下面是可能出現的錯誤：

1. 你不能找到各種數值原因的輪廓。例如，您可能會錯過交叉點，例如兩條曲線在曲線上幾乎相切。您可能會將其視爲單個交叉點，但是當您執行射線交叉點奇偶校驗測試時，您會看到單個交叉點，以便在奇偶校驗不應該時翻轉。

2. 您可能無法計算出足夠的衍生產品以作出正確的轉折決策。在解析幾何的情況下，情況決不應該如此。

3. 你的射線擊中輪廓的頂點（段之間的連接）。 （請注意，有可在單個（X，Y）點是多個頂點。每個這些必須被單獨處理。）

在這種情況下，必須決定是否的傳入和傳出段頂點位於頂點射線的同一側。如果他們在同一方面，平價不受影響。否則，奇偶校驗翻轉。如果其中一條曲線與頂點處的射線相切，則可能需要使用更高的導數來決定。

1. 線段與測試射線共線。這實際上是2的特例，但容易處理：忽略它。

有很多細節，但你應該能夠處理它們。確保使用空間樹來避免計算不必要的交點。

第二個問題的答案來自於從輪廓中刪除任何雙向遍歷的段。這可能會產生多個子輪廓。其中之一將包含你的觀點。