计算到路径的距离

| 我有一组形成路径的要点。我想确定从任何给定点到该路径的最小距离。路径可能看起来像这样：

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

其中第一个值为x坐标，第二个为y坐标。路径是开放式的（不会形成闭环），并且由点之间的直线段组成。所以，给定一点，例如。 [90, 84]，如何计算该点到路径的最短距离？我不一定要寻找一个完整的解决方案，但是任何建议和想法都将不胜感激。

已邀请:

7 个回复

傻零凰死授

可以构造这样一种病理情况，其中最接近点P的线段连接两个点，这些点本身比路径中的任何其他点都远离P。因此，除非我遗漏了一些非常微妙的内容，否则必须计算到每个线段的距离，以获取到路径的最短距离。这是一个简单的示例：

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

给定点（10,1），最接近路径的距离将是沿线段（1,3）-（20,3）的点（10,3），但这两点距离更远（10,1）比路径中的任何其他点都好。因此，我不认为找到每个线段的距离并取最小的天真的算法没有捷径可走。

亥套惟间连

最好的办法是从一条线中找到最接近的点（制作路径）以测量距离并沿路径继续前进（并以最短距离存储该点）。

笛驮型迸

从点C到线段AB的距离是平行四边形ABCC'的面积。

部窖空

所以，我只是想了一秒钟。 erekalper已经发布了点和线之间的距离。但是，此公式的问题在于它假定行的长度是无限的，而您的问题并非如此。只是问题的一个示例：假设一条从（0,0）到（0,1）的直线和一个坐标为（0,10）的点。上面发布的公式将返回o距离为0，因为如果延长线，它将达到该点。不幸的是，在您的情况下，行的结尾为（0,1），因此距离实际上为9。因此，我的算法将是：检查直线端点处的角度是否<= 90°。如果是这样，则此路径的最短距离将可以通过已发布的公式进行计算。如果不是，则最短距离是到端点之一的距离。对路径的所有部分执行此操作，选择最小值

骂陋冠

点和线之间的距离由下式给出： d = |（x_2-x_1）（y_1-y_0）-（x_1-x_0）（y_2-y_1）| / sqrt（（x_2-x_1）^ 2-（y_2-y_1）^ 2），这是点积的扩展，其中（x_0，y_0）是该点的坐标，而（x_1，y_1）＆（x_2，y_2）是该线的端点。为每组点计算该值非常简单，然后确定哪一个是最低的。我并不确信这样做不是更优雅的方法，但是我并不知道。虽然我很想看看这里是否有人回答！编辑：对不起，这里的数学看起来很杂乱，没有格式化。这是该方程式的示意图，效果很好：（摘自MathWorld-Wolfram网络资源：wolfram.com）另一编辑：如Chris在他的帖子中所指出的，如果点是共线的，即行是由（0,0）-（0,1）定义的，而点是由（0 ，10）。如他所解释的，您需要检查以确保所查看的点实际上不在线本身的“扩展路径”上。如果是，那么它就是更近的端点与该点之间的距离。全部归功于克里斯！

豆兢

首先，您需要找出到每个线段的最短距离，然后选择最小距离。计算最短距离时，需要找出线段中最近的点。如果最近的点不在起点和终点之间，则必须使用距离作为起点或终点（以最近的那个为准）。此页面包含一些您可能需要的公式。

街茬

您需要使用线性代数（抖动）来计算从点到每条线的距离。这是描述数学的文章的链接：http://mathforum.org/library/drmath/view/55501.html 这是一个相当不错的图书馆。您需要查看称为PointSegmentDistance的方法。线段显然是一条直线，该直线从一个点开始，到第二个点结束，而一条直线有两个点，但在无限远处连续。

要回复问题请先登录或注册

计算到路径的距离

7 个回复

发起人

language_agnostic

geometry

math

问题状态

计算到路径的距离

与内容相关的链接

7 个回复

发起人

language_agnostic

geometry

math

问题状态