地图上最近的点

Question

我正在制作一个程序，您可以单击地图来查看其周围区域的“特写视图”，例如在 Google 地图上。

当用户单击地图时，它会获取他们单击位置的 X 和 Y 坐标。

假设我有一个布尔值数组，表示这些特写视图图片的位置：

public static boolean[][] view_set=new boolean[Map.width][Map.height];
//The array of where pictures are.  The map has a width of 3313, and a height of 3329.

程序搜索一个文件夹，其中图像以地图上拍摄位置的 X 和 Y 坐标命名。该文件夹包含以下图像（以及更多图像，但我只列出五个）：

2377,1881.jpg, 2384,1980.jpg, 2389,1923.jpg, 2425,1860.jpg, 2475,1900.jpg

这意味着：

view_set[2377][1881]=true;
view_set[2384][1980]=true;
view_set[2389][1923]=true;
view_set[2425][1860]=true;
view_set[2475][1900]=true;

如果用户单击 X 和 Y，例如 2377,1882，那么我需要程序找出哪个image 最接近（本例中的答案是 2377,1881）。

任何帮助将不胜感激， 谢谢。

Answer 1

对于这个问题，您的 boolean[][] 不是一个好的数据结构，至少如果它不是非常密集的话（例如，通常在周围 3×3 或可能有一个具有特写视图的点） 5×5 正方形）。

您需要一个具有最近邻搜索功能的二维地图。对于此目标来说，一个有用的数据结构是QuadTree。这是一棵4度树，用于表示空间数据。 （我在这里描述的是“带有点数据的区域四叉树”。）

基本上，它将一个矩形分成四个大小相等的矩形，并进一步细分每个矩形如果其中有多个点。

因此，树中的节点是以下之一：

• 空叶节点（对应于其中没有点的矩形）
• 只包含一个点的叶节点（对应于其中有一个点的矩形）
• 具有四个子节点的内部节点（对应于其中有多个点的矩形）

（在实现中，我们可以用其父节点中的空指针替换空叶节点。）

要找到一个点（或“点所在的节点”），我们从根源开始节点，查看我们的点是否在分界点的北/南/东/西，并转到对应的子节点。我们继续这个直到到达某个叶节点。

• 为了添加新点，我们要么得到一个空节点 - 然后我们可以将新点放在这里。如果我们最终到达一个已经有一个点的节点，请创建四个子节点（通过分割矩形）并将这两个点添加到适当的子节点。 （这可能是相同的，然后递归地重复。）

• 对于最近邻搜索，我们要么得到一个空节点 - 然后我们备份一个级别，并查看该父节点的其他子节点（比较每个距离）。如果我们到达其中有一个点的子节点，我们将测量搜索点到该点的距离。如果它小于到边或节点的距离，我们就完成了。否则，我们还必须查看相邻节点中的点，并比较这里的结果，取最小值。 （我认为，我们最多必须查看四个点。）

• 为了删除，找到一个点后，我们将其节点设为空。如果父节点现在只包含一个点，我们将其替换为单点叶节点。

搜索和添加/删除的时间复杂度为 O(深度)，其中最大深度受到 log((地图长度+宽度)/结构中两点的最小距离) 和平均值的限制深度或多或少取决于点的分布（例如到下一个点的平均距离）。

所需的空间取决于点的数量和树的平均深度。

这种数据结构有一些变体（例如，仅当节点中有超过 X 个点时才拆分节点，或者不一定在中间拆分），以优化空间使用并避免树的深度过大。

Answer 2

给定用户单击的位置，您可以使用 Dijkstra 搜索来搜索最近的图像。
基本上，您开始在单击位置周围越来越大的矩形中搜索图像。当然，您只需要搜索这些矩形的边界，因为您已经搜索了主体。一旦找到图像，该算法就应该停止。

伪代码：

int size = 0
Point result = default
while(result == default)
   result = searchRectangleBoundary(size++, pointClicked)

function Point searchRectangleBoundary(int size, Point centre)
{
    point p = {centre.X - size, centre.Y - size}
    for i in 0 to and including size
    {
        if(view_set[p.X + i][p.Y]) return { p.X + i, p.Y}
        if(view_set[p.X][p.Y + i]) return { p.X, p.Y + i}
        if(view_set[p.X + i][p.Y + size]) return { p.X + i, p.Y + size}
        if(view_set[p.X + size][p.Y + i]) return { p.X + size, p.Y + i}
    }
    return default
}

请注意，为了简洁起见，我省略了范围检查。

有一个小问题，但根据应用程序，这可能不是问题。它不使用欧几里得距离，而是使用曼哈顿距离。所以它不一定能找到最近的图像，而是最多找到 2 倍远的平方根的图像。

Answer 3

根据

• 您的评论，您有 350-500 个兴趣点，
• 您的问题表明您的地图宽度为 3313，高度为 3329
  • 我的计算器告诉我这代表大约 1100 万个布尔值

……你的处理方式是错误的。 @JBSnorro 的答案是一种在大海捞针（1100 万点）中找到针（350 点）的相当优雅的方法，但实际上，为什么首先要创建大海捞针呢？

根据我对您问题的评论，为什么不只使用 Pair类来表示坐标，将它们存储在一个集合中，然后扫描它们？它更简单、更快、消耗更少的内存，并且对于更大的地图来说更具可扩展性（假设兴趣点稀疏......鉴于它们是兴趣点，这似乎是一个明智的假设） ）。

..相信我，计算欧几里得距离约 425 次，比在 1100 万个值 boolean[][] 中徘徊寻找 25,950 中感兴趣的 1 值（尤其是在最坏情况分析中）要快得多。 。

---

如果您真的对每次扫描约 425 个值的想法不感兴趣，那么 (i) 您比我更强迫症 (:P)； (ii) 您应该查看最近邻居搜索算法。

Answer 4

我不知道你是否有这个要求。如果用户点是P1{x1,y1}并且你想计算它到P2{x2,y2}的距离，则使用毕达哥拉斯定理计算距离

distance^2 = (x2-x1)^2 + (y2-y1)^2

如果你只想知道最近的，可以避免计算平方根（距离越小，正方形也越小，所以它对你来说是一样的）。