判斷點與指定多邊形區(qū)域的關(guān)系的改進(jìn)算法

楊雅軍 段明義

摘要：介紹了判斷點與多邊形關(guān)系的多種方法，詳細(xì)給出射線法，并對該方法進(jìn)行優(yōu)化，并給出了算法。在實驗過程中該算法排除了一些點的判斷，只需執(zhí)行少量的射線法函數(shù)，實驗結(jié)果表明，該算法簡便、可靠、執(zhí)行速度快。

關(guān)鍵詞：點；多變形；關(guān)系；射線法；改進(jìn)算法

中圖分類號：TP391 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2014）22-5362-03

1 概述

在計算機(jī)圖形學(xué)、計算機(jī)輔助設(shè)計、衛(wèi)星定位系統(tǒng)、地理信息系統(tǒng)等進(jìn)行圖像處理時，經(jīng)常需要判斷一個點P與多邊形S的關(guān)系，判斷點P是否位于多邊形區(qū)域內(nèi)。解決該問題的方法有很多，有周角法、標(biāo)號法、符號法、弧長法和射線法等[1-4]，周角法又稱轉(zhuǎn)角法，是通過把點P與多邊形S上任一點Q相連，當(dāng)點Q沿多邊形各邊繞點P轉(zhuǎn)一圈后，求出連線PQ所劃過的累加夾角代數(shù)和a，若a=2p，則點P在多邊形內(nèi)，若a=p，則點P在多邊形邊界上，若a=0，則點P在多邊形外部，否則點P是多邊形的頂點；標(biāo)號法是通過以點P為原點，劃分四個象限，判斷多邊形各邊與各個象限的關(guān)系，從而確定點與多邊形的位置關(guān)系；符號法是通過擬定多邊形的解析方程f（x，y）=0，把點P的坐標(biāo)數(shù)據(jù)代入方程，由f（x，y）的符號判斷點的位置[5]；弧長法要求多邊形是有向多邊形，一般規(guī)定沿多邊形的正向，以被測點為圓心作單位圓，將全部有向邊向單位圓作徑向投影，并計算其中單位圓上弧長的代數(shù)和，若代數(shù)和為0，則點在多邊形外部，若代數(shù)和為2π則點在多邊形內(nèi)部，若代數(shù)和為π，則點在多邊形上[6]。這些算法中，大多算法復(fù)雜，要處理的特殊情況也很多，計算量大，影響了檢測速度。射線法是從點P向某一個方向（如x軸正向）引射線，計算和多邊形S交點的個數(shù)，如果個數(shù)是偶數(shù)或者0則點在多邊形外，如果是奇數(shù)，則在多邊形內(nèi)[7]。在判斷點與多邊形關(guān)系的算法中，用的最多也比較好用的是射線法。

2 算法描述

射線法判斷點P與多邊形的關(guān)系的基本思想是從P向X軸正向引射線，計算P和多邊形各邊交點的個數(shù)和，如果偶數(shù)或者0則點P在多邊形外，如果是奇數(shù)，則點P在多邊形內(nèi)，如下圖1所示：

4 結(jié)論

本文描述了點與多邊形關(guān)系的判斷方法，并詳細(xì)給出了射線法求解，針對多種特殊情況分析出改進(jìn)的射線法，使算法更簡便，提高了運算效率，為更復(fù)雜的多邊形關(guān)系的求解打下了良好的基礎(chǔ)。

參考文獻(xiàn)：

[1] 唐澤圣，周嘉玉，李新友.計算機(jī)圖形學(xué)[M].北京：清華大學(xué)出版社，2002.

[2] 周培德.計算幾何—算法設(shè)計與分析[M].北京：清華大學(xué)出版社，2008.

[3] Donald Hearn，Pauline Baker M. 計算機(jī)圖形學(xué)[M].蔡士杰，吳春镕，孫正興，譯.北京：電子工業(yè)出版社，2002.

[4] 燕昊.一種判斷點在多邊形內(nèi)的新方法[J].河南科學(xué)，2010，28（11）：1469-1472.

[5] 駱雯，孫延明，陳振威，陳錦昌.判斷點與封閉多邊形相對關(guān)系的改進(jìn)算法[J].機(jī)械，1999，26（3）：25-27.

[6] 孫家廣，胡事民.計算機(jī)圖形學(xué)基礎(chǔ)教程[M].北京：清華大學(xué)出版社，2005.

[7] 陳瑞卿，周健，虞烈.一種判斷點與多邊形關(guān)系的快速算法[J].西安交通大學(xué)學(xué)報，2007，41（1）：59-63.

[8] 苗春葆.點與多邊形關(guān)系的射線法[J].電腦編程技巧與維護(hù)，2008（3）：56-58.