Algorithm to determine which points should be visible on a map based on zoom

Question

Hi! I'm making a Google Maps-like application for a course at my Uni (not something complex, it should load the map of a city for example, not the whole world). The map can have many layers, including markers (restaurants, hospitals, etc.) The problem is that when you have many points and you zoom out the map it doesn't look right. At this zoom level only some points need to be visible (and at the maximum map size, all points). The question is: how can you determine which points should be visible for a specified zoom level?

Because I have implemented a PR Quadtree to speed up rendering I thought that I could define some "high-priority" markers (that are always visible, defined in the map editor) and put them in a queue. At each step a marker is removed from the queue and all it's neighbors that are at least D units away (D depends on the zoom levels) are chosen and inserted in the queue, and so on. Is there any better way than the algorithm I thought of?

Thanks in advance!

Answer 1

I had a similar problem and you cannot avoid having overlapped icons regardless the method to mark some icons as high-priority.

What I did(it might not be easy to apply in your case - in my case the map was rendered in a desktop application, with much more control above the rendering process) was to sort based on priority, and paint only markers which are not overlapping - showing also a message like "XXX overlapping markers removed". This way the user doesn't become overwhelmed with information and he still sees the most important information.

I hope this helps.

Answer 2

Not sure I understand completely, but perhaps you can assign each layer a "neighborhood density," based on the inverse of the average distance from each point to its closest neighbor. For a particular zoom level, you would calculate a maximum density that is comfortably viewable and use that as a threshold.

Answer 3

I have some experience in designing a map application from scratch I would recommend you to split the entire world into 16 zoom levels. Zoom Level 0 should show the entire world and Zoom level 15 should cover the street data.

Typically, you would have to use the zoom levels 0 to 3 to have boundaries of the countries. And each zoom level should have a zoom range of 1/4th of the previous zoom range. You can have a zoom to table map (assuming you are using a database to store the spatial related data). Once you define the zoom levels and the range of the zoom levels to table mapping you can have finer control on querying the data. And its recommended to construct a R-Tree indexing for your map data.

Each and everytime you get a layer/table (assuming a layer can be either a country boundary or a railway track or a street), its advisable to define a zoom level by yourself instead of spending time in finding an algorithm since the number of layers are not going to be huge.

I can keep going, but if you want specific answers, I can address them as well.