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