c++ - 从一组最接近直线的点中找到点的最快算法是什么？

Question

我有:
- 一组已知大小的点(在我的例子中，只有 6 个点)
- 以 x = s + t * r 为特征的线，其中 x、s 和 r 是 3D vector

我需要找到最接近给定线的点。实际距离对我来说并不重要。

我查看了几个看似相关的不同问题(包括 this 一个)，并知道如何在我的高中数学课上解决这个问题。但是我无法在不计算每个距离的情况下找到解决方案，而且我确信必须有更好/更快的方法。性能在我的应用程序中绝对至关重要。

还有一件事:所有数字都是整数(点的坐标以及 s 和 r vector 的元素)。同样，出于性能原因，我希望将 float 学运算保持在最低限度。

Answer 1

您必须至少处理每个点一次才能知道它们的距离。除非你想用不同的线多次重复这个过程，否则简单地计算每个点的距离是不可避免的。所以算法必须是 O(n)。

既然你不关心实际距离，我们可以对点距计算做一些简化。确切距离由 ( source ) 计算:

d^2 = |r⨯(p-s)|^2 / |r|^2

其中 ⨯ 是叉积，|r|^2 是 vector r 的平方长度。由于 |r|^2 对所有点都是常数，我们可以在不改变结果的情况下从距离计算中省略它:

d^2 = |r⨯(p-s)|^2

比较近似平方距离并保持最小值。这个公式的优点是你可以用整数做任何事情，因为你提到所有坐标都是整数。