判断点是否在多边形内

ゝ一纸荒年。 2022-03-25 08:40 289阅读 0赞

再经典不过的算法了：

// 功能：判断点是否在多边形内  
// 方法：求解通过该点的水平线与多边形各边的交点  
// 结论：单边交点为奇数，成立!

//参数：  
// POINT p 指定的某个点  
// LPPOINT ptPolygon 多边形的各个顶点坐标（首末点可以不一致）  
// int nCount 多边形定点的个数

BOOL PtInPolygon (POINT p, LPPOINT ptPolygon, int nCount)  
\{  
　　int nCross = 0;

for (int i = 0; i < nCount; i++)  
　　\{  
　　　　POINT p1 = ptPolygon\[i\];  
　　　　POINT p2 = ptPolygon\[(i + 1) % nCount\];

// 求解 y=p.y 与 p1p2 的交点

if ( p1.y == p2.y ) // p1p2 与 y=p0.y平行  
　　　　　　continue;

if ( p.y < min(p1.y, p2.y) ) // 交点在p1p2延长线上  
　　　　　　continue;  
　　　　if ( p.y >= max(p1.y, p2.y) ) // 交点在p1p2延长线上  
　　　　　　continue;

// 求交点的 X 坐标 --------------------------------------------------------------  
　　　　double x = (double)(p.y - p1.y) \* (double)(p2.x - p1.x) / (double)(p2.y - p1.y) + p1.x;

if ( x > p.x )  
　　　　　　nCross++; // 只统计单边交点  
　　\}

// 单边交点为偶数，点在多边形之外 ---   
  　return (nCross % 2 == 1);  
\}

**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再多边形内部。

射线算法

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

2.         以point为起点，以无穷远为终点作平行于X轴的直线**line(**x,y; -∞,y)；

**3.        ** 循环取得(for(i=0;i<n;i++))多边形的每一条边**side**(xi,yi;xi+1,yi+1)，且判断是否平行于X轴，如果平行continue，否则，i++；

4.         同时判断point(x,y)是否在**side**上，如果是，则返回1(点在多边形  
上)，否则继续下面的判断；

5.         判断线**side**与**line**是否有交点，如果有则count++，否则，i++。

6.         判断交点的总数，如果为奇数则返回0（点在多边形内），偶数则返回2（点在多边形外）。

![1346835270_4955.jpg][]

代码：

/\* 射线法判断点q与多边形polygon的位置关系，要求polygon为简单多边形，顶点逆时针排列

如果点在多边形内：返回0

如果点在多边形边上：返回1

如果点在多边形外：返回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<Point> 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(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 ) );

// 判断线段相交

bool Intersect(LineSegment L1, LineSegment L2)

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)

);

// 判断点在多边形内

bool InPolygon(const Polygon& polygon, Point point)

int n = polygon.size();

int count = 0;

LineSegment line;

line.pt1 = point;

line.pt2.y = point.y;

line.pt2.x = - INFINITY;

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

// 得到多边形的一条边

LineSegment side;

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++;

\} else if( IsOnline(side.pt2, line) ) \{

if( side.pt2.y > side.pt1.y ) count++;

\} else if( Intersect(line, side) ) \{

count++;

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

else \{ return 2;\}

[1346835270_4955.jpg]: https://img-my.csdn.net/uploads/201209/05/1346835270_4955.jpg

判断点是否在多边形内

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关判断一个点是否在多边形内部

相关射线法判断地图上点是否在多边形内

相关点在多边形内算法，JS判断一个点是否在一个复杂多边形的内部

相关 java判断某个点是否在所画范围内(多边形/圆形)

相关 python 计算一个点是否在多边形内（转）

相关 java怎么判断一个点是否在一个多边形内

相关判断点是否在多边形内

相关 C++ 点在多边形内算法——判断一个点是否在一个复杂多边形的内部

相关 java判断某个点是否在所画范围内(多边形)

相关 java判断点在多边形内