找出段是否完全位於多邊形內

Question

如何找出從P的邊界上的點A開始到P的邊界上的點B處的段是否完全包含在P的內部？

編輯：假設在這種情況下，沒有必要檢查該段與多邊形邊界上其他段的交點，因爲稍後會進行。

這可以在恆定的時間內完成嗎？

Answer 1

根據編輯過的描述，假設多邊形很簡單，它以逆時針排序的順序表示爲段列表，查詢段的內部不與多邊形的邊界相交，並且對於查詢段的任一端點，我們知道哪個多邊形段或多個段包含該端點。

如果端點是多邊形頂點，則有兩種可能的情況。通過比較相對於頂點的角度和2D行列式測試，可以在不變的時間區分這些問題。

Case 1: segment not in polygon 

     \ query segment 
     \ 
*<--------*<--------* 
    polygon 
    interior 


Case 2: segment in polygon 

*<--------*<--------* 
    polygon \ 
    interior \ query segment 

如果端點位於多邊形段的內部，然後有一個類似的測試（假裝有一個頂點那裏）。

以下是角度測試的詳細信息。翻譯所有東西，使多邊形頂點在(0,0)。然後我們有

(e,f)  (0,0)  (c,d) 
    *<--------*<--------* 
    polygon \ 
    interior \ query segment 
       * 
      (a,b) 

旋轉（和規模，沒關係）一切，以便查詢段位於x軸。這是通過矩陣

[ a b] 
[-b a] 

相乘以獲得新的圖

 * (ac+bd,ad-bc) = (p,q) 
    /
    /
    |_  query 
    *-----------* (a^2+b^2,0) 
/
/
|_ 
* (ae+bf,af-be) = (r,s). 

根據我們的假設退化，(p,q) != (0,0)完成。現在，如果q>0 || (q==0 && p>0)處於(p,q)處於上半平面。否則，它位於下半平面。同樣爲(r,s)。

如果(p,q)位於上半平面且(r,s)位於較低位置，則查詢段在裏面。如果反之亦然，那麼它就在外面。否則，這些點位於同一個半平面內。行列式測試是ps-qr > 0（內部）還是ps-qr < 0（外部）。由於多邊形很簡單，因此不能相同。

也許有人比我更有知識可以減少這種測試從四分之一的程度。

Answer 2

如果我正確理解你的問題，你嘗試以下兩種情況之間進行區分：

• AB完全多邊形
• 除了端點內，AB是完全的多邊形之外

我們已經排除了AB部分位於多邊形內部的情況，因爲您已經測試了AB是否與各邊相交。

在我看來的話，那你的問題就相當於問AB的中點是否包含在多邊形內。維基百科有一篇不錯的文章描述如何確定這個：http://en.wikipedia.org/wiki/Point_in_polygon。如果您希望事物在數值上穩定，我會建議繞組編號方法。