GIS點在多邊形內(nèi)算法1

第頁1.判斷點在多邊形內(nèi)外的簡單算法--改進弧長法今天學(xué)圖形學(xué)的時候發(fā)現(xiàn)了一個求多邊形內(nèi)外的超簡單算法，當(dāng)時覺得非常驚喜，后來晚上上完選修的時候在走廊遇到bug，bug也是很驚喜地感慨道：居然有甘簡單既辦法都捻唔到！遂將其寫下，供大家分享，希望不會太火星。

這個算法是源自《計算機圖形學(xué)基礎(chǔ)教程》（孫家廣，清華大學(xué)出版社），在該書的48-49頁，名字可稱為“改進的弧長法”。該算法只需O(1)的附加空間，時間復(fù)雜度為O(n)，但系數(shù)很??；最大的優(yōu)點是具有很高的精度，只需做乘法和減法，若針對整數(shù)坐標(biāo)則完全沒有精度問題。而且實現(xiàn)起來也非常簡單，比轉(zhuǎn)角法和射線法都要好寫且不易出錯。

首先從該收中摘抄一段弧長法的介紹：“弧長法要求多邊形是有向多邊形，一般規(guī)定沿多邊形的正向，邊的左側(cè)為多邊形的內(nèi)側(cè)域。以被測點為圓心作單位圓，將全部有向邊向單位圓作徑向投影，并計算其中單位圓上弧長的代數(shù)和。若代數(shù)和為0，則點在多邊形外部；若代數(shù)和為2π則點在多邊形內(nèi)部；若代數(shù)和為π，則點在多邊形上?！?/p>

按書上的這個介紹，其實弧長法就是轉(zhuǎn)角法。但它的改進方法比較厲害：將坐標(biāo)原點平移到被測點P，這個新坐標(biāo)系將平面劃分為4個象限，對每個多邊形頂點P，只考慮其所在的象限，然后按鄰接順序訪問多邊形的各個頂點P，分析P和P[i+1]，有下列三種情況：

（1）P[i+1]在P的下一象限。此時弧長和加π/2；

（2）P[i+1]在P的上一象限。此時弧長和減π/2；

（3）P[i+1]在Pi的相對象限。首先計算f=y[i+1]*x-x[i+1]*y（叉積），若f=0，則點在多邊形上；若f<0，弧長和減π；若f>0，弧長和加π。

最后對算出的代數(shù)和和上述的情況一樣判斷即可。

實現(xiàn)的時候還有兩點要注意，第一個是若P的某個坐標(biāo)為0時，一律當(dāng)正號處理；第二點是若被測點和多邊形的頂點重合時要特殊處理。

以上就是書上講解的內(nèi)容，其實還存在一個問題。那就是當(dāng)多邊形的某條邊在坐標(biāo)軸上而且兩個頂點分別在原點的兩側(cè)時會出錯。如邊(3,0)-(-3,0)，按以上的處理，象限分別是第一和第二，這樣會使代數(shù)和加π/2，有可能導(dǎo)致最后結(jié)果是被測點在多邊形外。而實際上被測點是在多邊形上（該邊穿過該點）。

對于這點，我的處理辦法是：每次算P和P[i+1]時，就計算叉積和點積，判斷該點是否在該邊上，是則判斷結(jié)束，否則繼續(xù)上述過程。這樣犧牲了時間，但保證了正確性。

具體實現(xiàn)的時候，由于只需知道當(dāng)前點和上一點的象限位置，所以附加空間只需O(1)。實現(xiàn)的時候可以把上述的“π/2”改成1，“π”改成2，這樣便可以完全使用整數(shù)進行計算。不必考慮頂點的順序，逆時針和順時針都可以處理，只是最后的代數(shù)和符號不同而已。整個算法編寫起來非常容易。

針對以上算法，我寫了一個代碼，拿ZOJ1081PointsWithin進行測試，順利Accepted。這證明該算法的正確性還是可以保障的。

以下附上我的代碼：

//ZOJ1081,改進弧長法判點在形內(nèi)形外

#include<stdio.h>

#include<math.h>

constintMAX=101;

structpoint{intx,y;}p[MAX];intmain()

