判断点是否在多边形内

原文地址：http://blog.csdn.net/kaitiren/article/details/11913453

有一个ｎ边形，顶点为p1,p2,...,pn;给定一个已知点p,判断p在此多边形内还是外。

预备知识： 两线段相交的定义，如果一条线段的两端分别处在另一条线段的两端，则此两线段相交

判断2点在线段的两侧可以用向量的叉乘实现！

基本步骤：

１，过ｐ点垂直向上作一条射线

２，判断此射线与ｎ边形ｎ条边的交点

３，把所有交点相加，如果是奇数则说明在多边形内，否则在多边形外

思路非常的简单，另外说明一下几种特殊的情况：

１，射线与多边形的顶点相交；比如射线过多边形的Pi点，则如果Pi-1和Pi+1在此射线的异侧，此交点可以算一个，如果此两点在射线的同侧，则此交点不计。此结论非常简单，画个图应该就能明白了

２，ｐ点在多边形的某一条边上；也认为ｐ在多边形中

３，ｐ不在多边形的边上，但ｐ的射线与多边形的某一条边重合；比如与Pi,Pi+1线段重合，则如果Pi-1和Pi+2在射线的两侧，此情况也算一个交点，否则此情况不计交点。跟一种的情况类似，画个图应该明白了！

顺便提一下点在平面细图中的判断

平面细图就是有m个多边形构成，但任何两个多边形都没有边的相交，只有顶点的重合

这样相当于就是调用m次点在多边形中的算法

以上实现是非常简单了，偶最近在看并行算法方面的东东，因此本篇主要是为并行算法作准备的

判断点是否处于多边形内的三种方法

1. 叉乘判别法 （只适用于凸多边形）

想象一个凸多边形，其每一个边都将整个2D屏幕划分成为左右两边，连接每一边的第一个端点和要测试的点得到一个矢量v，将两个2维矢量扩展成3维的，然后将该边与v叉乘，判断结果3维矢量中Z分量的符号是否发生变化，进而推导出点是否处于凸多边形内外。这里要注意的是，多边形顶点究竟是左手序还是右手序，这对具体判断方式有影响。

2. 面积判别法 （只适用于凸多边形）

第四点分别与三角形的两个点组成的面积分别设为S1,S2,S3，只要S1+S2+S3>原来的三角形面积就不在三角形范围中.可以使用海伦公式 。推广一下是否可以得到面向凸多边形的算法？（不确定）

3. 角度和判别法 （适用于任意多边形）

double angle = 0;
realPointList::iterator iter1 = points.begin();
for (realPointList::iterator iter2 = (iter1 + 1); iter2 < points.end(); ++iter1, ++iter2)
{
double x1 = (*iter1).x - p.x;
double y1 = (*iter1).y - p.y;
double x2 = (*iter2).x - p.x;
double y2 = (*iter2).y - p.y;
angle += angle2D(x1, y1, x2, y2);
}

if (fabs(angle - span::PI2) < 0.01) return true;
else return false;

另外，可以使用bounding box来加速。
if (p.x < (*iter)->boundingBox.left ||
p.x > (*iter)->boundingBox.right ||
p.y < (*iter)->boundingBox.bottom ||
p.y > (*iter)->boundingBox.top) 。。。。。。

对于多边形来说，计算bounding box非常的简单。只需要把水平和垂直方向上的最大最小值找出来就可以了。

对于三角形：第四点分别与三角形的两个点的交线组成的角度分别设为j1,j2,j3，只要j1+j2+j3>360就不在三角形范围中。

4. 水平/垂直交叉点数判别法 （适用于任意多边形）

注意到如果从P作水平向左的射线的话，如果P在多边形内部，那么这条射线与多边形的交点必为奇数，如果P在多边形外部，则交点个数必为偶数（0也在内）。所以，我们可以顺序考虑多边形的每条边，求出交点的总个数。还有一些特殊情况要考虑。假如考虑边(P1,P2)，
1)如果射线正好穿过P1或者P2,那么这个交点会被算作2次，处理办法是如果P的从坐标与P1,P2中较小的纵坐标相同，则直接忽略这种情况
2)如果射线水平，则射线要么与其无交点，要么有无数个，这种情况也直接忽略。
3)如果射线竖直，而P0的横坐标小于P1,P2的横坐标，则必然相交。
4)再判断相交之前，先判断P是否在边(P1,P2)的上面，如果在，则直接得出结论：P再多边形内部。

实现：

语法：result=insidepolygon(Point *polygon,int N,Point p);
参数：
*polygon： 多边形顶点数组
N： 多边形顶点个数
p： 被判断点
返回值： 0：点在多边形内部；1：点在多边形外部
注意：
若p点在多边形顶点或者边上，返回值不确定，需另行判断
需要 math.h
源程序：
#define MIN(x,y) (x < y ? x : y)
#define MAX(x,y) (x > y ? x : y)

typedef struct {
double x,y;
} Point;

int insidepolygon(Point *polygon,int N,Point p)
{
int counter = 0;
int i;
double xinters;
Point p1,p2;

p1 = polygon[0];
for (i=1;i<=N;i++) {
p2 = polygon[i % N];
if (p.y > MIN(p1.y,p2.y)) {
if (p.y <= MAX(p1.y,p2.y)) {
if (p.x <= MAX(p1.x,p2.x)) {
if (p1.y != p2.y) {
xinters = (p.y-p1.y)*(p2.x-p1.x)/(p2.y-p1.y)+p1.x;
if (p1.x == p2.x || p.x <= xinters)
counter++;
}
}
}
}
p1 = p2;
}

if (counter % 2 == 0)
return(OUTSIDE);
else
return(INSIDE);
}

