1

Given the coordinates of a polygon, I found many algorithms to detect if a point is in a polygon - for example: [1] and [2]. But none of these algorithms are able to detect if the point lies on the vertices of this polygon. For example I have a polygon:

|---------------------|
|                     |
|                     |
|---------------------|

My point is in the right upper corner. I want an algorithm that tells me whether the point is inside the polygon. How can I do this?

4

2 回答 2

1

除了处理与浮点 不完全匹配但足够接近的问题外，相同的算法应该适用于两者。
只需在多边形内部选择一个点，创建从测试点到内部点的测试线段，然后，对于多边形中的每个线段，确定测试线段是否与该多边形线段相交，要计为相交，请计算相交多边形段的一端开，另一端闭合，即如果交点与多边形的起点完全相同，则计算它，但如果与终点完全相同，则不计算它。您需要这样做，以便当测试线段与多边形顶点相交时，您只能将其视为与顶点任一侧的两个线段之一相交。

那么如果测试点在多边形内，则相交的数量为偶数，如果在多边形外，则为奇数。

于 2013-07-08T13:45:53.810 回答
1

刚刚在这里找到了解决方案。这非常简单，[1]中的代码已经实现a并且b已经实现。可以在此处找到源代码的其他信息。

const float EPSILON = 0.001f;

bool IsPointOnLine(Point linePointA, Point linePointB, Point point) 
{
   float a = (linePointB.y - linePointA.y) / (linePointB.x - linePointB.x);
   float b = linePointA.y - a * linePointA.x;
   if ( fabs(point.y - (a*point.x+b)) < EPSILON)
   {
       return true;
   }

   return false;
}
于 2013-07-09T09:14:39.563 回答