如何在kd-tree中表示線段

Question

我有大量的2D線段。我想用 kd-tree結構來表示它們，然後通過線段找到 特定線段。有關如何使用kd-tree做到這一點的任何想法？

Answer 1

段應該位於它相交的每個kd樹葉中。也就是說，假設線段由一對點(p1, p2)表示，則應該在kd樹節點中存儲對此線段的引用。這個線段應該在它通過的每個kd-tree節點中，這部分不同於處理點時，其中每個點只存儲在1 kd樹節點內。

拆分kd樹節點時，可以在水平或垂直線上分割。如果至少有一個端點位於左側子樹中，則線段位於「左側」子樹中。對於正確的子樹同樣如此。

您應該通過做一些類似於線段端點的點查詢來找到附近。也就是說，查看查詢端點附近的所有kd-tree樹葉。

然後，對於這些分檔中的潛在分段，您可以通過查看從查詢端點到候選分段的垂直線的長度來進行精確的長度比較，反之亦然（將候選線端點與查詢進行比較線）。

如何做到這一點的細節在這裏回答：Shortest distance between a point and a line segment。你應該做4次測試，一行到另一行的端點，反之亦然，並取最小值。注意忽略投影點在線段外的情況的距離。

這可以工作，因爲線不曲線，所以兩條線之間的最近點必須位於其中一個端點。

Answer 2

你不能實現帶段的kd-tree。 kd-tree是專門爲k向量空間設計的，分段不是向量空間的一部分。想法是kd-tree使用超平面來分割kd-空間，如果你不在kd-向量空間中，那不是理想的。

但是，您需要的可能是Bounding Volume Hierarchy，https://en.wikipedia.org/wiki/Bounding_volume_hierarchy，這是一種用於碰撞檢測的技術。