陳金林,劉謝進,李寧
(淮南師范學院 數(shù)學與計算科學系,安徽 淮南 232038)
在計算幾何、計算機圖形學等領域常用簡單多邊形來描述幾何形體,很多情況下運算處理的對象是簡單平面多邊形[1]。判別多邊形是否為簡單多邊形以及簡單多邊形內(nèi)外點的判別算法就很重要,因為這些算法是許多算法的基礎[2]。迄今為止,對判斷點與多邊形位置關系算法的研究比較多。經(jīng)典的算法有叉積判斷法[3],射線法[4,5],有向三角形面積之和的符號法[6],有向回路法和網(wǎng)格法[7]等。其中叉積法只適用于凸多邊形,并且對所有邊都需叉積運算,運算量大。文獻[8]所涉及到有向回路法本質(zhì)上是非零環(huán)繞數(shù)規(guī)則法,但它只適用于凸多邊形,空間復雜度較大,本質(zhì)上是一種以空間換取時間的算法。射線法通常需要求交點,雖然在文獻[8]對射線法進行了改進,但也只是減少求交點數(shù)量。在文獻[9]中所提及的射線法不需要求交點,但對關聯(lián)集合求解判別增加了空間復雜度。
點與相關邊的判別法[10-14]是掃描與點關聯(lián)性(密切邊[11]、單調(diào)性[12])最大的邊,在多邊形中這樣的邊可能不唯一,判別測試點與此相關邊的位置關系,確定點與多邊形的位置關系。此類算法計算速度快,穩(wěn)定性高,但是查找到的相關的邊通常不唯一。本文提出了基于點與角的最短距離的一種新的方法,掃描與點距離最小時關聯(lián)的邊,這樣的邊在多邊形中可能不止一個,但掃描過程結束后只保留一個作為判斷依據(jù),在多邊形中,有兩個角共有這條邊。……