點與簡單多邊形位置關系判別新算法

陳金林，劉謝進，李寧

(淮南師范學院 數(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ù)，在多邊形中，有兩個角共有這條邊。……