兩種區(qū)域內(nèi)外測試算法的研究

摘要:二維圖形的光柵化(區(qū)域)填充是計算機(jī)圖形學(xué)中一個重要的研究課題，在該學(xué)科中，我們把區(qū)域表示成點(diǎn)陣形式的填充圖形。因此，判斷某點(diǎn)是否是多邊形內(nèi)點(diǎn)的算法很重要。該文詳細(xì)介紹兩種方法，奇-偶規(guī)則和非零環(huán)繞數(shù)規(guī)則，并對兩種方法的實際應(yīng)用做了一些比較。

關(guān)鍵詞:區(qū)域填充;奇-偶規(guī)則;非零環(huán)繞數(shù)規(guī)則

中圖分類號:TP311文獻(xiàn)標(biāo)識碼:A文章編號:1009-3044(2010)21-6070-02

Analysis of the two Test Algorithms about Inside or Outside the Region

GUAN Xu

(Faculty of Mathematics Computer Science， Hubei University， Wuhan 430062， China)

Abstract: Two-dimensional graphics rasterization (regional) filled is an important research topic in computer graphics. Determine whether a point is inside polygon point algorithm is very important. In this paper， here are two ways mainly detailed， Odd-even Rule and Nonzero Winding Number Rule， and the practical application of two methods to do some more.

Key words: region filling; odd-even rules; non-zero number of rules

在計算機(jī)圖形學(xué)中，多邊形是重要的研究對象。對多邊形區(qū)域的填充，在計算機(jī)圖形學(xué)中有多種方法的實現(xiàn)，本文主要介紹奇-偶規(guī)則和非零環(huán)繞數(shù)規(guī)則，為判斷多變形內(nèi)外點(diǎn)提供更高效的方法。

奇-偶規(guī)則和非零環(huán)繞數(shù)規(guī)則比傳統(tǒng)的掃描線算法更高效，在時間復(fù)雜度和空間復(fù)雜度上都有所減少。但是這兩種方法還存在問題:對普通的多邊形兩種方法都適用，但是對復(fù)雜多邊形來說奇-偶規(guī)則就不太適用;這兩種方法，沒有對特殊情況作出解決方法，例如，當(dāng)水平射線與多邊形頂點(diǎn)相交，當(dāng)水平射線與多變形的邊相交等情況上對填充點(diǎn)的點(diǎn)亮問題沒有給出合適的解決方法。由于奇-偶規(guī)則和非零環(huán)繞數(shù)規(guī)則在有關(guān)文獻(xiàn)和研究成果并不多見，本文就這兩種方法做詳細(xì)的介紹，并對實際的應(yīng)用情況作相應(yīng)的比較。

1 兩種算法的概念

1.1 奇-偶規(guī)則

奇-偶規(guī)則是從任意位置p作一條水平射線，若與該射線相交的多邊形邊的數(shù)目為奇數(shù)，則p是多邊形內(nèi)部點(diǎn)，否則是外部點(diǎn)。對于內(nèi)部的點(diǎn)，用顏色值來點(diǎn)亮，外部點(diǎn)，則用背景色點(diǎn)之。利用奇-偶規(guī)則來判定一個點(diǎn)是內(nèi)點(diǎn)還是外點(diǎn)，也有特殊的情況。如圖1，對基本的情況，用奇-偶規(guī)則的定義很明顯的就能判定出來，但是對于特殊情況就要進(jìn)行討論并做特殊的處理:當(dāng)任意位置作出的水平射線與多邊形的兩條邊都相交，兩條邊分別落在水平射線的兩邊，這時，交點(diǎn)的個數(shù)算一個。若兩條邊同時落在了水平射線的一邊，此時，交點(diǎn)的個數(shù)作為零;當(dāng)從任意點(diǎn)引的水平射線與多邊形底邊重合，對多變形的水平邊通常不作考慮。

1.2 非零環(huán)繞數(shù)規(guī)則

非零環(huán)繞數(shù)規(guī)則使多邊形的邊變?yōu)槭噶浚瑢h(huán)繞數(shù)初始化為零，再從任意位置p作一條射線。當(dāng)從p點(diǎn)沿射線方向移動時，對在每個方向上穿過射線的邊計數(shù)，當(dāng)多邊形的邊從右到左穿過射線時，環(huán)繞數(shù)加1，從左到右時，環(huán)繞數(shù)減1。處理完多邊形的所有相關(guān)邊之后，若環(huán)繞數(shù)為非零，則p為內(nèi)部點(diǎn)，否則，p是外部點(diǎn)。具體的說明如圖1。

圖(a)，從點(diǎn)P引出一條水平射線，該射線與多邊形的兩邊相交，由于多邊形的邊已經(jīng)矢量化，所以對于CD邊，是從射線的左到右，此時環(huán)繞數(shù)減一。對于AB邊，是從射線的右到左，此時環(huán)繞數(shù)加一。最后環(huán)繞數(shù)累計為0，點(diǎn)P為外部點(diǎn);圖(b)，從P點(diǎn)引出的水平射線與多邊形的AB邊相交，從射線的右邊到左邊，環(huán)繞數(shù)加一，最后累計環(huán)繞數(shù)為1非0，P為內(nèi)部點(diǎn)。非零環(huán)繞數(shù)的實現(xiàn)方法描述如下:

