我在离散空间中有一组点,坐标是N个double[]阵列。
例如:
点T1 = {1.3,2.5,4-3} -> double[] x= {1.3},double[] y= {2.5},double[] z= {4.3}
然后,我有一个函数,它在连续的空间中从一个给定的点在所有方向上产生一个偏移量,我需要在我的矩阵/双数组中找到最接近的匹配。
问题是我不能对这些数组进行排序并应用二进制搜索,因为Point的组件在排序之后很可能没有相同的索引。
是否有一些数据结构/算法可以用来避免迭代搜索最近的匹配点?
是否最好组织点,以便有一个数组实例描述整个点,而不是每个组件的数组?
编辑
它看起来是理想的解决方案是使用k-d树,如注释中所建议的那样。计算机科学算法不是我的领域,因此,在我研究这个主题时,用k-d树或一些替代方法来演示最小示例的答案将是最有帮助的。
发布于 2015-06-12 06:58:40
如果我理解你的问题,你有N个大小为M的浮子阵列,每个阵列包含一个点在N维空间中沿轴的坐标。您也有一个浮点数,并且您希望找到浮点数的索引,其中浮点数最接近组件之一。如果这是正确的,我将创建一个数组,其元素是对( value,index),其中的值是组件之一,索引带来了该组件所属点的索引。然后,可以使用值作为sorting.key对数组进行排序。此时,您可以使用浮点数进行二进制搜索。
当然,只有在需要搜索多个浮点数的情况下,构建和排序数组才有意义,因为排序将采用O( K= )和K= N*M,然后搜索将使用O (log )。如果您只需要搜索一个浮点数,那么最好对数组进行完整搜索,这将是O (K)。
https://stackoverflow.com/questions/30796618
复制相似问题