[geos-devel] GEOSConstrainedDelaunayTriangulation

[Darafei "Komяpa" Praliaskouski]

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.


On Sat, Sep 25, 2021 at 11:12 PM Martin Davis <mtnclimb at gmail.com> wrote:

> Constrained DelaunayTriangulation for polygonal geometry is now available
> via geosop:
>
> bin/geosop -a polygons.wkt -f wkt constrainedDelaunay
>
> Performance is equivalent to the JTS version (which is very good). There
> seems to be slowness on MultiPolygons for some reason - we'll look into
> that soon.
>
> On Thu, Sep 23, 2021 at 2:20 PM Paul Ramsey <pramsey at cleverelephant.ca>
> wrote:
>
>> FYI on a big new port dropping from JTS today. Maybe Martin can share
>> some pictures.
>>
>>   - CAPI: GEOSConstrainedDelaunayTriangulation, builds a constrained
>> triangulation
>>           of an input Polygon or MultiPolygon, returning a
>> GeometryCollection(Polygon)
>>           of the triangles.
>>
>>
>>
>> https://github.com/libgeos/geos/commit/896af228fb27076bdd7f0529d55b3e79e3f10191
>> _______________________________________________
>> geos-devel mailing list
>> geos-devel at lists.osgeo.org
>> https://lists.osgeo.org/mailman/listinfo/geos-devel
>>
> _______________________________________________
> geos-devel mailing list
> geos-devel at lists.osgeo.org
> https://lists.osgeo.org/mailman/listinfo/geos-devel
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/geos-devel/attachments/20210929/272d8fc1/attachment.html>