c++ - 如何在 kd-tree 中表示线段

Question

我有大量的二维线段。我想用 kd-tree 结构表示它们，然后在附近找到特定线段的线段。关于如何用 kd-tree 做到这一点的任何想法？

Answer 1

该段应该在它相交的每个 kd-tree 叶子中。也就是说，假设一条线段由一对点表示(p1, p2)，您应该在 kd 树节点中存储对该线段的引用。这条线段应该在它所经过的每个kd-tree节点中，这部分不同于处理点时，每个点只存储在1个kd树节点内。

拆分 kd 树节点时，您在水平或垂直线上拆分。如果至少一个端点在左子树中，则线段在“左”子树中。同样对于右子树。

您应该通过使用线段的端点执行类似于点查询的操作来查找附近。也就是说，查看查询端点附近的所有 kd-tree 叶子。

然后对于这些 bin 中的潜在线段，您可以通过查看从查询端点到候选线段的垂直线的长度来进行精确的长度比较，反之亦然（将候选线端点与查询线进行比较）。

此处回答了如何执行此操作的详细信息：点和线段之间的最短距离。你应该做 4 次测试，一条线的端点到另一条线，反之亦然，并取最小值。注意忽略点投影到线段之外的情况的距离。

这是可行的，因为线不会弯曲，因此两条线之间的最近点必须位于端点之一。

Answer 2

您不能使用段实现 kd-tree。kd-tree 是专门为 k 向量空间设计的，段不是向量空间的一部分。想法是 kd-tree 使用超平面来划分 kd-space，如果您不在 kd-vector 空间中，那并不理想。

但是，您需要的可能是 Bounding Volume Hierarchy，https: //en.wikipedia.org/wiki/Bounding_volume_hierarchy ，这是一种用于碰撞检测的技术。