我有：
- 一组已知大小的点(在我的情况下，只有6分(
- 以x = s t * r为特征的线，其中x，s和r是3D矢量
我需要找到最接近给定线路的点。实际距离对我来说并不重要。
我看了几个似乎相关的不同问题(包括这个问题(，并且知道如何从高中数学课上的纸上解决这个问题。但是我在不计算各个距离的情况下找不到解决方案，而且我确信必须有更好/更快的方法。性能对于我的应用绝对至关重要。
还有一件事：所有数字都是整数(S和R向量的点和元素的坐标(。同样，出于绩效原因，我想将浮点数学保持在最低。
您必须至少一次处理每个点才能知道它们的距离。除非您想用不同的行重复多次该过程，否则简单地计算每个点的距离是不可避免的。因此，算法必须为o(n(。
由于您不在乎实际的距离，因此我们可以简化点距离计算。确切的距离由(来源(计算：
d^2 = |r⨯(p-s)|^2 / |r|^2
其中 ⨯是交叉产品，而 |r|^2是向量r的平方长度。由于|r|^2对于所有点都是恒定的，因此我们可以从距离计算中省略它而不会改变结果：
d^2 = |r⨯(p-s)|^2
比较近似的正方形距离并保持最小值。此公式的优点是您可以使用整数来完成所有操作，因为您提到所有坐标都是整数。
我恐怕您无法逃脱少于6个距离的计算(如果可以的话，至少要排除一个点 - 包括最近的一个(。p>查看预处理是否有意义：线路固定和点是否有所不同？考虑旋转坐标以使线保持水平。
几乎没有要点，这是您的瓶颈。测量在热点处的地方，重新设计算法/数据表示，调整编译器优化，编译以组装并弄乱。严格按照该顺序。
乔恩·本特利(Jon Bentley(的"写作有效程序"(可悲的是，不可能打印出来(和"编程珍珠"(第二版(充满了有关实际编程的建议。