有什么算法可以确定一个点在不在多边形内？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Computation - 科学计算

有什么算法可以确定一个点在不在多边形内？

有什么算法可以确定一个点在不在多边形内？# Computation - 科学计算

p*r2003-08-06 07:08

1 楼

给定平面坐标系，给定一些点的坐标，这些点构成一个多边形。然后给出一个点的坐标，
判断这个点是否在多边形内。
或者给出一条直线 x=a, 如何算出这条直线和这个多边形的交点？
哪儿能找到这个问题的算法？

sc2003-08-06 07:08

2 楼

就是数交点个数,注意交点和顶点重合的时候要判断

【在 p******r 的大作中提到】

: 给定平面坐标系，给定一些点的坐标，这些点构成一个多边形。然后给出一个点的坐标，
: 判断这个点是否在多边形内。
: 或者给出一条直线 x=a, 如何算出这条直线和这个多边形的交点？
: 哪儿能找到这个问题的算法？

t*n2003-08-06 07:08

3 楼

I am using a code like this for your first problem:
http://www.math.iastate.edu/burkardt/c_src/orourke/inpoly.c
Hope this help.

【在 sc 的大作中提到】

: 就是数交点个数,注意交点和顶点重合的时候要判断

m*d2003-08-06 07:08

4 楼

Let the point be (x, y).
Line up the vertices(DingDian) as (x1, y1), (x2, y2), ..., (xn, yn).
Calculate
ci=det(matrix
x y 1
xi yi 1
x(i1) y(i+1) 1
)
for i=0, 1, ..., n-1. Of course, denote (x0, y0) = (xn, yn).
If all the ci's are positive, or all are negative, the point is
in the polygon. Otherwise, i.e., some positive and some negative,
the point is not in the polygon.

坐标，

【在 t****n 的大作中提到】

: I am using a code like this for your first problem:
: http://www.math.iastate.edu/burkardt/c_src/orourke/inpoly.c
: Hope this help.

c*t2003-08-06 07:08

5 楼

totally wrong,
Your solution only works for convex polygons.

【在 m******d 的大作中提到】

: Let the point be (x, y).
: Line up the vertices(DingDian) as (x1, y1), (x2, y2), ..., (xn, yn).
: Calculate
: ci=det(matrix
: x y 1
: xi yi 1
: x(i1) y(i+1) 1
: )
: for i=0, 1, ..., n-1. Of course, denote (x0, y0) = (xn, yn).
: If all the ci's are positive, or all are negative, the point is

a*i2003-08-06 07:08

6 楼

Same feeling here. What is your solution to non-convex
polygons?
Don't have a good answer yet...

【在 c****t 的大作中提到】

: totally wrong,
: Your solution only works for convex polygons.

sc2003-08-06 07:08

7 楼

发信人: oneaddone (我叫倒乱,来自乱岛,我是来捣乱的!), 信区: Algorithm
标题: Re: 请教一个题,觉得这里肯定有人知道
发信站: 日月光华 (2003年06月12日01:23:32 星期四), 站内信件
判断点是否在多边形中
以点P为端点，向左方作射线L，由于多边形是有界的，所以射线L的左端一定在多边形外
，考虑沿着L从无穷远处开始自左向右移动，遇到和多边形的第一个交点的时候，进入到
了多边形的内部，遇到第二个交点的时候，离开了多边形，……所以很容易看出当L和多
边形的交点数目C是奇数的时候，P在多边形内，是偶数的话P在多边形外。
但是有些特殊情况要加以考虑。如果L和多边形的顶点相交，有些情况下交点只能计算一
个，有些情况下交点不应被计算（你自己画个图就明白了）；如果L和多边形的一条边重
合，这条边应该被忽略不计。为了统一起见，我们在计算射线L和多边形的交点的时候，
1。对于多边形的水平边不作考虑；2。对于多边形的顶点和L相交的情况，如果该顶点是
其所属的边上纵坐标较大的顶点，则计数，否则忽略；3。对于P在多边形边上的情形，
直接可判断P属于多边行。由

c*t2003-08-06 07:08

8 楼

for 2D case, it's easy to handle this way.
If 3D, too many degenerate cases to consider. So later a lot of researcher
have carried out research on robust degenerecy handling.
In my opinion, the most beautiful work is the one named SOS (simulation of
simplicity). Search google for details.

【在 sc 的大作中提到】

: 发信人: oneaddone (我叫倒乱,来自乱岛,我是来捣乱的!), 信区: Algorithm
: 标题: Re: 请教一个题,觉得这里肯定有人知道
: 发信站: 日月光华 (2003年06月12日01:23:32 星期四), 站内信件
: 判断点是否在多边形中
: 以点P为端点，向左方作射线L，由于多边形是有界的，所以射线L的左端一定在多边形外
: ，考虑沿着L从无穷远处开始自左向右移动，遇到和多边形的第一个交点的时候，进入到
: 了多边形的内部，遇到第二个交点的时候，离开了多边形，……所以很容易看出当L和多
: 边形的交点数目C是奇数的时候，P在多边形内，是偶数的话P在多边形外。
: 但是有些特殊情况要加以考虑。如果L和多边形的顶点相交，有些情况下交点只能计算一
: 个，有些情况下交点不应被计算（你自己画个图就明白了）；如果L和多边形的一条边重

c*t2003-08-06 07:08

9 楼

#964 is a standard solution mentioned in every graphics, computational
geometry book. Donot know why so many people seemed never heard of it.

【在 a**i 的大作中提到】

: Same feeling here. What is your solution to non-convex
: polygons?
: Don't have a good answer yet...