最有效的方法，如果一個點或一個凸多邊形四

Question

我試圖找出最有效的/快速的方法來添加大量凸四邊形（四個給定的X，Y點）成數組/列表，然後檢查這些四邊形是否位於這些四邊形內或邊界上。

我最初嘗試使用光線投射，但認爲這是一個有點矯枉過正，因爲我知道我的所有多邊形將是四邊形，而且他們也都凸。

目前，我每次分裂成四共享的邊緣，然後檢查是否點上或在每個使用各自的領域這兩個三角形的兩個三角形。

例如 三角形ABC和測試點P. if（areaPAB + areaPAC + areaPBC == areaABC）{return true; }

這似乎是它可以運行有點慢，因爲我需要計算的4個不同的三角形區域運行檢查，如果四的第一個三角形返回false，我必須得到4個區域。 （我有一個位在檢查的ε來彌補浮點錯誤）

我希望有可能涉及對一個四點的單次檢查，而不是分裂它的一個更快的方法分成兩個三角形。

我已嘗試通過將多邊形的成陣列，以減少檢查次數[，]。添加多邊形時，它會檢查最小和最大x值和y值，然後使用這些值，將相同的多邊形放入適當的陣列位置。當根據可用多邊形檢查一個點時，它將從列表數組中檢索適當的列表。

我一直在尋找類似的問題，我想我現在使用的可能是找出一個點是否在三角形中的最快方法，但我希望有一個更好的方法來測試一個總是凸出的四邊形。我查過的每個多邊形測試似乎都是針對具有多邊或不規則形狀的多邊形進行測試。

感謝您百忙之中閱讀到什麼是prolly一個簡單的問題，我的長篇大論問題的時間。

Answer 1

我相信，最快的方法是：

1：通過跨產品的標誌找到所有向量對（DirectedEdge-CheckedPoint）相互對齊。如果所有四個標誌是一樣的，然後點在內部

增加：每邊

EV[i] = V[i+1] - V[i], where V[] - vertices in order 
PV[i] = P - V[i] 
Cross[i] = CrossProduct(EV[i], PV[i]) = EV[i].X * PV[i].Y - EV[i].Y * PV[i].X 

十字[I]值是正的，如果P點位於左半面相對至第i邊緣（V [i] - V [i + 1]），否則爲負。如果所有Cross []值均爲正，則點p在四邊形內，頂點按逆時針順序排列。如果所有Cross []值都是負值，則點p在四邊形內，頂點按順時針順序排列。如果數值有不同的符號，則點位於四邊形之外。

如果四元組對於許多點查詢是相同的，則dmuir建議預先計算每條邊的均勻線方程。均勻線方程是a * x + b * y + c = 0。（a，b）是邊緣的法向量。該等式具有重要性質：表達符號 （a * P.x + b * Y + c）確定半平面，其中點P位於（與交叉產品相同）

2：將四元組拆分爲2個三角形，並對每個三角形使用向量方法：使用基向量表達CheckedPoint向量。

P = a*V1+b*V2 

點是內部時的a，b> = 0且其總和< = 1

兩種方法都需要約10-15加法，6-10乘法和2-7比較（我不考慮浮點誤差補償）

Answer 2

如果你可以用每個四邊形存儲每個邊的方程，那麼你可以在MBo的答案上節省一點時間。

例如，如果對於四邊形的每個邊都有一個內向指向法向量N，並且常量d（對於邊上的一個頂點p是Np），則點x在四邊形中，如果和只有在Nx> = d的情況下。所以這就是2次乘法，每個邊的一個加法和一個比較，並且每個點需要執行多達4個測試。此技術適用於任何凸多邊形。