Simulated annealing works great for placing map labels. Lets say you have to label POI with flags, you do not want the flags to overlap and you can only place the labels NSEW of the POI.
1. Plop the labels down in random* directions.
2. Calculate the total overlap.
3. Randomly* move 10% of the labels.
4. Calculate the total overlap again,
If the overlap is improved, keep your changes,
If things got worse, then backtrack.
5. Sometimes you randomly keep changes that make things worse, this is the annealing part. This is how you escape local minima.
* The randomness does not have to be 100%, you can try smartly avoiding nearest neighbors 2/3 of the time and then do a random move 1/3 of the time. If you always try and be smart you will tend get trapped in a local minima.
Comments
Simulated annealing works great for placing map labels. Lets say you have to label POI with flags, you do not want the flags to overlap and you can only place the labels NSEW of the POI.
1. Plop the labels down in random* directions.
2. Calculate the total overlap.
3. Randomly* move 10% of the labels.
4. Calculate the total overlap again, If the overlap is improved, keep your changes, If things got worse, then backtrack.
5. Sometimes you randomly keep changes that make things worse, this is the annealing part. This is how you escape local minima.
* The randomness does not have to be 100%, you can try smartly avoiding nearest neighbors 2/3 of the time and then do a random move 1/3 of the time. If you always try and be smart you will tend get trapped in a local minima.