我有一组由两点定义的段。给定一个点，我怎样才能发现离该点最近的段？
我已经编写了一个算法来计算点和线段之间的距离。无论如何计算每个段的距离然后选择距离最短的段并不是很有效:(
由于这些段代表街道，这实际上是一个反向地理编码问题，所以我希望这个问题有众所周知的解决方案......
多谢！
问问题
1608 次
1 回答
4
使用网格、kd-tree、四叉树或类似的二进制空间划分方法。然后，从您的点所在的树单元开始，开始探索线段，直到从该点到包含该线段的单元的距离大于目前找到的最小距离。
http://en.wikipedia.org/wiki/Binary_space_partitioning
（当然，这是假设路段/街道变化很少，但您有很多点要定位）。
于 2010-08-06T12:57:03.463 回答