11

私は100から200ポイント（x、y）のセットを持っています。どれが他の特定の距離内にあるかを確認する必要があります。特定の距離は、プログラム全体で固定されています。たとえば、50です。ポイント1がポイント5、7、25、90、96、105などの範囲内にあるとします。同様に、ポイント2は23、45などの範囲内にあります... x、y座標で位置を特定するためのオブジェクトの保存

ここではQuadTreeが提案されていますが、これを使用して、外接する長方形内のすべてのポイントを取得できます。しかし、境界円内のすべてのポイントを取得するにはどうすればよいですか？最大距離内で緯度/経度に最も近いポイントを返す方法がありますが、距離内のすべてのポイントを取得するにはどうすればよいですか？ http://openmap.bbn.com/doc/api/com/bbn/openmap/util/quadtree/QuadTree.html#QuadTree(float、float、float、float、int）

1つの方法は、ツリーから各ポイントを取得したときに削除し、nullになるまで、最も近いポイントを再度クエリすることです。それが唯一の方法ですか？

4

1 に答える 1

22

(x, y) を中心とする半径 r の円があり、円内にある四分木内のすべての点を見つけたいとします。1つのアイデアは次のとおりです。

  1. 円に内接する境界ボックスを作成します。これは円を含む最小の長方形で、左上隅 (x - r, y - r) と右下隅 (x + r, y + r) があります。円内の任意の点も正方形内にある必要がありますが、その逆はできません。

  2. その四角形にある一連の点について四分木を照会します。これらの点を P とします。

  3. 長方形内にあることがわかっている P 内の各点について、それが円内にもあるかどうかを確認します。これを行うには、その点から (x, y) までの距離が r 以下かどうかを確認します。つまり、点 (x 0 , y 0 ) が与えられた場合、(x - x 0 ) 2 + (y - y 0 ) 2を計算し、この値が r 2以下の場合、点サークルに含まれています。

これは非効率に見えるかもしれませんが、実際には非常に高速です。円の面積に対する正方形の面積の比率は、4 / π ≈ 1.27 です。つまり、ポイントがある程度均等に分散されていると仮定すると、必要なポイントよりも約 27% 多いポイントしか見つかりません。

于 2011-07-14T20:40:30.730 に答える