問題タブ [octree]

3D 空間でパスファインディングを実行するために使用したい octree があります。特定のノードの近くにあるノードを簡単に見つけられるようにするために、モートン コードを使用してノードを並べ替えています。うまく機能しているようです。取得したノードのサブセットは、比較的近くにクラスター化されています。私が苦労しているのは、ノードの直接の隣人を取得する効率的な方法を見つけることです。

ツリーの以前のバージョンでは、葉がすべて同じサイズのノードで、必要なサイズになるまで、ツリーを細分化していました。これにより、各ノード間に一貫したオフセットがあったため、隣接ノードを簡単に見つけることができました。そのため、ノードを見つけると予想される位置でモートン コードを再計算し、コードに基づいてノードを取得することができました。しかし、ジオメトリがあまりない領域 (たとえば、8 つの空の子を取得する場所) ではツリーを分割しないことで、ツリーをより効率的にしようとしています。その結果、特定のノードが持つ可能性のあるネイバーの数も、ネイバーのサイズもわかりません (2 のべき乗であることを除いて)。

私の最初の考えは、配列内のいずれかの方向で近くのノードを検索することでした。これは機能しますが、すべての隣接ノードを取得することを保証するにはあまりにも広いネットをキャストする必要があり、大量のノードを評価するのに時間を費やしていました。それは私には必要ありません。簡単なテストでは、アレイ内のいずれかの方向に 50 個のノードがあっても、すべての近隣ノードを取得できる保証はないことがわかりました。

ツリーは静的であるため、上記のブルート フォース メソッドを使用してノードの隣接ノードを 1 回生成し、隣接ノードを保存することができます。しかし、これによりプログラムの初期ロード時間が許容レベルを超えて増加する可能性があるのではないかと心配しています. 隣人をリアルタイムで見つけることができるアルゴリズムはありますか?

編集：探しているものと試したことを明確にするために質問を言い換えました。

現在、Barnes-Hut octree を作成しようとしていますが、これを適切に行う方法をまだ完全には理解していません。ここのスレッド、この記事、その他のスレッドを読みました。すべてのノードに内部の粒子のインデックスに関する情報が含まれている場合、および空のノードを保存し続ける場合、ツリーを作成する方法を理解していると思います。しかし、あなたがしたくない場合は？最後に必要な情報のみが得られるようにツリーを作成する方法: たとえば、空でないすべてのノードの単極子と四重極。正直なところ、私は非常に多くの異なる試みを行ったので、今では完全に混乱しています. 各ノードには何を含める必要がありますか? そのようなものの疑似コードは何でしょうか?

PS ところで、単極子と四極子では違うのですか？つまり、単極子を計算するためにノード内の粒子に関する正確な情報は必要ないと想像できますが (ノードの全質量にすぎません)、4 倍の場合は?

前もって感謝します！

PS ちなみに、関係があればジュリア語を使用します。

Cypher を使用して Neo4j で octree 構造を作成したいと考えています。以下の図のようなものを作成したいと思います。

各ノードと関係を「手動で」作成することなく、これをどのように実装できるかについてのアイデアはありますか?