Bindings for 'Mapbox' Ear Cutting Triangulation Library

Provides constrained triangulation of polygons. Ear cutting (or ear clipping) applies constrained triangulation by successively 'cutting' triangles from a polygon defined by path/s. Holes are supported by introducing a bridge segment between polygon paths. This package wraps the 'header-only' library 'earcut.hpp' < https://github.com/mapbox/earcut.hpp.git> which includes a reference to the method used by Held, M. (2001) .


lifecycle Travis-CI BuildStatus BuildStatus AppVeyor BuildStatus Coveragestatus CRAN RStudio mirrordownloads

The goal of decido is to provide an R binding to the Mapbox library earcut.hpp for constrained polygon triangulation. Decido is aimed at package developers at the moment, there are not high-level classes or objects but the earcut functionality can be easily used in higher-level tools or just used directly.

Ear cutting (or ear clipping) applies constrained triangulation by successively ‘cutting’ triangles from a polygon defined by path/s. Holes are supported, the earcut library works with single-island-with-holes polygons, analogous to the POLYGON type in simple features.

This augments the Javascript version available in rearcut (also an R wrapper of the JS version by Mapbox). Only very minimal comparison testing has yet been done to compare these implementations.

Installation

Install the released version from CRAN.

install.packages("decido")

You can install the development version from GitHub with the following code. You will need the set of development tools for building source packages with binary code.

## install.packages("devtools")
devtools::install_github("hypertidy/decido", build_vignettes = TRUE)

Example

This is a basic example of triangulating a single-ring polygon. The output is a vector of triplet indices defining each triangle.

library(decido)
x <- c(0, 0, 0.75, 1, 0.5, 0.8, 0.69)
y <- c(0, 1, 1, 0.8, 0.7, 0.6, 0)
earcut(cbind(x, y))
#>  [1] 2 1 7 7 6 5 5 4 3 2 7 5 5 3 2

See the documentation and vignette for more.

Open the getting started vignette.

vignette("decido", package = "decido")

Development

This is motivated by the topology aspirations of hypertidy/silicate. We need tools for decomposing shape data into primitives for analysis and visualization. Decomposition into graph types is already well supported and exercised, but triangulations of paths versus triangulations from edges are two key facilities needed for greater control.

This broader project is fairly well advanced in silicate and show-cased in hypertidy/anglr.

Other implementations

Ear clipping (or ear cutting) is also available in the rgl function triangulate (implemented in R), and in the lawn function lawn_tesselate (implemented via the Mapbox Javascript library earcut). In rgl the function also classifies input coordinates according to their nesting, a necessary first step if the relaionship between holes and islands is not known. The INLA package has some kind of constraint-based triangulation, but I don’t yet know the details.

In comparison to path-based ear-clipping, other libraries ‘Triangle’ and ‘CGAL’ provide edge-based mostly Delaunay triangulation. The Triangle library is available in the R package RTriangle. Experimental implementations binding CGAL are in rcgal and laridae.

Do you know of others? Let me know! Triangulation is common across many R packages, but constrained algorithms are pretty rare (it’s hard). There are many Delaunay and other non-constrained implementations in many packages, and I’m compiling a list of those as well. OTOH there’s rgeos, sf, deldir, geometry, tripack, spatstat, akima, several mesh-related packages Rvcg, meshsimp, icosa, webglobe …


Please note that the decido project is released with a Contributor Code of Conduct. By participating in this project you agree to abide by its terms.

News

decido 0.2.0

  • Increased automated test coverage of underlying library code.

  • Fixed a memory bug, thanks to CRAN checks.

  • Cleaned up some Rcpp defaults.

  • Updated readme.

  • Move oz to Suggests.

decido 0.1.0

  • Modified description based on advice from CRAN.

  • earcut is now generic, with a default argument that operates on matrix, list or data frame inputs - future extensions may dispatch on class of single xy argument.

  • Breaking change, all R functions now have xy as first argument, no more x or y as separate vectors. xy maybe a matrix, a list, or a dataframe.

decido 0.0.1

  • Added a vignette and more complete documentation.

  • Added helper functions plot_holes and plot_ears to wrap calls to polypath for polygon plot and triangle plot respectively, using the same style as function earcut.

  • Modified to use 1-based indexing always at R level, and wrapped internal function earcut_cpp with R level earcut with checks on inputs.

  • Removed need for numholes argument.

  • Fixed immense logic bug, not sure how it was working at all before.

  • Fixed file naming and declarations, thanks to Andrew Smith.

  • Added support for holes via earcut(x, y, holes = , numholes = ).

  • First implementation from basic template.

Reference manual

It appears you don't have a PDF plugin for this browser. You can click here to download the reference manual.

install.packages("decido")

0.2.0 by Michael Sumner, 4 months ago


https://hypertidy.github.io/decido


Report a bug at https://github.com/hypertidy/decido/issues


Browse source code at https://github.com/cran/decido


Authors: Michael Sumner [aut, cre] , Andrew Smith [ctb] (provided C++ guidance) , Mapbox [cph] (author of header library earcut.hpp) , Mark Padgham [ctb] (help with CRAN issues)


Documentation:   PDF Manual  


MIT + file LICENSE license


Imports Rcpp

Suggests covr, testthat, knitr, oz, rmarkdown

Linking to Rcpp

System requirements: C++11


See at CRAN