Polygon simplification is something others have written about, using R packages such as shapefiles. This explores how package ‘rgeos’ uses the Ramer–Douglas–Peucker algorithm, a method commonly used in GIS systems for simplifying shapefiles. It works by imposing a deviation tolerance threshold on all points (vertices) of a vector, and keeping only those that fall outside the threshold. In other words it keeps only the vertices that best define an object’s shape. To be effective the tolerance variable must be set within a range relevant to the data’s coordinate system. The diagram below demonstrates the process:

Ramer–Douglas–Peucker simplifying

B. Draw a straight line from start to end points (‘a’). Identify the vertex furthest from this (‘c’). If its distance to the line (‘b’) exceeds tolerance (‘e’), mark it for retention and draw a new line to the end.

C. Identify vertex furthest from the ‘c’ to end point line, and measure its distance from it. If > ‘e’ mark to be retained, and draw a new line to the end.

D. Repeat step C until no vertices remain above the ‘e’ threshold except those marked for retention. Remove all other vertices.

The process must work a little differently for polygons since the start and end points are the same – I’m guessing some algorithms calculate this from the first vertex to the most distant.

Ramer–Douglas–Peucker with ‘rgeos’

The ‘rgeos’ package in R contains a number of polygon tools, of which ‘gSimplify’ is an RDP algorithm. The outcome is illustrated in the maps below, with the ‘e’ deviation tolerance used noted for each. Since the coordinate system is decimal degrees, the effective range for ‘e’ at this scale is probably < 0.5.

(1) original | (2) e = 0.1 | (3) e = 0.5

The British mainland polygon reduces from 1,954 vertices to 284 at e=0.1 and 64 at e=0.5. Examining the effects closer up (Scotland’s west coast):

Code

This demonstrates the process as well as showing some basic tools for examining the resulting object. The Praise of Insects blog also has some useful tips. Any comments are welcome.

Click here for the code