劉文峰，徐雪仁，巫震宇，段衛(wèi)國(guó)，趙鋒銳

(北京遙感信息研究所，北京 100192)

一種球面坐標(biāo)下點(diǎn)面位置關(guān)系檢測(cè)算法

劉文峰，徐雪仁，巫震宇，段衛(wèi)國(guó)，趙鋒銳

(北京遙感信息研究所，北京 100192)

摘要點(diǎn)與多邊形的位置關(guān)系是計(jì)算幾何學(xué)領(lǐng)域的一個(gè)重要問題。在航空航天、地理遙感等領(lǐng)域需要高效精確的球面坐標(biāo)系下的點(diǎn)與多邊形位置關(guān)系檢測(cè)算法，傳統(tǒng)的平面逼近方法容易引入較大的誤差。將平面內(nèi)的射線法發(fā)展到球面坐標(biāo)系下，采用3級(jí)級(jí)聯(lián)處理的方法實(shí)現(xiàn)精確的位置關(guān)系檢測(cè)。實(shí)驗(yàn)表明，本算法的正確檢測(cè)率優(yōu)于傳統(tǒng)的平面逼近算法。

關(guān)鍵詞球面坐標(biāo)；多邊形；位置關(guān)系；坐標(biāo)變換

A Position Relationship Detect Algorithm for Points and Polygons in Spherical Coordinate System

LIU Wen-feng,XU Xue-ren,WU Zhen-yu,DUAN Wei-guo,ZHAO Feng-rui

(BeijingInstituteofRemoteSensingInformation,Beijing100192,China)

AbstractThe position relationship between points and polygons is an important problem in the field of computational geometry.The effective and precise algorithm for detecting positions between points and polygons is widely used in the fields of aerospace and geographical remote sensing.Significant bias is easily introduced in traditional planar approximation algorithm.This paper proposes an algorithm which evolves the planar ray method to the spherical coordinate system,and adopts a three-level cascade process to achieve precise position detection.The experiment results show that this algorithm has the correct detection rate better than that of traditional planar approximation algorithm.

Key wordsspherical coordinate system;polygon;position relationship;coordinate transformation

0引言

點(diǎn)與多邊形的位置關(guān)系是計(jì)算機(jī)圖形學(xué)、計(jì)算幾何學(xué)、地理信息系統(tǒng)、CAD/CAM自動(dòng)化系統(tǒng)等研究領(lǐng)域的一個(gè)重要問題[1]。目前已經(jīng)有大量的成熟算法，如環(huán)繞法、角度相加法及射線法等[2,3]。但這些算法討論的范疇僅限于平面坐標(biāo)系。而在航空航天、地理遙感等研究領(lǐng)域，經(jīng)常需要在球面坐標(biāo)系下進(jìn)行精確的數(shù)據(jù)處理，因此需要研究在球面坐標(biāo)系下的點(diǎn)與多邊形位置關(guān)系檢測(cè)算法。

傳統(tǒng)的研究方法是將球面逼近為平面來進(jìn)行研究，在處理大量的地理數(shù)據(jù)和遙感數(shù)據(jù)時(shí)，不僅耗時(shí)耗資源，而且容易引入較大的定位誤差[4,5]。本文借鑒平面坐標(biāo)系下的射線法，將其發(fā)展至球面坐標(biāo)系下，并針對(duì)球面坐標(biāo)下的坐標(biāo)變換、求交問題、特殊情況處理進(jìn)行詳細(xì)設(shè)計(jì)，從而精確判斷點(diǎn)與球面多邊形的位置關(guān)系。

1算法原理

1.1　基本概念

在球面坐標(biāo)系下，多邊形是由一系列大圓弧組成的封閉圖形。球面上的任何區(qū)域和形狀都可以用球面多邊形來進(jìn)行逼近。通常而言，連接球面上2點(diǎn)P和Q有2條大圓弧，在研究中通常只考慮較短的那條圓弧[6,7]。

