在 2D 几何中有n 个随机点,对于每个点,p
我需要找到 4 个(如果不存在,则更少)最近的点( qa
, qb
, qc
, qd
),其中qa是最近的左上点,qb是最近的右上点,qc是最接近的左下点,qd是最接近点p的右下点。具有相同的x坐标被认为是左,具有相同的y坐标被认为是底部。
存储点坐标及其最近邻引用的最佳数据结构是什么?什么算法最快或执行得最多?
注意:这个问题远远超过最近邻算法,因为每个点需要 4 个相邻点。
在 2D 几何中有n 个随机点,对于每个点,p
我需要找到 4 个(如果不存在,则更少)最近的点( qa
, qb
, qc
, qd
),其中qa是最近的左上点,qb是最近的右上点,qc是最接近的左下点,qd是最接近点p的右下点。具有相同的x坐标被认为是左,具有相同的y坐标被认为是底部。
存储点坐标及其最近邻引用的最佳数据结构是什么?什么算法最快或执行得最多?
注意:这个问题远远超过最近邻算法,因为每个点需要 4 个相邻点。
您可以尝试空间填充曲线和四叉树数据结构。空间填充曲线将 2 维减少到 1 维,并且在 2 个网格的功率下效果最佳。四叉树将平面分成 4 个四边形。空间填充曲线是采用 2 个变量并给出 1 个数字作为结果的数学函数。它也可以有 3,4,5 个变量,但最简单的是 2。因为它给出 1 个数字并接受 2 个变量,所以它可以帮助解决二维或更多维度的问题。
使用 k-dim 树索引(在这种情况下 k=2),因此是四叉树。这应该允许您有效地搜索您的点的左、右、上和下空间。您可能可以为此在 dmbs 中制定一个查询,但从概念上讲,我会搜索点自己的“四边形”,然后根据四边形中点的位置,我们可以知道我们是否在一个方向上找到了最近的点。然后我们知道要搜索其余点的四边形。
由于您对每个点都执行此操作,因此您知道存在对称性,即点 P1 将 P2 作为最近的左邻,因此 P2 将 P1 作为最近的右邻。所以相应地更新点对象。