寻找众多线段中距离某点最近的线段的算法（反向地理编码）

Question

我有一组由两个点定义的线段。给定一个点，如何找到最接近该点的线段？

我已经编写了一个算法来计算点与线段之间的距离。然而，为每个线段计算这样的距离，然后选择距离最小的线段并不是真正有效的方法 :(

由于这些线段代表街道，因此实际上这是一个反向地理编码问题，所以我希望有人已经解决了这个问题...

非常感谢！

- Giorgio

---

这组段落是否以任何方式排序？ - Bart Kiers

这些线段是否重叠？您是指直线上的线段，还是例如球面上的线段？如果是后者，那么您的两个点如何定义该线段？（可能有不同的定义）无论如何，按照某些标准对线段进行排序通常会有所帮助。 - peterchen

@Giorgio：你找到那个算法了吗？能否分享或给我一个链接？非常感谢！ - Richard Le

Answer 1

使用网格、kd树、四叉树或类似的二进制空间划分方法。然后，从包含点的树单元格开始，探索线段，直到点到包含线段的单元格的距离大于迄今为止找到的最小距离为止。

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

（当然，这是建立在段/街道很少改变的情况下，但您有很多要定位的点。）

- Victor Nicollet

---

没有办法知道任何给定的线段是否与任何给定的分区相交，而不进行（至少）与点-线段距离相同的计算，因此任何分区方法只有在线段集满足某些条件时才可能更快（例如，最大线段长度<<分区尺寸）。 - MusiGenesis

@MusiGenesis：关键是使每个段成为构建树时所交叉的所有叶子的一部分。这样，如果其中一个叶子足够接近点，则会测试该段，如果没有叶子足够接近，则永远不会测试该段。由于树只构建一次，因此执行此操作的成本分摊在随后发生的所有请求中。 - Victor Nicollet

同意。我原以为每次都有不同的段落集。 - MusiGenesis