地图上最近的点

Question

我正在制作一个程序，你可以点击地图查看周围区域的“特写视图”，比如谷歌地图

当用户单击地图时，它会获得他们单击位置的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;

例如，如果用户单击23771882的X和Y，那么我需要程序来确定哪个图像最接近（本例中的答案是23771881）

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

Answer 1

给定用户单击的位置，您可以使用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 2

基于

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

。。。你走错了路@JBSnoro的答案是一种在干草堆（1100万点）中找到针（350点）的非常优雅的方式，但实际上，为什么要首先创建干草堆呢

根据我对你问题的评论，为什么不使用^{}类来表示坐标，将它们存储在一个集合中，然后扫描它们呢？它更简单、更快、更少的内存消耗，并且对于更大的地图更具可伸缩性（假设兴趣点是稀疏的……考虑到它们是兴趣点，这似乎是一个合理的假设）

。。相信我，计算欧几里德距离约425次，胜过在1100万个值上徘徊boolean[][]寻找感兴趣的25950中的1值（特别是在最坏情况分析中）

---

如果你真的不喜欢每次扫描425个值，那么（我）你比我更强迫症（:P）；（ii）您应该查看nearest neighbour search算法

Answer 3

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

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

如果你只想知道最近的距离，你可以避免计算平方根（距离越小，平方也越小，所以它同样适用于你）

Answer 4

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

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

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

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

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

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

要找到一个点（或“点将位于的节点”），我们从根节点开始，查看我们的点是否位于分界点的北/南/东/西，然后转到相应的子节点。我们继续这个过程，直到到达某个叶节点

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

• 对于最近邻搜索，我们要么以一个空节点结束，然后备份一个级别，并查看该父节点的其他子节点（比较每个距离）。如果我们到达一个包含一个点的子节点，我们将测量搜索点到该点的距离。如果它小于到边或节点的距离，我们就完成了。否则，我们也必须查看相邻节点中的点，并在此处比较结果，取最小值。（我想我们最多要看四点。）

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

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

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

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