1

i have to find all interior points in a polygon. I used the following function, to check every point (x,y), but for some points returns true even if the point is exterior or is on the edge of the polygon. 

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 = trueif

于 2012-08-24T15:28:55.083 に答える
1

I don't see how your algorithm could work as a general point inside polygon test.

Take a look here for working algorithms: How can I determine whether a 2D Point is within a Polygon?

于 2012-08-24T16:05:04.180 に答える