[geos-devel] GEOSConstrainedDelaunayTriangulation

[Martin Davis]

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 <
me at 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.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/geos-devel/attachments/20210929/70389eab/attachment.html>