-
-
Notifications
You must be signed in to change notification settings - Fork 3
/
README.Rmd
147 lines (105 loc) · 6.64 KB
/
README.Rmd
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
---
output: github_document
editor_options:
chunk_output_type: console
---
<!-- README.md is generated from README.Rmd. Please edit that file -->
<!-- badges: start -->
[](https://github.com/hypertidy/decido/actions)
[](https://www.tidyverse.org/lifecycle/#stable)
[](https://travis-ci.org/hypertidy/decido)
[](https://ci.appveyor.com/project/mdsumner/decido)
[](https://codecov.io/github/hypertidy/decido?branch=master)
[](https://CRAN.R-project.org/package=decido)
[](https://CRAN.R-project.org/package=decido)
<!-- badges: end -->
```{r setup, include = FALSE}
knitr::opts_chunk$set(
collapse = TRUE,
comment = "#>",
fig.path = "man/figures/README-",
out.width = "100%"
)
```
# decido
The goal of decido is to provide an R binding to the Mapbox library [earcut.hpp](https://github.com/mapbox/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.
## Installation
Install the released version from CRAN.
```R
install.packages("decido")
```
You can install the development version from GitHub with the following code.
```R
## install.packages("remotes")
remotes::install_github("hypertidy/decido")
```
## Example
This is a basic example of triangulating a single-ring polygon. The
output is a vector of triplet indices defining each triangle.
```{r example}
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))
```
See the [documentation](https://hypertidy.github.io/decido/) and [vignette](https://hypertidy.github.io/decido/articles/decido.html) for more.
Open the getting started vignette.
```R
vignette("decido", package = "decido")
```
## Development
There is a C++ headers API for decido.
```{r headers}
library(Rcpp)
cppFunction(
depends = "decido"
, includes = '#include "decido/decido.hpp"'
, code = '
Rcpp::IntegerVector earcut0( SEXP polygon ) {
return decido::api::earcut( polygon );
}
'
)
poly <- list(matrix(c(0,0,0,1,1,1,1,0,0,0), ncol = 2, byrow = T))
earcut0( poly )
```
## Motivation
Triangles can be addictive once you get used to them and can really focus attention on how simple things work. I love this sneaky trick for turning a set of unique coordinates into a picture with basic array, plot, and index idioms.
```{r tricks}
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)
idx <- earcut(cbind(x, y))
## idx is triplets of indices into x,y
plot(cbind(x, y)[rbind(matrix(idx, nrow = 3)[c(1:3, 1), ], NA), ], type = "l", lwd = 2, col = "darkgrey")
```
The need for polygon triangulation was originally motivated by the topology aspirations of
[silicate](https://CRAN.r-project.org/package=silicate) needing 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 which provides
ear-cutting triangulations and enhanced with high-quality methods in
[hypertidy/anglr](https://github.com/hypertidy/anglr).
To triangulate sf polygons see [function
here](https://github.com/hypertidy/decido/issues/9). For high-quality
triangulations of sf polygons directly see
[sfdct](https://CRAN.r-project.org/package=sfdct).
## Other implementations
Ear clipping (or ear cutting) is also available in the [rgl](https://CRAN.r-project.org/package=rgl) function `triangulate` (implemented in R), and in the [lawn](https://CRAN.r-project.org/package=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 relationship 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](https://CRAN.r-project.org/package=RTriangle), for spatial formats in the [anglr](https://CRAN.r-project.org/package=anglr), and in a limited sf wrapper in [sfdct](https://CRAN.r-project.org/package=sfdct).
The best prospects for high-quality trianguation is probably the [CGAL](https://www.cgal.org/) library, and this now available to R via the [cgalheaders](https://github.com/dickoa/cgalheaders) package, similarly used in the [prepair](https://github.com/dickoa/prepair) package.
Older experimental implementations binding CGAL are in [rcgal](https://github.com/s-u/rcgal) and [laridae](https://github.com/hypertidy/laridae).
There's an interesting new package [terrainmeshr](https://CRAN.r-project.org/package=terrainmeshr)for triangulating rasters based on the [hmm](https://github.com/fogleman/hmm) library, this is leveraged in the dev-version of the [anglr](https://CRAN.r-project.org/package=anglr).
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 ...
There's a rough and old benchmark here: https://rpubs.com/cyclemumner/416456
---
Please note that the decido project is released with a [Contributor Code of Conduct](https://github.com/hypertidy/decido/blob/master/CODE_OF_CONDUCT.md). By participating in this project you agree to abide by its terms.