3

在 2D 几何中有n 个随机点,对于每个点,p我需要找到 4 个(如果不存在,则更少)最近的点( qa, qb, qc, qd),其中qa是最近的左上点,qb是最近的右上点,qc是最接近的左下点,qd是最接近点p的右下点。具有相同的x坐标被认为是左,具有相同的y坐标被认为是底部。

存储点坐标及其最近邻引用的最佳数据结构是什么?什么算法最快或执行得最多?

注意:这个问题远远超过最近邻算法,因为每个点需要 4 个相邻点。

4

2 回答 2

1

您可以尝试空间填充曲线和四叉树数据结构。空间填充曲线将 2 维减少到 1 维,并且在 2 个网格的功率下效果最佳。四叉树将平面分成 4 个四边形。空间填充曲线是采用 2 个变量并给出 1 个数字作为结果的数学函数。它也可以有 3,4,5 个变量,但最简单的是 2。因为它给出 1 个数字并接受 2 个变量,所以它可以帮助解决二维或更多维度的问题。

  1. http://social.technet.microsoft.com/wiki/contents/articles/9694.tuning-spatial-point-data-queries-in-sql-server-2012.aspx
  2. https://www.google.com/search?q=nearest+neigbor+search+space+filling+curve

在此处输入图像描述

于 2012-07-18T23:33:51.517 回答
1

使用 k-dim 树索引(在这种情况下 k=2),因此是四叉树。这应该允许您有效地搜索您的点的左、右、上和下空间。您可能可以为此在 dmbs 中制定一个查询,但从概念上讲,我会搜索点自己的“四边形”,然后根据四边形中点的位置,我们可以知道我们是否在一个方向上找到了最近的点。然后我们知道要搜索其余点的四边形。

由于您对每个点都执行此操作,因此您知道存在对称性,即点 P1 将 P2 作为最近的左邻,因此 P2 将 P1 作为最近的右邻。所以相应地更新点对象。

于 2012-07-19T00:50:39.430 回答