[發明專利]一種夾角和法結合叉乘法判定點與任意多邊形位置關系方法

在審

• 申請號: 201710144698.8
• 申請日: 2017-03-10
• 公開（公告）號: CN106991698A
• 公開（公告）日: 2017-07-28
• 發明（設計）人: 柳珍
• 申請（專利權）人: 深圳市龍騰飛通訊裝備技術有限公司
• 主分類號: G06T7/70
• 分類號: G06T7/70
• 代理公司: 深圳市深聯知識產權代理事務所(普通合伙)44357
• 代理人: 徐炫

技術領域

本發明涉及一種判定點與任意多邊形位置關系方法，特別涉及一種夾角和法結合叉乘法判定點與任意多邊形位置關系方法，屬于圖形處理技術領域。

背景技術

地理信息系統中，點與任意多邊形區域的拓撲關系可以分為三種：點在區域外、點在區域邊界上和點在區域內。

判定點與多邊形位置關系，目前主要有叉乘判定法：一個凸多邊形，其每一個邊都將整個2D屏幕劃分成為左右兩邊，連接每一邊的第一個端點和要測試的點得到一個矢量v，將兩個2維矢量擴展成3維的，然后將該邊與v叉乘，判斷結果3維矢量中Z分量的符號是否發生變化，進而推導出點是否處于凸多邊形內外。

夾角和判定法：令P＝{p1，p2，…，pn，p1}是一個頂點為pi(xi，yi)，i＝1，2，…，n的封閉多邊形，pt是一個判定點，PtPi為連接pt和pi的諸向量，αi表示向量PtPi到PtPi+1的夾角，若∑αi＝0，Pt在P的外面；若∑αi＝2π，Pt在P的里面。

射線法：從待判斷點引出一條射線，射線與多邊形相交，如果交點為偶數，則點不在多邊形內，如果交點為奇數，則點在多邊形內。

叉乘判定法原理簡單、易于程序實現，但只適用于凸多邊形；夾角和判定法也易于程序實現，且適用于任意多邊形，但臨界情況不易解決；射線法易于進行結合改進，但很難處理一些臨界情況，穩定性差。

發明內容

本發明要解決的技術問題是克服現有技術的缺陷，提供一種夾角和法結合叉乘法判定點與任意多邊形位置關系方法。

為了解決上述技術問題，本發明提供了如下的技術方案：

本發明提供了一種夾角和法結合叉乘法判定點與任意多邊形位置關系方法，設P＝{p1，p2，…，pn，p1}是一個頂點為pi(xi，yi)，i＝1，2，…，n的任意多邊形，Pt是一個判定點。PtPi為連接pt和pi的諸向量，αi表示向量PtPi到PtPi+1的夾角；計算向量PtPi的方位角βi，PtPi+1的方位角βi+1；夾角αi由方位角之差來計算：αi＝|βi+1-βi|；因αi(-180°＜αi≤180。)，當αi＞180°時，αi＝360°-αi；通過Pt與PiPi+1叉乘判斷夾角方向，大于零時夾角αi方向為正，不大于零時夾角αi方向為負；計算夾角和，當夾角和等于360°時，點在多邊形內；夾角和等于0°時，點在多邊形外。

作為本發明的優選技術方案，所述第一個頂點只有一個方位角，得不到夾角值。

作為本發明的優選技術方案，所述第一個頂點也做為最后的頂點從而封閉多邊形。

本發明所達到的有益效果是：本發明通過增加叉乘法來判斷夾角的方向，保證了判別點與任意多邊形位置關系臨界情況的判定，且采用方位角差計算夾角，計算量較小。

附圖說明

附圖用來提供對本發明的進一步理解，并且構成說明書的一部分，與本發明的實施例一起用于解釋本發明，并不構成對本發明的限制。在附圖中：

圖1是本發明的判定流程圖；

具體實施方式

以下結合附圖對本發明的優選實施例進行說明，應當理解，此處所描述的優選實施例僅用于說明和解釋本發明，并不用于限定本發明。

實施例1

如圖1所示，本發明提供了一種夾角和法結合叉乘法判定點與任意多邊形位置關系方法，設P＝{p1，p2，…，pn，p1}是一個頂點為pi(xi，yi)，i＝1，2，…，n的任意多邊形，Pt是一個判定點。PtPi為連接pt和pi的諸向量，αi表示向量PtPi到PtPi+1的夾角；計算向量PtPi的方位角βi，PtPi+1的方位角βi+1；夾角αi由方位角之差來計算：αi＝|βi+1-βi|；因αi(-180°＜αi≤180°)，當αi＞180°時，αi＝360°-αi；通過Pt與PiPi+1叉乘判斷夾角方向，大于零時夾角αi方向為正，不大于零時夾角αi方向為負；計算夾角和，當夾角和等于360°時，點在多邊形內；夾角和等于0°時，點在多邊形外。