1

我必须找到多边形中的所有内部点。我使用以下函数来检查每个点 (x,y)，但对于某些点，即使该点位于外部或位于多边形的边缘，也会返回 true。

bool IsInside(int no_vert,float *vertx, float *verty, float testx, float testy)
{
  int i;
  int j;
  bool c=false;
  for (i = 0, j = no_vert-1; i < no_vert; j = i++) 
  {
      if ( ((verty[i]>testy) != (verty[j]>testy)) && (testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]) )
      {
         c = true;
      }
  }
  return c;
}
4

3 回答 3

3

你想做的不是测试

testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i])

但关系保持不变（即总是<或总是>）。

做到这一点的常见方法是（未经测试，不需要特殊情况下的平等）

bool result = true;
bool sign = ((xt-x[n-1])*(y[0]-y[n-1]) < (yt-y[n-1])*(y[0]-y[n-1]));
for (i = 0; result && i < no_vert; i++) 
{
   if (sign != ((xt-x[i])*(y[i]-y[i-1]) < (yt-y[i-1])*(y[i]-y[i-1]))
      result = false;
}
return result;

顺便说一句，这仅适用于凸多边形。

于 2012-08-24T15:55:51.393 回答
1

您的问题可能由于舍入错误而发生。即使一个点位于多边形的边缘（或非常靠近边缘但仍在外部），您确定它是否在内部的方法由于使用有限精度而受到数值误差的影响。换句话说，在这样的测试中得到错误答案是正常的（我建议你阅读浮点运算）。

我建议您不要严重依赖这种类型的精确验证，而是编写代码并开发可以处理这种误报/否定的算法。这种东西在计算几何中无处不在。

编辑：我认为另一个可能的错误是你应该有c = !c而不是c = true在if块内。

于 2012-08-24T15:28:55.083 回答
1

我看不出您的算法如何作为多边形测试中的一般点工作。

在这里查看工作算法： 如何确定 2D 点是否在多边形内？

于 2012-08-24T16:05:04.180 回答