Data structure for storing points on a map

Question

Java

There is a map whose center is constantly changing (the user moves). With each movement, you need to determine whether the points on the map are visible or not. If yes, then you need to draw them, if not, then show the compass with the direction to the nearest point.

Location updates can be from 1 per second to 1 per minute. The number of objects is approximately 1000-1500, usually only 5-7 are visible on the map.

What is the best data structure to use to store these objects in order to quickly get the points that are closest?

Now everything is stored in a regular array, and every time the location is updated, I go through all the points in a regular cycle, calculate the distance and azimuth, save it to an object and move on.

Not sure if this is the best way. Maybe there are some other options? At first I thought about the queue, but how is it better than the option with, for example, a smaller array, where X points will be stored at a distance Y?

Answer 1

To speed up something, you need to calculate and remember something in advance :) In your case, you need to do the so-called. spatial indexing of data. In big blocks it looks like this:

1. We determine for ourselves the geographical projection in which you can work with the map. For example, Mercator, like Google.
2. Knowing the projection, we divide the map into a geographical grid of a fixed size, the optimal size is determined empirically, based on the density of points and the size of the map.
3. For each point , we calculate in advance the index of the grid cell corresponding to it.
4. To draw points, we calculate the numbers of cells that are visible on the current screen (according to the coordinates of the screen corners, taking into account the current scale)
5. Having a list of displayed cells, we process the points that are only in these cells.

Yes, and GDAL will help you ...

Answer 2

In principle, it is possible to build a graph of connections between points in such a way that each point will be connected only with its nearest neighbors. The user is closest to some vertex of the graph P, we assume that he is attached to it. With each update, you need to check if the user is closer to any of the vertices of the graph associated with P. In the latter case, you need to change the anchor vertex. If the connections between any P and other vertices are significantly less than the number of vertices, then there is less need to update.
The most difficult thing seems to be determining which vertices are considered "nearest". We can consider as the closest those that will be visible if the given vertex is visible. Plus, you can split the map into directions and find the vertex with the smallest distance in a given direction, if there are no vertices "in view" in the direction. But here you can still think :)
In general, updating a vector of 1500 objects once a second is not such a difficult task. Unless you need to save computing resources (some kind of embedded hardware or battery operation), then I would not bother.

Answer 3

A quadtree is also suitable for your task: en.wikipedia.org/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%...
consider a square if it is entirely further than the available intermediate answer).
The search for all points that need to be displayed is done recursively in the same way.
In the worst case, this structure can be quite slow, but on average, all operations are quite fast. The implementation of this structure is very simple.