判断点在多边形内的多种写法

判断点在多边形内的多种写法

(

射线算法

)

(2010-10-09 17:04:24)

转

载

标签：

计算几何

射线法

杂谈

▼

分类：

经验总结

************ *******************************

*

射线算法一

*

*******************************************

1.

已知点

poi nt(x,y)

和多边形

Polygon

（

x1,y1;x2,y2;….xn,yn;

）；

2.

以

< br>point

为起点，以无穷远为终点作平行于

X

轴的直线

line(

x,y; -

∞

,y)

；

3.

循环取得

(for(i=0;i

多边形的每一条边

side

(xi,yi;xi+1,yi+1)

，

且判断是否平行于

X

轴，如果平行< /p>

continue

，否则，

i++

；

4.

同时判断

point(x,y)

是否在

side

上，如果是，则返回

1(

点在多边形

上

)

，否则继续下面的判断；

5. < /p>

判断线

side

与

line

是否有交点，如果有则

count++

，否则，

i++

。

6.

判断交点的总数，如果为奇数则返回< /p>

0

（点在多边形内），偶数则返回

2

（点在多边

形外）。

代码：

const double INFINITY = 1e10;

const double ESP = 1e-5;

const int MAX_N = 1000;

struct Point

{

double x, y;

};

struct LineSegment

{

Point pt1, pt2;

};

typedef vector Polygon;

//

计算叉乘

|P0P1| ×

|P0P2|

double Multiply(Point p1, Point p2, Point p0)

{

return ( (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y) );

}

//

判断线段是否包含点

point

bool IsOnline(Point point, LineSegment line)

{

return( ( fabs(Multiply(1, 2, point)) < ESP ) &&

( ( point.x - 1.x ) * ( point.x - 2.x ) <= 0 ) &&

( ( point.y - 1.y ) * ( point.y - 2.y ) <= 0 ) );

}

//

判断线段相交

bool Intersect(LineSegment L1, LineSegment L2)

{

return( (max(1.x, 2.x) >= min(1.x, 2.x)) &&

(max(1.x, 2.x) >= min(1.x, 2.x)) &&

(max(1.y, 2.y) >= min(1.y, 2.y)) &&

(max(1.y, 2.y) >= min(1.y, 2.y)) &&

(Multiply(1, 2, 1) * Multiply(2, 2, 1) >= 0) &&

(Multiply(1, 2, 1) * Multiply(2, 2, 1) >= 0) );

}

//

判断点在多边形内

bool InPolygon(const Polygon& polygon, Point point)

{

int n = ();

int count = 0;

LineSegment line;

1 = point;

2.y = point.y;

2.x = - INFINITY;

for( int i = 0; i < n; i++ )

{

//

得到多边形的一条边

LineSegment side;

1 = polygon[i];

2 = polygon[(i + 1) % n];

if( IsOnline(point, side) )

{

return1

}

//

如果

< br>side

平行

x

轴则不作考虑< /p>

if( fabs(1.y - 2.y) < ESP )

{

continue;

}

if( IsOnline(1, line) )

{

if( 1.y > 2.y ) count++;

}

else if( IsOnline(2, line) )

{

if( 2.y > 1.y ) count++;

}

else if( Intersect(line, side) )

{

count++;

}

}

if ( count % 2 == 1 ) {return 0;}

else { return 2;}

}

}

**** ***************************************

*

射线算法二

*

******************************************* < /p>

本文是采用射线法判断点是否在多边形内的

C

语言程序。多年前，我自己实现了这样一个

算法。但是随着时间的推移，我决定重写 这个代码。参考周培德的《计算几何》一书，结合

我的实践和经验，我相信，在这个算法 的实现上，这是你迄今为止遇到的最优的代码。

这是个

C

语言的小算法的实现程序，本来不想放到这里。可是，当我自己要实 现这样一个

算法的时候，

想在网上找个现成的，

考察下来竟然一个符合需要的也没有。

我对自己大学读

书时写的代码没有信心，所以，决定重新写一个，并把它放到这里，以飨读者。也增加一下

BLOG

的点击量。

首先定义点结构如下：

以下是引用片段：

typedef struct

{

double x, y;

} vertex_t;

本算法里所指的多边形，

是指由一系 列点序列组成的封闭简单多边形。

它的首尾点可以是或

不是同一 个点（不强制要求首尾点是同一个点）。

这样的多边形可以是任意形状的，包括多

条边在一条绝对直线上。因此，定义多边形结构如下：

以下是引用片段：

typedef struct

{

int num_vertices;

vertex_t *vertex;

} vertexlist_t;

为加快 判别速度，首先计算多边形的外包矩形（

rect_t

），判断 点是否落在外包矩形内，只

有满足落在外包矩形内的条件的点，才进入下一步的计算。为 此，引入外包矩形结构

rect_t

和求点集合的外包矩形内的 方法

vertices_get_extent

，代码如下：< /p>

以下是引用片段：

typedef struct

{

double min_x, min_y, max_x, max_y;

} rect_t;

void vertices_get_extent (const vertex_t* vl, int np,

rect_t* rc )

{

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;

}

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;

}

}

当点满足落在多边形外包矩形内的条件，

要进一步判断点

（

v

）

是否在多边形

（

vl

：

np

）

内。

本程序采用射线法，由待测试点（

v

）水平引出一条射线

B

< br>（

v

，

w

），计算

B

与

vl

< br>边线的

交点数目，记为

c

，根据 奇内偶外原则（

c

为奇数说明

v

在

vl

内，否则

v< /p>

不在

vl

内）判断点

是否在多边形内。

具体原理就不多说。为计算线段间是否 存在交点，引入下面的函数：

（

1< /p>

）

is_same

判断

< br>2

（

p

、

q

）个点是（

1

）否（

0

）在直线

l

（