c++ - kdツリーで線分を表す方法

Question

2Dには膨大な数の線分があります。それらすべてをkd-tree構造で表現し、特定の線分の近くの線分を見つけたいと思います。kd-treeでこれを行う方法について何かアイデアはありますか？

Answer 1

セグメントは、交差するすべての kd-tree リーフにある必要があります。つまり、線分が点のペアで表されるとしましょう(p1, p2)。この線分への参照を kd ツリー ノードに格納する必要があります。この線分は、通過するすべての kd ツリー ノードにある必要があります。この部分は、各ポイントが 1 つの kd ツリー ノード内にのみ格納されるポイントを処理する場合とは異なります。

kd ツリー ノードを分割するときは、水平線または垂直線で分割します。端点の少なくとも 1 つが左サブツリーにある場合、線分は「左」サブツリーにあります。右側のサブツリーについても同様です。

ライン セグメントの端点を使用してポイント クエリに似た操作を行うことで、近くを見つける必要があります。つまり、クエリ エンドポイントの近くにあるすべての kd ツリー リーフを調べます。

次に、これらのビンの潜在的なセグメントについて、クエリの端点から候補のセグメントまでの垂線の長さ、およびその逆を調べることで、正確な長さの比較を行うことができます (候補の線の端点をクエリの線と比較します)。

これを行う方法の詳細は、ここで回答されています: Shortest distance between a point and a line segment。1 つの線から他の線へのエンドポイント、およびその逆の 4 つのテストを実行し、最小値を取る必要があります。点が線分の外側に投影される場合の距離を無視するように注意してください。

これが機能するのは、線が曲がらないためです。そのため、2 つの線の間の最も近い点は端点の 1 つにある必要があります。

Answer 2

セグメントを使用して kd-tree を実装することはできません。kd-tree は k ベクトル空間用に特別に設計されており、セグメントはベクトル空間の一部ではありません。アイデアは kd-tree で、超平面を使用して kd-space を分割します。kd-vector 空間にいない場合、それは理想的ではありません。

ただし、衝突検出に使用される手法であるバウンディング ボリューム階層 ( https://en.wikipedia.org/wiki/Bounding_volume_hierarchy )が必要になる場合があります。