MS RFC 112: Retry “Follow” label positioning after maxoverlapangle colision

Date

2014/10

Author

Thomas Bonfort

Contact

thomas.bonfort@gmail.com

Status

Implemented

Version

MapServer 7.2

1. The Current Situation

The current algorithm used to place “FOLLOW” labels has the following limitations:

  • When two subsequent caracters of the label have a relative angle that is over the defined “maxoverlapangle”, the label is unconditionally discarded.

  • The function used to compute character positions relies on “gotos” that interrupt the code flow

  • Placement of repeated labels works optimally for odd number of repetitions only when using repeatdistance, i.e. even if there’s room for two labels, only one will be rendered

2. Proposed enhancement

  • The algorithm will be extended to account for and try to correct for colisions happening when maxoverlapangle kicks in, by ensuring that such colisions may only occur between words:

    • collisions hapenning on a ‘space’ character will be ignored

    • when a colision does occur, the label placement will be retried with an offset placed such that the colision falls either on a space or at the beginning or end of the string.

  • Code will be refactored to avoid usage of gotos

  • The placement algorithm will be modified to optimally treat an even number of label repetitions:

  • before:

-------label--------

  • after:

--label------label--

2.1 Questions/Limitations

  • Should the retrying behavior be enabled by default, and/or can it be deactivated ? Computing and testing a retried offset is not costly, the impact in terms of performance should be minimal and will result in more labels being placed.

  • Should the maximum allowed offset be configurable? Seems unnecessary for the time being, all the relevant info as to what the maximum offset can be is contained by the line length, label length, and repeatdistance.

2.2 Backwards Compatibility

None expected aside from the fact created maps may contain more/different labels than beforehand.

2.3 Performance Implications

Limited. Retrying a label after a colision is not a cpu-heavy operation. Costly operations such as computing glyph advances and/or shaping text runs are not re-run for each retry.

3. Implementation Details

3.1 Affected files

  • mapprimitive.c: implement retrying behavior - compute retried offsets

3.2 Tracking Issue

4. Voting History

+1 from SteveL, DanielM, StephanM, PerryN, MikeS, StephenW, ThomasB