Vectorization of raster to polygons

I would never start to write any vectorization code if there was any free library. However, recently I was involved as a tech lead in an interesting project related to geometry. We needed to calculate complex projections of numerous shapes. As we started with “clean” mathematical solution, we quickly end up with a huge number of calculations related to polygon triangulation – O(log n!). We spent a week and I found that we are in a real trouble – for real scenarios the process lasted for minutes. Then I decided to turn our faces to discretization (as it was declared at the beginning) and we did the job and got the result in a form of a matrix. It was Friday and on the next Monday, we ought to present the results. But in a vector form.

Search for raster vectorization in R packages shown this package and the function rasterToPolygons looked good, perhaps it was producing too many points for the polygons. If there is no needed R package then I need to create own. Well, still having a half of a weekend, I did some C++ coding and created this function that does the job in one pass.

Initial bitmap with an enclave and an option to do not allow exclaves and the result:

initial imagevectorization result #1

and an example from the volcano dataset:

 library(fasteraster);
 library(datasets);
 inp = volcano;
 res = raster2vector(volcano, 120, 200, 20);
 image(inp, col = rev(grey.colors(100)), useRaster = TRUE)
 plot(0, type = "l", xlim = c(0, nrow(inp)), ylim = c(0, ncol(inp)))
 a = lapply(res, function(x) lines(rbind(x, x[1,])))

produces:

volcano imagevectorization result #2

You can find source package: fasteraster_1.0.4.tar

and Linux 64 binary here: fasteraster_1.0.4_R_x86_64-pc-linux-gnu.tar

or get a fresh version right from CRAN: https://cran.r-project.org/package=fasteraster

Andy Bosyi,
Information Technology & Data Science
Linkedin: http://www.linkedin.com/in/andybosyi