由n條邊組成的球面多邊形可以由其n個(gè)頂點(diǎn)完全確定，通常表示為R(V1,V2,…,Vn),每個(gè)頂點(diǎn)Vi的位置由其經(jīng)緯度來確定，表示為Vi(λi,φi)。用于檢測(cè)點(diǎn)與多邊形位置關(guān)系的射線法原理可以描述為：已知一個(gè)球面多邊形S和多邊形之外的一個(gè)點(diǎn)X，對(duì)于任何一點(diǎn)P，如果連接X和P的大圓弧XP穿過多邊形S的邊界的次數(shù)為偶數(shù)的話，那么P在多邊形外部。如果次數(shù)為奇數(shù)，那么P在多邊形內(nèi)部，如圖1所示。因此，點(diǎn)與多邊形位置關(guān)系的檢測(cè)問題就轉(zhuǎn)化為圓弧XP與多邊形各邊的求交問題。

圖1　射線法原理

1.2　球面求交問題

為了判斷圓弧XP和多邊形的邊AB是否相交，首先判斷相交的必要條件，即以X為基點(diǎn)的圓弧XP的方位角是否位于圓弧XA和XB之間，如圖2所示。必要條件的檢測(cè)可以通過球面坐標(biāo)變換來實(shí)現(xiàn)，將X點(diǎn)變換為新球面坐標(biāo)系(λ′,φ′)的北極點(diǎn)，并使新坐標(biāo)系的零經(jīng)線通過原坐標(biāo)系的北極點(diǎn)。那么圓弧XA,XB,XP的方位角就轉(zhuǎn)化為新坐標(biāo)系下點(diǎn)A,B,P的經(jīng)度，由下式給出[8,9]：

滿足必要條件的點(diǎn)P不一定能保證XP和AB相交，如圖中的點(diǎn)P2。因此還要進(jìn)行進(jìn)一步的充分性檢測(cè)。為了保證圓弧XP和AB相交，那么X,P兩點(diǎn)必須要位于圓弧AB兩側(cè)。同樣的，可以用球面坐標(biāo)變換來實(shí)現(xiàn)，如圖3所示。在新的球面坐標(biāo)系(λ″,φ″)中，點(diǎn)A為北極點(diǎn)。如果點(diǎn)X和P的經(jīng)度值位于點(diǎn)B的經(jīng)度值兩側(cè)，那么圓弧XP必然與圓弧AB相交。特別的，如果β=0，那么點(diǎn)P正好位于圓弧AB上。

圖2　必要性條件

圖3　充分性條件檢測(cè)

1.3　特殊情況的處理

在檢測(cè)算法的運(yùn)行過程中，有幾個(gè)特殊情況需要進(jìn)行仔細(xì)處理以保證算法的順利運(yùn)行。首先是點(diǎn)X和點(diǎn)P正好為對(duì)極點(diǎn)，即連接點(diǎn)X和點(diǎn)P的直線為球面坐標(biāo)系的直徑。此時(shí)，連接XP的大圓弧不是唯一的，而有無數(shù)條，算法無法進(jìn)行。對(duì)于這種情況，選擇球面多邊形S內(nèi)部的另外一個(gè)點(diǎn)X2，重復(fù)進(jìn)行上述判斷即可完成位置關(guān)系的檢測(cè)。

圓弧XP和圓弧AB同處于一個(gè)球面大圓上也是一種特殊情況，此時(shí)圓弧XP和圓弧AB是否相交很難定義。這種情況可以通過對(duì)點(diǎn)X的位置進(jìn)行限定來避免，即在算法開始選擇點(diǎn)X時(shí)禁止其處于多邊形的任何一邊的大圓上。此外，也可以通過對(duì)坐標(biāo)系(λ′,φ′)中點(diǎn)A,B和P的緯度進(jìn)行判斷來排除。

1.4　算法的具體實(shí)現(xiàn)

當(dāng)實(shí)際的應(yīng)用中，算法的處理流程如下：

① 讀取待處理的球面多邊形R(V1,V2,…,Vn)和點(diǎn)P的坐標(biāo)數(shù)據(jù)，選取另一端點(diǎn)X；

② 對(duì)于球面多邊形R的每條邊AB(ViVi+1)，進(jìn)行圓弧XP和AB相交的必要性條件檢測(cè)；

③ 對(duì)于通過必要性檢測(cè)的圓弧AB，進(jìn)行圓弧相交的充分性條件檢測(cè)；

