Discussion about the processing done as part of https://github.com/MapServer/MapServer/pull/5854 - this article has been updated to reflect the refactoring done on 2/16/21.

Below is a 6-frame animation that shows the process implemented in the pull request. Green points are start vertices for a feature, red points are end vertices and blue points are intermediate nodes.

1. The raw feature and associated points.
2. Compute Thiessen Polygon using GEOS (version 3.5 or higher).
3. Remove any lines that aren't contained completely in the original feature (edge intersection).
4. Run GEOS line merge to create new features from fragments created in step 3 (more blue, less green/red).
5. Run a pruning process to remove lines where either the starting or ending vertex is not shared with another line. We're trying to limit the number of green and red vertices.
6. Run the pruning process again as necessary and finally label.

Notes:

• The process to prune lines runs a GEOS line merge at the end of each iteration.
• The current code loops until there are no more dangling lines to prune. This can be limited using a second parameter to the skeletonize function - for example a value of 1 means at most one pruning operation will be run.

Examples:

Animation: