math - 计算到路径的距离

Question

我有一组形成路径的点。我想确定从任何给定点到这条路径的最小距离。路径可能如下所示:

points = [
    [50, 58],
    [53, 67],
    [59, 82],
    [64, 75],
    [75, 73]
];

其中第一个值是 x 坐标，第二个值是 y 坐标。路径是开放式的(不会形成闭环)并且由点之间的直线段组成。

所以，给定一点，例如。 [90, 84] ，如何计算从该点到路径的最短距离？

我不一定要寻找一个完整的解决方案，但任何指示和想法将不胜感激。

Answer 1

可以构建病理情况，其中最接近点 P 的线段连接两个点，这两个点本身比路径中的任何其他点都离 P 更远。因此，除非我遗漏了一些非常微妙的东西，否则您必须计算到每个线段的距离以获得到路径的最短距离。

这是一个简单的例子:

(5,1)-(4,2)-(1,3)-(20,3)-(15,2)-(14,1)

给定点 (10,1)，离路径最近的距离是到点 (10,3)，它沿着线段 (1,3)-(20,3)，但是这两个点离(10,1) 比路径中的任何其他点。

所以我不相信找到到每个线段的距离并取最小值的朴素算法有任何捷径。