algorithm - 在没有已知方程的图中找到最近点的有效算法

Question

我问这个问题是出于好奇，因为我快速而肮脏的实现似乎已经足够好了。不过，我很好奇更好的实现方式是什么。

我有一张真实世界数据的图表。图中没有重复的 X 值，X 值以一致的速率递增，但 Y 数据基于真实世界的输出。我想以编程方式从任意给定点 P 找到图形上最近的点。我正在尝试找到一种有效(即快速)的算法来执行此操作。我不需要确切的最近点，我可以选择“几乎”最近的点。

明显的惰性解决方案是递增图中的每个点，计算距离，然后找到距离的最小值。然而，对于大图来说，这在理论上可能会很慢；对于我想要的来说太慢了。

因为我只需要一个近似的最近点，所以我想理想的最快方程将涉及生成一条最佳拟合线并使用该线实时计算该点的位置；但这听起来像是一个潜在的令人头疼的数学难题，我不想承担。

我的解决方案是一个 hack，它之所以有效，是因为我假设我的点 P 不是任意的，也就是说，我假设 P 通常会靠近我的图形线，当这种情况发生时，我可以从考虑中划掉较远的 X 值。我计算与 P 共享 X 坐标的直线上的点有多近，并使用该点和 P 之间的距离来计算可能更近的点的最大/最小 X 值。

我忍不住觉得应该有一个比我的解决方案更快的算法(这只是有用的，因为我假设 99% 的时间我的点 P 将是一个接近直线的点)。我尝试在谷歌上搜索更好的算法，但发现很多算法不太合适，以至于很难在一堆乱七八糟的不合适算法中找到我要找的东西。那么，这里有没有人推荐更有效的算法？请记住，我不需要完整的算法，因为我已经满足了我的需求，我只是好奇正确的解决方案是什么。

Answer 1

如果将 [x,y] 点存储在 quadtree 中您将能够快速找到最近的一个(类似于 O(log n))。我认为这是您在不假设要点所在的情况下可以做的最好的事情。与其在这里重复算法，不如看看这个 link .

您的解决方案非常好，通过检查点在 y 中的变化情况，您不能计算出您需要检查的 x 轴上的点数的界限，而不是使用任意一个点。