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

Question

我有：
-一组已知大小的点（在我的情况下，只有6个点）
-一条以x = s + t * r为特征的线，其中x，s和r是3D矢量

I need to find the point closest to the given line. The actual distance does not matter to me.

I had a look at several different questions that seem related (including this one) and know how to solve this on paper from my highschool math classes. But I cannot find a solution without calculating every distance, and I am sure there has to be a better/faster way. Performance is absolutely crucial in my application.

One more thing: All numbers are integers (coordinates of points and elements of s and r vectors). Again, for performance reasons I would like to keep the floating-point math to a minimum.

Answer 1

您必须至少处理一次每个点才能知道它们的距离。除非您想用不同的线多次重复此过程，否则不可避免地要简单地计算每个点的距离。因此算法必须为O（n）。

由于您不在乎实际距离，因此我们可以简化点距计算。精确的距离由（source）计算得出：

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

其中?，叉积|r|^2是向量的平方长度r。由于|r|^2对于所有点都是常数，因此我们可以在不更改结果的情况下从距离计算中忽略它：

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

比较近似的平方距离，并保持最小。该公式的优点是您可以使用整数来做所有事情，因为您提到所有坐标都是整数。