Mapgen.pl/Details

Algorithms and details

The following paragraphs try to explain some of the used algorithms.

• As of version 0.16 there is no interaction between space used by way labels and space used by icons and icon labels.
• I am fully aware that there are more intelligent (and more complex) ways to achieve optimum label placement! But since this is a sience of its own I try to find simple, fast and easy algorithms to achieve an almost optimum.

poi icon and label placement

• An icon will be placed at its original position if possible. If not mapgen will try 8 other differerent positions in a distance of max 10 pixels in each direction. The label, if present, will be moved as well.
• Label will be split into several lines if possible (abt. 20 chars per line).
• The label for the icon will be placed centered below the icon if possible. If not, some other positions are tried. But the label will always stick to the icon.
• Each drawn icon and each drawn label occupies a rectangle area which can not be used again by succeeding icons and labels.

So it can happen that an icon can not be placed. And it can happen that an icon is placed but not the according label.

way label placement

• Ways are merged when they share the same rule and label (name, ref i.e.)
• Ways will be split where a change in direction longitude is occuring. That is to make the label readable (no upside down labels)
• A ratio is calculated (label length / way length). Ways to be labeled are sorted descending by this value. This labels ways first where there are not many possibilities to place the label. Leaving room to move for labels that will be placed later.
• First it will be examined how many labels should be placed on a particular way
• If it is one label then n (5-10?) possible positions are calculated. The possible solutions are evaluated according to their angles / bends in the way and their distance to the middle of the way and if the position is available at all (no collision). Best solution (regarding quality) is chosen.
• If there are more labels to draw then more positions are calculated and evaluated regarding collisions. If there is no collision the label will be drawn.
• For collision detection a polyline is stored per drawn label. These lines will be checked for intersections when a new label shall be drawn.