mapnik/mapnik — pull request #2512 by kevinkreiser (2014-10-08 19:13:47+00:00)
Title: Add Ramer Douglas Peucker Algorithm to simplify_converter

This PR is meant to do exactly what is mentioned in the title. Namely there was a placeholder in the code for the RDP algorithm which allowed you to ask for that strategy but would throw an "unimplemented" exception. Since this is one of the more popular strategies for simplification and mapquest's related project mapquest/avecado is making use of these simplify_converters for vector tiles we thought we would go ahead and add this one.

Since the algorithm is not an online algorithm the first call for a vertex will run the thing in its entirety (similar to visvalingam_whyatt). Instead of constructing a new list by the general divide and conquer recursive strategy we instead mark vertices which are simplified out as we encounter them this can save on (re)allocations.