How to filter spatial data

Question

I have a database of map points, and I want to limit the display to showing at most ~50 points at a time. When a user zooms in, more points may be displayed.

Currently, I'm just taking a random sample of the result set. This isn't great, as there can be empty areas, that when zoomed in suddenly show a point.

My next thought was I could create a 10x5 grid, and iterate over the results. If a location in the grid was empty, I would show a point. This fixes the previous problem, but also doesn't give the user a sense of where concentrated areas are. Also, this is quite slow if the user decides to zoom out to the entire world.

Right now, I'm not using any spatial algorithm to sort the data. My plan is to get it working right first, and then get it fast. Reading a little into RTress, kd-trees, and quad-trees, I couldn't find anything that would help me select a 'smart' subset of the sample. It seems like there should be some sort of breadth first search which would solve this problem quite easily.

Answer 1

How about extending your original idea a bit. Break it into grids, then use a density analysis to create differently-sized points based upon the number of features in that area. That way a user is more visually aware of feature density simply by looking at the larger (or smaller) points.

As for making it faster, perhaps you could set a threshold for each grid. If the count hits a certain amount, move on to the next grid. That way you can have a "maximum" point and speed things up by ignoring points above that artificially set threshold (which you can determine based upon an empirical analysis of your data).

Answer 2

Michael Todd made some good suggestions. +1 for that.

I'd like to add that (depending on the type of data) you could add an extra property to your map points.

For example, for cities, you could add the amount of people living in it. Then depending on the zoomlevel, you only show cities of a certain size. Or better yet, give them a higher score in your selection algorithm. In empty areas you'll still see smaller ones, in crowded areas you'll only see large cities.

This approach works out nicely for any zoomlevel, while predefined sets of data per zoomlevel only work in discrete steps.

Answer 3

Since I have only a few thousand points, and plenty of offline time, I created an algorithm to create a dispersion factor by which I can sort the data.

1. I start with a random point from my set, give it a score of n=1, and add it to the selected list.
2. I then search for the point which is further from any point in the selected list.
3. I take this point, give it a score of n + 1, add it to the selected list, and then repeat step two until all points have been selected.

In my map, I take all points which match a range filter and sort them by rank ascending. Regardless of the filter or zoom, I'll have points which are distributed across the screen.