1????????? 算法背景
?????? 在電子海圖系統中，經常需要用到判斷一個點(可能是一個船位，或者其它點狀物標)是否在某個多邊形區域內(矩形或圓也可看作特殊的多邊形)，比如某個警戒區，作業區，禁航區，臺風影響區以及其它用戶關注的區域。一般點在多邊形的邊線上時也作為在多邊形內的一種特例。

2????????? 假設
2.1????????? 經度范圍
?????? 在各種電子海圖系統中，經度范圍的表示方式有多種，這里我們約定經度的取值范圍為-180~180。其中國際變更線既是180也是-180。

2.2????? 兩點間走小圓弧
?????? 由于地球是圓形的，如果只給出兩個點，那么它們之間可以形成兩條連線(可以有大圓弧和小圓弧兩條連線)。這里我們假設我們所需判斷的多邊形的任何兩條連線都是走小圓弧。這個假設一般情況下也是成立的，用戶不會需要繪制一個大小超過180度范圍的區域。

3????????? 算法特點
?????? 電子海圖的坐標系和一般的數學坐標系不同。數學坐標系在一個方向上始終保持遞增或者遞減，而電子海圖中，當穿過經度180度的國際變更線時，經度值會變回-180度。因此，對于區域跨國際變更線的情況要進行特殊處理。

4????????? 算法比較
?????? 對于點在多邊形內的判斷，在數學上有多種策略。常見的有面積法，角度法，射線法等；在開發工具中，還有CRgn對象的PtInRegion方法。由于面積法和角度法需要大量的計算，因此不予考慮。CRgn的PtInRegion雖然代碼簡單，但CRgn本身就是很消耗資源的一個對象，同時也受計算機開發工具的限制，也不在考慮之列。此處選擇射線法作為解決方案的基礎。

5????????? 線段法
?????? 線段法來源與數學方法中的射線法。

?????? 射線法的定義是從要判定的點向任意方向形成一條射線，計算該射線與多邊形所有邊的相交情況，如果相交的邊的數量是奇數，則該點在多邊形內；反之則在多邊形外。

?????? 結合電子海圖的特點，緯度方向呈單向遞增/遞減，并且緯度值不可能大于90度。因此產生一個新的方法—線段法(筆者的命名)，即不再是發出一條射線，而是從需要判定的點保持經度不變，向正北延伸直到90度緯線，形成一條線段，判定多邊形的各條邊與該線段的相交情況，以此判斷出點是否在多邊形內。

?????? 線段法中的線段命名為判定線段。

?

6????????? 判定過程
6.1????? 判定多邊形區域是否跨越國際變更線
?????? 由于跨越國際變更線的多邊形頂點坐標不是在遞增坐標系下，因此必須進行判定。如果確實跨越了國際變更線，則需要將所有經度值小于0的點加上360度，即可轉換為遞增序列。同時，如果需要判定的點的經度值小于0，也需要加上180度。

?????? 是否跨越國際變更線的判定方法如下：

?????? 逐條判斷多邊形的每條邊，如果相鄰兩點的經度值乘積小于0，并且兩者的絕對值之和大于180，則確認該多邊形跨越國際變更線。

?????? 因為相鄰兩點乘積小于0時，有兩種可能，或者跨越0度線，或者跨越180度線。如果跨越的是0度線，那么兩點的經度值的絕對值之和必然小于180。這里用到了我們兩點間走小圓弧的假設，只有在此條件下判定才能成立。

?

6.2????? 頂點過濾
?????? 如果需要判定的點就是多邊形的某個頂點，則直接認為點在多邊形內。判定點與頂點重合會影響后續的判斷邏輯。這里需要注意兩個點坐標判定相等的一個精度問題。

6.3????? 經緯度過濾
?????? 如果多邊形任意一條邊不滿足以下條件，則可不予處理：

1．邊的兩點的緯度值必須有一個在需要判定的點的緯度到90度之間(開區間)；

2．需要判定的點的經度值必須在兩邊的經度值之間(開區間)；

?????? 條件中都為開區間，以此過濾判定線段正好經過多邊形頂點的情況。這種情況下，經過一個點，等于與兩條邊相交，對最終判定沒有影響。

6.4????? 交點計算
?????? 經過以上幾個步驟后，還剩下以下圖示的情況，需要過濾邊ab。

?

???

?????? 圖中，邊ab和判定線段pp0滿足6.3條件。因此需要計算p0點在邊ab上的投影點才能確定兩線段是否相交。由于pp0與ab的交點的經度肯定就是p0點的經度，因此只需要計算交點的緯度值。如果緯度值大于p0，則交點在pp0上，確定該邊與pp0相交；如果緯度值等于p0，則表明p0就在ab上，直接認定p0點在區域內。

?????? 所有邊均判定完成后，計算與pp0相交的邊的數量，如果是奇數，則認定p0在多邊形內，否則不在。

?????? p0點在ab邊上的投影點計算：

?????? 假設a(x1,y1),b(x2,y2),p0在ab線上的投影p1(x0,y0)。那么現在未知值就是y0。根據簡單的數學公式，可得以下算式：（在前幾步驟中，已經排除了x1和x2相等的可能，并且確定p1點在線段ab上）

?????? (y1-y0)(x1-x0) = (y1-y2)/(x1-x2)

轉換為計算機公式就是：y0 = y1 – (y1-y2)*(x1-x0)/(x1-x2)

?????? 根據已知條件即可計算出y0。

?

