6

SCVT (Spherical Centroidal Voronoi Tesselation) を実装するプログラムを書いています。単位球上に分布する点のセットから始めます (ランダム点または等面積スパイラルのオプションがあります)。数百からおそらく 64K ポイントがあります。

次に、おそらく数百万のランダムなサンプル ポイントを生成する必要があります。各サンプルについて、セット内の最も近いポイントを見つけ、それを使用してそのポイントの「重み」を計算します。(この重みは、別の球面セットから検索する必要がある場合がありますが、そのセットは、アルゴリズムの任意の実行に対して静的なままです。)

次に、元のポイントを計算されたポイントに移動し、プロセスをおそらく 10 回または 20 回繰り返します。これにより、後で使用するボロノイ タイルの中心が得られます。

後で、ユーザーがクリックしたタイルを確認するために、特定のポイントの最近傍を見つける必要があります。これは上記の問題の中で自明に解決され、とにかく超高速である必要はありません。私が効率的である必要があるのは、単位球上の何百万もの最近傍です。ポインタはありますか？

ああ、私は x、y、z 座標を使用していますが、それは決まったものではありません。物事を単純化するように見えます。私も C を使用していますが、これは C に最も慣れているためですが、その選択にも執着していません。:)

サンプル ポイントにスパイラル パターンを使用することを検討しました。これにより、次の検索の良い出発点として、少なくとも最後に見つかったポイントの近傍が得られるからです。しかし、そうすると、どんなツリー検索も役に立たなくなりそうです。

編集：[申し訳ありませんが、タイトルとタグで明確だと思っていました。ランダムポイントを簡単に生成できます。問題は最近傍探索です。すべての点が単位球上にある場合の効率的なアルゴリズムは?]

4

7 に答える 7

3

あなたのポイントは、球全体に均一に分布しています。したがって、それらを球座標に変換して離散化することは非常に理にかなっています。最初に 2D グリッドを検索すると、最近傍の選択が球の小さな部分に一定時間で絞り込まれます。

于 2009-04-14T23:56:43.343 に答える
1

私は極から極へと球に沿って渦巻く曲線を考案しました (私は最初ではないと確信しています)。隣接する巻線からの距離は一定のままです（正しく行った場合）。z(-1南極から+1北極) の場合:

n = a constant defining a given spiral
k = sqrt(n * pi)

r = sqrt(z^2)
theta = k * asin(z)
x = r * cos(theta)
y = r * sin(theta)

傾斜がk/2_ _ _sqrt(4pi/n)dz/d(x,y)1/k

とにかく、k巻き間距離が球の最大のタイルをカバーするように設定してください。メイン セットのすべての点thetaについて、曲線上の最も近い点の を計算し、それらの番号で点のリストにインデックスを付けます。特定のテスト ポイントについて、その (theta曲線上の最も近いポイントの) を計算し、それをインデックスで見つけます。そこから外側 (両方向) に検索thetaし、現在の最近傍から離れた値まで検索します。その限界に達した後、その隣接点までの距離がテスト ポイントから次の隣接する巻線までの距離よりも短い場合、最も近い隣接点が見つかりました。thetaそうでない場合は、値をジャンプして2pi、同じ方法でその巻線を検索します。

批評？

于 2009-04-18T03:10:26.000 に答える
1

オクトリーと呼ばれるデータ構造にポイントを整理すると、近くのポイントを効率的に検索するのに役立つ場合があります。http://en.wikipedia.org/wiki/Octreeを参照

于 2009-04-14T09:59:57.363 に答える
0

KD Trieを使用すると、検索を高速化できます。エラーを許容できる場合は、パフォーマンスを大幅に向上させることもできます。ANNライブラリは、選択したεの範囲内で結果を提供します。

于 2009-04-13T21:04:56.040 に答える
0

ネイバー検索に関する記事は次のとおりです。http：//en.wikipedia.org/wiki/Nearest_neighbor_search 私の理解では、すべてのボロノイ中心を通過する簡単なアルゴリズムを使用して、ポイントと中心点の間の3D距離を計算できます。

distance_2 = (x - x_0)^2 + (y - y_0)^2 + (z - z_0)^2

ここで、（x_0、y_0、z_0）は関心のあるポイント（クリック）であり、{（x、y、z）}はボロノイ中心です。最短距離で最も近い中心が得られます。

于 2009-04-13T05:42:26.273 に答える
0

わかった。NEARPT3 http://www.ecse.rpi.edu/Homepages/wrf/Research/nearpt3/nearpt3.pdfアルゴリズムは、あなたの場合に役立つ可能性があります。そして、それはすべて、Nポイントに使用できるスペースの数によって異なります。O（N * logN）の場合、kDツリーベース（http://www.inf.ed.ac.uk/teaching/courses/inf2b/learnnotes/inf2b-learn06-lec.pdf）のようなアルゴリズムがあります。 O（logN）が最も近い点を見つけるために機能します。64Kポイントの場合Nlog_2N=約10^6であり、これは最新のコンピュータのメモリに簡単に収まります。

于 2009-04-14T05:40:50.623 に答える
0

四分木を作成するよりも簡単な別の可能性は、近傍行列を使用することです。

まず、すべてのポイントを 2D 正方行列に配置します (ポイントを極座標に変換することにより)。次に、完全または部分的な空間ソートを実行して、ポイントがマトリックス内で順序付けられるようにします。

小さな Y (またはファイ) を持つポイントは行列の一番上の行に移動でき、同様に、大きな Y を持つポイントは一番下の行に移動します。X (または theta) 座標が小さい点でも同じことが起こり、左側の列に移動する必要があります。そして対称的に、大きな X 値を持つポイントは右側の列に移動します。

空間的な並べ替えを行った後 (シリアルまたはパラレル アルゴリズムの両方で、これを達成する方法はたくさんあります)、点 P が実際に近傍行列に格納されている隣接セルにアクセスするだけで、特定の点 P の最も近い点を検索できます。

このアイデアの詳細については、次の論文 (PDF コピーをオンラインで見つけることができます) で読むことができます: Supermassive Crowd Simulation on GPU based on Emergent Behavior。

並べ替えの手順により、興味深い選択肢が得られます。ペーパーで説明されている偶奇転置ソートのみを使用できます。これは、実装が非常に簡単です（CUDAでも）。このパスを 1 回だけ実行すると、部分的な並べ替えが行われます。これは、マトリックスがほぼ並べ替えられている場合にすでに役立つ可能性があります。つまり、ポイントの動きが遅い場合は、多くの計算を節約できます。

完全な並べ替えが必要な場合は、そのような偶奇転置パスを数回実行できます (次の Wikipedia ページで説明されています)。

http://en.wikipedia.org/wiki/Odd%E2%80%93even_sort

于 2014-02-08T21:32:22.910 に答える