This is a write-up of a lightning talk I gave at PGDay Chicago 2025, but I've also added some additional thoughts/notes at the bottom. Here are the original slides.
Showing an empty map is boring.
The last few years, I've been working on applications that, in part, help archaeologists and historians do research within a state. For instance, Idaho.
Since doing research in an area is common, I wanted to make sure the map search experience was fun. And not only when zooming in on a particular area, like here with Boise:
Exploration and scanning for shapes, for historic buildings and archaeological sites, when zoomed out should be possible and encouraged.
Looking at a blank map of Idaho doesn't encourage me to start poking around.
Showing dots where shapes are could lead me to interesting places.
But we don't want to show every shape when zoomed out. Searching would be slow.
What if we pick only some shapes, to show the density in different areas?
Unfortunately, calculating this precisely would also be slow, either on read or write.
Instead, let's try to show some of the dots to approximate the density.
Then, if a user knows generally where a shape is located, they can zoom and pan to it with the dots as a guide.
What Properties Should Hold?
So, looking at examples of what other companies had done, I realized there are three properties I wanted to hold.
Zoom Property:
When zooming in, all purple dots should still show up in the zoomed-in area.
Panning Property:
And also, when panning over, all purple dots should still be visible in the viewport.
Density Property:
If possible, I want to have a dot close to wherever there's a shape (e.g. a historic building). So I want to remove dots from dense areas first (like Boise), since those will probably still have other dots nearby.
Randomness
I ended up giving every dot a random number and then picking the visible dots with the greatest value.
select point
from gis_table
where st_intersects(shape, :viewport)
order by rand desc
limit $1
This gives us a uniform distribution of all the dots in the viewport while keeping this zooming property.
We already know the purple dots will have a high enough number for this big area, so they'll still appear for the small area.
Unfortunately, we can lose dots in the sparse areas as easily as the ones in the dense areas, so it doesn't give us everything.
Similarly, we don't get the panning property. Sliding over reveals new dots that can have a higher number than the ones in our viewports, which is why the four dots disappear.
This approach is fairly fast. We end up loading all the intersecting row references into memory and then sorting. But since we can use a spatial index for the intersect, we avoid reading (potentially very large) geometries. In practice, I get around 100-300ms for a search, which is acceptable.
Panning:
Now, the panning property is fixable with tiling, which every map would want to do anyway for caching purposes.
Instead of looking at what's inside the viewport, we fetch all the tiles that intersect the viewport.
Now dots aren't dependant on the the exact viewport. If the viewport intersects the tile, the dot appears. Otherwise, not.
As you can see above, dot number four is in a different tile, which is why it showed up, even though now five and six are visible in the panned part.
This has the added advantage of limiting the impact of dense areas crowding out sparse areas, giving us a weak form of the density property.
Further Work:
We can think of the random number we attached to each shape as a scoring function. We aren't prioritizing one over the other, so it's random.
Like Google Maps, we could have picked some other scoring criteria to drive users to particular points of interest.
If we scored differently, we would still want the above three properties.
Additions:
I mentioned in my talk that I looked at two examples of how other companies have done search: Zillow and Google Maps.
Interestingly, Zillow has the problem with panning discussed above - dots will visibly appear and disappear as you pan across. I figure they're using a similar technique/pattern, just without the tiling.
Scattered Thoughts on Packing
Google Maps matches both the zooming and panning properties. They consciously score in a way such that points of interest don't show up too near each other (a stronger form of our density property). I assume they do this in a background process, but I'm not sure how they would calculate it. Assuming nothing else is taken into account, the problem could be written out something like this:
How can we maximize the number of points in a region where congruent circles drawn around each point don't intersect?
And we would need to figure out the zooming property. Ugh.
Maybe there's a good heuristic that gives us an approximation?
I think iteratively picking points (based on a scoring function) and removing all other points around it would work.
Is there a better alternative?
Artifacts
I mentioned that tiling improves the density property for our map. Unfortunately, it also reveals a deficiency.
What happens if we have a uniformly dense area spread across two tiles, but that area only encompasses part of some of the tiles? (or inside our viewport and right outside it)
We get this weird artifacting. A line of dots appears in what should be a uniformly distributed region.
If we were to use the heuristic I mentioned above, this issue would disappear.
Questions
- Is this problem/solution written up anywhere else?
- Are there other properties we might want to hold?