{

intn,m,i,sum,t1,t2,f,prob=0;

pointt;

while(scanf("%d",&n),n)

{

if(prob++)printf("\n");

printf("Problem%d:\n",prob);

scanf("%d",&m);

for(i=0;i<n;i++)scanf("%d%d",&p.x,&p.y);

p[n]=p[0];

while(m--)

{

scanf("%d%d",&t.x,&t.y);

for(i=0;i<=n;i++)p.x-=t.x,p.y-=t.y;//坐標(biāo)平移

t1=p[0].x>=0?(p[0].y>=0?0:3):(p[0].y>=0?1:2);

//計算象限

for(sum=0,i=1;i<=n;i++)

{

if(!p.x&&!p.y)break;//被測點為多邊形頂點

f=p.y*p[i-1].x-p.x*p[i-1].y;

//計算叉積

if(!f&&p[i-1].x*p.x<=0&&p[i-1].y*p[i].y<=0)break;

//點在邊上

t2=p.x>=0?(p.y>=0?0:3):(p.y>=0?1:2);//計算象限

if(t2==(t1+1)%4)sum+=1;

//情況1

elseif(t2==(t1+3)%4)sum-=1;

//情況2

elseif(t2==(t1+2)%4)

//情況3

{

if(f>0)sum+=2;elsesum-=2;

}

t1=t2;

}

if(i<=n||sum)printf("Within\n");elseprintf("Outside\n");

for(i=0;i<=n;i++)p.x+=t.x,p.y+=t.y;

//恢復(fù)坐標(biāo)

}

}

return0;

}2.C語言中實現(xiàn)點在多邊形內(nèi)算法本文是采用射線法判斷點是否在多邊形內(nèi)的C語言程序。多年前，我自己實現(xiàn)了這樣一個算法。但是隨著時間的推移，我決定重寫這個代碼。參考周培德的《計算幾何》一書，結(jié)合我的實踐和經(jīng)驗，我相信，在這個算法的實現(xiàn)上，這是你迄今為止遇到的最優(yōu)的代碼。

這是個C語言的小算法的實現(xiàn)程序，本來不想放到這里?？墒?，當(dāng)我自己要實現(xiàn)這樣一個算法的時候，想在網(wǎng)上找個現(xiàn)成的，考察下來竟然一個符合需要的也沒有。我對自己大學(xué)讀書時寫的代碼沒有信心，所以，決定重新寫一個，并把它放到這里，以饗讀者。也增加一下BLOG的點擊量。

首先定義點結(jié)構(gòu)如下：

以下是引用片段：

Copy

code/*

Vertex

structure

*/

typedef

struct

{

double

x,

y;

}

vertex_t;

本算法里所指的多邊形，是指由一系列點序列組成的封閉簡單多邊形。它的首尾點可以是或不是同一個點(不強制要求首尾點是同一個點)。這樣的多邊形可以是任意形狀的，包括多條邊在一條絕對直線上。因此，定義多邊形結(jié)構(gòu)如下：

以下是引用片段：

Copy

code/*

Vertex

list

structure

–

polygon

*/

typedef

struct

{

int

num_vertices;

/*

Number

of

vertices

in

list

*/

vertex_t

*vertex;

/*

Vertex

array

pointer

*/

}

vertexlist_t;

為加快判別速度，首先計算多邊形的外包矩形(rect_t)，判斷點是否落在外包矩形內(nèi)，只有滿足落在外包矩形內(nèi)的條件的點，才進入下一步的計算。為此，引入外包矩形結(jié)構(gòu)rect_t和求點集合的外包矩形內(nèi)的方法vertices_get_extent，代碼如下：

以下是引用片段：

Copy

code/*

bounding

rectangle

type

*/

typedef

struct

{

double

min_x,

min_y,

max_x,

max_y;

}

rect_t;

/*

gets

extent

of

vertices

*/

void

vertices_get_extent

(const

vertex_t*

vl,

int

np,

/*

in

vertices

*/

rect_t*

rc

/*

out

extent*/

)

