The naming of ConstrainedDelaunayTriangulation is deliberate. It *is* a Constrained Delaunay Triangulation that currently works only on polygonal inputs. The implementation of the Ear-Clipping algorithm is done in PolygonTriangulator [1]. The ConstrainedDelaunayTriangulator uses that triangulation as input, and "improves" it to be a true CDT of polygons.
The hope/intent is to expand the CDT functionality to handle more general (i.e. linear) constraints in the future. But that does not mean that it can't be called CDT now. Tesselate just means "a tiling of some sort", and does not imply the more specific case of Constrained Delaunay Triangulation. As far as I can tell this terminology was introduced by SFCGAL, and in fact SFCGAL implements it using ConstrainedDelaunayTriangulation [3]. I don't know why they introduced a new term for this (anyone have an insight into this?) Also, IMO there is no requirement that PostGIS and GEOS terminology align. PostGIS has a different pedigree and set of dependencies. If this gets exposes as ST_Tesselate then that's fine. But that's a separate discussion that should be had when the PostGIS bindings are worked on. [1] https://git.osgeo.org/gitea/geos/geos/src/branch/main/src/triangulate/polygon/PolygonTriangulator.cpp [2] https://git.osgeo.org/gitea/geos/geos/src/branch/main/src/triangulate/polygon/ConstrainedDelaunayTriangulator.cpp [3] https://gitlab.com/Oslandia/SFCGAL/-/blob/master/src/triangulate/triangulatePolygon.cpp#L161 On Wed, Sep 29, 2021 at 12:59 PM Darafei "Komяpa" Praliaskouski < m...@komzpa.net> wrote: > Hi, > > After some thought, naming is terribly off and would cause a mess. The > thing should be called GEOSTesselate or GEOSTriangulatePolygon but not just > GEOSConstrainedDelaunayTriangulation. > > - the function implemented in GEOS under name of > GEOSConstrainedDelaunayTriangulation is priorly called ST_Tesselate in > SFCGAL / PostGIS. > > - ear clipping algorithm does not produce a Delaunay triangulation. In > Vladimir Agafonkin's earcut it's referenced as "polygon triangulation". The > docs referenced from its readme call alternative implementations "tesselator". > It is the name I know well from 3D graphics. > > - ST_ConstrainedDelaunayTriangles exists in PostGIS and does not > correspod to what GEOSConstrainedDelaunayTriangulation now does. > > - https://www.cs.jhu.edu/~misha/Spring20/Chew87.pdf calls the different > thing a Constrained Delaunay Triangulation. It is not limited to interior > of polygons but just accepts any edges as constraints. >
_______________________________________________ geos-devel mailing list geos-devel@lists.osgeo.org https://lists.osgeo.org/mailman/listinfo/geos-devel
