Re: Algorithms/Code Needed to Remove Overlap of Markers on a Map

On Tue, Aug 16, 2005 at 12:01:39AM -0500, Mike M wrote:
> I am looking for algorithms to reduce/remove overlap/stacking of geographic
> coordinate markers on a map. These markers are an overlay on a map (in my
> case the new Google Maps API). 
> 
> The algorithm would accept a set of points and dimensions of the marker used
> at each point, and would re-arrange the points so that marker overlap is
> either reduced by to zero or some tunable amount (for example, you might
> specify that every point should be at least 50% visible).
> 
> I've seen this type of algorithm described as geometric packing. So far I
> have come up empty on searches (I'm still looking though), and wanted to see
> if anyone knows of any free GIS APIs/systems that provide this, as perhaps I
> can re-use their algorithm(s). Or general algorithms I should seek out.

I think what the problem you're referring to is usually called
"label placement" problem, which is NP-hard, and the solution you're
looking for is the "simulated annealing" algorithm, which doesn't guarantee
anything, but is very fast and efficient in typical cases, but requires
a bit of problem-specifitc tuning.

There are plenty of papers on simulated annealing and its application in
GIS available online.