0

四分木を使用して分割している空間データ（平面上の（x、y）ポイント）があります。アイデアは、どのポイントが特定の（a、b）ポイントに隣接しているかを見つけることです。2つの間にある程度の（たとえばL）距離がある場合、ポイントは隣接しています。問題は、空間が周期的であるということです。つまり、ポイントがエッジに非常に近い場合（<L）、このポイントは反対側のエッジに近いポイントに隣接している必要があります。（この場合、周期的とは、平面が繰り返されることを意味します） 

|=================== | ===================|
|(a, b)         (c,d)| (a, b)      (c,d)  |
|                    |                    |
|  (e,f)             |   (e, f)           |
|               (h,i)|               (h,i)|
|=================== | ===================|
|(a, b)         (c,d)| (a, b)      (c,d)  |
|                    |                    |
|  (e,f)             |   (e, f)           |
|               (h,i)|               (h,i)|
| ================== | ===================|

つまり、ポイント（a、b）と（c、d）と（h、i）は隣接している必要があります。（a、b）の隣接点は、中心が（a、b）の半径Lの円の内側の点です。

論文、ハウツーはすべて大歓迎です。

ありがとう、

彼ら：

あなたの答えをありがとう、私はしばらくの間スタックオーバーフローをチェックしていません別のプロジェクトで忙しかったのですぐにあなたの答えをチェックします！どうもありがとう。

4

3 に答える 3

2

「検索円」を円周率 pi/2 の円グラフに分割してみませんか? テキストと単純な画像でこれを理解できるかどうか見てみましょう。

代替テキスト http://img168.imageshack.us/img168/8426/circleinquarters.gif

「円探索」を 4 つの「円グラフ」と見なすという考え方なので、C(a, b, L) で探索を行うときは、四分木を下に渡すときに円がそうでないことを考慮する必要があります。 t は四分木の左上隅と交差するだけなので、この場合、4 つの分岐に分岐する必要があります (この領域が周期的でない場合は、1 つだけではありません)。

于 2009-06-02T18:57:00.040 に答える
1 
xdist = min( (x1-x2) % px, (x2-x1) % px )

ここで、px は x 期間です。

ydist であり、残りは読者の演習として残されています :-)

于 2009-06-02T18:55:40.447 に答える
1

ルート レベルのみが定期的に複製されるため、四分木をそのままにしておく方が簡単に思えます。周期性を考慮して、(x+i*dx,y+j*dy,L)各リクエストに対して複数のリクエストを実行します(x,y,L)。クエリ ディスクがツリーのルート ノードと交差するように i,j をループします。

于 2009-06-02T19:01:49.360 に答える