2

点のセットPとセグメントのセットSが与えられた場合、任意のセグメントの指定された距離d内のすべての点を効率的に見つける方法はありますか？次数のブルートフォース比較なしO(|P||S|)？

線分のセット間のすべての交差点のBentley-Ottman検索が実行さO(n log n)れます。この問題は同様のフレーバーを持っているため、同様のパフォーマンスが可能かどうか疑問に思います。

C++での寛容なオープンソース実装のボーナスポイント。

4

1 に答える 1

0

ポイント上にボロノイ図ネットワークを構築します。各セルに、すべての隣接セルへのポインターを保持させます。何よりも可能です。

  1. ポイントが与えられたら、それがどのセルにあるかを見つけます。単純に、ネットワークの左下隅からポイントまで線を引き、そのコーナーセルから開始して、ポイントに近づき、それが入っているセルを見つけます。

  2. 線が与えられたら、それが交差するすべてのセルを見つけます。些細なことです。

  3. 線とオフセット距離を指定して、コリドー内のすべてのセルを見つけます。2から続きます。

  4. 等

ボロノイネットワークは、空間ナビゲーションとクエリのサポート構造として機能します。すべての操作はローカルであるため、線形の複雑さです。ダイアグラムが作成された後。:)

于 2012-09-20T07:44:52.003 に答える