④ 進(jìn)行特殊情況的處理，得到圓弧XP與球面多邊形R各邊的相交次數(shù)，從而判斷點(diǎn)P與球面多邊形的位置。

在實(shí)際應(yīng)用中，通常可以選擇北極點(diǎn)(或南極點(diǎn))作為上述算法中的點(diǎn)X，這樣可以減少算法的運(yùn)算量。在運(yùn)算前，首先以北極點(diǎn)P0作為點(diǎn)X，判斷其是否在待處理的球面多邊形區(qū)域中。如果不在，那么按照上述算法進(jìn)行處理即可；如果在，將算法檢測(cè)的結(jié)果取反。

判斷北極點(diǎn)P0是否在球面多邊形區(qū)域中時(shí)，可以將球面多邊形和北極點(diǎn)都投影至赤道平面，判斷投影區(qū)域是否包含北極點(diǎn)。如果不包含，那么北極點(diǎn)就不在球面多邊形內(nèi)部。如果包含，繼續(xù)區(qū)球面多邊形在北半球的子區(qū)域，進(jìn)一步判斷新區(qū)域的投影區(qū)域是否包含北極點(diǎn)。如果是，那么北極點(diǎn)就在原球面多邊形區(qū)域中，算法最后的檢測(cè)結(jié)果要取反。

對(duì)于上述的第3種特殊情況，如圖4所示。如果按照左閉右開的邊長(zhǎng)區(qū)間[Vi,Vi+1)判斷，圓弧XP與多邊形各邊的相交次數(shù)會(huì)增加2，而實(shí)際上只能按照增加1來處理，最終檢測(cè)結(jié)果才不會(huì)出現(xiàn)誤判。判斷的方法如下：

如果λP>max(λi,λi+1)，不計(jì)入相交次數(shù);如果λP

圖4　圓弧重合的特殊情況

2實(shí)驗(yàn)驗(yàn)證

為了驗(yàn)證本文算法的性能，隨機(jī)生成100個(gè)點(diǎn)組成球面多邊形。在其各邊附近隨機(jī)生成10 000個(gè)待檢測(cè)點(diǎn)，利用本文的算法檢測(cè)和球面多邊形的位置關(guān)系。同時(shí)利用將球面近似為平面的檢測(cè)方法進(jìn)行對(duì)比試驗(yàn)。檢測(cè)結(jié)果的正確性可以用立體幾何檢測(cè)法來驗(yàn)證。實(shí)驗(yàn)得到的檢測(cè)性能如圖5所示。其中，各點(diǎn)的位置經(jīng)度精確到0.01°。

圖5　算法性能對(duì)比

南大西洋輻射異常區(qū)(SAA)是指位于南美洲東邊的南大西洋地磁異常區(qū)域，該區(qū)域高能帶電粒子的輻射通量非常大，很多高能探測(cè)設(shè)備在經(jīng)過該區(qū)域時(shí)需要關(guān)閉或者停止工作[7]。因此，精確檢測(cè)衛(wèi)星進(jìn)出SAA區(qū)域的時(shí)機(jī)對(duì)于衛(wèi)星有效載荷的正確運(yùn)行具有重要意義。本文選取硬X射線調(diào)制望遠(yuǎn)鏡(HXMT)為檢測(cè)對(duì)象，利用傳統(tǒng)的平面內(nèi)算法和本文算法進(jìn)行比較。當(dāng)衛(wèi)星的位置采用間隔為40 s時(shí)，2種算法的檢測(cè)結(jié)果基本類似。而當(dāng)采用間隔為1 s時(shí)，2種算法的檢測(cè)性能差別很大，如圖6所示。圖中的實(shí)線表示SAA區(qū)域的邊界，點(diǎn)為衛(wèi)星軌跡，”o”表示區(qū)域內(nèi)部，”+”表示區(qū)域外部。很明顯，本文算法的檢測(cè)結(jié)果非常精確。

圖6　SAA區(qū)域檢測(cè)

3結(jié)束語

