13

2D ポイントのコレクションがあり、入力ポイントが の凸包の内側にあるか外側にあるかSをテストする必要があります。qS

O(log(N))二分決定なので、決定木を使えば理論的には達成できると思っていました。

ただし、データを整理する方法と、アルゴリズムが実際に答えを得るためにどのように見えるかはわかりませんO(log(N))。

この考えを念頭に置いて調査していると、次のことがわかりました。

これら 2 つのケースをより迅速に見つけるにはどうすればよいでしょうか。二分探索。2 つのチェーンのポイントの最初の座標で x を検索するだけです。チェーン内にある場合は、頂点を通過する交差を見つけたことになります (また、交差の種類を慎重に判断する必要もありません)。x がチェーン内の頂点の座標でない場合、それに最も近い 2 つの値は、(x,y) からの光線が交差するセグメントを示します。したがって、点が時間 O(log n)で凸多角形にあるかどうかをテストできます。

ポイントが任意のポリゴン (または複数のポリゴンのどれ) にあるかどうかを、同じO(log n)の時間範囲内でテストできるデータ構造があることがわかりました。しかし、それらはもっと複雑なので、ここで説明する時間はありません。それらについては、ICS 164 のある時点で説明します。

( http://www.ics.uci.edu/~eppstein/161/960307.html )

アイデアはありますか：

  1. データ構造はどのように見えるべきO(log(N))ですか?
  2. アルゴリズムはどのように見えるべきですか?
4

6 に答える 6

4

最初にチェーンを 1 つだけ扱いましょう。(qx, qy)が線分の凸状チェーンの上にあるかどうかを確認します。

高価な部分は、x座標のリストをバイナリ検索して、クエリポイントよりも小さい最大のものを見つけることです。これに必要なのは、x順番にソートされたチェーンのポイントの配列だけです。次に、単純な「線の上の点」です。テスト。

次に、点が凸多角形内にあるかどうかを確認します。その凸多角形のエッジを上鎖と下鎖として表すと、上鎖の下のものと下鎖の上のものとの交点になります。つまり、2 つのバイナリ検索です。

（時計回りにソートされた順序などでポイントを取得した場合でも、二分探索または四点探索を使用して対数時間でポリゴン内の最小および最大の座標を見つけることができますx。したがって、事前に計算する必要さえありませんあなたがしたくない場合は、上部と下部のチェーン.)

編集：あなたの質問は、「ポ​​イントロケーションデータ構造はどのように見えますか?」として解析できることもわかりました。「効率的な内部/外部テストを可能にするために、凸包をどのように保存しますか?」ではなく、

インサイドアウトテストよりも、もう少し一般的な状況でポイントの位置を調べるのは自然なことです。があります

CGALは、いくつかの異なる方法でポイントの位置を特定できます。これは、実装しているアルゴリズムと、アルゴリズムが使用するコンピューターをよく理解している賢い人々によって書かれています。おそらく、まだ正しく機能するものをあまり高速に見つけることはできないでしょう。

そうは言っても、Haran と Halperinは CGAL のさまざまなアルゴリズムのパフォーマンスを比較しました。彼らは 2008 年の時点で最新のコンピューターを使用し、多くのテスト データを作成し、各テスト ケースで CGAL のさまざまなポイント ロケーション戦略を試しました。とりわけ、約 140 万のランダムに配置されたエッジのケースがあり、その最適なデータ構造は、ポイント ロケーション クエリに答えるのに約 190 マイクロ秒しか必要としません。

これは、典型的なポイント ロケーション アルゴリズムの複雑さを考えると非常に高速です --- 私にはできませんでした。そして理論は、それが O(log n) のように成長することを教えてくれます。ただし、その O(log n) は、並べ替えられた配列を検索するのにかかる O(log n) 時間よりも数桁遅くなります。計算幾何学を行うときは、このことを念頭に置いてください。定数は重要であり、多くの場合、それほど小さくはありません。

于 2013-06-13T17:24:52.290 に答える
1

これは、スイープ アルゴリズムを使用して実行できるはずです (水平方向のスイープ ラインを使用したラスタライズなど)。並べ替えられた頂点のエッジの構築は n*log(n) ですが、並べ替えが完了すると、ポイント q に基づいてスイープ ラインを設定し、スイープ ラインが交差するエッジを見つけることができます。

凸面の場合、スイープ ラインの凹面を気にする必要がないため、ラスタライズは単純化されます。

簡単なアウトラインは、ポリゴンを一周し、エッジ オブジェクトを構築し、ワインディングを使用して左側と右側を決定することです。各ポイントのすべての y 値は、並べ替えられたリスト (または配列、セット、マップなど) に入ります。

ポイント qy を使用して左右のエッジを検索すると、qx が左右の座標の間にあるかどうかを簡単に判断できます。最初に凸包を計算して、左側/右側が凸であることを確認できます。

（うわー、ラスタースキャン変換を探していたら、卒業した翌年の学部生のノートがここにありました。）

于 2013-06-13T20:24:41.880 に答える