离x，y最近的一条线上的点

Question

离x，y最近的一条线上的点

6

可能重复：
如何判断一个点是否靠近某条线？

//Returns the point on the line traced from start to end which
//comes nearest to 500,000, 500,000. The points are scaled between
//1,000,000 and 0 from their original fp types.
Point closestToCentre(Point start, Point end);

有没有比逐个像素单步执行更快的方法？

能否有比我更敏捷的人展示他们的数学和几何才能呢？

_______编辑___________

谢谢Kris，这让我感到困惑：

[x; -a/bx-c/b]=[0; -c/b]-1/b[-b; a]x.

现在我明白了，它只是将向量（主要是y分量）分成两部分，这两部分组合起来得到相同的结果。然后我的旧部分分数脑细胞就兴奋了一分钟 :)

_______编辑_________

Jason Moore，感谢你的启发，以下是我正在做的事情，以图形方式呈现：

64x64 square with 2 sample lines each passing edge to edge and missing the centre by some distance

我希望您能更清楚地理解。

____编辑______

因此，我可以合理地期望从中心垂直于我的样本线取一条线，并将其延伸，但如何确定它们何时相交？

enter image description here

我认为Kris的方程页面是正确的选择。如果你们都告诉我这是一个两步过程。现在只需要两个同时方程，所以我可能不需要Kris的推导。

____编辑____

无论好坏，我不知道，但作为搜索引擎的stackoverflow的优点已经向我展示了几种研究途径。主要是我喜欢这里的第一个解决方案：点和线段之间的最短距离。

但为了自己证明这一点，我需要来自matti解决方案底部（但是倒数第二个）的链接：

http://www.topcoder.com/tc?d1=tutorials&d2=geometry1&module=Static

这个推导非常简单优雅，即使我也能够理解！

鉴于http://mathworld.wolfram.com/Point-LineDistance2-Dimensional.html。

- John

我想普遍存在的快速排序很快就要被耗尽了。不！它们已经排好序了！！离成功如此之近，但是…… - John

这是一个三角学问题。尝试在 http://math.stackexchange.com/ 上提问。 - Enigmativity

好吧，对于其他人来说可能是重复的问题。但是找到距离给定点最近的线上点与判断一个点是否靠近一条直线是两个不同的问题。你可以使用前者的答案来找到后者的答案，但值得注意的是，那个问题的选择解决方案并不能回答这个问题。 - Tatarize

2个回答

1

我认为最快的方法是一个两步过程:

假设你的线是无限长的，在通过（500,000，500,000）的垂直平分线上找到你的线的交点。
确保该点实际上在您的线上，否则寻找最接近的端点。

Kris的帖子非常好地涵盖了第一步，您只需要添加第二步的检查，因为您有一个线段，您就可以完美解决问题。

让点1=（x1，y1），终点2=（x2，y2）。然后包含这两个点的线是

y = (y2-y1)/(x2-x1) * (x-x1)+y1

通过（5e5，5e5）的perp。平分线是

y = (x1-x2)/(y1-y2) * (x-5e5)+5e5

你的点（x，y）是上述两个方程（或其中一个端点）的解（x，y）。这可能比mathworld链接更直接。请注意，当您的线条几乎垂直或几乎水平时，此解决方案会失败，而我认为mathworld解决方案样式不会失败，尽管我没有仔细查看。

- Sean

抱歉，这篇文章的冗长让我转向我的VC IDE和迭代解决方案。你提到的“2.确保该点实际上在你的线上，否则找到最近的端点。”还没有读Kris的链接，但听起来你似乎期望我在我的线上找到我的点，这是最不可能的。 - John

很抱歉如果我表达不清楚。第二步只是从三个候选点中选择最接近的点：在第一步中找到的点，或者两个端点中的一个。在这里没有涉及任何复杂的数学计算。如果以下条件为真：x < min(p1.x, p2.x) || y < min(p1.y, p2.y) || x > max(p1.x, p2.x) || y > max(p1.y, p2.y)，你必须从两个端点中选择正确的最接近点。 - Sean

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- justkris · Accepted Answer

这是将点投影到直线上的线性投影问题，可以通过一些向量技巧来解决，详细说明可见于MathWorld。该文章详细介绍了如何找到从点到线的最短距离，其中一个中间步骤是找到从点x,y到原始直线的垂线。相交这两条线将给出在直线上最接近x,y的点。

根据评论编辑：链接中的方程式（2）的作用是将向量转换为类似于y = mx + c的形式，使您能够快速轻松地读取梯度，从而可以轻松地计算出垂直梯度。