mdsumner
commented
7 years ago Examples
Here's what standard Delaunay will do when applied individually to simple features.
p1 <- cbind(x = c(0, 0, 0.75, 1, 0.5, 0.8, 0.69, 0),
y = c(0, 1, 1, 0.8, 0.7, 0.6, 0, 0))
p2 <- cbind(x = c(0.2, 0.2, 0.3, 0.5, 0.5, 0.2),
y = c(0.2, 0.4, 0.6, 0.4, 0.2, 0.2))
p4 <- cbind(x = c(0.69, 0.8, 1.1, 1.23, 0.69),
y = c(0, 0.6, 0.63, 0.3, 0))
library(sf)
g <- data.frame(a = 1:2)
g[["geometry"]] <- st_sfc(st_multipolygon(list(list(p1, p2[nrow(p2):1, ]))), st_multipolygon(list(list(p4))))
g <- st_as_sf(g)
plot(g)
gt <- g
st_geometry(gt) <- st_triangulate(st_geometry(g))
plot(gt, col = scales::alpha(c("dodgerblue", "firebrick"), 0.3), main = "convex hull each feature")
plot(st_geometry(g), add = TRUE, lwd = 4)The sf dataset:
The triangles align to the convex hull of the coordinates of each feature, and overlap each other because they are created without knowledge of the other, or of the input edges generally.
In the constrained version the triangles are completely aligned to the original inputs (triangles in holes are trivially filtered out by seeding the algorithm on input, or detecting them afterwards - and it can be done per-feature or per-feature-set, there are pros and cons for different situations).
I don't have concise code for this on hand but this is the result:
Here's a result from rgl for just the first feature, the actual triangles depend on where the paths start and the algorithm being deterministic or not, but it doesn't need segments as input, and comes with easy 3D plotting and so on.
xyna <- rbind(p1[-1, ], NA, p2[-1, ])
rgl_tr <- rgl::triangulate(xyna, random = FALSE)
plot(g, col = "grey")
apply(rgl_tr, 2, function(a) polygon(xyna[a, ], col = "dodgerblue"))
edzer
Ironholds
Robinlovelace
I would like to have access to constrained triangulation algorithms. This means that index-pairs on a set of coordinates defining segments (i.e. lines) can be input to constrain the result. This is typically used to modify what would be a Delaunay Triangulation (filling the convex hull) to include those lines. Good algorithms can provide provably good triangular meshes and include extra features like 1) insertions of extra Steiner points (segmentization) 2) maximum triangle area 3) maximum internal angles.
Being able to do this means you can triangulate polygons with concavities and/or holes and only get triangles where you had polygon, which is not generally true of most triangulation algorithms.
Extra coolness would come from being able to update an existing mesh by inserting/removing segments, and being able to apply triangulation or update it within local regions of a data set. CGAL has some of this capacity https://doc.cgal.org/latest/Triangulation_2/ The reason that would be useful, beyond raw performance, is that the triangulation result always depends on the coordinate system in use, so while we often use generic crs like "longitude-latitude" or Mercator for general storage and transfer, it will make sense to project individual features to a local space for triangulating, even if those elements then get used in a totally different coordinate system.
My wishlist questions are:
I can guide the example data sets and preparing them for input from
sf, comparing withrglandRTriangleand so forth, but compiling external libs into R is very hard for me.Existing libraries
There are many R packages with triangulation, but only two have a constrained version afaik.
RTriangle, that wraps Shewchuk's Triangle lib: https://www.cs.cmu.edu/~quake/triangle.html it's extremely fast and easy to use and offers many bells and whistles, but is precluded from use in commercial contexts.rglwith itsextrude3dthat applies an ear-clipping algorithm, which is a constrained triangulation but has no guarantees of "goodness". Ear clipping can be used to get small triangles by inserting Steiner points and retriangulating, but it'll never be as good as near-Delaunay.Does anyone know of any others?
CGAL, BOOST, JTS, Manifold GIS, and Triangle have tools for the constrained Delaunay algorithms (I have a longer list of libs somewhere, but it's not longer than 10 or so.
Manifold's Radian engine is putting massive effort into this kind of capability, and are quietly developing a super-powered spatially capable database engine with a free viewer, though Windows-only at this stage (mid 2017).
Triangle is available in R package RTriangle, but under a non-commercial license.
CGAL has been built in small form in an R package here: https://github.com/s-u/rcgal I've compiled and used triangulation with CGAL very basically via Rcpp, but generally the CGAL code is too advanced for me.
geomeryprovidesconvhullnwhich gives the convex hull in nD, and so closed meshes in 3D are available easily.Manifold is straightforward but it only offers one form of the algorithm, only works on Windows, and is closed source and proprietary. It's good software, but not a serious contender for this problem at the moment.
The best text I know on this topic is:
https://www.crcpress.com/Delaunay-Mesh-Generation/Cheng-Dey-Shewchuk/p/book/9781584887300