From b59ba8df91417c8ddde511a2dc4206ec34d15271 Mon Sep 17 00:00:00 2001 From: Paul Ramsey Date: Fri, 12 Jun 2015 18:35:14 +0000 Subject: [PATCH] #1137, Add a tolerance distance to ST_RemoveRepeatedPoints git-svn-id: http://svn.osgeo.org/postgis/trunk@13666 b70326c6-7e19-0410-871a-916f4a2858ee --- NEWS | 9 ++++++--- doc/reference_processing.xml | 5 ++++- liblwgeom/liblwgeom.h.in | 2 +- liblwgeom/liblwgeom_internal.h | 10 +++++----- liblwgeom/lwcollection.c | 4 ++-- liblwgeom/lwcompound.c | 1 - liblwgeom/lwgeom.c | 14 +++++++------- liblwgeom/lwline.c | 6 +++--- liblwgeom/lwlinearreferencing.c | 2 +- liblwgeom/lwmpoint.c | 2 +- liblwgeom/lwpoly.c | 4 ++-- liblwgeom/lwsegmentize.c | 2 +- liblwgeom/lwtriangle.c | 2 +- liblwgeom/ptarray.c | 23 +++++++++++++---------- postgis/lwgeom_functions_basic.c | 22 +++++++++++++--------- postgis/postgis.sql.in | 4 ++-- postgis/postgis_drop_after.sql | 1 + regress/remove_repeated_points.sql | 2 ++ regress/remove_repeated_points_expected | 1 + 19 files changed, 66 insertions(+), 50 deletions(-) diff --git a/NEWS b/NEWS index c55dff09e..66c093205 100644 --- a/NEWS +++ b/NEWS @@ -32,6 +32,9 @@ PostGIS 2.2.0 - Add |=| operator with CPA semantic and KNN support with PgSQL 9.5+ (Sandro Santilli / Boundless) + - #3131, KNN support for the geography type (Paul Ramsey / CartoDB) + - #2703, Exact KNN results for all geometry types, aka "KNN re-check" (Paul Ramsey / CartoDB) + - #1137, Allow a tolerance value in ST_RemoveRepeatedPoints (Paul Ramsey / CartoDB) - #3062, Allow passing M factor to ST_Scale (Sandro Santilli / Boundless) - #3139, ST_BoundingDiagonal (Sandro Santilli / Boundless) - #3129, ST_IsValidTrajectory (Sandro Santilli / Boundless) @@ -40,8 +43,8 @@ PostGIS 2.2.0 - Canonical output for index key types - ST_SwapOrdinates (Sandro Santilli / Boundless) - #2918, Use GeographicLib functions for geodetics (Mike Toews) - - #3074, ST_Subdivide (Paul Ramsey / CartoDB) - - #3040, KNN GiST index based centroid (<<->>) and box (<<#>>) + - #3074, ST_Subdivide to break up large geometry (Paul Ramsey / CartoDB) + - #3040, KNN GiST index based centroid (<<->>) n-D distance operators (Sandro Santilli / Boundless) - Interruptibility API for liblwgeom (Sandro Santilli / CartoDB) - #2939, ST_ClipByBox2D (Sandro Santilli / CartoDB) @@ -75,7 +78,7 @@ PostGIS 2.2.0 - #2227, Simplification with Visvalingam-Whyatt algorithm ST_SimplifyVW, ST_SetEffectiveArea (Nicklas Avén) - Functions to encode and decode TWKB - ST_AsTWKB, ST_GeomFromTWKB (Paul Ramsey / Nicklas Avén) + ST_AsTWKB, ST_GeomFromTWKB (Paul Ramsey / Nicklas Avén / CartoDB) * Enhancements * diff --git a/doc/reference_processing.xml b/doc/reference_processing.xml index 8392e854a..e1805c284 100644 --- a/doc/reference_processing.xml +++ b/doc/reference_processing.xml @@ -2438,6 +2438,7 @@ MULTILINESTRING((164 1,11.7867965644036 1,1 11.7867965644036,1 195), geometry ST_RemoveRepeatedPoints geometry geom + float8 tolerance @@ -2450,8 +2451,10 @@ MULTILINESTRING((164 1,11.7867965644036 1,1 11.7867965644036,1 195), any kind of geometry. Since simplification occurs on a object-by-object basis you can also feed a GeometryCollection to this function. + If the tolerance parameter is provided, vertices within the tolerance + of one another will be considered the "same" for the purposes of removal. - Availability: 2.0.0 + Availability: 2.2.0 &P_support; &Z_support; diff --git a/liblwgeom/liblwgeom.h.in b/liblwgeom/liblwgeom.h.in index 9bac3af5e..7c7641f63 100644 --- a/liblwgeom/liblwgeom.h.in +++ b/liblwgeom/liblwgeom.h.in @@ -1545,7 +1545,7 @@ extern int lwgeom_covers_lwgeom_sphere(const LWGEOM *lwgeom1, const LWGEOM *lwge /** * Remove repeated points! */ -extern LWGEOM* lwgeom_remove_repeated_points(LWGEOM *in); +extern LWGEOM* lwgeom_remove_repeated_points(LWGEOM *in, double tolerance); extern char lwtriangle_is_repeated_points(LWTRIANGLE *triangle); diff --git a/liblwgeom/liblwgeom_internal.h b/liblwgeom/liblwgeom_internal.h index e2f3def22..b8ff9807a 100644 --- a/liblwgeom/liblwgeom_internal.h +++ b/liblwgeom/liblwgeom_internal.h @@ -345,11 +345,11 @@ void closest_point_on_segment(const POINT4D *R, const POINT4D *A, const POINT4D /* * Repeated points */ -POINTARRAY *ptarray_remove_repeated_points(POINTARRAY *in); -LWGEOM* lwmpoint_remove_repeated_points(LWMPOINT *in); -LWGEOM* lwline_remove_repeated_points(LWLINE *in); -LWGEOM* lwcollection_remove_repeated_points(LWCOLLECTION *in); -LWGEOM* lwpoly_remove_repeated_points(LWPOLY *in); +POINTARRAY *ptarray_remove_repeated_points(POINTARRAY *in, double tolerance); +LWGEOM* lwmpoint_remove_repeated_points(LWMPOINT *in, double tolerance); +LWGEOM* lwline_remove_repeated_points(LWLINE *in, double tolerance); +LWGEOM* lwcollection_remove_repeated_points(LWCOLLECTION *in, double tolerance); +LWGEOM* lwpoly_remove_repeated_points(LWPOLY *in, double tolerance); /* * Closure test diff --git a/liblwgeom/lwcollection.c b/liblwgeom/lwcollection.c index 7d44352c9..be254dc89 100644 --- a/liblwgeom/lwcollection.c +++ b/liblwgeom/lwcollection.c @@ -437,7 +437,7 @@ LWCOLLECTION* lwcollection_extract(LWCOLLECTION *col, int type) } LWGEOM* -lwcollection_remove_repeated_points(LWCOLLECTION *coll) +lwcollection_remove_repeated_points(LWCOLLECTION *coll, double tolerance) { uint32_t i; LWGEOM **newgeoms; @@ -445,7 +445,7 @@ lwcollection_remove_repeated_points(LWCOLLECTION *coll) newgeoms = lwalloc(sizeof(LWGEOM *)*coll->ngeoms); for (i=0; ingeoms; i++) { - newgeoms[i] = lwgeom_remove_repeated_points(coll->geoms[i]); + newgeoms[i] = lwgeom_remove_repeated_points(coll->geoms[i], tolerance); } return (LWGEOM*)lwcollection_construct(coll->type, diff --git a/liblwgeom/lwcompound.c b/liblwgeom/lwcompound.c index 8c28400e2..b5dd4a927 100644 --- a/liblwgeom/lwcompound.c +++ b/liblwgeom/lwcompound.c @@ -261,4 +261,3 @@ lwcompound_get_endpoint(const LWCOMPOUND *lwcmp) return lwline_get_lwpoint(lwline, lwline->points->npoints-1); } - \ No newline at end of file diff --git a/liblwgeom/lwgeom.c b/liblwgeom/lwgeom.c index a9bb312d8..0823f3d1f 100644 --- a/liblwgeom/lwgeom.c +++ b/liblwgeom/lwgeom.c @@ -1404,7 +1404,7 @@ extern int lwgeom_dimensionality(LWGEOM *geom) return 0; } -extern LWGEOM* lwgeom_remove_repeated_points(LWGEOM *in) +extern LWGEOM* lwgeom_remove_repeated_points(LWGEOM *in, double tolerance) { LWDEBUGF(4, "lwgeom_remove_repeated_points got type %s", lwtype_name(in->type)); @@ -1412,19 +1412,19 @@ extern LWGEOM* lwgeom_remove_repeated_points(LWGEOM *in) switch (in->type) { case MULTIPOINTTYPE: - return lwmpoint_remove_repeated_points((LWMPOINT*)in); + return lwmpoint_remove_repeated_points((LWMPOINT*)in, tolerance); break; case LINETYPE: - return lwline_remove_repeated_points((LWLINE*)in); + return lwline_remove_repeated_points((LWLINE*)in, tolerance); case MULTILINETYPE: case COLLECTIONTYPE: case MULTIPOLYGONTYPE: case POLYHEDRALSURFACETYPE: - return lwcollection_remove_repeated_points((LWCOLLECTION *)in); + return lwcollection_remove_repeated_points((LWCOLLECTION *)in, tolerance); case POLYGONTYPE: - return lwpoly_remove_repeated_points((LWPOLY *)in); + return lwpoly_remove_repeated_points((LWPOLY *)in, tolerance); break; case POINTTYPE: @@ -1442,8 +1442,8 @@ extern LWGEOM* lwgeom_remove_repeated_points(LWGEOM *in) return in; default: - lwnotice("lwgeom_remove_repeated_points: unsupported geometry type: %s", - lwtype_name(in->type)); + lwnotice("%s: unsupported geometry type: %s", + __func__, lwtype_name(in->type)); return in; break; } diff --git a/liblwgeom/lwline.c b/liblwgeom/lwline.c index f28a04986..582ac91f6 100644 --- a/liblwgeom/lwline.c +++ b/liblwgeom/lwline.c @@ -421,11 +421,11 @@ lwline_measured_from_lwline(const LWLINE *lwline, double m_start, double m_end) } LWGEOM* -lwline_remove_repeated_points(LWLINE *lwline) +lwline_remove_repeated_points(LWLINE *lwline, double tolerance) { - POINTARRAY* npts = ptarray_remove_repeated_points(lwline->points); + POINTARRAY* npts = ptarray_remove_repeated_points(lwline->points, tolerance); - LWDEBUGF(3, "lwline_remove_repeated_points: npts %p", npts); + LWDEBUGF(3, "%s: npts %p", __func__, npts); return (LWGEOM*)lwline_construct(lwline->srid, lwline->bbox ? gbox_copy(lwline->bbox) : 0, diff --git a/liblwgeom/lwlinearreferencing.c b/liblwgeom/lwlinearreferencing.c index d61423339..27fa21749 100644 --- a/liblwgeom/lwlinearreferencing.c +++ b/liblwgeom/lwlinearreferencing.c @@ -1101,7 +1101,7 @@ lwgeom_tcpa(const LWGEOM *g1, const LWGEOM *g2, double *mindist) tmax = FP_MIN(gbox1->mmax, gbox2->mmax); if ( tmax < tmin ) { - LWDEBUGF(1, "Inputs never exist at the same time"); + LWDEBUG(1, "Inputs never exist at the same time"); return -2; } diff --git a/liblwgeom/lwmpoint.c b/liblwgeom/lwmpoint.c index 2169560b9..17b5bac53 100644 --- a/liblwgeom/lwmpoint.c +++ b/liblwgeom/lwmpoint.c @@ -76,7 +76,7 @@ void lwmpoint_free(LWMPOINT *mpt) } LWGEOM* -lwmpoint_remove_repeated_points(LWMPOINT *mpoint) +lwmpoint_remove_repeated_points(LWMPOINT *mpoint, double tolerance) { uint32_t nnewgeoms; uint32_t i, j; diff --git a/liblwgeom/lwpoly.c b/liblwgeom/lwpoly.c index 03ba68dc2..2c21e3783 100644 --- a/liblwgeom/lwpoly.c +++ b/liblwgeom/lwpoly.c @@ -286,7 +286,7 @@ lwpoly_from_lwlines(const LWLINE *shell, } LWGEOM* -lwpoly_remove_repeated_points(LWPOLY *poly) +lwpoly_remove_repeated_points(LWPOLY *poly, double tolerance) { uint32_t i; POINTARRAY **newrings; @@ -294,7 +294,7 @@ lwpoly_remove_repeated_points(LWPOLY *poly) newrings = lwalloc(sizeof(POINTARRAY *)*poly->nrings); for (i=0; inrings; i++) { - newrings[i] = ptarray_remove_repeated_points(poly->rings[i]); + newrings[i] = ptarray_remove_repeated_points(poly->rings[i], tolerance); } return (LWGEOM*)lwpoly_construct(poly->srid, diff --git a/liblwgeom/lwsegmentize.c b/liblwgeom/lwsegmentize.c index d67c9ba12..12b5668ad 100644 --- a/liblwgeom/lwsegmentize.c +++ b/liblwgeom/lwsegmentize.c @@ -280,7 +280,7 @@ lwcompound_segmentize(const LWCOMPOUND *icompound, uint32_t perQuad) return NULL; } } - ptarray_out = ptarray_remove_repeated_points(ptarray); + ptarray_out = ptarray_remove_repeated_points(ptarray, 0.0); ptarray_free(ptarray); return lwline_construct(icompound->srid, NULL, ptarray_out); } diff --git a/liblwgeom/lwtriangle.c b/liblwgeom/lwtriangle.c index ce106cd34..905d088fa 100644 --- a/liblwgeom/lwtriangle.c +++ b/liblwgeom/lwtriangle.c @@ -152,7 +152,7 @@ lwtriangle_is_repeated_points(LWTRIANGLE *triangle) char ret; POINTARRAY *pa; - pa = ptarray_remove_repeated_points(triangle->points); + pa = ptarray_remove_repeated_points(triangle->points, 0.0); ret = ptarray_same(pa, triangle->points); ptarray_free(pa); diff --git a/liblwgeom/ptarray.c b/liblwgeom/ptarray.c index 3a21ac442..1058d4acf 100644 --- a/liblwgeom/ptarray.c +++ b/liblwgeom/ptarray.c @@ -1423,20 +1423,21 @@ ptarray_longitude_shift(POINTARRAY *pa) * */ POINTARRAY * -ptarray_remove_repeated_points(POINTARRAY *in) +ptarray_remove_repeated_points(POINTARRAY *in, double tolerance) { POINTARRAY* out; size_t ptsize; size_t ipn, opn; + const POINT2D *last_point, *this_point; - LWDEBUG(3, "ptarray_remove_repeated_points called."); + LWDEBUGF(3, "%s called", __func__); /* Single or zero point arrays can't have duplicates */ if ( in->npoints < 3 ) return ptarray_clone_deep(in); ptsize = ptarray_point_size(in); - LWDEBUGF(3, "ptsize: %d", ptsize); + LWDEBUGF(3, " ptsize: %d", ptsize); /* Allocate enough space for all points */ out = ptarray_construct(FLAGS_GET_Z(in->flags), @@ -1446,18 +1447,20 @@ ptarray_remove_repeated_points(POINTARRAY *in) opn=1; memcpy(getPoint_internal(out, 0), getPoint_internal(in, 0), ptsize); + last_point = getPoint2d_cp(in, 0); LWDEBUGF(3, " first point copied, out points: %d", opn); - for (ipn=1; ipnnpoints; ++ipn) + for ( ipn = 1; ipn < in->npoints; ++ipn) { - if ( (ipn==in->npoints-1 && opn==1) || memcmp(getPoint_internal(in, ipn-1), - getPoint_internal(in, ipn), ptsize) ) + this_point = getPoint2d_cp(in, ipn); + if ( (ipn == in->npoints-1 && opn==1) || + (tolerance == 0 && memcmp(getPoint_internal(in, ipn-1), getPoint_internal(in, ipn), ptsize) != 0) || + (tolerance > 0.0 && distance2d_pt_pt(last_point, this_point) > tolerance) ) { /* The point is different from the previous, * we add it to output */ - memcpy(getPoint_internal(out, opn++), - getPoint_internal(in, ipn), ptsize); - LWDEBUGF(3, " Point %d differs from point %d. Out points: %d", - ipn, ipn-1, opn); + memcpy(getPoint_internal(out, opn++), getPoint_internal(in, ipn), ptsize); + last_point = this_point; + LWDEBUGF(3, " Point %d differs from point %d. Out points: %d", ipn, ipn-1, opn); } } diff --git a/postgis/lwgeom_functions_basic.c b/postgis/lwgeom_functions_basic.c index 45884790c..4c2e585e0 100644 --- a/postgis/lwgeom_functions_basic.c +++ b/postgis/lwgeom_functions_basic.c @@ -2659,20 +2659,24 @@ Datum ST_RemoveRepeatedPoints(PG_FUNCTION_ARGS); PG_FUNCTION_INFO_V1(ST_RemoveRepeatedPoints); Datum ST_RemoveRepeatedPoints(PG_FUNCTION_ARGS) { - GSERIALIZED *input = PG_GETARG_GSERIALIZED_P_COPY(0); - GSERIALIZED *output; - LWGEOM *lwgeom_in = lwgeom_from_gserialized(input); - LWGEOM *lwgeom_out; + GSERIALIZED *g_in = PG_GETARG_GSERIALIZED_P_COPY(0); + GSERIALIZED *g_out; + LWGEOM *lwgeom_in = lwgeom_from_gserialized(g_in); + LWGEOM *lwgeom_out = NULL; + double tolerance = 0.0; - /* lwpgnotice("ST_RemoveRepeatedPoints got %p", lwgeom_in); */ + if ( PG_NARGS() > 1 && ! PG_ARGISNULL(1) ) + tolerance = PG_GETARG_FLOAT8(1); - lwgeom_out = lwgeom_remove_repeated_points(lwgeom_in); - output = geometry_serialize(lwgeom_out); + lwgeom_out = lwgeom_remove_repeated_points(lwgeom_in, tolerance); + g_out = geometry_serialize(lwgeom_out); + if ( lwgeom_out != lwgeom_in ) + lwgeom_free(lwgeom_out); lwgeom_free(lwgeom_in); - PG_FREE_IF_COPY(input, 0); - PG_RETURN_POINTER(output); + PG_FREE_IF_COPY(g_in, 0); + PG_RETURN_POINTER(g_out); } Datum ST_FlipCoordinates(PG_FUNCTION_ARGS); diff --git a/postgis/postgis.sql.in b/postgis/postgis.sql.in index ae133f75e..6127f0b61 100644 --- a/postgis/postgis.sql.in +++ b/postgis/postgis.sql.in @@ -3286,8 +3286,8 @@ CREATE OR REPLACE FUNCTION ST_UnaryUnion(geometry) -- Only checks consecutive points for lineal and polygonal geoms. -- Checks all points for multipoint geoms. -- --- Availability: 2.0.0 -CREATE OR REPLACE FUNCTION ST_RemoveRepeatedPoints(geometry) +-- Availability: 2.2.0 +CREATE OR REPLACE FUNCTION ST_RemoveRepeatedPoints(geom geometry, tolerance float8 default 0.0) RETURNS geometry AS 'MODULE_PATHNAME', 'ST_RemoveRepeatedPoints' LANGUAGE 'c' IMMUTABLE STRICT diff --git a/postgis/postgis_drop_after.sql b/postgis/postgis_drop_after.sql index 185cfca7c..ab9c8eda1 100644 --- a/postgis/postgis_drop_after.sql +++ b/postgis/postgis_drop_after.sql @@ -137,6 +137,7 @@ DROP FUNCTION IF EXISTS st_geometry_ge(geometry, geometry); DROP FUNCTION IF EXISTS st_geometry_eq(geometry, geometry); DROP FUNCTION IF EXISTS st_geometry_cmp(geometry, geometry); DROP FUNCTION IF EXISTS SnapToGrid(geometry, float8, float8); +DROP FUNCTION IF EXISTS st_removerepeatedpoints(geometry); DROP FUNCTION IF EXISTS geometry_gist_sel_2d (internal, oid, internal, int4); DROP FUNCTION IF EXISTS geometry_gist_joinsel_2d(internal, oid, internal, smallint); diff --git a/regress/remove_repeated_points.sql b/regress/remove_repeated_points.sql index e3060b5b5..96021364f 100644 --- a/regress/remove_repeated_points.sql +++ b/regress/remove_repeated_points.sql @@ -20,3 +20,5 @@ SELECT 9, ST_AsText(ST_RemoveRepeatedPoints('CURVEPOLYGON(CIRCULARSTRING( SELECT 10, ST_AsText(ST_RemoveRepeatedPoints('LINESTRING(0 0, 0 0)')); SELECT 11, ST_AsText(ST_RemoveRepeatedPoints('LINESTRING(0 0, 0 0, 0 0, 0 0, 0 0)')); SELECT 12, ST_SRID(ST_RemoveRepeatedPoints('SRID=3;LINESTRING(0 0, 0 0, 0 0, 0 0, 0 0)')); +SELECT 13, ST_AsText(ST_RemoveRepeatedPoints('LINESTRING(0 0, 1 0, 2 0, 3 0, 4 0)',1.5)); + diff --git a/regress/remove_repeated_points_expected b/regress/remove_repeated_points_expected index 410a73b6e..753cc5212 100644 --- a/regress/remove_repeated_points_expected +++ b/regress/remove_repeated_points_expected @@ -11,3 +11,4 @@ 10|LINESTRING(0 0,0 0) 11|LINESTRING(0 0,0 0) 12|3 +13|LINESTRING(0 0,2 0,4 0) -- 2.50.1