algorithm - 带方向的最近邻算法（左/右/上/下）

Question

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

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

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

Answer 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

Answer 2

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

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