From 5c78167eced1d749f09cb8bded2b06e57a18f4d2 Mon Sep 17 00:00:00 2001 From: Sandro Santilli Date: Wed, 27 Jun 2012 15:53:53 +0000 Subject: [PATCH] Add ST_DelaunayTriangles (#1215) git-svn-id: http://svn.osgeo.org/postgis/trunk@9994 b70326c6-7e19-0410-871a-916f4a2858ee --- NEWS | 1 + doc/reference_processing.xml | 44 ++++++++++++++++++++++++++++++ postgis/lwgeom_geos.c | 34 +++++++++++++++++++++++ postgis/postgis.sql.in.c | 24 ++++++++++++++++ regress/Makefile.in | 7 +++++ regress/delaunaytriangles.sql | 5 ++++ regress/delaunaytriangles_expected | 4 +++ 7 files changed, 119 insertions(+) create mode 100644 regress/delaunaytriangles.sql create mode 100644 regress/delaunaytriangles_expected diff --git a/NEWS b/NEWS index 02d5aaf43..8704a81e2 100644 --- a/NEWS +++ b/NEWS @@ -3,6 +3,7 @@ PostGIS 2.1.0 * New Features * + - ST_DelaunayTriangles (Sandro Santilli / Vizzuality) - ST_NearestValue, ST_Neighborhood (Bborie Park / UC Davis) - ST_Raster2WorldCoord, ST_World2RasterCoord (Bborie Park / UC Davis) - #1643, Tiger Geocoder - Tiger 2011 loader (Regina Obe / Paragon Corporation) diff --git a/doc/reference_processing.xml b/doc/reference_processing.xml index 871057265..eb7fdced9 100644 --- a/doc/reference_processing.xml +++ b/doc/reference_processing.xml @@ -870,6 +870,50 @@ st_astext + + + ST_DelaunayTriangles + + +Return a Delaunay triangulation around the given input points. + + + + + + + geometry ST_DelaunayTriangles + geometry g1 + float tolerance + int4 flags + + + + + + Description + + +Return a Delaunay +triangulation around the vertices of the input geometry. +Output is a COLLECTION of polygons (for flags=0) or a MULTILINESTRING +(for flags=1). The tolerance, if any, is used to snap input vertices +togheter. + + + Availability: 2.1.0 - requires GEOS >= 3.4.0. + + + + + See Also + + + + + + ST_Difference diff --git a/postgis/lwgeom_geos.c b/postgis/lwgeom_geos.c index b54535739..cd31cf643 100644 --- a/postgis/lwgeom_geos.c +++ b/postgis/lwgeom_geos.c @@ -72,6 +72,7 @@ Datum hausdorffdistancedensify(PG_FUNCTION_ARGS); Datum ST_UnaryUnion(PG_FUNCTION_ARGS); Datum ST_Equals(PG_FUNCTION_ARGS); Datum ST_BuildArea(PG_FUNCTION_ARGS); +Datum ST_DelaunayTriangles(PG_FUNCTION_ARGS); Datum pgis_union_geometry_array(PG_FUNCTION_ARGS); @@ -3374,6 +3375,39 @@ Datum ST_BuildArea(PG_FUNCTION_ARGS) PG_RETURN_POINTER(result); } +/* + * Take the vertices of a geometry and builds + * Delaunay triangles around them. + */ +PG_FUNCTION_INFO_V1(ST_DelaunayTriangles); +Datum ST_DelaunayTriangles(PG_FUNCTION_ARGS) +{ + GSERIALIZED *result; + GSERIALIZED *geom; + LWGEOM *lwgeom_in, *lwgeom_out; + double tolerance = 0.0; + int flags = 0; + + geom = (GSERIALIZED*)PG_DETOAST_DATUM(PG_GETARG_DATUM(0)); + tolerance = PG_GETARG_FLOAT8(1); + flags = PG_GETARG_INT32(2); + + lwgeom_in = lwgeom_from_gserialized(geom); + lwgeom_out = lwgeom_delaunay_triangulation(lwgeom_in, tolerance, flags); + 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); +} + /* * ST_Snap * diff --git a/postgis/postgis.sql.in.c b/postgis/postgis.sql.in.c index e9541e0b8..021ba0572 100644 --- a/postgis/postgis.sql.in.c +++ b/postgis/postgis.sql.in.c @@ -2965,6 +2965,30 @@ CREATE OR REPLACE FUNCTION ST_Node(g geometry) LANGUAGE 'c' IMMUTABLE STRICT COST 100; +-------------------------------------------------------------------------------- +-- ST_DelaunayTriangles +-------------------------------------------------------------------------------- + +-- ST_DelaunayTriangles(g1 geometry, tolerance float8, flags int4) +-- +-- Builds Delaunay triangulation out of geometry vertices. +-- +-- Returns a collection of triangular polygons with flags=0 +-- or a multilinestring with flags=1 +-- +-- If a tolerance is given it will be used to snap the input points +-- each-other. +-- +-- +-- Availability: 2.1.0 +-- Requires GEOS >= 3.4.0 +-- +CREATE OR REPLACE FUNCTION ST_DelaunayTriangles(g1 geometry, tolerance float8 DEFAULT 0.0, flags int4 DEFAULT 0) + RETURNS geometry + AS 'MODULE_PATHNAME', 'ST_DelaunayTriangles' + LANGUAGE 'c' IMMUTABLE STRICT + COST 100; + -------------------------------------------------------------------------------- -- Aggregates and their supporting functions diff --git a/regress/Makefile.in b/regress/Makefile.in index 336489906..a454f5f5f 100644 --- a/regress/Makefile.in +++ b/regress/Makefile.in @@ -140,6 +140,13 @@ ifeq ($(shell expr $(POSTGIS_GEOS_VERSION) ">=" 33),1) relate_bnr endif +ifeq ($(shell expr $(POSTGIS_GEOS_VERSION) ">=" 34),1) + # GEOS-3.4 adds: + # ST_DelaunayTriangles + TESTS += \ + delaunaytriangles +endif + ifeq ($(HAVE_JSON),yes) # JSON-C adds: # ST_GeomFromGeoJSON() diff --git a/regress/delaunaytriangles.sql b/regress/delaunaytriangles.sql new file mode 100644 index 000000000..f87cdc66c --- /dev/null +++ b/regress/delaunaytriangles.sql @@ -0,0 +1,5 @@ +-- TODO: normalize ! +SELECT 1, ST_AsText(ST_DelaunayTriangles('MULTIPOINT(5 5, 6 0, 7 9)'::geometry)); +SELECT 2, ST_AsText(ST_DelaunayTriangles('MULTIPOINT(5 5, 6 0, 7 9, 8 9)'::geometry)); +SELECT 3, ST_AsText(ST_DelaunayTriangles('MULTIPOINT(5 5, 6 0, 7 9, 8 9)'::geometry, 2)); +SELECT 4, ST_AsText(ST_DelaunayTriangles('MULTIPOINT(5 5, 6 0, 7 9, 8 9)'::geometry, 2, 1)); diff --git a/regress/delaunaytriangles_expected b/regress/delaunaytriangles_expected new file mode 100644 index 000000000..78e5c6d31 --- /dev/null +++ b/regress/delaunaytriangles_expected @@ -0,0 +1,4 @@ +1|GEOMETRYCOLLECTION(POLYGON((5 5,6 0,7 9,5 5))) +2|GEOMETRYCOLLECTION(POLYGON((5 5,6 0,8 9,5 5)),POLYGON((5 5,8 9,7 9,5 5))) +3|GEOMETRYCOLLECTION(POLYGON((5 5,6 0,7 9,5 5))) +4|MULTILINESTRING((5 5,7 9),(5 5,6 0),(6 0,7 9)) -- 2.40.0