library(RCDT)
The ‘RCDT’ package is based on the C++ library ‘CDT’. It allows to construct 2D constrained Delaunay triangulations. A constrained Delaunay triangulation is like an ordinary Delaunay triangulation but it can force certain given segments to belong to the triangulation as edges.
For example, it allows to triangulate a concave polygon, by forcing the edges of this polygon to belong to the triangulation. Let’s illustrate this possibility with a pentagram.
# vertices
<- sqrt((5-sqrt(5))/10) # outer radius
R <- sqrt((25-11*sqrt(5))/10) # circumradius of the inner pentagon
r <- pi/180 # factor to convert degrees to radians
k <- R * vapply(0L:4L, function(i) cos(k * (90+72*i)), numeric(1L))
X <- R * vapply(0L:4L, function(i) sin(k * (90+72*i)), numeric(1L))
Y <- r * vapply(0L:4L, function(i) cos(k * (126+72*i)), numeric(1L))
x <- r * vapply(0L:4L, function(i) sin(k * (126+72*i)), numeric(1L))
y <- rbind(
vertices c(X[1L], Y[1L]),
c(x[1L], y[1L]),
c(X[2L], Y[2L]),
c(x[2L], y[2L]),
c(X[3L], Y[3L]),
c(x[3L], y[3L]),
c(X[4L], Y[4L]),
c(x[4L], y[4L]),
c(X[5L], Y[5L]),
c(x[5L], y[5L])
)# constraint edges: indices
<- cbind(1L:10L, c(2L:10L, 1L))
edges # constrained Delaunay triangulation
<- delaunay(vertices, edges)
del # plot
<- par(mar = c(0, 0, 0, 0))
opar plotDelaunay(
type = "n", asp = 1, fillcolor = "distinct", lwd_borders = 3,
del, xlab = NA, ylab = NA, axes = FALSE
)
par(opar)
Since the polygon is triangulated, it is easy to get its area. It is
given by the function delaunayArea
:
delaunayArea(del)
#> [1] 0.3102707
sqrt(650 - 290*sqrt(5)) / 4 # exact value
#> [1] 0.3102707
Another possibility offered by the constrained Delaunay triangulation is the triangulation of a “donut polygon”, roughly speaking a “polygon with holes”. Let’s see an example.
<- 6L
nsides <- seq(0, 2*pi, length.out = nsides+1L)[-1L]
angles <- cbind(cos(angles), sin(angles))
outer_points <- outer_points / 2
inner_points <- rbind(outer_points, inner_points)
points # constraint edges
<- 1L:nsides
indices <- cbind(
edges_outer c(indices[-1L], indices[1L])
indices,
)<- edges_outer + nsides
edges_inner <- rbind(edges_outer, edges_inner)
edges # constrained Delaunay triangulation
<- delaunay(points, edges)
del # plot
<- par(mar = c(0, 0, 0, 0))
opar plotDelaunay(
type = "n", asp = 1, axes = FALSE, xlab = NA, ylab = NA,
del, fillcolor = "yellow", lwd_borders = 3, col_borders = "navy"
)
par(opar)
The area of the outer hexagon is 3*sqrt(3)/2
and the
area of the inner hexagon (the hole) is 3*sqrt(3)/8
. Let’s
check:
delaunayArea(del)
#> [1] 1.948557
3*sqrt(3)/2 - 3*sqrt(3)/8
#> [1] 1.948557