2

無限 (倍精度) の 2D 平面上に一連の点があります。

このセットの凸包が与えられた場合、入力セットのすべての点から比較的離れた凸包の内側にあるいくつかの点をどのように見つけることができますか?

下の画像では、黒い点は元のセットの一部であり、ハッチングされた領域は、半径 R で「成長」した場合にすべての点が占めるスペースを表しています。

オレンジ色のポイントは、私が取得したいものの例です。それらがすべての黒い点から比較的離れている限り、正確にどこにあるかは問題ではありません。

最遠点検索 http://en.wiki.mcneel.com/content/upload/images/point_far_search.png

更新: delaunay アルゴリズムを使用して大きな空の三角形を見つけることは、このための優れたアプローチのようです: Delaunay ソリューション http://en.wiki.mcneel.com/content/upload/images/DelaunaySolutionToInternalFurthestPoints.png

4

2 に答える 2

1

これは素朴なアルゴリズムです:

  1. 凸形状内の点のリストを取得します。
  2. それらのうち、他の点までの最小距離を見つけます。
  3. それぞれの R 値ですべてのポイントをランク付けします
  4. 上の x ポイントを選択します。

（2）については、これを半径検索と考えても、各点から他の点までの距離を計算することになります。これは、点が別の点の特定の半径内にあるかどうかを調べることは、距離を見つけることと同じことだからです。ポイントの間。

検索を最適化するには、スペースをグリッドに分割し、各ポイントをグリッド位置に割り当てます。次に、上記 (2) の検索では、最初に同じ正方形とその周囲の 8 つの正方形内がチェックされます。別のポイントまでの最小距離が同じ正方形内にある場合は、その値を返します。それが 8 つのうちの 1 つからのものであり、その距離が 9 の外側の点がより近くなる可能性がある場合、それらの 9 の外側のグリッド位置の次のアウトラインをチェックして、9 の内側で見つかったものよりも近いものがないか確認する必要があります。 .

于 2009-09-25T00:30:59.777 に答える
1

これは、 KD-Treeを使用して解決できる問題の良い例です ... Numerical Recipes 3rd Addition にいくつかの良いメモがあります。

比較的孤立した点の位置を見つけようとしている場合...おそらく、最大のクワッド要素の中心が良い候補になるでしょう。

複雑さは、KD ツリーを作成するための O(n log^2 n) になります...そして、クワッド サイズの並べ替えられたリストの作成は O(n Log n) になります。多数のポイントでも妥当なようです (もちろん、要件によって異なります)。

于 2009-09-25T01:04:32.860 に答える