计算到路径的距离
我有一组形成路径的点。我想确定从任何给定点到这条路径的最小距离。该路径可能如下所示：
points = [
[50, 58],
[53, 67],
[59, 82],
[64, 75],
[75, 73]
];
其中第一个值是 x 坐标，第二个值是 y 坐标。该路径是开放式的（不会形成闭环）并且由点之间的直线段组成。
所以，给定一个点，例如。 [90, 84]，如何计算从该点到路径的最短距离？
我不一定要寻找完整的解决方案，但任何指示和想法将不胜感激。
I have a set of points that form a path. I would like to determine the minimum distance from any given point to this path. The path might look something like this:
points = [
[50, 58],
[53, 67],
[59, 82],
[64, 75],
[75, 73]
];
where the first value is the x coordinate and the second the y coordinate. The path is open ended (it will not form a closed loop) and is made of straight segments between the points.
So, given a point, eg. [90, 84], how to calculate the shortest distance from that point to the path?
I'm not necessarily looking for a complete solution, but any pointers and ideas will be appreciated.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（7）
可以构建病态情况，其中距点 P 最近的线段连接两个点，而这两个点本身比路径中的任何其他点距 P 更远。因此，除非我错过了一些非常微妙的东西，否则您必须计算到每个线段的距离以获得到路径的最短距离。
这是一个简单的示例：
给定点 (10,1)，到路径的最近距离将是到点 (10,3)，该点沿着线段 (1,3)-(20,3)，但是这两个点比路径中的任何其他点距离 (10,1) 更远。
所以我不相信寻找到每条线段的距离并取最小值的简单算法有任何捷径。
It is possible to construct pathological cases in which the closest line segment to a point P connects two points which are themselves farther from P than any other points in the path. Therefore, unless I am missing something very subtle, you must calculate the distance to each line segment to get the shortest distance to the path.
Here is a simple example:
Given point (10,1), the closest distance to the path would be to the point (10,3), which is along the line segment (1,3)-(20,3), but those two points are farther from (10,1) than any other point in the path.
So I don't believe there are any shortcuts to the naïve algorithm of finding the distance to each line segment and taking the minimum.
最好的办法是找到距离一条线最近的点（形成路径）测量距离并沿着路径移动（并存储最短距离的点）。
The best thing would be to find the closest point from a line (making the path) measure the distance and move on along the path (and store the point for shortest distance).
点C到线段AB的距离是平行四边形ABCC'的面积。
The distance from a point C to a line segment AB is the area of the parallelogram ABCC'.
所以，我想了一下。 erekaper 已经发布了点和线之间的距离。然而，这个公式的问题在于它假设直线具有无限长度，但您的问题并非如此。举一个问题的例子：假设有一条从 (0,0) 到 (0,1) 的简单直线和一个坐标为 (0,10) 的点。上面发布的公式将返回 0 的距离，因为如果延长线，它会碰到该点。不幸的是，在你的情况下，线结束于 (0,1)，因此距离实际上是 9。
因此我的算法是：检查线端点处的角度是否 <= 90°。如果是这样，则可以通过已发布的公式计算该路径的最短距离。如果不是，则最短距离是到端点之一的距离。对路径的所有部分执行此操作，选择最小值
So, I just though about it for a second. erekalper already posted the distance between a point and a line. However, the problem with this formula is that it assumes the line has infinite length, which is not the case for your problem. Just an example for the problem: Assume a simple line that goes from (0,0) to (0,1) and a point with coordinates (0,10). The formula posted above would return o distance of 0, because if you extend the line it would hit the point. Unfortunately, in your case the line ends at (0,1), thus the distance is actually 9.
Thus my algorithm would be: Check if the angles at the endpoints of your lines are <= 90°. If so, the shortest distance for this path will be computable by the formula already posted. If not, the shortest distance is the distance to one of the endpoints. Do this for all parts of the path, choose the minimum
点和线之间的距离由下式给出：
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) 的点。正如他所解释的那样，您需要检查以确保所查看的点实际上不在线条本身的“扩展路径”上。如果是，那么它只是较近端点和该点之间的距离。一切都归功于克里斯！
The distance between a point and a line is given by:
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),
which is an expansion of the dot product, where (x_0, y_0) are the coordinates of the point, and (x_1, y_1) & (x_2, y_2) are the endpoints of the line.
It would be pretty simple to calculate this for each set of points, and then just determine which one is the lowest. I'm not unconvinced there's not a more elegant way to do so, but I'm not aware of it. Though I'd love to see if someone here answers with one!
Edit: Sorry that the math in here looks so messy without formatting. Here's an image of what this equation looks like, done nicely:
(from MathWorld - A Wolfram Web Resource: wolfram.com)
Another edit: As Chris pointed out in his post, this doesn't work if the points are in-line, i.e., if the line is defined by (0,0)-(0,1) and the point by (0,10). Like he explains, you need to check to make sure that the point being looked at isn't actually on the "extended path" of line itself. If it is, then it's just the distance between the closer endpoint and the point. All credit to Chris!
首先，您需要找出到每个线段的最短距离，然后选择最小距离。计算最短距离时，需要找出线段中最近的点。如果最近的点不在起点和终点之间，则必须使用到起点或终点的距离（以最近者为准）。
此页面包含您可能需要的一些公式。
First you need to find out shortest distance to each line segment and then you choose the smallest distance. When you calculate the shortest distance, you need to find out the nearest point in the line segment. If the nearest point is not between the start and end point, you must use the distance to start or end point (whichever is the nearest).
This page has some formulas that you are likely to need.
您需要使用线性代数（shivers）来计算从该点到每条线的距离。
以下是描述数学的文章的链接：链接
这是一个非常好的库。您需要查看名为
PointSegmentDistance的方法。 线段显然是一条从一个点开始到第二个点结束的线，而线有两点但继续无穷大。You need to use linear algebra (shivers) to calculate the distance from the point to each of the lines.
Here is a link to an article that describes the math: Link
And here is a pretty good library. You need to look at the methods called
PointSegmentDistance. A segment is apparently a line that begins at one point and ends at the second point, whereas a line has two points but continue in infinity.