地图上的最近点

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;

如果用户点击例如2377,1882的X和Y,那么我需要程序来确定哪个图像最接近(在这种情况下答案是2377,1881).

任何帮助将不胜感激,谢谢.

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 倍远的平方根的图像。