在哈希映射中搜索坐标。

Question

我正在开发一个GUI应用程序。该GUI由一张带有城市的地图组成。每个城市都有X和Y坐标。城市存储在类似以下方式的HashMap中:

cities.put(new Coordinates(X, Y), "City Name");

X和Y只是代表城市中心点的整数。如果您需要用圆圈标记一个城市，X和Y将表示该圆圈的中心。

我没有问题获取鼠标单击的坐标。但是我的问题是我不知道如何搜索HashMap并获取最近的城市。没有人能够完美地单击特定的X和特定的Y坐标。因此，我必须允许像+- 15这样的范围。

- Sameer

---

你有一些以半径为15的圆形标识的城市，位置在x，y处。我假设这些圆不会重叠，否则就需要其他规则来定义唯一性。那么你的问题就变成了“这个点是否在这个圆内”，这个问题之前已经有人回答过（https://dev59.com/pXRB5IYBdhLWcg3w4bAo）。你可能可以使用一些策略来首先确定潜在的候选者，但我认为这些策略可能取决于你的数据及其分布情况。 - Romski

你可能会发现，内置类型都不适合你的查询。我猜想其中一种空间树可能是更好的工具，但是我对于数据结构领域不够熟悉，无法确定是哪一种并给出明确的答案。 - user289086

这里有一篇关于vp-trees的优秀文章，附有示例代码（虽然是C++）链接，看起来正是你所需要的。 - Oncaphillis

Answer 1

将地图分成网格，以便可以从网格内的点计算出任何网格方格的左上坐标。

例如，如果一个地图是100x100，并且您希望它包含10个网格方格乘以10个网格方格，则任何网格方格的左上坐标为：

top = y - y%10;
left = x - x%10;

然后，你的地图会是：

Map<Coordinates, City>

当你想要查找附近的城市时，需要计算点击位置的网格坐标，并将其用作地图的键。

如果在一个网格内有多个城市，则地图的值需要是一个City对象列表。

编辑：这也可以通过使用Coordinates类的哈希码和.equals()方法进行一些技巧性操作，使用类似网格数学的原理来解决。

- Jason

---

只有当城市完全正交于（/ 10）网格时，此方法才有效。但如果是这样的话，将它们表示为连续体中的点就很愚蠢了 - 只需将瓦片存储为2D数组，其中每个瓦片可以包含一个城市。假设OP使用更精细的坐标空间，因为在较粗的空间中，城市可能会模糊地排列在减少网格分辨率的位置上。 - Kirk Woll

不，它们不必完全对齐网格。'%' 运算符确保无论它们出现在网格正方形的哪个位置，都可以计算出正确的网格坐标。当然，如果多个城市可能位于同一个网格正方形中，则地图必须包含城市列表。 - Jason

这是一个很好的观点。您可以将其用作类似于哈希映射（与顺序查找相比）实现的优化形式，其中每个哈希码可能具有多个值。 - Kirk Woll

如果我的鼠标位置在给定网格的右下角，即使到相邻正方形的左上角城市的欧几里得距离更小，我也会击中同一网格左上角的城市。 - Oncaphillis

好的，为了最准确，你应该只存储一个城市数组（包含它们的坐标），然后迭代该数组，计算与点击位置的距离并找到最近的城市。或者使用这个地图方法来找到点击位置附近的四个最近的网格，然后只在这些网格中迭代城市。 - Jason

如果你不在地图边缘，你将需要搜索8个网格。 - Oncaphillis