{

int

i;

if

(np

>

0){

rc->min_x

=

rc->max_x

=

vl[0].x;

rc->min_y

=

rc->max_y

=

vl[0].y;

}else{

rc->min_x

=

rc->min_y

=

rc->max_x

=

rc->max_y

=

0;

/*

=0

?

no

vertices

at

all

*/

}

for(i=1;

i

{

if(vl[i].x

<

rc->min_x)

rc->min_x

=

vl[i].x;

if(vl[i].y

<

rc->min_y)

rc->min_y

=

vl[i].y;

if(vl[i].x

>

rc->max_x)

rc->max_x

=

vl[i].x;

if(vl[i].y

>

rc->max_y)

rc->max_y

=

vl[i].y;

}

}

當(dāng)點滿足落在多邊形外包矩形內(nèi)的條件，要進一步判斷點(v)是否在多邊形(vl：np)內(nèi)。本程序采用射線法，由待測試點(v)水平引出一條射線B(v，w)，計算B及vl邊線的交點數(shù)目，記為c，根據(jù)奇內(nèi)偶外原則(c為奇數(shù)說明v在vl內(nèi)，否則v不在vl內(nèi))判斷點是否在多邊形內(nèi)。

具體原理就不多說。為計算線段間是否存在交點，引入下面的函數(shù)：

(1)is_same判斷2(p、q)個點是(1)否(0)在直線l(l_start，l_end)的同側(cè);

(2)is_intersect用來判斷2條線段(不是直線)s1、s2是(1)否(0)相交;

以下是引用片段：

Copy

code/*

p,

q

is

on

the

same

of

line

l

*/

static

int

is_same(const

vertex_t*

l_start,

const

vertex_t*

l_end,

/*

line

l

*/

const

vertex_t*

p,

const

vertex_t*

q)

{

double

dx

=

l_end->x

-

l_start->x;

double

dy

=

l_end->y

-

l_start->y;

double

dx1=

p->x

-

l_start->x;

double

dy1=

p->y

-

l_start->y;

double

dx2=

q->x

-

l_end->x;

double

dy2=

q->y

-

l_end->y;

return

((dx*dy1-dy*dx1)*(dx*dy2-dy*dx2)

>

0?

1

:

0);

}

/*

2

line

segments

(s1,

s2)

are

intersect?

*/

static

int

is_intersect(const

vertex_t*

s1_start,

const

vertex_t*

s1_end,

const

vertex_t*

s2_start,

const

vertex_t*

s2_end)

{

return

(is_same(s1_start,

s1_end,

s2_start,

s2_end)==0

&&

is_same(s2_start,

s2_end,

s1_start,

s1_end)==0)?

1:

0;

}

下面的函數(shù)pt_in_poly就是判斷點(v)是(1)否(0)在多邊形(vl：np)內(nèi)的程序：

以下是引用片段：

Copy

codeint

pt_in_poly

(

const

vertex_t*

vl,

int

np,

/*

polygon

vl

with

np

vertices

*/

const

vertex_t*

v)

{

int

i,

j,

k1,

k2,

c;

rect_t

rc;

vertex_t

w;

if

(np

<

3)

return

0;

vertices_get_extent(vl,

np,

&rc);

if

(v->x

<

rc.min_x

||

v->x

>

rc.max_x

||

v->y

<

rc.min_y

||

v->y

>

rc.max_y)

return

0;

/*

Set

a

horizontal

beam

l(*v,

w)

from

v

to

the

ultra

right

*/

w.x

=

rc.max_x

+

DBL_EPSILON;

w.y

=

v->y;

c

=

0;

/*

Intersection

points

counter

*/

for(i=0;

i

{

j

=

(i+1)

%

np;

if(is_intersect(vl+i,

vl+j,

v,

&w))

{

c++;

}

else

if(vl[i].y==w.y)

{

k1

=

(np+i-1)%np;

while(k1!=i

&&

vl[k1].y==w.y)

k1

=

(np+k1-1)%np;

k2

=

(i+1)%np;

while(k2!=i

&&

vl[k2].y==w.y)

k2

=

(k2+1)%np;

if(k1

!=

k2

&&

is_same(v,

&w,

vl+k1,

vl+k2)==0)

c++;

if(k2

<=

i)

break;

i

=

k2;

}

}

return

c%2;

}

本想配些插圖說明問題，但是，CSDN的文章里放圖片我還沒用過。以后再試吧!實踐證明，本程序算法的適應(yīng)性極強。但是，對于點正好落在多邊形邊上的極端情形，有可能得出2種不同的結(jié)果。3.判斷一個幾何點在多邊形內(nèi)的例子：

#define

X

0

#define

Y

1

typedef

enum

{

FALSE,

TRUE

}

bool;

#define

DIM

2

/*

Dimension

of

points

*/

typedef

int

tPointi[DIM];

/*

type

integer

point

*/

typedef

double

tPointd[DIM];

/*

type

double

point

*/

#define

PMAX

10000

/*

Max

#

of

pts

in

polygon

*/

typedef

tPointi

tPolygoni[PMAX];/*

type

integer

polygon

*/

char

InPoly(

tPointi

q,

tPolygoni

P,

int

n

);

void

PrintPoly(

int

n,

tPolygoni

P

);

void

PrintPoint(

tPointi

p

);

void

Copy

(

tPolygoni

a,

tPolygoni

b

,

int

n

);

main()

{

int

n;

tPolygoni

P,

Porig;

tPointi

q;

n

=

ReadPoly(

P

);

Copy(

P,

Porig,

n

);

while(

scanf(

"%d

%d",

&q[X],

&q[Y])

!=

EOF

)

{

printf(

"InPoly

=

%c\n",

InPoly(

q,

P,

n

)

);

/*

Refill

the

destroyed

polygon

with

original.

*/

Copy(

Porig,

P,

n

);

}

}

/*

InPoly

returns

a

char

in

{i,o,v,e}.

See

above

for

definitions.

*/

char

InPoly(

tPointi

q,

tPolygoni

P,

int

n

)

{

int

i,

i1;

/*

point

index;

i1

=

i-1

mod

n

*/

int

d;

/*

dimension

index

*/

double

x;

/*

x

intersection

of

e

with

ray

*/

int

Rcross

=

0;

/*

number

of

right

edge/ray

crossings

*/

int

Lcross

=

0;

/*

number

of

left

edge/ray

crossings

*/

printf("\n==>InPoly:

q

=

");

PrintPoint(q);

putchar('\n');

/*

Shift

so

that

q

is

the

origin.

Note

this

destroys

the

polygon.

This

is

done

for

pedogical

clarity.

*/

for(

i

=

0;

i

<

n;

i++

)

{

for(

d

=

0;

d

<

DIM;

d++

)

P[i][d]

=

P[i][d]

-

q[d];

}

/*

For

each

edge

e=(i-1,i),

see

if

crosses

ray.

*/

for(

i

=

0;

i

<

n;

i++

)

{

/*

First

see

if

q=(0,0)

is

a

vertex.

*/

if

(

P[i][X]==0

&&

P[i][Y]==0

)

return

'v';

i1

=

(

i

+

n

-

1

)

%

n;

/*

printf("e=(%d,%d)\t",

i1,

i);

*/

/*

if

e

"straddles"

the

x-axis...

*/

/*

The

commented-out

statement

is

logically

equivalent

to

the

one

following.

*/

/*

if(

(

(

P[i][Y]

>

0

)

&&

(

P[i1][Y]

<=

0

)

)

||

(

(

P[i1][Y]

>

0

)

&&

(

P[i]

[Y]

<=

0

)

)

)

{

*/

if(

(

P[i][Y]

>

0

)

!=

(

P[i1][Y]

>

0

)

)

{

/*

e

straddles

ray,

so

compute

intersection

with

ray.

*/

x

=

(P[i][X]

*

(double)P[i1][Y]

-

P[i1][X]

*

(double)P[i][Y])

/

(double)(P[i1][Y]

-

P[i][Y]);

/*

printf("straddles:

x

=

%g\t",

x);

*/

/*

crosses

ray

if

strictly

positive

intersection.

*/

if

(x

>

0)

Rcross++;

}

/*

printf("Right

cross=%d\t",

Rcross);

*/

/*

if

e

straddles

the

x-axis

when

reversed...

*/

/*

if(

(

(

P[i]

[Y]

<

0

)

&&

(

P[i1][Y]

>=

0

)

)

||

(

(

P[i1][Y]

<

0

)

&&

(

P[i]

[Y]

>=

0

)

)

)

{

*/

if

(

(

P[i][Y]

<

0

)

!=

(

P[i1][Y]

<

0

)

)

{

/*

e

straddles

ray,

so

compute

intersection

with

ray.

*/

x

=

(P[i][X]

*

P[i1][Y]

-

P[i1][X]

*

P[i][Y])

/

(double)(P[i1][Y]

-

P[i][Y]);

/*

printf("straddles:

x

=

%g\t",

x);

*/

/*

crosses

ray

if

strictly

positive

intersection.

*/

if

(x

<

0)

Lcross++;

}

/*

printf("Left

cross=%d\n",

Lcross);

*/

}

/*

q

on

the

edge

if

left

and

right

cross

are

not

the

same

parity.

*/

if(

(

Rcross

%

2

)

!=

(Lcross

%

2

)

)

return

'e';

/*

q

inside

iff

an

odd

number

of

crossings.

*/

if(

(Rcross

%

2)

==

1

)

return

'i';

else

return

'o';

}

void

PrintPoint(

tPointi

p

)

{

int

i;

putchar('(');

for

(

i

=

0;

i

<

DIM;

i++

)

{

printf("%d",

p[i]);

if

(

i

!=

DIM-1

)

putchar(',');

}

putchar(')');

}

/*

Reads

in

the

coordinates

of

the

vertices

of

a

polygon

from

stdin,

puts

them

into

P,

and

returns

n,

the

number

of

vertices.

Formatting

conventions:

etc.

*/

int

ReadPoly(

tPolygoni

P

)

{

int

i,

n;

do

{

printf(

"Input

the

number

of

vertices:\n");

scanf(

"%d",

&n

);

if

(

n

<=

PMAX

)

break;

printf("Error

in

read_poly:

too

many

points;

max

is

%d\n",

PMAX);

}

while

(

1

);

printf(

"Polygon:\n"

);

printf(

"

i

x

y\n");

for

(

i

=

0;

i

<

n;

i++

)

{

scanf(

"%d

%d",

&P[i][0],

&P[i][1]

);

printf("%3d%4d%4d\n",

i,

P[i][0],

P[i][1]);

}

printf("n

=

%3d

vertices

read\n",n);

putchar('\n');

return

n;

}

void

PrintPoly(

int

n,

tPolygoni

P

)

{

int

i;

printf("Polygon:\n");

printf("

i

x

y\n");

for(

i

=

0;

i

<

n;

i++

)

printf("%3d%4d%4d\n",

i,

P[i][0],

P[i][1]);

}

/*

Copy

polygon

a

to

b

(overwriting

b).

*/

void

Copy(

tPolygoni

a,

tPolygoni

b,

int

n

)

{

int

i,

j;

for

(

i=0;

i

<

n;

i++)

for

(

j

=

0;

j

<

DIM;

j++

)

b[i][j]

=

a[i][j];

}

bool

EqPoint(

tPointi

a,

tPointi

b

)

{

int

i;

for

(

i

=

0;

i

<

DIM;

i++

)

if

(

a[i]

!=

b[i])

return

FALSE;

return

TRUE;

}

1.

已知點point(x,y)和多邊形Polygon（x1,y1;x2,y2;….xn,yn;）；2.

以point為起點，以無窮遠為終點作平行于X軸的直線line(x,y;-∞,y)；3.

循環(huán)取得(for(i=0;i<n;i++))多邊形的每一條邊side(xi,yi;xi+1,yi+1)，且判斷是否平行于X軸，如果平行continue，否則，i++；4.

同時判斷point(x,y)是否在side上，如果是，則返回1(點在多邊形

上)，否則繼續(xù)下面的判斷；5.

判斷線side及l(fā)ine是否有交點，如果有則count++，否則，i++。6.

判斷交點的總數(shù)，如果為奇數(shù)則返回0（點在多邊形內(nèi)），偶數(shù)則返回2（點在多邊形外）。代碼：/*

射線法判斷點q及多邊形polygon的位置關(guān)系，要求polygon為簡單多邊形，頂點逆時針排列

如果點在多邊形內(nèi)：

返回0

如果點在多邊形邊上：

返回1

如果點在多邊形外：

返回2constdoubleINFINITY=1e10;constdoubleESP=1e-5;constintMAX_N=1000;structPoint{doublex,y;structLineSegment{Pointpt1,pt2;typedefvector<Point>Polygon;//

計算叉乘

|P0P1|

×

|P0P2|doubleMultiply(Pointp1,Pointp2,Pointp0)return((p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y));//

判斷線段是否包含點pointboolIsOnline(Pointpoint,LineSegmentline)return((fabs(Multiply(line.pt1,line.pt2,point))<ESP)&&((point.x-line.pt1.x)*(point.x-line.pt2.x)<=0)&&((point.y-line.pt1.y)*(point.y-line.pt2.y)<=0));//

判斷線段相交boolIntersect(LineSegmentL1,LineSegmentL2)return((max(L1.pt1.x,L1.pt2.x)>=min(L2.pt1.x,L2.pt2.x))&&(max(L2.pt1.x,L2.pt2.x)>=min(L1.pt1.x,L1.pt2.x))&&(max(L1.pt1.y,L1.pt2.y)>=min(L2.pt1.y,L2.pt2.y))&&(max(L2.pt1.y,L2.pt2.y)>=min(L1.pt1.y,L1.pt2.y))&&(Multiply(L2.pt1,L1.pt2,L1.pt1)*Multiply(L1.pt2,L2.pt2,L1.pt1)>=0)&&(Multiply(L1.pt1,L2.pt2,L2.pt1)*Multiply(L2.pt2,L1.pt2,L2.pt1)>=0)//

判斷點在多邊形內(nèi)boolInPolygon(constPolygon&polygon,Pointpoint)intn=polygon.size();intcount=0;LineSegmentline;line.pt1=point;line.pt2.y=point.y;line.pt2.x=-INFINITY;for(inti=0;i<n;i++){//

得到多邊形的一條邊LineSegmentside;side.pt1=polygon[i];side.pt2=polygon[(i+1)%n];if(IsOnline(point,side)){return1;//

如果side平行x軸則不作考慮if(fabs(side.pt1.y-side.pt2.y)<ESP){continue;if(IsOnline(side.pt1,line)){if(side.pt1.y>side.pt2.y)count++;}elseif(IsOnline(side.pt2,line)){if(side.pt2.y>side.pt1.y)count++;}elseif(Intersect(line,side)){count++;

if(count%2==1){return0;}else{return2;}4.用射線相交來判斷點是否在多邊形內(nèi)的算法點在邊上，射線通過頂點，射線通過邊的情況都考慮了：

PublicLx(20)AsDouble

PublicLy(20)AsDouble

PublicLnAsInteger

'定義多邊形的坐標(biāo)，邊數(shù)

PublicPxAsDouble

PublicPyAsDouble

'定義點的坐標(biāo)

'該過程判斷點是否在多邊形內(nèi)，點在邊上判斷為在多邊形內(nèi)，方法為射線相交法，返回1為在多邊形內(nèi)，0為在多邊形外

PublicFunctionpinshp()

Dimlc(20)AsInteger

Dimls(20)AsInteger

pinshp=0

inline=0

Forz=0ToLn

zn=z+1

Ifzn>LnThenzn=0

'點在邊上判斷

IfLy(zn)=Ly(z)AndPy=Ly(z)Then

IfPx>Lx(z)AndPx<Lx(zn)Theninline=1

IfPx>Lx(zn)AndPx<Ly(z)Theninline=1

EndIf

Ifinline=1ThenExitFor

IfLy(zn)<>Ly(z)ThenIfLx(z)+(Lx(zn)-Lx(z))*(Py-Ly(z))/(Ly(zn)-Ly(z))=PxTheninline=1:ExitFor

'點在邊上判斷

lc(z)=Gcnn(Lx(z),Ly(z),Lx(zn),Ly(zn))'判斷是否相交，線段端點在延長線上為不相交

ls(z)=Gsid(Lx(z),Ly(z),Lx(zn),Ly(zn))'線段端點是否在延長線上，如在，判斷線段在哪側(cè)

pinshp=pinshp+lc(z)

Nextz

Ifinline=1Thenpinshp=1:ExitFunction'如改Ifinline=1Thenpinshp=0則點在邊上判斷為在多邊形外

Forz=0ToLn

zn=z-1

Ifzn<0Thenzn=Ln

Ifls(z)>0Andls(zn)>0Then

Ifls(z)<>ls(zn)Thenpinshp=pinshp+1

EndIf

Nextz

pinshp=pinshpAnd1

EndFunction

PublicFunctionGcnn(zx1,zy1,zx2,zy2)

Gcnn=0

Ifzx1>=PxAndzy1=PyThenGcnn=0:ExitFunction

Ifzx2>=PxAndzy2=PyThenGcnn=0:ExitFunction

Ifzy1>PyAndzy2>PyThenGcnn=0:ExitFunction

Ifzy1<PyAndzy2<PyThenGcnn=0:ExitFunction

Ifzy1=zy2ThenGcnn=0:ExitFunction

zpx=zx1+(zx2-zx1)*(Py-zy1)/(zy2-zy1)

Ifzpx>PxThenGcnn=1

EndFunction

PublicFunctionGsid(zx1,zy1,zx2,zy2)

Gsid=0

Ifzx1>=PxAndzy1=PyThen

Ifzy2<PyThenGsid=1ElseGsid=2

EndIf

Ifzx2>=PxAndzy2=PyThen

Ifzy1<PyThenGsid=1ElseGsid=2

EndIf

EndFunction5.判斷點在多邊形內(nèi)，射線算法1.

已知點point(x,y)和多邊形Polygon（x1,y1;x2,y2;….xn,yn;）；2.

以point為起點，以無窮遠為終點作平行于X軸的直線line(x,y;-∞,y)；3.

循環(huán)取得(for(i=0;