Why is R's implementation of the Douglas-Peucker algorithm so slow?

Question

Plotting geographical polygons is not R's strength, but it can be very rewarding if done well. I'm using data from the UK and the detail in the polygon borders is ridiculously high, making any plotting or manipulation function (especially after fortify has been run to make it ggplot-able) slow.

The logical approach is to simplify the polygon geometries, so they are less complex.

I followed this post to implement the Douglas-Peucker algorithm to do this in R, but it was painfully slow. Applied to this dataset (regions of England), the following code took ~10 minutes to run on my Intel® Core™ i7-3630QM machine with 16 Gb of RAM:

for(i in 1:length(gors@polygons)){
  for(j in 1:length(gors@polygons[[i]]@Polygons)){
    temp <- as.data.frame(gors@polygons[[i]]@Polygons[[j]]@coords)
    names(temp) <- c("x", "y")
    temp2 <- dp(temp, 0.01)
    gors@polygons[[i]]@Polygons[[j]]@coords <- as.matrix(cbind(temp2$x, temp2$y))
  }QGIS
}

In QGIS, the same function took approximately one second. Of course, I'll probably be using the QGIS implementation in the future, but just found it perplexing that the R implementation takes soooo long. Any ideas how to make it faster or implement the algorithm in a more efficient way greatly appreciated.

Answer 1

Well I think you can use rgeos function gSimplify which interface GEOS::simplify

In the help file you'll have more information, for example this is the header

Simplify Geometry

Description:

 Function simplifies the given geometry using the Douglas-Peuker
 algorithm

Using your data something along this line should do this

require(rgeos)
require(rgdal)

gors <- readOGR(dsn = "/tmp/gor", layer = "GOR_st121")

system.time(gor_topo <- gSimplify(gors, tol = 0.01))
##  user  system elapsed 
## 0.713   0.010   0.727

I have an I7 but my spec are less impressive than yours so I expect this function to be faster when you'll try it.