ポリゴンが「厳密に」単純かどうかをテストするアルゴリズムを探しています。通常、テストには、ポリゴン セグメント間の交差のチェックが含まれます。しかし、ここでは、常にエッジとエッジの交差に該当するとは限らないケースをチェックしたいので、何を調べればよいかわかりません。
上の画像では、BC と D は単純な多角形ではありませんが、交差テストに失敗するのは D だけです。私の用語 (厳密に単純な意味で) も少しずれているかもしれませんが、この図は私の言いたいことを示していると思います。
1092 次
3 に答える
1
少なくとも共通点がある場合、2 つの線が交差するとします。
1 つのエッジを取り、他のエッジとの交点を数えます。持っている場合
- 交差点が 2 つある場合、左端と右端が 1 つずつあり、すべて問題ありません。
- 3 つ以上の交点がある場合、終点から始まる 3 つ以上のエッジ (ケース B)、中央のエッジの終点 (ケース C)、または別の線との交点 (ケース D) のいずれかです。
したがって、私の意見では、あなたの心配は根拠がありません。
しかし、ここでは、常にエッジエッジ交差に該当するとは限らない場合を確認したいので [...]
このアプローチはここでも機能します。
于 2012-04-01T21:08:00.927 に答える
0
これら 3 つのクラスの無効なポリゴンは、個別にチェックする必要があります。
ケース B:
ポリゴンに重複する頂点がないことを確認してください。
ケース C:
頂点がどの辺にも達していないことを確認してください。浮動小数点数を使用していると仮定すると、浮動小数点数が正確に等しいと評価される必要があるため、これは扱いにくいものになる可能性があります。EPSこれは、それらが互いの中にあることはできないと言うことで回避できますが、ほとんど無効である他のいくつかのポリゴンを無効にする可能性があります。本当に最高の精度が必要でない限り、私は個人的にEPS自分自身を使用します（その時点で私が何をすべきかわかりません）。
ケース D:
あなたが言ったように、これはエッジが交差しているかどうかを確認することで見つけることができます。
ケース E:
2 つのエッジがオーバーラップ (無限に多くの点で交差) し、それらの頂点はオーバーラップしません。
これが別のケースである必要があるかどうかはわかりませんが、この状況はケース D のチェックではキャッチされない可能性があります (ゼロで割ってしまうと思います)。したがって、2 つのエッジがまったく同じ線に対応していないことも確認する必要があります。
他のケースは今のところ考えられない
于 2012-04-01T20:43:17.990 に答える