6

我有一组由两点定义的段。给定一个点,我怎样才能发现离该点最近的段?

我已经编写了一个算法来计算点和线段之间的距离。无论如何计算每个段的距离然后选择距离最短的段并不是很有效:(

由于这些段代表街道,这实际上是一个反向地理编码问题,所以我希望这个问题有众所周知的解决方案......

多谢!

4

1 回答 1

4

使用网格、kd-tree、四叉树或类似的二进制空间划分方法。然后,从您的点所在的树单元开始,开始探索线段,直到从该点到包含该线段的单元的距离大于目前找到的最小距离。

http://en.wikipedia.org/wiki/Binary_space_partitioning

(当然,这是假设路段/街道变化很少,但您有很多点要定位)。

于 2010-08-06T12:57:03.463 回答