data-structures - 行を kd ツリーに最適に格納する方法

Question

ポイントを保存するために kd-trees が伝統的に使用されていることは知っていますが、代わりにラインを保存したいと考えています。kd ツリーの分割とすべての交点で線を分割するのが最善でしょうか? または、最近傍を見つけるためにエンドポイントだけを kd-suffice に保存しますか?

Answer 1

kd ツリー自体は、点オブジェクト用に設計されています。箱、球体、またはこのようなものでさえありません。を保存する6dツリーを何とか使用できると思いますminx, maxx, miny, maxy, minz, maxz。しかし、それを正しく照会する方法については完全にはわかりません。

ここでは、 R* ツリー (ウィキペディア)を選択することをお勧めします。それは実際に空間拡張を持つオブジェクト用に設計されています。関連する出版物を調べると、複雑なオブジェクトのさまざまな近似を実験していました。たとえば、それらを三角形化すること、外接球、バウンディング ボックスを使用すること、そして興味深いことに、5 コーナー ポリゴンが場合によっては最高のパフォーマンスを提供する IIRC を使用することが報われるかどうかなどです。

とにかく、R*-tree ファミリーは興味深い選択かもしれません。

Answer 2

まあ、交差点で線を分割する必要があります。そうしないと、木の葉の重みで問題が発生します。

一方、木を走査するために SAH やその他のアルゴリズムを使用しない場合は、kd 木の独自のアイデアを自由に使用できます。ただし、従来のアルゴリズムに縛られている場合は、行を分割する必要があります。木の各葉に重みがあるという理由だけでそれを行う必要があります（あなたの場合、それはその中の線の長さに依存すると思います）。

また、線を分割しないと、葉の重みも間違ってしまいます。いいえ、行を分割しない場合は、行が属する両方のリーフでそれらを複製する必要があります。

Answer 3

kd ツリーを使用する必要がありますか? 拡張されたプリミティブの場合、bv ツリーの方が効率的かもしれません。