出于好奇心,我想问这个问题,因为我的简单实现似乎已经足够好了。然而,我很好奇一个更好的实现会是什么样子。
我有一组真实世界数据的图形。图表中没有重复的X值,并且在整个图形上X值以一致的速率递增,但是Y数据基于真实世界输出。我想编程地从任意给定点P找到图形上最近的点。我正在寻找一种高效(即快速)的算法来实现这一点。我不需要最精确的最近点,我可以接受一个“几乎”最近的点。
显然的懒惰解决方案是逐个遍历图中的每个点,计算距离,然后找到最小距离。但是,对于大型图表,理论上可能太慢了;对于我想要的东西来说太慢了。
由于我只需要一个近似的最近点,我想象中最理想的最快公式涉及生成最佳拟合线并使用该线实时计算点应该在哪里;但这听起来像是一个潜在的数学头疼,我不打算接受。
我的解决方案是一个hack,它仅在我假定我的点P不是任意的情况下起作用,即我假定P通常会靠近我的图形线,并且当发生这种情况时,我可以将远离X值从考虑中排除。我计算了与P共享X坐标的线上的点有多接近,并使用该点与P之间的距离来计算可能更接近点的最大/最小X值。
我不禁感到应该有比我的解决方案更快的算法(仅因为我假设99%的时间我的点P已经接近该线)。我尝试谷歌搜索更好的算法,但找到的算法中没有完全符合要求的算法,所以在所有不适当的算法混杂的情况下很难找到我要找的东西。所以,这里是否有人有建议的算法可以更有效地实现?请记住,由于我的需求已得到满足,我不需要完整的算法,只是好奇应该是什么样的正确解决方案。