21

線が凸多角形と交差するかどうかを検出する O(n) アルゴリズムは、多角形のエッジが線と交差するかどうかをチェックし、交差の数が奇数か偶数かを調べます。

O(log n) アルゴリズムなど、漸近的に高速なアルゴリズムはありますか?

4

5 に答える 5

19

lhfの答えは正しいに近いです。これは、彼の問題を修正するバージョンです。

多角形に頂点 v0、v1、...、vn が反時計回りにあるとします。点 x0 と x1 が直線上にあるとします。

2 つの点に注意してください。まず、2 つの線の交点を見つける (およびその存在を判断する) ことは、一定の時間で実行できます。第 2 に、点が線の左側にあるか右側にあるかを一定の時間で判断できます。

O(log n) アルゴリズムを取得するために、lhf と同じ基本的な考え方に従います。基本的なケースは、ポリゴンに 2 つまたは 3 つの頂点がある場合です。これらは両方とも一定時間で処理できます。

線 (v0,v(n/2)) が線 (x0,x1) と交差するかどうかを判断します。

ケース 1: 交差しない。

この場合、関心のある線は多角形を分割する線の左側または右側にあるため、多角形のその半分に再帰することができます。具体的には、x0 が (v0,v(n/2)) の左側にある場合、右側の「半分」にあるすべての頂点 {v0, v1, ... v(n/2)} は同じ側にあります。 (x0,x1) であり、多角形のその「半分」には交差がないことがわかります。

ケース 2: 交差します。

このケースは少しトリッキーですが、交差点をポリゴンの「半分」に一定時間で絞り込むことができます。3 つのサブケースがあります。

ケース 2.1: 交点は点 v0 と v(n/2) の間にある

完了です。ラインはポリゴンと交差します。

ケース 2.2: 交点が v0 に近い (つまり、v0 側のポリゴンの外側)

線 (x0,x1) が線 (v0,v1) と交差するかどうかを判断します。

そうでない場合は、線はポリゴンと交差しません。

もしそうなら、交差点を見つけてください。p が線 (v0, v(n/2)) の右側にある場合は、多角形の右半分 {v0, v1, ..., v(n/2)} に再帰します。それ以外の場合は再帰します左の「半分」{v0、v(n/2)、... vn}。

この場合の基本的な考え方は、ポリゴン内のすべてのポイントがライン (v0、v1) の片側にあるということです。(x0, x1) が (v0, v1) との交点の片側で (v0, v(n/2)) から離れている場合。その辺にはポリゴンとの交差がないことがわかっています。

ケース 2.3: 交点が v(n/2) に近い場合

このケースは、ケース 2.2 と同様に処理されますが、v(n/2) の適切な近傍を使用します。

完了です。レベルごとに、これには 2 つの線の交点、左右のチェック、および点が線上のどこにあるかを判断する必要があります。各再帰は、頂点の数を 2 で割ります (技術的には少なくとも 4/3 で割ります)。したがって、O(log n) の実行時間を取得します。

于 2010-12-22T08:22:29.210 に答える
3

この記事は明確な O(log n) ソリューションを提供すると思います。指定された線に垂直な方向の極値を見つけます。

于 2011-04-26T09:14:35.783 に答える
2

境界ボックスが役立つ場合があります。

アフィン空間の凸部分は、そのすべてのエンベロープ超平面の交点であることを思い出してください。エンベロープ超平面のサブセットの交点のみを考慮することによって、多角形の近似値を取得できます (「境界凸多角形」と読みます)。ラインとこの近似値の交点を見つけ、必要に応じて調整してください。

交差点の数が少ないと予想される場合、これはすべてうまく機能します。

于 2010-12-21T10:04:39.030 に答える
1

線の左側にある点 A と右側にある別の点を見つけるだけです。残りの問題は、そのポイントをすばやく見つける方法です。

于 2010-12-21T13:45:29.020 に答える
0

凸多角形からランダムな 2 点 A と B を取得します。

  • それらが線の反対側にある場合、それらは交差します
  • それらが同じ側にある場合、両方のポリゴン部分（時計回りのABとBAとしましょう）で次のようにします。
    • A を通る線 l に平行な線を作成します
    • 多角形上の l からの最大距離にある点を見つけます。これは、最初は単調に非減少であり、次に単調に非増加である関数の最大値を見つけることと同じです。これは、三項探索によって O(log n) で実行できます


これらの2つの最も遠い点が線の異なる側にある場合、線は多角形と交差し、そうでない場合は交差しません

。ところで、O(log n)でも実際の交点を見つけることができます。

于 2010-12-21T19:24:06.017 に答える