我有大量的二维线段。我想代表他们 kd-tree结构，然后通过线段找到附近的a 特定的线段。关于如何使用 kd-tree 执行此操作的任何想法？
最佳答案
该段应该在它相交的每个 kd-tree 叶子中。也就是说，假设一条线段由一对点 (p1, p2) 表示，您应该在 kd 树节点中存储对该线段的引用。这条线段应该在它经过的每一个kd-tree节点中，这部分不同于处理点时，每个点只存储在1个kd树节点内。
在拆分kd树节点时，是在水平线或垂直线上进行拆分。如果至少一个端点在左子树中，则线段在“左”子树中。右子树也类似。
您应该通过使用线段的端点执行类似于点查询的操作来找到附近。也就是说，查看查询端点附近的所有 kd-tree 叶子。
然后对于那些 bin 中的潜在线段，您可以通过查看从查询端点到候选线段的垂直线的长度来进行精确长度比较，反之亦然(将候选线端点与查询线进行比较).
这里回答了如何执行此操作的详细信息:Shortest distance between a point and a line segment .你应该做 4 次测试，一条线的端点到另一条线，反之亦然，取最小值。注意忽略点投影到线段外的情况的距离。
这是可行的，因为线不弯曲，所以两条线之间最近的点必须位于端点之一。
关于c++ - 如何在 kd-tree 中表示线段，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/14376679/