7????????? 總結
?????? 本方法采用了純數學的算法。與具體開發語言和工具沒有關聯。可最大限度的進行共享。而且選用了計算量最小的數學公式，保證了判定的效率。當然，由于筆者能力有限，或許還有更為簡單的算法，或許本文中還有部分錯誤和遺漏之處，歡迎大家批評指正，互相學習。

?

附源代碼

view plaincopy to clipboardprint?
//判斷指定的坐標是否在水域范圍內??
BOOL CStressSeaArea::IsPosIn(DOUBLE_LONG_LAT dllPos)??
{??
??? int nSize = m_StressSeaAreaInfo.arLatLong.GetSize();??
??? if(nSize <= 2)??
??????? return FALSE;??
??? BOOL bCross180 = IsCrossLong180();??
??? //如果穿過180度經線，負經度值需要轉換為正經度值??
??? if(bCross180 && dllPos.dLongitude < 0)??
??? {??
??????? dllPos.dLongitude += 360;??
??? }??
??? int nCrossNum = 0;??
??? for(int i=0; i<nSize; i++)??
??? {??
??????? DOUBLE_LONG_LAT dllPos1 = m_StressSeaAreaInfo.arLatLong.GetAt(i);??
??????? DOUBLE_LONG_LAT dllPos2;??
??????? if(i!=nSize-1)//最后一點與第一點形成最后一條線段??
??????????? dllPos2 = m_StressSeaAreaInfo.arLatLong.GetAt(i+1);??
??????? else?
??????????? dllPos2 = m_StressSeaAreaInfo.arLatLong.GetAt(0);??
??????? if(bCross180)??
??????? {??
??????????? if(dllPos1.dLongitude < 0)??
??????????????? dllPos1.dLongitude += 360;??
??????????? if(dllPos2.dLongitude < 0)??
??????????????? dllPos2.dLongitude += 360;??
??????? }??
??????? //如果頂點就是dllPos，則認為點在水域內??
??????? if((fabs(dllPos1.dLatitude - dllPos.dLatitude) < 0.000001) &&???
??????????? (fabs(dllPos1.dLongitude - dllPos.dLongitude) < 0.000001))??
??????????? return TRUE;??
??????? if((fabs(dllPos2.dLatitude - dllPos.dLatitude) < 0.000001) &&???
??????????? (fabs(dllPos2.dLongitude - dllPos.dLongitude) < 0.000001))??
??????????? return TRUE;??
??????? //如果兩點中有一個點的緯度在90~dllPos.dLatitude間，則滿足緯度條件??
??????? if(((dllPos1.dLatitude < 90) && (dllPos1.dLatitude > dllPos.dLatitude)) ||??
??????????? ((dllPos2.dLatitude < 90) && (dllPos2.dLatitude > dllPos.dLatitude)))??
??????? {??
??????????? //繼續判斷經度是否滿足條件。如果dllPos.dLongitude在兩點的經度之間，則滿足條件??
??????????? if(((dllPos.dLongitude > dllPos1.dLongitude) && (dllPos.dLongitude < dllPos2.dLongitude)) ||??
??????????????? ((dllPos.dLongitude > dllPos2.dLongitude) && (dllPos.dLongitude < dllPos1.dLongitude)))??
??????????? {??
??????????????? //計算兩條線段的交點的緯度值??
??????????????? float fLat = dllPos1.dLatitude - (dllPos1.dLatitude-dllPos2.dLatitude)*(dllPos1.dLongitude-dllPos.dLongitude)/(dllPos1.dLongitude-dllPos2.dLongitude);??
??????????????? //如果緯度值就是dllPos.dLatitude，表明點在多邊形邊線上，認為在多邊形內??
??????????????? if(fabs(fLat - dllPos.dLatitude) < 0.00001)??
??????????????????? return TRUE;??
??????????????? //如果緯度值大于dllPos.dLatitude，表明兩條線段是相交線段，計數加1??
??????????????? if(fLat > dllPos.dLatitude)??
??????????????????? nCrossNum++;??
??????????? }??
??????? }??
??? }??
??? if(nCrossNum %2 == 1)??
??????? return TRUE;??
??? return FALSE;??
}??
?
?
BOOL CStressSeaArea::IsCrossLong180()??
{??
??? int nSize = m_StressSeaAreaInfo.arLatLong.GetSize();??
??? if(nSize <= 2)??
??????? return FALSE;??
??? //判斷水域是否跨180經線??
??? double dLong1 = 0;??
??? int i=0;??
??? for(i=0; i<=nSize; i++)??
??? {??
??????? DOUBLE_LONG_LAT pos;??
??????? if(i==nSize)??
??????????? pos = m_StressSeaAreaInfo.arLatLong.GetAt(0);??
??????? else?
??????????? pos = m_StressSeaAreaInfo.arLatLong.GetAt(i);??
??????? if(i!=0)??
??????? {??
??????????? if(pos.dLongitude * dLong1 < 0)//如果相鄰兩點的經度值符號相反，則表明肯定跨0度或者180度經線??
??????????? {??
??????????????? //如果絕對值之和大于180，那么就是跨180度經線(這里有個假設：兩點間經度差小于180)??
??????????????? if(fabs(dLong1) + fabs(pos.dLongitude) >= 180)??
??????????????? {??
??????????????????? return TRUE;??
??????????????? }??
??????????? }??
??????? }??
??????? dLong1 = pos.dLongitude;??
??? }??
??? return FALSE;??
}?

?

本文來自CSDN博客，轉載請標明出處：http://blog.csdn.net/happyparrot/archive/2009/07/01/4311919.aspx

轉載于:https://blog.51cto.com/no001/371342

總結

以上是生活随笔為你收集整理的电子海图中点在多边形内的判定的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。