From ecd75db48c44af50cca2ce7fa2100a74344ed2bb Mon Sep 17 00:00:00 2001 From: Sandro Santilli Date: Mon, 4 Jan 2016 14:39:09 +0000 Subject: [PATCH] Decimate lines on topology load Improves snapping robustness Updates expected results in topogeo_addlinestring for old and new snapping code (GEOS-3.3.8-, GEOS-3.3.9+) Fixes #3402 and #3402, including automated tests for them. git-svn-id: http://svn.osgeo.org/postgis/trunk@14540 b70326c6-7e19-0410-871a-916f4a2858ee --- liblwgeom/lwgeom_topo.c | 71 ++++++++-- .../test/regress/topogeo_addlinestring.sql | 32 +++++ .../topogeo_addlinestring_expected_newsnap | 131 ++++++++++-------- .../topogeo_addlinestring_expected_oldsnap | 127 +++++++++-------- 4 files changed, 233 insertions(+), 128 deletions(-) diff --git a/liblwgeom/lwgeom_topo.c b/liblwgeom/lwgeom_topo.c index 24553cc36..ac4f057ad 100644 --- a/liblwgeom/lwgeom_topo.c +++ b/liblwgeom/lwgeom_topo.c @@ -5103,8 +5103,9 @@ lwt_AddPoint(LWT_TOPOLOGY* topo, LWPOINT* point, double tol) LWGEOM *prj; int contains; GEOSGeometry *prjg, *gg; + LWT_ELEMID edge_id = e->edge_id; - LWDEBUGF(1, "Splitting edge %" LWTFMT_ELEMID, e->edge_id); + LWDEBUGF(1, "Splitting edge %" LWTFMT_ELEMID, edge_id); /* project point to line, split edge by point */ prj = lwgeom_closest_point(g, pt); @@ -5163,7 +5164,7 @@ lwt_AddPoint(LWT_TOPOLOGY* topo, LWPOINT* point, double tol) LWDEBUGF(1, "Edge %" LWTFMT_ELEMID " does not contain projected point to it", - e->edge_id); + edge_id); /* In order to reduce the robustness issues, we'll pick * an edge that contains the projected point, if possible */ @@ -5234,7 +5235,7 @@ lwt_AddPoint(LWT_TOPOLOGY* topo, LWPOINT* point, double tol) } #endif - if ( -1 == lwt_ChangeEdgeGeom( topo, e->edge_id, snapline ) ) + if ( -1 == lwt_ChangeEdgeGeom( topo, edge_id, snapline ) ) { /* TODO: should have invoked lwerror already, leaking memory */ lwgeom_free(prj); @@ -5258,7 +5259,7 @@ lwt_AddPoint(LWT_TOPOLOGY* topo, LWPOINT* point, double tol) #endif /* TODO: pass 1 as last argument (skipChecks) ? */ - id = lwt_ModEdgeSplit( topo, e->edge_id, lwgeom_as_lwpoint(prj), 0 ); + id = lwt_ModEdgeSplit( topo, edge_id, lwgeom_as_lwpoint(prj), 0 ); if ( -1 == id ) { /* TODO: should have invoked lwerror already, leaking memory */ @@ -5269,6 +5270,20 @@ lwt_AddPoint(LWT_TOPOLOGY* topo, LWPOINT* point, double tol) } lwgeom_free(prj); + + /* + * TODO: decimate the two new edges with the given tolerance ? + * + * the edge identifiers to decimate would be: edge_id and "id" + * The problem here is that decimation of existing edges + * may introduce intersections or topological inconsistencies, + * for example: + * + * - A node may end up falling on the other side of the edge + * - The decimated edge might intersect another existing edge + * + */ + break; /* we only want to snap a single edge */ } _lwt_release_edges(edges, num); @@ -5366,13 +5381,16 @@ _lwt_AddLineEdge( LWT_TOPOLOGY* topo, LWLINE* edge, double tol ) { LWCOLLECTION *col; LWPOINT *start_point, *end_point; - LWGEOM *tmp; + LWGEOM *tmp, *tmp2; LWT_ISO_NODE *node; LWT_ELEMID nid[2]; /* start_node, end_node */ LWT_ELEMID id; /* edge id */ POINT4D p4d; int nn, i; + LWDEBUGG(1, lwline_as_lwgeom(edge), "_lwtAddLineEdge"); + LWDEBUGF(1, "_lwtAddLineEdge with tolerance %g", tol); + start_point = lwline_get_lwpoint(edge, 0); if ( ! start_point ) { @@ -5437,7 +5455,6 @@ _lwt_AddLineEdge( LWT_TOPOLOGY* topo, LWLINE* edge, double tol ) col = lwgeom_as_lwcollection(tmp); if ( col ) {{ - LWGEOM *tmp2; col = lwcollection_extract(col, LINETYPE); @@ -5489,7 +5506,34 @@ _lwt_AddLineEdge( LWT_TOPOLOGY* topo, LWLINE* edge, double tol ) } /* No previously existing edge was found, we'll add one */ - /* TODO: skip checks, I guess ? */ + + /* Remove consecutive vertices below given tolerance + * on edge addition */ + if ( tol ) + {{ + tmp2 = lwline_remove_repeated_points(edge, tol); + LWDEBUGG(1, tmp2, "Repeated-point removed"); + edge = lwgeom_as_lwline(tmp2); + lwgeom_free(tmp); + tmp = tmp2; + + /* check if the so-decimated edge _now_ exists */ + id = _lwt_GetEqualEdge ( topo, edge ); + LWDEBUGF(1, "_lwt_GetEqualEdge returned %" LWTFMT_ELEMID, id); + if ( id == -1 ) + { + lwgeom_free(tmp); /* probably too late, due to internal lwerror */ + return -1; + } + if ( id ) + { + lwgeom_free(tmp); /* takes "edge" down with it */ + return id; + } + }} + + + /* TODO: skip checks ? */ id = lwt_AddEdgeModFace( topo, nid[0], nid[1], edge, 0 ); LWDEBUGF(1, "lwt_AddEdgeModFace returned %" LWTFMT_ELEMID, id); if ( id == -1 ) @@ -5532,7 +5576,7 @@ lwt_AddLine(LWT_TOPOLOGY* topo, LWLINE* line, double tol, int* nedges) LWGEOM *geomsbuf[1]; LWGEOM **geoms; int ngeoms; - LWGEOM *noded; + LWGEOM *noded, *tmp; LWCOLLECTION *col; LWT_ELEMID *ids; LWT_ISO_EDGE *edges; @@ -5548,8 +5592,17 @@ lwt_AddLine(LWT_TOPOLOGY* topo, LWLINE* line, double tol, int* nedges) LWDEBUGF(1, "Working tolerance:%.15g", tol); LWDEBUGF(1, "Input line has srid=%d", line->srid); + /* Remove consecutive vertices below given tolerance upfront */ + if ( tol ) + {{ + LWLINE *clean = lwgeom_as_lwline(lwline_remove_repeated_points(line, tol)); + tmp = lwline_as_lwgeom(clean); /* NOTE: might collapse to non-simple */ + LWDEBUGG(1, tmp, "Repeated-point removed"); + }} else tmp=(LWGEOM*)line; + /* 1. Self-node */ - noded = lwgeom_node((LWGEOM*)line); + noded = lwgeom_node((LWGEOM*)tmp); + if ( tmp != (LWGEOM*)line ) lwgeom_free(tmp); if ( ! noded ) return NULL; /* should have called lwerror already */ LWDEBUGG(1, noded, "Noded"); diff --git a/topology/test/regress/topogeo_addlinestring.sql b/topology/test/regress/topogeo_addlinestring.sql index f1667af07..b34e911e1 100644 --- a/topology/test/regress/topogeo_addlinestring.sql +++ b/topology/test/regress/topogeo_addlinestring.sql @@ -276,6 +276,38 @@ SELECT 't3280', 'L1b' || topology.TopoGeo_AddLinestring('bug3280', geom) ORDER BY 1; SELECT 't3280.end', topology.DropTopology('bug3280'); +-- See http://trac.osgeo.org/postgis/ticket/3380 +SELECT 't3380.start', CreateTopology( 'bug3380', 0, 0.01) > 0; +SELECT 't3380.L1', TopoGeo_AddLinestring('bug3380', ' +LINESTRING( +1612829.90652844007126987 4841274.48807844985276461, +1612830.1566380700096488 4841287.23833953030407429, +1612883.15799825009889901 4841277.73794914968311787) +', 0); +SELECT 't3380.L2', TopoGeo_AddLinestring('bug3380', ' +LINESTRING( +1612790.88055733009241521 4841286.88526585046201944, +1612830.15823523001745343 4841287.12674008030444384, +1612829.98813172010704875 4841274.56198261026293039) +', 0); +SELECT 't3380.L3', TopoGeo_AddLinestring('bug3380', ' + LINESTRING( +1612830.15823523 4841287.12674008, +1612881.64990281 4841274.56198261) +', 0); +SELECT 't3380.end', DropTopology( 'bug3380' ); + +-- See http://trac.osgeo.org/postgis/ticket/3402 + +SELECT 't3402.start', CreateTopology('bug3402') > 1; +SELECT 't3402.L1', TopoGeo_addLinestring('bug3402', +'010200000003000000C1AABC2B192739418E7DE0E6AB9652411F85EB5119283941F6285CEF2D9652411F85EB5128283941F6285CCF2C965241' +, 0); +SELECT 't3402.L2', TopoGeo_addLinestring('bug3402', +'010200000003000000BCAABC2B192739418F7DE0E6AB96524185EB51382828394115AE47D12C96524187EB51382828394115AE47D12C965241' +, 0); +SELECT 't3402.end', DropTopology('bug3402'); + -- See http://trac.osgeo.org/postgis/ticket/3412 SELECT 't3412.start', CreateTopology('bug3412', 0, 0.001) > 0; SELECT 't3412.L1', TopoGeo_AddLinestring('bug3412', diff --git a/topology/test/regress/topogeo_addlinestring_expected_newsnap b/topology/test/regress/topogeo_addlinestring_expected_newsnap index f4f9ee96b..0c564763c 100644 --- a/topology/test/regress/topogeo_addlinestring_expected_newsnap +++ b/topology/test/regress/topogeo_addlinestring_expected_newsnap @@ -43,9 +43,9 @@ E|15|sn12|en32 E|33|sn32|en19 E|34|sn31|en32 E|35|sn32|en33 +snap|7 snap|36 snap|39 -snap|40 N|34||POINT(18 22) N|35||POINT(22.4 22) N|36||POINT(21 20.4) @@ -56,14 +56,13 @@ E|36|sn34|en17 E|37|sn35|en18 E|38|sn36|en17 E|39|sn35|en36 -E|40|sn17|en35 +snap_again|7 snap_again|36 snap_again|39 -snap_again|40 -crossover|43 +crossover|42 +crossover|44 crossover|45 crossover|46 -crossover|47 N|37||POINT(9 20) N|38||POINT(16.2 14) N|39||POINT(21 10) @@ -72,110 +71,112 @@ N|41||POINT(21 7) E|9|sn15|en38 E|20|sn9|en41 E|21|sn15|en40 -E|41|sn37|en16 -E|42|sn38|en14 -E|43|sn37|en38 -E|44|sn39|en14 -E|45|sn38|en39 -E|46|sn40|en37 -E|47|sn41|en39 -crossover_again|43 +E|40|sn37|en16 +E|41|sn38|en14 +E|42|sn37|en38 +E|43|sn39|en14 +E|44|sn38|en39 +E|45|sn40|en37 +E|46|sn41|en39 +crossover_again|42 +crossover_again|44 crossover_again|45 crossover_again|46 -crossover_again|47 contains|25 +contains|47 contains|48 -contains|49 N|42||POINT(7 36) N|43||POINT(14 34) -E|48|sn21|en42 -E|49|sn43|en22 +E|47|sn21|en42 +E|48|sn43|en22 +nodecross|49 nodecross|50 -nodecross|51 N|44||POINT(18 37) N|45||POINT(22 37) -E|50|sn44|en4 -E|51|sn4|en45 +E|49|sn44|en4 +E|50|sn4|en45 iso_ex_2segs|28 -#1613.1|52 +#1613.1|51 N|46||POINT(556267.6 144887) N|47||POINT(556267 144887.4) -E|52|sn46|en47 +E|51|sn46|en47 +#1613.2|53 #1613.2|54 -#1613.2|55 N|48||POINT(556250 144887) N|49||POINT(556267.6 144887) N|50||POINT(556310 144887) -E|52|sn46|en49 -E|53|sn49|en47 -E|54|sn48|en49 -E|55|sn49|en50 -#1631.1|56 +E|51|sn46|en49 +E|52|sn49|en47 +E|53|sn48|en49 +E|54|sn49|en50 +#1631.1|55 N|51||POINT(556267.6 144887) N|52||POINT(556267.6 144888) -E|56|sn51|en52 +E|55|sn51|en52 +#1631.2|56 #1631.2|57 -#1631.2|58 N|53||POINT(556254.6 144886.6) N|54||POINT(556267.6 144887) -E|57|sn53|en51 -E|58|sn51|en54 -#1641.1|59 +E|56|sn53|en51 +E|57|sn51|en54 +#1641.1|58 N|55||POINT(-0.2 0.4) N|56||POINT(0.2 0.4) -E|59|sn55|en56 +E|58|sn55|en56 +#1641.2|60 #1641.2|61 -#1641.2|62 N|57||POINT(0 0.2) N|58||POINT(0 0.4) N|59||POINT(0 0.4) -E|59|sn55|en58 -E|60|sn58|en56 -E|61|sn57|en58 -E|62|sn58|en59 -#1641.3|63 +E|58|sn55|en58 +E|59|sn58|en56 +E|60|sn57|en58 +E|61|sn58|en59 +#1641.3|62 N|60||POINT(-0.2 0.4) N|61||POINT(0.2 0.4) -E|63|sn60|en61 +E|62|sn60|en61 +#1641.4|64 #1641.4|65 -#1641.4|66 N|62||POINT(0 0.2) N|63||POINT(0 0.4) N|64||POINT(0 0.4) -E|63|sn60|en63 -E|64|sn63|en61 -E|65|sn62|en63 -E|66|sn63|en64 +E|62|sn60|en63 +E|63|sn63|en61 +E|64|sn62|en63 +E|65|sn63|en64 #1650.1 N|65|0|POINT(0 0) -#1650.3|67 +#1650.3|66 N|66||POINT(10 0) -E|67|sn65|en66 +E|66|sn65|en66 #1654.1|N|67 N|67|0|POINT(0 0) +#1654.2|67 #1654.2|68 -#1654.2|69 N|68||POINT(-10 1) N|69||POINT(10 1) -E|68|sn68|en67 -E|69|sn67|en69 -#1706.1|E|70 +E|67|sn68|en67 +E|68|sn67|en69 +#1706.1|E|69 N|70||POINT(20 10) N|71||POINT(10 20) -E|70|sn70|en71 -#1706.2|E*|70 +E|69|sn70|en71 +#1706.2|E*|69 +#1706.2|E*|71 #1706.2|E*|72 -#1706.2|E*|73 N|72||POINT(10 0) N|73||POINT(10 10) N|74||POINT(15 10) -E|70|sn70|en74 -E|71|sn73|en71 -E|72|sn72|en73 -E|73|sn74|en73 +E|69|sn70|en74 +E|70|sn73|en71 +E|71|sn72|en73 +E|72|sn74|en73 #1714.1|N|75 N|75|0|POINT(10 0) -#1714.2|E*|74 +#1714.2|E*|73 +N|76||POINT(0 20) +E|73|sn75|en76 Topology 'city_data' dropped t3280.start|t t3280|L11 @@ -183,6 +184,16 @@ t3280|L22 t3280|L1b4 t3280|L1b2 t3280.end|Topology 'bug3280' dropped +t3380.start|t +t3380.L1|1 +t3380.L2|3 +t3380.L2|4 +t3380.L3|5 +t3380.end|Topology 'bug3380' dropped +t3402.start|t +t3402.L1|1 +t3402.L2|3 +t3402.end|Topology 'bug3402' dropped t3412.start|t t3412.L1|1 t3412.L2|2 diff --git a/topology/test/regress/topogeo_addlinestring_expected_oldsnap b/topology/test/regress/topogeo_addlinestring_expected_oldsnap index f367e7816..dec535d4b 100644 --- a/topology/test/regress/topogeo_addlinestring_expected_oldsnap +++ b/topology/test/regress/topogeo_addlinestring_expected_oldsnap @@ -43,9 +43,9 @@ E|15|sn12|en32 E|33|sn32|en19 E|34|sn31|en32 E|35|sn32|en33 +snap|7 snap|36 snap|39 -snap|40 N|34||POINT(18 22) N|35||POINT(22.4 22) N|36||POINT(21 20.4) @@ -56,14 +56,13 @@ E|36|sn34|en17 E|37|sn35|en18 E|38|sn36|en17 E|39|sn35|en36 -E|40|sn17|en35 snap_again|7 snap_again|36 snap_again|39 -crossover|43 +crossover|42 +crossover|44 crossover|45 crossover|46 -crossover|47 N|37||POINT(9 20) N|38||POINT(16.2 14) N|39||POINT(21 10) @@ -72,109 +71,109 @@ N|41||POINT(21 7) E|9|sn15|en38 E|20|sn9|en41 E|21|sn15|en40 -E|41|sn37|en16 -E|42|sn38|en14 -E|43|sn37|en38 -E|44|sn39|en14 -E|45|sn38|en39 -E|46|sn40|en37 -E|47|sn41|en39 -crossover_again|43 +E|40|sn37|en16 +E|41|sn38|en14 +E|42|sn37|en38 +E|43|sn39|en14 +E|44|sn38|en39 +E|45|sn40|en37 +E|46|sn41|en39 +crossover_again|42 +crossover_again|44 crossover_again|45 crossover_again|46 -crossover_again|47 contains|25 +contains|47 contains|48 -contains|49 N|42||POINT(7 36) N|43||POINT(14 34) -E|48|sn21|en42 -E|49|sn43|en22 +E|47|sn21|en42 +E|48|sn43|en22 +nodecross|49 nodecross|50 -nodecross|51 N|44||POINT(18 37) N|45||POINT(22 37) -E|50|sn44|en4 -E|51|sn4|en45 +E|49|sn44|en4 +E|50|sn4|en45 iso_ex_2segs|28 -#1613.1|52 +#1613.1|51 N|46||POINT(556267.6 144887) N|47||POINT(556267 144887.4) -E|52|sn46|en47 +E|51|sn46|en47 +#1613.2|53 #1613.2|54 -#1613.2|55 N|48||POINT(556250 144887) N|49||POINT(556267.6 144887) N|50||POINT(556310 144887) -E|52|sn46|en49 -E|53|sn49|en47 -E|54|sn48|en49 -E|55|sn49|en50 -#1631.1|56 +E|51|sn46|en49 +E|52|sn49|en47 +E|53|sn48|en49 +E|54|sn49|en50 +#1631.1|55 N|51||POINT(556267.6 144887) N|52||POINT(556267.6 144888) -E|56|sn51|en52 +E|55|sn51|en52 +#1631.2|56 #1631.2|57 -#1631.2|58 N|53||POINT(556254.6 144886.6) N|54||POINT(556267.6 144887) -E|57|sn53|en51 -E|58|sn51|en54 -#1641.1|59 +E|56|sn53|en51 +E|57|sn51|en54 +#1641.1|58 N|55||POINT(-0.2 0.4) N|56||POINT(0.2 0.4) -E|59|sn55|en56 +E|58|sn55|en56 +#1641.2|60 #1641.2|61 -#1641.2|62 N|57||POINT(0 0.2) N|58||POINT(0 0.4) N|59||POINT(0 0.4) -E|59|sn55|en58 -E|60|sn58|en56 -E|61|sn57|en58 -E|62|sn58|en59 -#1641.3|63 +E|58|sn55|en58 +E|59|sn58|en56 +E|60|sn57|en58 +E|61|sn58|en59 +#1641.3|62 N|60||POINT(-0.2 0.4) N|61||POINT(0.2 0.4) -E|63|sn60|en61 +E|62|sn60|en61 +#1641.4|64 #1641.4|65 -#1641.4|66 N|62||POINT(0 0.2) N|63||POINT(0 0.4) N|64||POINT(0 0.4) -E|63|sn60|en63 -E|64|sn63|en61 -E|65|sn62|en63 -E|66|sn63|en64 +E|62|sn60|en63 +E|63|sn63|en61 +E|64|sn62|en63 +E|65|sn63|en64 #1650.1 N|65|0|POINT(0 0) -#1650.3|67 +#1650.3|66 N|66||POINT(10 0) -E|67|sn65|en66 +E|66|sn65|en66 #1654.1|N|67 N|67|0|POINT(0 0) +#1654.2|67 #1654.2|68 -#1654.2|69 N|68||POINT(-10 1) N|69||POINT(10 1) -E|68|sn68|en67 -E|69|sn67|en69 -#1706.1|E|70 +E|67|sn68|en67 +E|68|sn67|en69 +#1706.1|E|69 N|70||POINT(20 10) N|71||POINT(10 20) -E|70|sn70|en71 -#1706.2|E*|70 -#1706.2|E*|72 +E|69|sn70|en71 +#1706.2|E*|69 +#1706.2|E*|71 N|72||POINT(10 0) N|73||POINT(9 12) -E|70|sn70|en73 -E|71|sn73|en71 -E|72|sn72|en73 +E|69|sn70|en73 +E|70|sn73|en71 +E|71|sn72|en73 #1714.1|N|74 N|74|0|POINT(10 0) -#1714.2|E*|73 +#1714.2|E*|72 N|75||POINT(0 20) -E|73|sn74|en75 +E|72|sn74|en75 Topology 'city_data' dropped t3280.start|t t3280|L11 @@ -182,6 +181,16 @@ t3280|L22 t3280|L1b4 t3280|L1b2 t3280.end|Topology 'bug3280' dropped +t3380.start|t +t3380.L1|1 +t3380.L2|3 +t3380.L2|4 +t3380.L3|5 +t3380.end|Topology 'bug3380' dropped +t3402.start|t +t3402.L1|1 +t3402.L2|3 +t3402.end|Topology 'bug3402' dropped t3412.start|t t3412.L1|1 t3412.L2|2 -- 2.40.0