<div dir="ltr"><div>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.</div><div><br></div><div>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.</div><div><br></div><div>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?)</div><div><br></div><div>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.</div><div><br></div>[1] <a href="https://git.osgeo.org/gitea/geos/geos/src/branch/main/src/triangulate/polygon/PolygonTriangulator.cpp">https://git.osgeo.org/gitea/geos/geos/src/branch/main/src/triangulate/polygon/PolygonTriangulator.cpp</a><div>[2] <a href="https://git.osgeo.org/gitea/geos/geos/src/branch/main/src/triangulate/polygon/ConstrainedDelaunayTriangulator.cpp">https://git.osgeo.org/gitea/geos/geos/src/branch/main/src/triangulate/polygon/ConstrainedDelaunayTriangulator.cpp</a></div><div>[3] <a href="https://gitlab.com/Oslandia/SFCGAL/-/blob/master/src/triangulate/triangulatePolygon.cpp#L161">https://gitlab.com/Oslandia/SFCGAL/-/blob/master/src/triangulate/triangulatePolygon.cpp#L161</a></div><div><div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Wed, Sep 29, 2021 at 12:59 PM Darafei "Komяpa" Praliaskouski <<a href="mailto:me@komzpa.net">me@komzpa.net</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr">Hi,<div><br></div><div>After some thought, naming is terribly off and would cause a mess. The thing should be called GEOSTesselate or GEOSTriangulatePolygon but not just GEOSConstrainedDelaunayTriangulation.</div><div><br></div><div> - the function implemented in GEOS under name of <span>GEOSConstrainedDelaunayTriangu</span><span>lation is priorly called ST_Tesselate in SFCGAL / PostGIS. </span></div><div><span><br> - 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 "</span>tesselator". It is the name I know well from 3D graphics.<br><span><br> - ST_ConstrainedDelaunayTriangles exists in PostGIS and does not correspod to what  </span><span>GEOSConstrainedDelaunayTriangu</span><span>lation now does.<br></span><span><br> - </span><a href="https://www.cs.jhu.edu/~misha/Spring20/Chew87.pdf" target="_blank">https://www.cs.jhu.edu/~misha/Spring20/Chew87.pdf</a> calls the different thing a Constrained Delaunay Triangulation. It is not limited to interior of polygons but just accepts any edges as constraints.<span><br></span></div></div>
</blockquote></div></div></div></div>