The convex hull is not the solution for maps
You know those coverage or "footprint" outlines that fade in on some clustered maps when you hover your mouse over a marker cluster? Like the one below, on the right, covering the 144 markers of the map shown on the left? These envelopes can be quite bloated, suggesting coverage of areas that clearly have no underlying markers at all. Like seas, lakes and deserts. It is a little misleading really.
The problem occurs when interactive maps use the so-called convex hull to calculate a polygon, or outline, of the area covered by markers. The issue with the convex hull is not that it doesn't cover all markers. It is that it covers way more than that.
Convex hull algorithms are wonderful mathematical solutions, but not for the problem at hand. Not for maps, if your aim is to give the user accurate information about the footprint of a cluster.
Basically a convex hull is like putting an elastic sleeping bag over your head and spreading out your arms. It will feel very tight, but at the same time not cling to the body everywhere. Because the elastic material will stretch diagonally from your fists down to your feet, very much like that long diagonal edge crossing the Gulf in the image above. You will also look stupid, but that's not the point.
What we need for our maps is more like a hugging windsurfer wetsuit. Then when you stretch out your arms it still feels comfortable and your silhouette remains recognisable.
Some fine and complex algorithms exist to determine the outline of a scattering of points, usually involving Alpha shapes and concave hulls. Few are suitable for slotting in as client-side code that needs to power high-performing interactive maps.
So at RegionBound we devised for our marker clustering plugin our own"wetsuit" algorithm to beat the Elastic Sleeping Bag Blues. We call it the Heuristic Hull.
Below you can see the algorithm in action. The wetsuit-effect can be tailored to your liking with a parameter, called the hug-factor. A value of less than, say 0.5, produces a very loose-fitting coverage envelope, like someone who puts their arms around you, but hardly touching you. A hug-factor of 0.99 is like someone squeezing you so tightly that your love handles bulge out, even if you didn't know you had any.
In the screenshot below, the temptation is to compare the blue outline against the Florida border. But the aim of the algorithm is not to approximate the border on the map, but to represent the extent of the markers in a way that is superior to the classic convex hull.
The coverage outline of the first image below was created using a hug-factor of 0.95. In the second it is 0.80. Not that you'd need to know. You don't need to specify a hug factor. The RegionBound plugin will automatically set one for you for each cluster, based on the number of markers contained.
Some properties of the Heuristic Hull approach are:
- it will always represent the points envelope as a single polygon; it won't return a series of islands
- all of the corner points in the hull envelope also occur in the original marker set, no interpolations
- the hull always includes the most northern, southern, eastern and western points
- the hull returned is horizontally convex
- the envelope may skirt a marker or cross itself
- it works best on marker clouds that have no vertical indentations, i.e. works great on C, E and L shapes, not so great on M and V shapes
- it is fast: the hull for 3000 points is calculated in a few milliseconds in any browser; so it is very suited for interactive applications
