4

I am working on a GUI application. The GUI consists of a map with cities. Each city has an X and a Y coordinate. The cities are stored in a HashMap like the following:

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

Where X and Y are just some integers that represent the middle point of the city. As in if you had to label a city with a circle, the X and Y would represent the center of that circle.

I have no trouble getting the coordinates of the mouse click. However my problem is I do not know how to search through the HashMap and get the closest city. No person is going to be able to perfectly click on the specific X and the specific Y coordinate. So I have to allow like a +- 15.

Sameer
  • 281
  • 1
  • 2
  • 8
  • You have cities identified by a circle of radius 15 at position x, y. I'm presuming there's an assumption that the circles don't overlap, or else there is some other rule for defining uniqueness. Your question then becomes 'does this point lie in this circle' whhich has been answered before (http://stackoverflow.com/questions/481144/equation-for-testing-if-a-point-is-inside-a-circle). There are probably strategies you could use to identify potential candidates first, but I expect these would depend on your data and how it's distributed. – Romski Nov 11 '14 at 02:17
  • 1
    You may find that none of the built in types are appropriate to the query you have. I suspect that one of the [spatial trees](http://en.wikipedia.org/wiki/Template:CS_trees) may be a better tool, though I'm not familiar enough with that area of data structures to say "yes, its that one" and give you a definitive answer. –  Nov 11 '14 at 03:34
  • There's a excellent article about vp-trees with sample code (in C++ though) [here](http://stevehanov.ca/blog/index.php?id=130) which looks exactly like it's the suff your looking for. – Oncaphillis Nov 11 '14 at 19:05

1 Answers1

1

Divide your map into a grid such that the top-left coordinates of any grid square can be calculated from a point within the grid.

For example, if a map was 100 x 100 and you wanted it to contain 10 grid squares by 10 grid squares, the top-left coordinates for any grid square would be:

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

Then, your map would be:

Map<Coordinates, City>

where City is an object containing the name and the real coordinates of the city (not the grid coordinates).

When you want to find the nearby city, calculate the grid coordinate for the clicked position, and use it as the key to your map.

If you have more than one city within a grid, the values for your map will need to be a list of City objects.

EDIT: This could also be solved by doing some trickery with the hashcode and .equals() method of the Coordinates class using a similar principle of the grid mathematics.

Jason
  • 11,744
  • 3
  • 42
  • 46
  • 1
    This will only work if the cities are perfectly orthogonal to the (`/ 10`) grid. But if that were so, representing them as points within a continuum would be silly -- just store the tiles as a 2D array, where each tile may contain a city. Presumably the OP is using a finer-grained coordinate space because the cities could line up ambigulously in a coarser space where you reduce the resolution of the grid. – Kirk Woll Nov 11 '14 at 02:13
  • No, they don't have to align perfectly to the grid. The '%' operator ensures that wherever in the grid square they appear, the correct grid coordinates can be calculated. Of course if more than one city could ever be in the same grid square, the map would have to contain lists of cities. – Jason Nov 11 '14 at 02:16
  • that's a good point. You could use this as a similar form of optimization as is implemented by the nature of hash maps (vs. sequential lookup) where each hashcode may have multiple values. – Kirk Woll Nov 11 '14 at 02:17
  • If my mouse position is in the lower right corner of a given grid I would hit a city in the upper left corner of the same grid even if the euclidean distance to a city in the upper left corner of a neighbouring square is smaller. – Oncaphillis Nov 11 '14 at 02:31
  • Right, so to be the most accurate, you should just store an array of cities (containing their coordinates), and then iterate that array, calculating the distance from the click and finding the nearest one. Or use this map method to find the four nearest grids to the click, and then only iterating cities in those grids. – Jason Nov 11 '14 at 02:36
  • 1
    If you're not at the border of the map you'll have to search 8 grids – Oncaphillis Nov 11 '14 at 02:39