分享到：

原文地址：http://blog.csdn.net/kaitiren/article/details/11913453

有一个ｎ边形，顶点为p1,p2,...,pn;给定一个已知点p,判断p在此多边形内还是外。

预备知识： 两线段相交的定义，如果一条线段的两端分别处在另一条线段的两端，则此两线段相交

判断2点在线段的两侧可以用向量的叉乘实现！

基本步骤：

１，过ｐ点垂直向上作一条射线

２，判断此射线与ｎ边形ｎ条边的交点

３，把所有交点相加，如果是奇数则说明在多边形内，否则在多边形外

思路非常的简单，另外说明一下几种特殊的情况：

１，射线与多边形的顶点相交；比如射线过多边形的Pi点，则如果Pi-1和Pi+1在此射线的异侧，此交点可以算一个，如果此两点在射线的同侧，则此交点不计。此结论非常简单，画个图应该就能明白了

２，ｐ点在多边形的某一条边上；也认为ｐ在多边形中

３，ｐ不在多边形的边上，但ｐ的射线与多边形的某一条边重合；比如与Pi,Pi+1线段重合，则如果Pi-1和Pi+2在射线的两侧，此情况也算一个交点，否则此情况不计交点。跟一种的情况类似，画个图应该明白了！

顺便提一下点在平面细图中的判断

平面细图就是有m个多边形构成，但任何两个多边形都没有边的相交，只有顶点的重合

这样相当于就是调用m次点在多边形中的算法

以上实现是非常简单了，偶最近在看并行算法方面的东东，因此本篇主要是为并行算法作准备的

判断点是否处于多边形内的三种方法

1. 叉乘判别法 （只适用于凸多边形）

想象一个凸多边形，其每一个边都将整个2D屏幕划分成为左右两边，连接每一边的第一个端点和要测试的点得到一个矢量v，将两个2维矢量扩展成3维的，然后将该边与v叉乘，判断结果3维矢量中Z分量的符号是否发生变化，进而推导出点是否处于凸多边形内外。这里要注意的是，多边形顶点究竟是左手序还是右手序，这对具体判断方式有影响。

2. 面积判别法 （只适用于凸多边形）

第四点分别与三角形的两个点组成的面积分别设为S1,S2,S3，只要S1+S2+S3>原来的三角形面积就不在三角形范围中.可以使用海伦公式 。推广一下是否可以得到面向凸多边形的算法？（不确定）

3. 角度和判别法 （适用于任意多边形）

double angle = 0;
realPointList::iterator iter1 = points.begin();
for (realPointList::iterator iter2 = (iter1 + 1); iter2 < points.end(); ++iter1, ++iter2)
{
double x1 = (*iter1).x - p.x;
double y1 = (*iter1).y - p.y;
double x2 = (*iter2).x - p.x;
double y2 = (*iter2).y - p.y;
angle += angle2D(x1, y1, x2, y2);
}

if (fabs(angle - span::PI2) < 0.01) return true;
else return false;

另外，可以使用bounding box来加速。
if (p.x < (*iter)->boundingBox.left ||
p.x > (*iter)->boundingBox.right ||
p.y < (*iter)->boundingBox.bottom ||
p.y > (*iter)->boundingBox.top) 。。。。。。

对于多边形来说，计算bounding box非常的简单。只需要把水平和垂直方向上的最大最小值找出来就可以了。

对于三角形：第四点分别与三角形的两个点的交线组成的角度分别设为j1,j2,j3，只要j1+j2+j3>360就不在三角形范围中。

4. 水平/垂直交叉点数判别法 （适用于任意多边形）

注意到如果从P作水平向左的射线的话，如果P在多边形内部，那么这条射线与多边形的交点必为奇数，如果P在多边形外部，则交点个数必为偶数（0也在内）。所以，我们可以顺序考虑多边形的每条边，求出交点的总个数。还有一些特殊情况要考虑。假如考虑边(P1,P2)，
1)如果射线正好穿过P1或者P2,那么这个交点会被算作2次，处理办法是如果P的从坐标与P1,P2中较小的纵坐标相同，则直接忽略这种情况
2)如果射线水平，则射线要么与其无交点，要么有无数个，这种情况也直接忽略。
3)如果射线竖直，而P0的横坐标小于P1,P2的横坐标，则必然相交。
4)再判断相交之前，先判断P是否在边(P1,P2)的上面，如果在，则直接得出结论：P再多边形内部。

实现：

语法：result=insidepolygon(Point *polygon,int N,Point p);
参数：
*polygon： 多边形顶点数组
N： 多边形顶点个数
p： 被判断点
返回值： 0：点在多边形内部；1：点在多边形外部
注意：
若p点在多边形顶点或者边上，返回值不确定，需另行判断
需要 math.h
源程序：
#define MIN(x,y) (x < y ? x : y)
#define MAX(x,y) (x > y ? x : y)

typedef struct {
double x,y;
} Point;

int insidepolygon(Point *polygon,int N,Point p)
{
int counter = 0;
int i;
double xinters;
Point p1,p2;

p1 = polygon[0];
for (i=1;i<=N;i++) {
p2 = polygon[i % N];
if (p.y > MIN(p1.y,p2.y)) {
if (p.y <= MAX(p1.y,p2.y)) {
if (p.x <= MAX(p1.x,p2.x)) {
if (p1.y != p2.y) {
xinters = (p.y-p1.y)*(p2.x-p1.x)/(p2.y-p1.y)+p1.x;
if (p1.x == p2.x || p.x <= xinters)
counter++;
}
}
}
}
p1 = p2;
}

if (counter % 2 == 0)
return(OUTSIDE);
else
return(INSIDE);
}