[postgis-tickets] [SCM] PostGIS branch master updated. 3.3.0alpha1-60-gc75326215
git at osgeo.org
git at osgeo.org
Wed Jun 15 12:56:24 PDT 2022
This is an automated email from the git hooks/post-receive script. It was
generated because a ref change was pushed to the repository containing
the project "PostGIS".
The branch, master has been updated
via c7532621527e72926dc23efe855e3bc1a00145a5 (commit)
from 25b4d74a77ecb3e97ee4c892444c7d0d291c13fa (commit)
Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.
- Log -----------------------------------------------------------------
commit c7532621527e72926dc23efe855e3bc1a00145a5
Author: Paul Ramsey <pramsey at cleverelephant.ca>
Date: Wed Jun 15 12:56:03 2022 -0700
ST_TriangulatePolygon for contrained polygon triangulation
GEOS 3.11 only, "constrained polygon triangulation" outputs a set of triangles that exactly covers the input polygon.
diff --git a/NEWS b/NEWS
index 046a24fcd..f4a2690c9 100644
--- a/NEWS
+++ b/NEWS
@@ -53,6 +53,7 @@ Use below to enable it.
- GH657, GiST: do not call no-op decompress function (Aliaksandr Kalenik)
- #4912, GiST: fix crash on STORAGE EXTERNAL for geography (Aliaksandr Kalenik)
- ST_ConcaveHull GEOS 3.11+ native implementation (Paul Ramsey, Martin Davis)
+ - ST_ConcaveHull GEOS 3.11+ polygon-respecting native implementation (Paul Ramsey, Martin Davis)
- #4574, GH678, #5121 Enable Link-Time Optimizations using --enable-lto (Sergei Shoulbakov)
- GH676, faster ST_Clip (Aliaksandr Kalenik)
- #5135, Fast GiST index build is enabled by default for PostgreSQL 15+ (Sergei Shoulbakov)
@@ -66,6 +67,8 @@ Use below to enable it.
- GH659, MARC21/XML, ST_GeomFromMARC21, ST_AsMARC21 (Jim Jones)
- #5132, GH683, sfcgal: ST_3DUnion aggregate function (Sergei Shoulbakov)
- #5143, SFCGAL ST_AlphaShape and ST_OptimalAlphaShape (Loïc Bartoletti)
+ - ST_TriangulatePolygon with GEOS 3.11+ (Paul Ramsey, Martin Davis)
+ - ST_SimplifyPolygonHull with GEOS 3.11+ (Paul Ramsey, Martin Davis)
* Bug Fix *
- #5100, Support for PostgreSQL 15 (atoi removal) (Laurenz Albe)
diff --git a/doc/html/image_src/Makefile.in b/doc/html/image_src/Makefile.in
index ae87cc694..75a57f388 100644
--- a/doc/html/image_src/Makefile.in
+++ b/doc/html/image_src/Makefile.in
@@ -143,6 +143,7 @@ IMAGES= \
../images/st_pointonsurface02.png \
../images/st_pointonsurface03.png \
../images/st_pointonsurface04.png \
+ ../images/st_triangulatepolygon01.png \
../images/st_sharedpaths01.png \
../images/st_sharedpaths02.png \
../images/st_shortestline01.png \
diff --git a/doc/html/image_src/st_triangulatepolygon01.wkt b/doc/html/image_src/st_triangulatepolygon01.wkt
new file mode 100644
index 000000000..262bfc60d
--- /dev/null
+++ b/doc/html/image_src/st_triangulatepolygon01.wkt
@@ -0,0 +1,2 @@
+ArgA;GEOMETRYCOLLECTION(POLYGON((78 0,117 39,156 19.5,78 0)),POLYGON((156 19.5,195 39,195 0,156 19.5)),POLYGON((117 39,78 0,39 19.5,117 39)),POLYGON((39 19.5,0 0,0 39,39 19.5)),POLYGON((78 0,156 19.5,195 0,78 0)),POLYGON((117 39,39 19.5,0 39,117 39)))
+ArgB;POLYGON((0 0,0 39,117 39,156 19.5,195 39,195 0,78 0,39 19.5,0 0))
diff --git a/doc/reference_processing.xml b/doc/reference_processing.xml
index ea7c61bf9..9dcdc31b2 100644
--- a/doc/reference_processing.xml
+++ b/doc/reference_processing.xml
@@ -996,7 +996,7 @@ POLYGON((154 14,150 14,154 6,154 14))
</informaltable>
</refsection>
<refsection>
- <title>3D Examples</title>
+ <title>Example 1</title>
<programlisting>-- 3D multipoint --
SELECT ST_AsText(ST_DelaunayTriangles(ST_GeomFromText(
'MULTIPOINT Z(14 14 10,
@@ -1006,13 +1006,71 @@ SELECT ST_AsText(ST_DelaunayTriangles(ST_GeomFromText(
GEOMETRYCOLLECTION Z (POLYGON Z ((14 14 10,20 10 150,34 6 25,14 14 10))
,POLYGON Z ((14 14 10,34 6 25,150 14 100,14 14 10)))</programlisting>
</refsection>
+ </refentry>
+
+
+ <refentry id="ST_TriangulatePolygon">
+ <refnamediv>
+ <refname>ST_TriangulatePolygon</refname>
+ <refpurpose>Computes the constrained Delaunay triangulation of polygons</refpurpose>
+ </refnamediv>
+
+ <refsynopsisdiv>
+ <funcsynopsis>
+ <funcprototype>
+ <funcdef>geometry <function>ST_TriangulatePolygon</function></funcdef>
+ <paramdef><type>geometry</type> <parameter>geom</parameter></paramdef>
+ </funcprototype>
+ </funcsynopsis>
+ </refsynopsisdiv>
+
+ <refsection>
+ <title>Description</title>
+ <para>Computes the constrained Delaunay triangulation of polygons. The "constrained Delaunay triangulation" of a polygon is a set of triangles covering the polygon, with the maximum total interior angle over all possible triangulations. It provides the "best quality" triangulation of the polygon.</para>
+
+ <para>Availability: 3.3.0</para>
+ </refsection>
+
+ <refsection>
+ <title>Example</title>
+ <para>A square is triangulated</para>
+ <programlisting>
+SELECT ST_AsText(
+ ST_TriangulatePolygon('POLYGON((0 0, 0 1, 1 1, 1 0, 0 0))'));
+
+ st_astext
+---------------------------------------------------------------------------
+ GEOMETRYCOLLECTION(POLYGON((0 0,0 1,1 1,0 0)),POLYGON((1 1,1 0,0 0,1 1)))
+ </programlisting>
+ </refsection>
+ <refsection>
+ <title>Example</title>
+ <programlisting>SELECT ST_AsText(ST_TriangulatePolygon(
+ 'POLYGON((0 0, 0 1, 3 1, 4 0.5, 5 1, 5 0, 2 0, 1 0.5, 0 0))'
+ ));
+</programlisting>
+ <informalfigure>
+ <mediaobject>
+ <imageobject>
+ <imagedata fileref="images/st_triangulatepolygon01.png" />
+ </imageobject>
+ <caption><para>Polygon Triangulation</para></caption>
+ </mediaobject>
+ </informalfigure>
+ </refsection>
<refsection>
<title>See Also</title>
- <para><xref linkend="ST_ConstrainedDelaunayTriangles" />, <xref linkend="ST_ConcaveHull" />, <xref linkend="ST_Dump" />, <xref linkend="ST_Tesselate" />
+ <para><xref linkend="ST_ConstrainedDelaunayTriangles" />, <xref linkend="ST_ConcaveHull" />, <xref linkend="ST_Dump" />, <xref linkend="ST_Tesselate" />, <xref linkend="ST_TriangulatePolygon" />
</para>
</refsection>
+
+ <refsection>
+ <title>See Also</title>
+ <para><xref linkend="ST_DelaunayTriangles" />, <xref linkend="ST_ConstrainedDelaunayTriangles" />, <xref linkend="ST_Tesselate" /></para>
+ </refsection>
</refentry>
+
<refentry id="ST_FilterByM">
<refnamediv>
<refname>ST_FilterByM</refname>
diff --git a/liblwgeom/liblwgeom.h.in b/liblwgeom/liblwgeom.h.in
index 94f79ad72..7ffffa8a7 100644
--- a/liblwgeom/liblwgeom.h.in
+++ b/liblwgeom/liblwgeom.h.in
@@ -2525,6 +2525,7 @@ LWGEOM* lwgeom_node(const LWGEOM* lwgeom_in);
*/
LWGEOM* lwgeom_delaunay_triangulation(const LWGEOM *geom, double tolerance, int32_t edgeOnly);
+
/**
* Take vertices of a geometry and build the Voronoi diagram
*
@@ -2562,6 +2563,14 @@ LWGEOM* lwgeom_concavehull(const LWGEOM* geom, double ratio, uint32_t allow_hole
LWGEOM*
lwgeom_simplify_polygonal(const LWGEOM* geom, double vertex_fraction, uint32_t is_outer);
+/**
+ * Take vertices of a polygon and build a constrained triangulation
+ * that respects the boundary of the polygon.
+ *
+ * @param geom the input geometry
+ */
+LWGEOM* lwgeom_triangulate_polygon(const LWGEOM* geom);
+
#endif
/**
diff --git a/liblwgeom/lwgeom_geos.c b/liblwgeom/lwgeom_geos.c
index f52acf724..afdad095a 100644
--- a/liblwgeom/lwgeom_geos.c
+++ b/liblwgeom/lwgeom_geos.c
@@ -2015,6 +2015,7 @@ lwgeom_delaunay_triangulation(const LWGEOM* geom, double tolerance, int32_t outp
return result;
}
+
static GEOSCoordSequence*
lwgeom_get_geos_coordseq_2d(const LWGEOM* g, uint32_t num_points)
{
@@ -2172,4 +2173,31 @@ lwgeom_simplify_polygonal(const LWGEOM* geom, double vertex_fraction, uint32_t i
return result;
}
+LWGEOM*
+lwgeom_triangulate_polygon(const LWGEOM* geom)
+{
+ LWGEOM* result;
+ int32_t srid = RESULT_SRID(geom);
+ uint8_t is3d = FLAGS_GET_Z(geom->flags);
+ GEOSGeometry *g1, *g3;
+
+ if (srid == SRID_INVALID) return NULL;
+
+ initGEOS(lwnotice, lwgeom_geos_error);
+
+ if (!(g1 = LWGEOM2GEOS(geom, AUTOFIX))) GEOS_FAIL();
+
+ /* if output != 1 we want polys */
+ g3 = GEOSConstrainedDelaunayTriangulation(g1);
+
+ if (!g3) GEOS_FREE_AND_FAIL(g1);
+ GEOSSetSRID(g3, srid);
+
+ if (!(result = GEOS2LWGEOM(g3, is3d)))
+ GEOS_FREE_AND_FAIL(g1, g3);
+
+ GEOS_FREE(g1, g3);
+ return result;
+}
+
#endif
diff --git a/postgis/lwgeom_geos.c b/postgis/lwgeom_geos.c
index a07b1a4e8..8919e20e5 100644
--- a/postgis/lwgeom_geos.c
+++ b/postgis/lwgeom_geos.c
@@ -3234,6 +3234,43 @@ Datum ST_DelaunayTriangles(PG_FUNCTION_ARGS)
PG_RETURN_POINTER(result);
}
+/*
+ * Take a polygon and build a constrained
+ * triangulation that respect the edges of the
+ * polygon.
+ */
+PG_FUNCTION_INFO_V1(ST_TriangulatePolygon);
+Datum ST_TriangulatePolygon(PG_FUNCTION_ARGS)
+{
+#if POSTGIS_GEOS_VERSION < 31100
+
+ lwpgerror("The GEOS version this PostGIS binary "
+ "was compiled against (%d) doesn't support "
+ "'GEOSConstrainedDelaunayTriangulation' function (3.11.0+ required)",
+ POSTGIS_GEOS_VERSION);
+ PG_RETURN_NULL();
+
+#else /* POSTGIS_GEOS_VERSION >= 31100 */
+ GSERIALIZED *result;
+ GSERIALIZED *geom = PG_GETARG_GSERIALIZED_P(0);
+ LWGEOM *lwgeom_in = lwgeom_from_gserialized(geom);
+ LWGEOM *lwgeom_out = lwgeom_triangulate_polygon(lwgeom_in);
+ lwgeom_free(lwgeom_in);
+
+ if (!lwgeom_out)
+ {
+ PG_FREE_IF_COPY(geom, 0);
+ PG_RETURN_NULL();
+ }
+
+ result = geometry_serialize(lwgeom_out);
+ lwgeom_free(lwgeom_out);
+
+ PG_FREE_IF_COPY(geom, 0);
+ PG_RETURN_POINTER(result);
+#endif
+}
+
/*
* ST_Snap
*
diff --git a/postgis/postgis.sql.in b/postgis/postgis.sql.in
index 00035820f..5e1d202ff 100644
--- a/postgis/postgis.sql.in
+++ b/postgis/postgis.sql.in
@@ -3917,6 +3917,24 @@ CREATE OR REPLACE FUNCTION ST_DelaunayTriangles(g1 geometry, tolerance float8 DE
LANGUAGE 'c' IMMUTABLE STRICT PARALLEL SAFE
_COST_HIGH;
+--------------------------------------------------------------------------------
+-- ST_TriangulatePolygon
+--------------------------------------------------------------------------------
+
+-- ST_TriangulatePolygon(g1 geometry)
+--
+-- Builds a triangulation that respects the boundaries of the polygon.
+--
+-- Returns a collection of triangular polygons.
+--
+-- Availability: 3.3.0
+--
+CREATE OR REPLACE FUNCTION ST_TriangulatePolygon(g1 geometry)
+ RETURNS geometry
+ AS 'MODULE_PATHNAME', 'ST_TriangulatePolygon'
+ LANGUAGE 'c' IMMUTABLE STRICT PARALLEL SAFE
+ _COST_HIGH;
+
--------------------------------------------------------------------------------
-- _ST_Voronoi
--------------------------------------------------------------------------------
diff --git a/regress/core/geos311.sql b/regress/core/geos311.sql
index cce4ae686..6731ade0e 100644
--- a/regress/core/geos311.sql
+++ b/regress/core/geos311.sql
@@ -51,3 +51,20 @@ SELECT 'simplifypolygonhull-3' AS test,
'POLYGON((0 0, 0 1, 0.5 0.1, 0.5 0.1, 1 1, 1 0, 0 0))'::geometry,
0.85),1);
+-- ST_TriangulatePolygon --
+select 'triangulatepolygon-1' AS text,
+ ST_AsText(ST_Normalize(ST_TriangulatePolygon('POLYGON((0 0, 0 1, 1 1, 1 0, 0 0))')), 1);
+
+select 'triangulatepolygon-2' AS text,
+ ST_AsText(ST_Normalize(ST_TriangulatePolygon('MULTIPOLYGON(((0 0, 0 1, 1 1, 1 0, 0 0)))')), 1);
+
+select 'triangulatepolygon-3' AS text,
+ ST_AsText(ST_Normalize(ST_TriangulatePolygon('LINESTRING(0 0, 0 1, 1 1, 1 0, 0 0)')), 1);
+
+select 'triangulatepolygon-4' AS text,
+ ST_AsText(ST_Normalize(ST_TriangulatePolygon('POINT(1 0)')), 1);
+
+select 'triangulatepolygon-5' AS text,
+ ST_AsText(ST_Normalize(ST_TriangulatePolygon(
+ 'GEOMETRYCOLLECTION(POLYGON((0 0,0 1,1 1,0 0)),POLYGON((1 1,1 0,0 0,1 1)), POINT(1 1))'
+ )), 1);
diff --git a/regress/core/geos311_expected b/regress/core/geos311_expected
index 01d9fbbfc..1ef8e742e 100644
--- a/regress/core/geos311_expected
+++ b/regress/core/geos311_expected
@@ -5,3 +5,8 @@ concavehull02-points|t|ST_Polygon|t
simplifypolygonhull-1|POLYGON((0 0,0 1,1 1,1 0,0 0))
simplifypolygonhull-2|POLYGON((0 0,0 1,1 1,1 0,0 0))
simplifypolygonhull-3|POLYGON((0 0,0 1,0.5 0.1,1 1,1 0,0 0))
+triangulatepolygon-1|GEOMETRYCOLLECTION(POLYGON((0 0,1 1,1 0,0 0)),POLYGON((0 0,0 1,1 1,0 0)))
+triangulatepolygon-2|GEOMETRYCOLLECTION(POLYGON((0 0,1 1,1 0,0 0)),POLYGON((0 0,0 1,1 1,0 0)))
+triangulatepolygon-3|GEOMETRYCOLLECTION EMPTY
+triangulatepolygon-4|GEOMETRYCOLLECTION EMPTY
+triangulatepolygon-5|GEOMETRYCOLLECTION(POLYGON((0 0,1 1,1 0,0 0)),POLYGON((0 0,0 1,1 1,0 0)))
-----------------------------------------------------------------------
Summary of changes:
NEWS | 3 ++
doc/html/image_src/Makefile.in | 1 +
doc/html/image_src/st_triangulatepolygon01.wkt | 2 +
doc/reference_processing.xml | 62 +++++++++++++++++++++++++-
liblwgeom/liblwgeom.h.in | 9 ++++
liblwgeom/lwgeom_geos.c | 28 ++++++++++++
postgis/lwgeom_geos.c | 37 +++++++++++++++
postgis/postgis.sql.in | 18 ++++++++
regress/core/geos311.sql | 17 +++++++
regress/core/geos311_expected | 5 +++
10 files changed, 180 insertions(+), 2 deletions(-)
create mode 100644 doc/html/image_src/st_triangulatepolygon01.wkt
hooks/post-receive
--
PostGIS
More information about the postgis-tickets
mailing list