將平面內(nèi)點(diǎn)和多邊形位置關(guān)系的射線檢測(cè)算法發(fā)展到球面坐標(biāo)系下。根據(jù)球面幾何的相關(guān)理論對(duì)算法進(jìn)行了發(fā)展，算法包括必要性條件檢測(cè)、充分性條件檢測(cè)和特殊情況處理3個(gè)主要環(huán)節(jié)，通過3個(gè)環(huán)節(jié)的順序檢測(cè)得到球面坐標(biāo)系下點(diǎn)和多邊形的位置關(guān)系結(jié)果。基于Matlab軟件設(shè)計(jì)了驗(yàn)證實(shí)驗(yàn)，結(jié)果表明，本文算法對(duì)于大量邊界點(diǎn)的檢測(cè)能達(dá)到95%的正確檢測(cè)率，遠(yuǎn)高于平面逼近算法。同時(shí)通過南大西洋輻射異常區(qū)的實(shí)驗(yàn)充分顯示了本算法的優(yōu)越性。本文的研究結(jié)果可以廣泛應(yīng)用于遙感、航空航天和計(jì)算機(jī)圖形學(xué)等領(lǐng)域。

參考文獻(xiàn)

[1]孫家廣.計(jì)算機(jī)圖形學(xué)[M].北京：清華大學(xué)出版社,1998.

[2]ASHOURIAN M，ENTESHARI R，JEON J.Digital Watermarking of Three-dimensional Polygonal Models in the Spherical Coordinate System [C]∥Computer Graphics International,2004:590-593.

[3]HORMANN K,AGATHOS A.The Point in Polygon Problem for Arbitrary Polygons[J].Computational Geometry:Theory and Applications-COMGEO,2001,20(3):131-144.

[4]OHBUCHI R，MASUDA H，AONO M.Watermarking Three-dimensional Polygonal Models Through Geometric and Topological Modifications[J].Selected Areas in Communications,IEEE Journal on,1998(5):909-969.

[5]SUNDARESWARA R， SCHRATER P.Extensible Point Location Algorithm[C]∥Geometric Modeling and Graphics,2003.Proceedings.2003 International Conference on,2003:85-89.

[6]鄭順義,鄧德彥.基于三角網(wǎng)無縫拼接的三維重建[J].武漢大學(xué)學(xué)報(bào)(信息科學(xué)版),2009(1):32-36.

[7]黃躍,陳黎,盧宇.點(diǎn)在球面多邊形內(nèi)外的判定方法及應(yīng)用[J].天文研究與技術(shù),2011(4):31-33.

[8]顧祥龍,王元?dú)J,鄭海昕,等.基于MATLAB并行處理的前向定時(shí)同步方法研究[J].無線電通信技術(shù),2013,39(3):36-38,42.

[9]SHINAGAWA Y，KAWAMICHI R， KUNII T L，et al.Developing Surfaces[C]∥Shape Modeling International,2002.Proceedings,2002:253-260.

[10]李源泉,申建平.多目標(biāo)自動(dòng)運(yùn)行系統(tǒng)設(shè)計(jì)[J].無線電工程,2012,42(6):35-38.

[11]ZHANG Wen-li.Real-time Tree Model Reconstructing for Fruit Harvesting Robot System[J].2008 9th International Conference on Computer-Aided Industrial Design and Conceptual Design,2008(11):580-584.

[12]陳旸,趙祖松,黃巍.同時(shí)數(shù)字多波束技術(shù)實(shí)現(xiàn)雷達(dá)三坐標(biāo)搜索[J].無線電工程,2013,43(9):45-47,64.

劉文峰男，(1986—)，工程師/博士。主要研究方向：衛(wèi)星任務(wù)控制技術(shù)。

徐雪仁男，(1965—)，研究員，博士。主要研究方向：衛(wèi)星任務(wù)控制技術(shù)。

作者簡(jiǎn)介

收稿日期：2015-05-12

中圖分類號(hào)TP391.41

文獻(xiàn)標(biāo)識(shí)碼A

文章編號(hào)1003-3106(2015)08-0047-04

doi:10.3969/j.issn.1003-3106.2015.08.13

引用格式：劉文峰，徐雪仁，巫震宇，等.一種球面坐標(biāo)下點(diǎn)面位置關(guān)系檢測(cè)算法[J].無線電工程，2015，45(8)：47-50.