KD ツリーを使用してポイントを保存し、別の特定のポイントに近いポイントの一部をすばやく反復処理できることを知っています。ラインに似たようなものがあるのだろうかと思っています。
3Dの一連の行 L (そのデータ構造に格納される) と別の「クエリ行」q が与えられた場合、q に「十分に近い」L 内のすべての行をすばやく反復できるようにしたいと考えています。私が使用しようとしている距離は、2 つの点 u と v の間の最小ユークリッド距離です。ここで、u は最初の線上のある点で、v は 2 番目の線上のある点です。その距離を計算することは問題ではありません (外積に関する優れたトリックがあります)。
たぶん、皆さんは良いアイデアを持っているか、論文や説明などを探す場所を知っているでしょう...
TIA、s。
もう 1 つのオプション (ディスクベースのデータベース システムでの空間インデックス作成に最も一般的に使用されるオプション) は、R-Treeです。KD ツリーよりも実装が少し複雑ですが、一般的に高速であると考えられており、ラインとポリゴンのインデックス作成に問題はありません。
これにも KD-Tree を使用できます。
ポイントではなく、プリミティブで機能する KD-Tree を構築することができます。多くのレイ トレーサーは、トライアングル ヒット テストを大幅に高速化するためにこれを行っています。私が見た中で最も適切な説明は、このレイ トレーシング チュートリアルにあります。
100% 正確ではありませんが、潜在的に高速な解決策は、線分ごとにポイントのリストを保持し、これらを標準のポイントベースの KD ツリーに挿入することです。最も近い点を見つけて、線分でタグ付けし、それを使用して最も近い線を取得します。粗雑ですが、多くの場合、他のオプションに比べて非常に高速です。「コツ」は、セグメントに沿ったポイント間に大きなスペースを維持する (高速) と、セグメントをより多くのポイントに分割する (低速ですが、より正確) の適切なバランスを見つけることです。