计算到路径的距离

Question

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

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

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

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

我不一定在寻找完整的解决方案,但任何指针和想法都将受到赞赏.

Answer 1

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

\n\n

这是一个简单的例子：

\n\n

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

\n\n

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

\n\n

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

\n