二维平面上点与多边形位置关系判断

要判断点是否落在多边形内部，图形学书上给出了三种解决方法，一种是针对凸多边形的叉乘法，二是角度和判别法，三是水平/垂直交叉点数判别法。由于后两种可以针对任意多边形，故权衡之后我用了最简单最直接的角度和判别法。

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非常的简单。只需要把水平和垂直方向上的最大最小值找出来就可以了。

---

本文属Span Zhang（张友邦）原创，转载请注明出处。

中国原创分形艺术、中国原创分形软件第一站

---