Simplifying spatial polygons in R

February 20, 2012
By

(This article was first published on ***site moved to geotheory.co.uk*** » R, and kindly contributed to R-bloggers)

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


A. Inputs: (1) a vector/polygon to be simplified; (2) the deviation tolerance (lets say ‘e’)

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.

bla1

(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


To leave a comment for the author, please follow the link and comment on his blog: ***site moved to geotheory.co.uk*** » R.

R-bloggers.com offers daily e-mail updates about R news and tutorials on topics such as: visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...



If you got this far, why not subscribe for updates from the site? Choose your flavor: e-mail, twitter, RSS, or facebook...

Comments are closed.