第一種方法叉乘法，向量S是多邊形的一條邊向量，S1，S2分別是該邊的兩個端點(diǎn)的向量，則S的邊向量表示為為S1-S2，轉(zhuǎn)化成坐標(biāo)為(Sx，Sy)。從P點(diǎn)引出的射線向量為(Px，Py)，則S與P的叉乘為PxSy-PySx;從P點(diǎn)出發(fā)的射線向量與穿過射線的每條邊的邊向量S叉乘，如果叉乘的結(jié)果為正，則說明邊是從射線的右邊穿到左邊，環(huán)繞數(shù)此時加一。否則，環(huán)繞數(shù)減一;第二種方法引入垂直于射線向量的向量U，設(shè)置該向量時最好是從點(diǎn)P沿著射線向量方向看是從右到左指向的向量，射線向量為(Px，Py)，所以垂直于該向量的元素有(-Px，Py)，于是判定條件可以轉(zhuǎn)化為:從點(diǎn)P引出的水平射線向量的垂直向量與該射線的相交邊向量的點(diǎn)乘為正，則環(huán)繞數(shù)加一，否則，環(huán)繞數(shù)減一。

2 程序?qū)崿F(xiàn)

為了簡化程序，減少時間復(fù)雜度，把奇-偶規(guī)則和非零環(huán)繞數(shù)規(guī)則結(jié)合在一起。相互彌補(bǔ)兩種規(guī)則的不足。其中cross()判斷水平射線是否與多邊形的某邊相交， 參數(shù)P1， P2 為多邊形兩頂頭坐標(biāo)， P為待判定的點(diǎn)。isinner()點(diǎn)坐標(biāo)是否位于內(nèi)部區(qū)域， 參數(shù)num為多邊形的頂點(diǎn)數(shù)，px()為一數(shù)組， 各元素均為POINT類型， 存放多邊形各頂點(diǎn)坐標(biāo)。

typedef struct

{long x;

Long y;} POINT;

typedef struct

{long left;

Long top;

Long right;

Long bottom;} RECT;

private int polygon (RECT r， POINT p){

if (p.x>=r.left p.x<=r，right) (p.y>=r.top p.y<=r.bottom)

polygon=1;

else polygon=0;}

private int cross (POINT p1，POINT p2，POINT p){

int direc， xt;

if (p.y>p1.y p.y>p2.y) || (p.y

cross=0;

if (p2.y=p1.y)

if (p.y=p1.y)

if (p.x>p1.x p.x>p2.x)

cross=2;/*水平射線與多邊形的邊重合*/

else

if (p.x

crosst=0;/*水平射線與多邊形的一條邊平行，且不重合*/

else

direc=1;/*相交點(diǎn)位于多邊形的邊界*/

else

cross=0;

xt=p1.x+(p2.x-p1.x)(p.y-p1.y)/(p2.y-p1.y);

if (xt>p.x)

cross=0;

else

if (xt=p.x)

direc=1;

else

if (p.y=p1.y || p.y=p2.y)

cross=2;

else

cross=1;}

private int isinner (int num， POINT p， POINT px ){

int ret， sum;

ret=0;sum=0;direc=0;

for(i=0;i

ret=intersect(px(num-1)，px(0)，p)

if (ret=2)

isinner=2;

sum=sum+ret;

ret=cross(px(num-1)，px(0)，p);

if (ret=2)

isinner=2;

sum=sum+ret:

if direc

isinner=1;

if (sum mod 2=0)

isinner=0;

else

isinner=1;}

3 結(jié)束語

論文介紹了鑒別物體內(nèi)部點(diǎn)的方法。對規(guī)則的(即不自交)多邊形或者簡單的形狀，非零環(huán)繞數(shù)規(guī)則和奇-偶規(guī)則都能給出相同的判定結(jié)果;但是對于比較復(fù)雜的情況，這兩種規(guī)則可能會產(chǎn)生不同的內(nèi)部和外部區(qū)域，而且對于非零環(huán)繞數(shù)規(guī)則，如果是規(guī)則的多邊形或者簡單的形狀，采用平面向量的計算方法就可以，但是對于復(fù)雜的空間的多邊形，則要采用空間向量的計算方法。一般來說，非零環(huán)繞數(shù)規(guī)則比奇-偶規(guī)則更為通用。

參考文獻(xiàn):

[1] 孫家廣.計算機(jī)圖形學(xué)[M].北京:清華大學(xué)出版社，2000:178-182.

[2] 柳朝陽，周曉平.計算機(jī)圖形學(xué)-圖形的計算與顯示原理[M].西安:西安電子科技大學(xué)出版社，2005:46-56.

[3] 孫正興，周良，鄭宏源.計算機(jī)圖形學(xué)基礎(chǔ)教程[M].北京:清華大學(xué)出版社，2004:68-70.

[4] 劉琪，鄧勇.熱點(diǎn)觸發(fā)檢測算法的設(shè)計與實現(xiàn)[J].China Academic Journal Electronic Publishing House，1999:2-3.

注:本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文