dre*_*rew 10 algorithm computational-geometry
我问这个问题是出于问题,因为我的快速和肮脏的实现似乎已经足够好了.但是我很好奇什么是更好的实现.
我有一个真实世界数据的图表.没有重复的X值,X值在图表上以一致的速率递增,但Y数据基于实际输出.我想以编程方式从任意给定点P找到图上最近的点.我正在努力寻找一种有效(即快速)的算法来做到这一点.我不需要确切的最近点,我可以找到一个"接近"最近点的点.
显而易见的懒惰解决方案是增加图中的每个点,计算距离,然后找到距离的最小值.然而,理论上这对于大型图表来说可能很慢; 对我想要的东西来说太慢了.
由于我只需要一个近似的最近点我想象理想的最快方程将涉及生成最佳拟合线并使用该线来实时计算该点的位置; 但这听起来像是一个潜在的数学头痛,我不打算接受.
我的解决方案是一个hack,只能因为我认为我的点P不是任意的,即我假设P通常接近我的图线,当发生这种情况时,我可以从考虑中划掉远处的X值.我计算与P共用X坐标的线上的点的接近程度,并使用该点与P之间的距离来计算可能更接近点的最大/最小X值.
我不禁觉得应该有一个更快的算法然后我的解决方案(这是有用的,因为我假设99%的时间我的点P将是一个接近线的点).我尝试使用谷歌搜索更好的算法,但发现很多算法不太合适,以至于在所有不合适的算法混乱中很难找到我想要的东西.那么,这里有没有人有一个更有效的建议算法？请记住,我不需要一个完整的算法,因为我的工作符合我的需要,我只是好奇什么是正确的解决方案.
小智 2
如果您可以使用数据结构，那么用于空间搜索（包括最近邻）的一些常见数据结构是......
r 树有多种变体。它与 B+ 树非常密切相关，但叶节点中的项目（点）具有不同的排序（取决于变体）。
Hilbert R 树基于 Hilbert 曲线使用严格的点排序。希尔伯特曲线（或者更确切地说是它的概括）非常擅长对多维数据进行排序，因此空间中邻近的点通常在线性排序中是邻近的。
原则上，希尔伯特排序可以通过对简单的点数组进行排序来应用。其中的自然聚类意味着搜索通常只需要搜索数组中的几个相当短的跨度 - 复杂的是您需要计算出它们是哪些跨度。
我曾经有一个关于进行希尔伯特曲线排序计算的好论文的链接，但我把它弄丢了。基于格雷码的排序会更简单，但在聚类方面不太有效。事实上，格雷码和希尔伯特曲线之间存在着深刻的联系——我丢失的那篇论文大量使用了格雷码相关的函数。
编辑- 我发现该链接 - http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.133.7490