Nearest point on the map

Question

I am making a program in which you can click on a map to see a “close-up” around it, for example, on Google Maps.

When the user clicks on the map, he gets the X and Y coordinates where they clicked.

Suppose I have an array of Boolean objects, where these images are in close view:

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. 

The program searches the folder where the images are called the X and Y coordinates, where they were taken on the map. The folder contains the following images (and much more, but I will list only five):

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

It means that:

 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; 

If the user clicks on X and Y, for example, 2377.1882, then I need a program to find out which image is closer (the answer in this case will be 2377.1881).

Any help would be appreciated, thanks.

Answer 1

Given the location that the user clicked, you can find the closest image using the Dijkstra search. Basically you start your search in the larger rectangles around the clicked location for the images. Of course, you only need to look for the borders of these rectangles, since you have already searched the body. This algorithm should stop as soon as the image is found.

Pseudocode:

 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[pX + i][pY]) return { pX + i, pY} if(view_set[pX][pY + i]) return { pX, pY + i} if(view_set[pX + i][pY + size]) return { pX + i, pY + size} if(view_set[pX + size][pY + i]) return { pX + size, pY + i} } return default } 

Note that for brevity I left the range check.

There is a small problem, but depending on the application, this may not be a problem. He does not use Euclidean distances, but manhattan meters. Thus, he does not necessarily find the closest image, but the image is no more than the square root 2 times.

Answer 2

Your boolean[][] not a good data structure for this problem, at least if it is not very dense (for example, usually at a point with a size of 3 × 3 or 5 × 5) there may be a close-up point.

You need a 2-D card with a search for the nearest neighbors. A useful data structure for this purpose is QuadTree . This is a degree 4 tree used to represent spatial data. (I describe here the "Square of the region with point data.")

In principle, it divides the rectangle four times into equal size rectangles and further subdivides each of the rectangles if it has more than one point.

So, the node in your tree is one of the following:

• empty leaf node (corresponding to a rectangle without dots in it)
• leaf node containing exactly one point (corresponding to a rectangle with one point in it)
• inner node with four child nodes (corresponding to a rectangle with more than one point in it)

(In implementations, we can replace empty leaf nodes with a null pointer in its parent.)

To find the point (or “node the point will be in”), we start from the root of the node, see if our point is north / south / east / west of the separation point and go to the corresponding child node. We continue this until we come to some leaf node.

• To add a new point, we either end up with an empty node - then we can put a new point here. If we finish with a node with a point already in it, create four child nodes (dividing the rectangle) and add both points to the corresponding child element of the node. (It could be the same thing and then repeat recursively.)

• To search for the nearest neighbor, we either end up with an empty node, then we will create a backup of one level and look at the other child nodes of this parent (comparing each distance). If we reach a child node with one point in it, we measure the distance from our search point to that point. If it is less than the distance to the edges or node, we are done. Otherwise, we will also have to look for points in neighboring nodes and compare the results here, taking a minimum. (I think we will have to watch no more than four points.)

• To delete, after finding the point, we make its node empty. If the parent node now contains only one point, we replace it with a single-point node sheet.

Search and add / delete are performed in O (depth) time complexity, where the maximum depth is limited by the log ((map length + width) / minimum distance of two points in your structure), and the average depth depends on the distribution of points (for example, the average distance to the next dots), more or less.

The required space depends on the number of points and the average depth of the tree.

There are several options for this data structure (for example, splitting a node only when there are more than X points in it or a split is not necessarily in the middle) to optimize the use of space and avoid too deep tree depths.

Answer 3

Based on

• your comment, which says that you have 350-500 points of interest,
• your question, which says that you have a map width of 3313 and a height of 3329
  • my calculator that tells me that it means ~ 11 million booleans

... you are doing it wrong. @JBSnorro's answer is a pretty nifty way to find a needle (350 points) in a haystack (11 million points), but actually, why create a haystack in the first place?

According to my comment on your question, why not just use the Pair<Integer,Integer> class to represent the coordinates, save them in the set and scan them? It is simpler, faster, less memory consuming and more scalable for large maps (assuming objects of interest are sparse ... which seems like a reasonable assumption, given that these are points of interest).

.. Believe me, calculating the Euclidean distance ~ 425 times, wandering around 11 million boolean[][] in magnitude, looking for 1 value in 25,950 percent (especially in the worst case analysis).

---

If you really are not enthusiastic about the idea of ​​scanning ~ 425 values ​​each time, then (i) you are more OCD than me ( :P ); (ii) you should check the nearest neighbor search algorithms .

Answer 4

I do not know if you are asking about this. If the user’s point is P1 {x1, y1} and you want to calculate his distance to P2 {x2, y2}, the distance is calculated using the Pythagoras'oror method

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

If you only want to know the closest, you can avoid calculating the square root (the smaller the distance, the smaller the square so that it serves you the same).