問題タブ [space-partitioning]

ベジエ パッチを三角形に変換する処理を行った後、ペインターのアルゴリズムを使用して投影された三角形を描画するために、バイナリ スペース パーティションを実行する必要があります。

ウィキペディアからアルゴリズムを実装し、数学に大いに役立ちました。

しかし、チャーリー・ブラウンの木を作っているのです! つまり、ほとんどのノードには完全に空のブランチが 1 つあります。全体の戦略はすべて間違っています。ティーポットは本質的に球形であるため、形状全体は、特定のコンポーネント三角形の 1 つの「側面」にのみ存在します。

だから私は、リンゴの芯のように配置された平面を分割する必要があると考えています:すべてがy軸の線を通過します。しかし、私はちょっと本から外れていますね。ティーポットを分割する最良の方法は何ですか?

これが私の bsp-tree ジェネレーターです。リンクされた質問に投稿された他の機能を使用します。

編集：dictstackoverflowを避けるための余分なジャグリング。完全なプログラムはこちらから入手できます( mat.psとteapotが必要です)。数値出力は、構築中のツリー ノードの深さを示します。

出力：

3 次元空間に多くのポイント (+100,000) があります。最近傍および範囲クエリを使用する必要があります。最初に kdtree (k=3) を使用しましたが、各ポイントには速度属性があります。彼らの場所は静的ではなく、場所を変えます。問題はここから始まります。古い位置を使用して最近傍および範囲クエリを実行するのは簡単です。しかし、速度に応じて新しい位置を計算する必要があります。新しい場所を計算した後、最も近い隣人を見つけて範囲内を検索する必要があります。

ポイントの場所が変わるたびに kdtree を更新する必要がありますが、コストがかかります。それは私を遅くします。何か提案はありますか、またはこの状況のた​​めのより良いデータ構造はありますか?

周期的な境界条件を持つ D 次元空間に N ポイントの点群があります。ここで、N は 500 から 10^8 の範囲で、D は 1 から 20 の範囲です。一緒。点群の各点について、その点に最も近い k 個を見つける必要があります。また、各ポイントからの距離、特に maxnorm 距離内にいくつのポイントが存在するかを調べる必要もあります。どのポイントが半径内にあるかを知る必要はありませんが、いくつあるかはわかりませんが、追加すると便利です。

私は kd-trees を試しましたが、それらはラッピング境界を処理しません。また、より大きなツリーの場合、複製は実行できません。さらに、高次元では遅くなります。

Vantage Point Trees に出会い、いくつかのコードを試してみましたが、kd ツリーよりも低速です。私が見つけたコードは再帰的な検索方法を使用していますが、バッチ処理はありません。プラス面の 1 つは、ラッピング条件をネイティブに処理できるため、重複する必要がないことです。

反復アプローチに変換し、バッチ検索ができるかどうかを確認することで、VP ツリーからさらにパフォーマンスを引き出すことができるかどうかを確認しようとしていますが、考えがありました。これらのデータ構造はすべて、任意のクエリ ポイントの最近傍を見つけるために機能しますが、クエリ ポイントはポイント クラウド内のポイントに制限されています。この制限により、よりパフォーマンスの高い構造が可能になる可能性があると思います（おそらくある種のナビゲーションメッシュですか？）。これを処理する構造を検索しようとしましたが、私のgoogle-fuは失敗しています。だから、誰かが次を処理できるデータ構造を知っているかどうか疑問に思っています:

• 500 ～ 10^8 ポイントなど、少数および多数のポイントを処理する
• 最大 20 次元を処理
• 周期的な境界で作業する (つまり、平らなトーラス)
• maxnorm距離で作業します（ソフト要件。ユークリッドは、手動で選別できる潜在的なリストを提供できますが、maxnormが優先されます）
• クエリ ポイントまでの k-NN を検索し、クエリ ポイントまでの距離でいくつのポイントが存在するかを検索できます
• クエリ ポイントは構造内のポイントであり、任意のポイントではありません
• クエリはバッチ処理できます。つまり、点群のすべての点について k 番目の NN を見つける必要があります。また、各点 i について、d[i] 内にいくつの点が存在するかを調べる必要があります。つまり、各ポイントには異なる検索半径があります。
• 挿入または削除をサポートする必要はありません。

ありがとう

各領域に意味のある要素がばらばらになるように、ポリゴンを領域 (より大きなポリゴン) に「分割」/サブセット化するという問題に直面しています。

たとえば、次のリージョン/ポリゴンがあります。ある時点で、1 つの領域 (ここでは R1 としましょう) の形状しかわかりません。L3 が R1 に属することは明らかです。L1、L2、P1 はどうですか？それらの周りにバウンディング ボックスを作成し、南東座標 (minX と minY) が R1 に属しているかどうかを確認することを考えました。このように、L1 は R2 と交差していなくても、R2 に属します。

この種のアルゴリズムについて何を調べる必要があるか、またはこの空間分離の問題を解決する方法について具体的な考えはありますか?