确定点是沿着一条线还是非常接近的算法

Question

好的，我有一个使用地图系统来绘制线条的应用程序。每条线 A、B 均以纬度/经度格式定义。当用户单击地图时，给我的只是一个点 C，用户单击的位置为纬度/经度格式。我想让用户能够通过单击来选择地图上的线路。问题是，由于缩放级别不同，用户很难精确地沿着线单击。我能期望的最好结果是它们在我定义的某个阈值距离内点击。仅给出此信息，我如何确定用户已单击或相当接近某行？

我对算法有一个粗略的想法，但我还没有充实它，而且我不确定这是否是最有效的方法。由于屏幕上随时可能有很多行，因此算法需要相当快。

到目前为止我想到的是首先检查 AC 和 BC 的距离。如果任一距离大于 AB，则用户没有单击该线。如果它通过了这项检查，那么我会计算角度 CAB 和 CBA。如果C正好在线上，那么两个角度都应该为0，我想，我的三角函数有点生锈了。否则，为了确定 C 是否“足够接近”，我将选择两个计算角度中最小的一个，并查看它是否低于某个预定义的阈值。

我是走在正确的道路上还是偏离了正轨？还有更好的想法吗？

Answer 1

您也可以直接计算该点到任何直线的距离。 维基百科文章为您提供了详细信息以及一些（伪）代码。

在您的情况下，您还必须单独考虑终点。即，您首先必须计算参数t（请参阅上面的文章）并检查它是否在0 到AB 长度的范围内。然后，如果距离低于预定义的量，则用户确实单击了该线，否则不单击。

您的案例中的公式如下所示：

(C - (A + t * (B-A))) * (B-A) = 0

=> t = (C.x - A.x) * (B.x - A.x) + (C.y - A.y) * (B.y - A.y) / ((B.x - A.X) * (B.x - A.x) + (B.y - A.y) * (B.y - A.y))

如果 t 低于 0 或高于 1，则用户不会单击该行。否则（即 t 介于 0 和 1 之间），您可以使用此值 t 计算距离 d：

d = dist(C, A+t*(B-A)) = sqrt( (C.x - A.x - t * (B.x - A.x))^2 + (C.y - A.y - t * (B.y - A.y))^2) 

If d > 低于某个预定义的阈值，您可以假设用户单击了您的线路。