# Constrained Triangulation for Simple Features

Build a constrained Delaunay triangulation from simple features objects, applying constraints based on input line segments, and triangle properties including maximum area, minimum internal angle. The triangulation code in 'RTriangle' uses the method of Cheng, Dey and Shewchuk (2012, ISBN:9781584887300). For a low-dependency alternative with low-quality path-based constrained triangulation see < https://CRAN.R-project.org/package=decido>.

The goal of sfdct is to provide constrained triangulation of simple features.

## Limitations

Triangulation is performed with respect to the vertices and edges per-feature. This means that each output feature will be composed of triangles that align to all input edges. This will also correspond to the outer hull of any lines or polygons. In a GEOMETRYCOLLECTION the same alignment only applies to geometries individually within the collection, so lines and polygons and point sets are all triangulated as if they were independent.

A future release will triangulate the GEOMETRYCOLLECTION as it it were one set of edges and vertices. This will also allow an entire data set to be triangulated as one.

It's not yet clear to me how to best maintain the original feature identity for the "entire data set" case, or if this even matters. Please get in touch if you are interested!

More general structures for working with grouped simplicial complex data structures are in the works, but aligning with simple features in this package provides a useful illustration of these nuances and how far we can push the standard tools.

## Example

This is a basic example which shows you how to decompose a MULTIPOLYGON `sf` data frame object into a GEOMETRYCOLLECTION `sf` data frame object made of triangles:

Denser triangles, and optionally `D` for ensuring Delaunay criterion is met.

See the vignettes for more examples.

If you are interested in development in this area see laridae which aims to provide a more powerful facility for finite element decomposition for complex shapes using CGAL. We'll also put an ear-clipping version, from rgl into silicate

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

# sfdct 0.0.5

• fix tests after st_cast changes in sf

# sfdct 0.0.4

• inserted spaces after the word POLYGON

# sfdct 0.0.3

• first CRAN release

• fixed lurking bug in all-POINT logic, ... was passed to pslg

# sfdct 0.0.2

• GEOMETRYCOLLECTION is now supported with an internal function only

• GEOMETRYCOLLECTION now supported, but only as sub-geometries treated like features - a future release will triangulate a simplicial complex of the GC

• introduced use of sp::over so that intersection tests are fast enough, will clean this up in future

• now properly returns GEOMETRYCOLLECTION of POLYGON triangles for sfg, sfc, and sf classes. Previous versions always returned either sf or sfc, so this wasn't consistent.

• more coverage of types, will at least work for the non-exotics in an sf dataframe

• first release

# Reference manual

install.packages("sfdct")

0.0.6 by Michael D. Sumner, 3 months ago

https://github.com/hypertidy/sfdct

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

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

Authors: Michael D. Sumner [aut, cre]

Documentation:   PDF Manual