Building on my work from last week I completed several smaller tasks this week. While each task on its own was not very big, together they have lead to a state where almost all tests pass!

Collision detection

The most important part was implementing collision detection for line placements.

First a short description of the old code:

• Calculate position of glyph
• Store position
• Repeat until all characters are processed
• Calculate bounding box (requires a lot of the same calculations already done for the position again)
• Check for collision
• Store bounding box
• Repeat for all characters
• Updated detector with stored bounding boxes

As one can see this is not very efficient because processing time is wasted when there is a collision on one of the first characters.

The new code therefore does this:

• Calculate position of glyph
• Store position
• Calculate bounding box (using the already computed values)
• Check for collision
• Store bounding box
• Repeat for all characters
• Updated detector with stored bounding boxes

This has two advantages:

• Position calculations don’t have to be done a second time
• If there a collision occurs processing is aborted immediately instead of wasting time processing all following characters

The new detector therefore should be a bit faster in the average case and much faster when there are lots of collisions.

Label position tolerance

This property was very easy to implement, but I think the current approach is not very efficient. When a placement can’t be made at the intended place up to 200(!) slightly different places are tried. This usually means moving the text one pixel and trying again. I think the displacement should grow exponentially. So instead of trying +-1, +-2, +-3, +-4, +-5,… try +-1, +-2, +-4, +-8, +-16, … This would bring a huge increase in performance. I implemented the old behavior because I don’t know if there are any applications which require it.

Offset lines

First I implemented support for dis-placement along the line. This allows you to render text offset from the center of the line. Then I also implemented displacement perpendicular to the line. However I did not use the algorithm from the old code (which estimated the direction an then shifted all characters in the same direction) but instead I produce true offsets using the new parallel line support in master.

The difference can be seen in this picture:

Code for this image: <TextSymbolizer spacing="1" placement="line" dy="-10" vertical-alignment="middle" ...>'Some Text'</TextSymbolizer>

With the old code text touches the line but it keeps the distance perfectly with the new code. Stylesheets using offsets probably need a modification to produce the same results: Up to now Mapnik ignored vertical-alignment for line placements, but the new code uses it. To get the old behavior one has to include vertical-alignment="middle".

Here is an example showing that it also works well with complex scripts:

Code for this image: <TextSymbolizer placement="line" spacing="20" max-char-angle-delta="0" dy="6" ...>"ផ្លូវ​១២៣"</TextSymbolizer>

Multi line labels

The offset functionality allowed me to implement multi line labels very efficiently. One can use the same functions for point and line placements now (jalign, wrap-width, wrap-before, embedded newline characters).

Example: Code for this image: <TextSymbolizer placement="line" spacing="20" max-char-angle-delta="0" dy="6" ...>"Hello&#10;World!"</TextSymbolizer>

As one can see sometimes the placement is not perfect, but this only happens for very rare cases (zig-zag-pattern). More common cases (straight lines, circles) are handled correctly. The problem is that there is currently no function to map a point on the original line to the offset line in offset_converter.

Performance tweaks

Profiler output for old versions of Mapnik has shown that during text rendering a lot of time spent is spent in trigonometric functions like sin, cos, and atan2. So instead of calculating theses values several times (IIRC the old code calculated them at least 5 times per character), I store them after the first time. I think even this one calculation could be removed but it would complicate some other things (determining which characters are upside down) so I’m waiting for data saying it is really necessary before doing it.

Grid renderer

As the API is stable now I also reenabled support for grid renderer.

Next steps

Only one big thing is left:

• Add support for ShieldSymbolizer