[postgis-tickets] [SCM] PostGIS branch stable-3.0 updated. 3.0.2-10-g73dd48b
git at osgeo.org
git at osgeo.org
Mon Oct 19 07:50:48 PDT 2020
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, stable-3.0 has been updated
via 73dd48b9cafffdb7012caa29e22cdf9d8c964b0e (commit)
from cb66c8b17428944dfccb5622db65ae3d52b19a07 (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 73dd48b9cafffdb7012caa29e22cdf9d8c964b0e
Author: Sandro Santilli <strk at kbt.io>
Date: Thu Oct 15 01:42:03 2020 +0200
Improve topology noding robustness
Avoids snapping again after noding.
Fixes #4758 in 3.0 branch
Includes automated test
diff --git a/NEWS b/NEWS
index 5350f53..0fc43d0 100644
--- a/NEWS
+++ b/NEWS
@@ -4,6 +4,7 @@ PostGIS 3.0.3dev
* Bug Fixes and Enhancements *
- #4742 tiger geocoder reverted to 2018 version on tiger upgrade
- #4757, Handle line collapse due to snap-to-existing node (Sandro Santilli)
+ - #4758, Improve topology noding robustness (Sandro Santilli)
- #4719, Fail fast when srids don't match ST_Intersection(geometry,raster)
Also schema qualify calls in function. (Regina Obe)
- #4739, Ensure all functions using postgis_oid initialize the internal cache (Raúl Marín)
diff --git a/liblwgeom/lwgeom_topo.c b/liblwgeom/lwgeom_topo.c
index e111e07..d269f85 100644
--- a/liblwgeom/lwgeom_topo.c
+++ b/liblwgeom/lwgeom_topo.c
@@ -18,7 +18,7 @@
*
**********************************************************************
*
- * Copyright (C) 2015-2017 Sandro Santilli <strk at kbt.io>
+ * Copyright (C) 2015-2020 Sandro Santilli <strk at kbt.io>
*
**********************************************************************/
@@ -5567,10 +5567,10 @@ _lwt_AddLine(LWT_TOPOLOGY* topo, LWLINE* line, double tol, int* nedges,
tol, qbox.xmin, qbox.ymin, qbox.xmax, qbox.ymax);
LWGEOM **nearby = 0;
- int nearbyindex=0;
+ int nearbyindex = 0;
int nearbycount = 0;
- /* 2. Node to edges falling within tol distance */
+ /* 2.0. Find edges falling within tol distance */
edges = lwt_be_getEdgeWithinBox2D( topo, &qbox, &numedges, LWT_COL_EDGE_ALL, 0 );
if (numedges == UINT64_MAX)
{
@@ -5584,7 +5584,7 @@ _lwt_AddLine(LWT_TOPOLOGY* topo, LWLINE* line, double tol, int* nedges,
{{
/* collect those whose distance from us is < tol */
nearbycount += numedges;
- nearby = lwalloc(nearbycount * sizeof(LWGEOM *));
+ nearby = lwalloc(numedges * sizeof(LWGEOM *));
for (i=0; i<numedges; ++i)
{
LW_ON_INTERRUPT(return NULL);
@@ -5596,56 +5596,11 @@ _lwt_AddLine(LWT_TOPOLOGY* topo, LWLINE* line, double tol, int* nedges,
if ( dist && dist >= tol ) continue;
nearby[nearbyindex++] = g;
}
- LWDEBUGF(2, "Found %d lines closer than tolerance (%g)", nearbyindex, tol);
- if ( nearbyindex )
- {{
- LWCOLLECTION *col;
- LWGEOM *iedges; /* just an alias for col */
- LWGEOM *snapped;
- LWGEOM *set1, *set2;
-
- LWDEBUGF(1, "Line intersects %d edges", nearbyindex);
-
- col = lwcollection_construct(COLLECTIONTYPE, topo->srid,
- NULL, nearbyindex, nearby);
- iedges = lwcollection_as_lwgeom(col);
- LWDEBUGG(1, iedges, "Collected edges");
- LWDEBUGF(1, "Snapping noded, with srid=%d "
- "to interesecting edges, with srid=%d",
- noded->srid, iedges->srid);
- snapped = _lwt_toposnap(noded, iedges, tol);
- lwgeom_free(noded);
- LWDEBUGG(1, snapped, "Snapped");
- LWDEBUGF(1, "Diffing snapped, with srid=%d "
- "and interesecting edges, with srid=%d",
- snapped->srid, iedges->srid);
- noded = lwgeom_difference(snapped, iedges);
- LWDEBUGG(1, noded, "Differenced");
- LWDEBUGF(1, "Intersecting snapped, with srid=%d "
- "and interesecting edges, with srid=%d",
- snapped->srid, iedges->srid);
- set1 = lwgeom_intersection(snapped, iedges);
- LWDEBUGG(1, set1, "Intersected");
- lwgeom_free(snapped);
- LWDEBUGF(1, "Linemerging set1, with srid=%d", set1->srid);
- set2 = lwgeom_linemerge(set1);
- LWDEBUGG(1, set2, "Linemerged");
- LWDEBUGG(1, noded, "Noded");
- lwgeom_free(set1);
- LWDEBUGF(1, "Unioning noded, with srid=%d "
- "and set2, with srid=%d", noded->srid, set2->srid);
- set1 = lwgeom_union(noded, set2);
- lwgeom_free(set2);
- lwgeom_free(noded);
- noded = set1;
- LWDEBUGG(1, set1, "Unioned");
-
- /* will not release the geoms array */
- lwcollection_release(col);
- }}
+ LWDEBUGF(1, "Found %d edges closer than tolerance (%g)", nearbyindex, tol);
}}
+ int nearbyedgecount = nearbyindex;
- /* 2.1. Node with existing nodes within tol
+ /* 2.1. Find nodes falling within tol distance *
* TODO: check if we should be only considering _isolated_ nodes! */
nodes = lwt_be_getNodeWithinBox2D( topo, &qbox, &numnodes, LWT_COL_NODE_ALL, 0 );
if (numnodes == UINT64_MAX)
@@ -5655,11 +5610,10 @@ _lwt_AddLine(LWT_TOPOLOGY* topo, LWLINE* line, double tol, int* nedges,
return NULL;
}
LWDEBUGF(1, "Line bbox intersects %d nodes bboxes", numnodes);
- int nearbyedgecount = nearbyindex;
if ( numnodes )
{{
/* collect those whose distance from us is < tol */
- nearbycount = nearbyindex + numnodes;
+ nearbycount = nearbyedgecount + numnodes;
nearby = nearby ?
lwrealloc(nearby, nearbycount * sizeof(LWGEOM *))
:
@@ -5672,21 +5626,29 @@ _lwt_AddLine(LWT_TOPOLOGY* topo, LWLINE* line, double tol, int* nedges,
LWGEOM *g = lwpoint_as_lwgeom(n->geom);
double dist = lwgeom_mindistance2d(g, noded);
/* must be closer than tolerated, unless distance is zero */
- if ( dist && dist >= tol ) continue;
+ if ( dist && dist >= tol )
+ {
+ LWDEBUGF(1, "Node %d is %g units away, we tolerate only %g", n->node_id, dist, tol);
+ continue;
+ }
nearby[nearbyindex++] = g;
++nn;
}
+ LWDEBUGF(1, "Found %d nodes closer than tolerance (%g)", nn, tol);
}}
+ int nearbynodecount = nearbyindex - nearbyedgecount;
+ nearbycount = nearbyindex;
- LWDEBUGF(1, "Number of nearby elements is %d", nearbyindex);
+ LWDEBUGF(1, "Number of nearby elements is %d", nearbycount);
- if ( numnodes )
+ /* 2.2. Snap to nearby elements */
+ if ( nearbycount )
{{
LWCOLLECTION *col;
LWGEOM *elems;
col = lwcollection_construct(COLLECTIONTYPE, topo->srid,
- NULL, nearbyindex, nearby);
+ NULL, nearbycount, nearby);
elems = lwcollection_as_lwgeom(col);
LWDEBUGG(1, elems, "Collected nearby elements");
@@ -5699,20 +5661,6 @@ _lwt_AddLine(LWT_TOPOLOGY* topo, LWLINE* line, double tol, int* nedges,
/* will not release the geoms array */
lwcollection_release(col);
- if ( numnodes )
- {{
- col = lwcollection_construct(MULTIPOINTTYPE, topo->srid,
- NULL, nearbyindex-nearbyedgecount,
- nearby + nearbyedgecount);
- LWGEOM *inodes = lwcollection_as_lwgeom(col);
- tmp = _lwt_split_by_nodes(noded, inodes);
- lwgeom_free(noded);
- noded = tmp;
- LWDEBUGG(1, noded, "Node-split");
- /* will not release the geoms array */
- lwcollection_release(col);
- }}
-
/*
-- re-node to account for ST_Snap introduced self-intersections
-- See http://trac.osgeo.org/postgis/ticket/1714
@@ -5722,11 +5670,110 @@ _lwt_AddLine(LWT_TOPOLOGY* topo, LWLINE* line, double tol, int* nedges,
lwgeom_free(noded);
noded = tmp;
LWDEBUGG(1, noded, "Unary-unioned");
+ }}
+
+ /* 2.3. Node with nearby edges */
+ if ( nearbyedgecount )
+ {{
+ LWCOLLECTION *col;
+ LWGEOM *iedges; /* just an alias for col */
+ LWGEOM *diff, *xset;
+
+ LWDEBUGF(1, "Line intersects %d edges", nearbyedgecount);
+
+ col = lwcollection_construct(COLLECTIONTYPE, topo->srid,
+ NULL, nearbyedgecount, nearby);
+ iedges = lwcollection_as_lwgeom(col);
+ LWDEBUGG(1, iedges, "Collected edges");
+
+ LWDEBUGF(1, "Diffing noded, with srid=%d "
+ "and interesecting edges, with srid=%d",
+ noded->srid, iedges->srid);
+ diff = lwgeom_difference(noded, iedges);
+ LWDEBUGG(1, diff, "Differenced");
+
+ LWDEBUGF(1, "Intersecting noded, with srid=%d "
+ "and interesecting edges, with srid=%d",
+ noded->srid, iedges->srid);
+ xset = lwgeom_intersection(noded, iedges);
+ LWDEBUGG(1, xset, "Intersected");
+ lwgeom_free(noded);
+ /* We linemerge here because INTERSECTION, as of GEOS 3.8,
+ * will result in shared segments being output as multiple
+ * lines rather than a single line. Example:
+
+ INTERSECTION(
+ 'LINESTRING(0 0, 5 0, 8 0, 10 0,12 0)',
+ 'LINESTRING(5 0, 8 0, 10 0)'
+ )
+ ==
+ MULTILINESTRING((5 0,8 0),(8 0,10 0))
+
+ * We will re-split in a subsequent step, by splitting
+ * the final line with pre-existing nodes
+ */
+ LWDEBUG(1, "Linemerging intersection");
+ tmp = lwgeom_linemerge(xset);
+ LWDEBUGG(1, tmp, "Linemerged");
+ lwgeom_free(xset);
+ xset = tmp;
+
+ /*
+ * Here we union the (linemerged) intersection with
+ * the difference (new lines)
+ */
+ LWDEBUG(1, "Unioning difference and (linemerged) intersection");
+ noded = lwgeom_union(diff, xset);
+ LWDEBUGG(1, noded, "Diff-Xset Unioned");
+ lwgeom_free(xset);
+ lwgeom_free(diff);
+
+ /* will not release the geoms array */
+ lwcollection_release(col);
}}
+
+ /* 2.4. Split by pre-existing nodes
+ *
+ * Pre-existing nodes are isolated nodes AND endpoints
+ * of intersecting edges
+ */
+ if ( nearbyedgecount )
+ {
+ nearbycount += nearbyedgecount * 2; /* make space for endpoints */
+ nearby = lwrealloc(nearby, nearbycount * sizeof(LWGEOM *));
+ for (int i=0; i<nearbyedgecount; i++)
+ {
+ LWLINE *edge = lwgeom_as_lwline(nearby[i]);
+ LWPOINT *startNode = lwline_get_lwpoint(edge, 0);
+ LWPOINT *endNode = lwline_get_lwpoint(edge, edge->points->npoints-1);
+ /* TODO: only add if within distance to noded AND if not duplicated */
+ nearby[nearbyindex++] = lwpoint_as_lwgeom(startNode);
+ nearbynodecount++;
+ nearby[nearbyindex++] = lwpoint_as_lwgeom(endNode);
+ nearbynodecount++;
+ }
+ }
+ if ( nearbynodecount )
+ {
+ col = lwcollection_construct(MULTIPOINTTYPE, topo->srid,
+ NULL, nearbynodecount,
+ nearby + nearbyedgecount);
+ LWGEOM *inodes = lwcollection_as_lwgeom(col);
+ /* TODO: use lwgeom_split of lwgeom_union ... */
+ tmp = _lwt_split_by_nodes(noded, inodes);
+ lwgeom_free(noded);
+ noded = tmp;
+ LWDEBUGG(1, noded, "Node-split");
+ /* will not release the geoms array */
+ lwcollection_release(col);
+ }
+
+
LWDEBUG(1, "Freeing up nearby elements");
+ /* TODO: free up endpoints of nearbyedges */
if ( nearby ) lwfree(nearby);
if ( nodes ) _lwt_release_nodes(nodes, numnodes);
if ( edges ) _lwt_release_edges(edges, numedges);
diff --git a/topology/test/regress/topogeo_addlinestring.sql b/topology/test/regress/topogeo_addlinestring.sql
index 460229a..fbe4a2a 100644
--- a/topology/test/regress/topogeo_addlinestring.sql
+++ b/topology/test/regress/topogeo_addlinestring.sql
@@ -388,3 +388,13 @@ SELECT 't4757.0', topology.TopoGeo_addPoint('bug4757', 'POINT(0 0)');
SELECT 't4757.1', topology.TopoGeo_addLinestring('bug4757',
'LINESTRING(0 -0.1,1 0,1 1,0 1,0 -0.1)', 1);
SELECT 't4757.end', topology.DropTopology('bug4757');
+
+-- See https://trac.osgeo.org/postgis/ticket/t4758
+select 't4758.start', topology.CreateTopology ('t4758', 0, 1e-06) > 0;
+select 't4758.0', topology.TopoGeo_addLinestring('t4758',
+ 'LINESTRING(11.38327215 60.4081942, 11.3826176 60.4089484)');
+select 't4758.1', topology.TopoGeo_addLinestring('t4758',
+ 'LINESTRING( 11.3832721 60.408194249999994, 11.38327215 60.4081942)');
+select 't4758.2', topology.TopoGeo_addLinestring('t4758',
+ 'LINESTRING( 11.38330505 60.408239599999995, 11.3832721 60.408194249999994)');
+SELECT 't4758.end', topology.DropTopology('t4758');
diff --git a/topology/test/regress/topogeo_addlinestring_expected b/topology/test/regress/topogeo_addlinestring_expected
index b591715..c681a39 100644
--- a/topology/test/regress/topogeo_addlinestring_expected
+++ b/topology/test/regress/topogeo_addlinestring_expected
@@ -158,7 +158,7 @@ iso_ex_2segs|28
#1706.2|E*|69
#1706.2|E*|70
#1706.2|E*|71
-#1706.2|E*|73
+#1706.2|E*|74
#1706.2|N|73||POINT(10 0)
#1706.2|N|74||POINT(10 10)
#1706.2|N|75||POINT(9 12)
@@ -168,11 +168,12 @@ iso_ex_2segs|28
#1706.2|E|71|sn73|en74
#1706.2|E|72|sn75|en72
#1706.2|E|73|sn76|en74
+#1706.2|E|74|sn75|en76
#1714.1|N|77
#1714.1|N|77|0|POINT(10 0)
-#1714.2|E*|74
+#1714.2|E*|75
#1714.2|N|78||POINT(0 20)
-#1714.2|E|74|sn77|en78
+#1714.2|E|75|sn77|en78
Topology 'city_data' dropped
t3280.start|t
t3280|L11
@@ -201,7 +202,7 @@ t3371.L2|2
t3371.end|Topology 'bug3711' dropped
t3838.start|t
t3838.L1|1
-t3838.L2|9
+t3838.L2|6
t3838.end|Topology 'bug3838' dropped
t1855_1.start|t
t1855_1.0|1
@@ -215,3 +216,10 @@ t1855_2.end|Topology 'bug1855' dropped
t4757.start|t
t4757.0|1
t4757.end|Topology 'bug4757' dropped
+t4758.start|t
+t4758.0|1
+t4758.1|2
+t4758.2|4
+t4758.2|5
+t4758.2|2
+t4758.end|Topology 't4758' dropped
-----------------------------------------------------------------------
Summary of changes:
NEWS | 1 +
liblwgeom/lwgeom_topo.c | 191 +++++++++++++--------
topology/test/regress/topogeo_addlinestring.sql | 10 ++
.../test/regress/topogeo_addlinestring_expected | 16 +-
4 files changed, 142 insertions(+), 76 deletions(-)
hooks/post-receive
--
PostGIS
More information about the postgis-tickets
mailing list