[postgis-tickets] [SCM] PostGIS branch master updated. 3.1.0alpha2-92-g7c05b5c
git at osgeo.org
git at osgeo.org
Thu Oct 15 07:26:38 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, master has been updated
via 7c05b5cdd8a9cf2b9f80666a0be2cac7cf06cd16 (commit)
via b1a18d427ed8a9a47dc94726aec4535d0e811c6d (commit)
from f8b99564cd50874bad0371b40a821d91b04c3c39 (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 7c05b5cdd8a9cf2b9f80666a0be2cac7cf06cd16
Author: Sandro Santilli <strk at kbt.io>
Date: Thu Oct 15 02:12:25 2020 +0200
Do not include non-isolated nodes twice to topology snap target
diff --git a/liblwgeom/lwgeom_topo.c b/liblwgeom/lwgeom_topo.c
index 46823c8..964b7ae 100644
--- a/liblwgeom/lwgeom_topo.c
+++ b/liblwgeom/lwgeom_topo.c
@@ -5619,8 +5619,10 @@ _lwt_AddLine(LWT_TOPOLOGY* topo, LWLINE* line, double tol, int* nedges,
}}
int nearbyedgecount = nearbyindex;
- /* 2.1. Find nodes falling within tol distance *
- * TODO: check if we should be only considering _isolated_ nodes! */
+ /* 2.1. Find isolated nodes falling within tol distance
+ *
+ * TODO: add backend-interface support for only getting isolated nodes
+ */
nodes = lwt_be_getNodeWithinBox2D( topo, &qbox, &numnodes, LWT_COL_NODE_ALL, 0 );
if (numnodes == UINT64_MAX)
{
@@ -5642,6 +5644,7 @@ _lwt_AddLine(LWT_TOPOLOGY* topo, LWLINE* line, double tol, int* nedges,
for (i=0; i<numnodes; ++i)
{
LWT_ISO_NODE *n = &(nodes[i]);
+ if ( n->containing_face == -1 ) continue; /* skip not-isolated nodes */
LWGEOM *g = lwpoint_as_lwgeom(n->geom);
double dist = lwgeom_mindistance2d(g, noded);
/* must be closer than tolerated, unless distance is zero */
@@ -5653,7 +5656,7 @@ _lwt_AddLine(LWT_TOPOLOGY* topo, LWLINE* line, double tol, int* nedges,
nearby[nearbyindex++] = g;
++nn;
}
- LWDEBUGF(1, "Found %d nodes closer than tolerance (%g)", nn, tol);
+ LWDEBUGF(1, "Found %d isolated nodes closer than tolerance (%g)", nn, tol);
}}
int nearbynodecount = nearbyindex - nearbyedgecount;
nearbycount = nearbyindex;
commit b1a18d427ed8a9a47dc94726aec4535d0e811c6d
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
Includes automated test
diff --git a/NEWS b/NEWS
index c5eec4e..49d9d96 100644
--- a/NEWS
+++ b/NEWS
@@ -13,6 +13,8 @@ Only tickets not included in 3.1.0alpha2
- GEOS 3.9
* Enhancements *
+
+ - #4758, Improve topology noding robustness (Sandro Santilli)
- Make ST_Subdivide interruptable (Sandro Santilli)
- #4660, Changes in double / coordinate printing (Raúl Marín)
- Use the shortest representation (enough to guarantee roundtrip).
diff --git a/liblwgeom/lwgeom_topo.c b/liblwgeom/lwgeom_topo.c
index 236a292..46823c8 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>
*
**********************************************************************/
@@ -5586,10 +5586,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)
{
@@ -5603,7 +5603,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);
@@ -5615,56 +5615,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)
@@ -5674,11 +5629,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 *))
:
@@ -5691,21 +5645,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");
@@ -5718,20 +5680,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
@@ -5741,11 +5689,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 fc194de..74de66e 100644
--- a/topology/test/regress/topogeo_addlinestring.sql
+++ b/topology/test/regress/topogeo_addlinestring.sql
@@ -387,3 +387,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 c760d95..2001ed6 100644
--- a/topology/test/regress/topogeo_addlinestring_expected
+++ b/topology/test/regress/topogeo_addlinestring_expected
@@ -162,12 +162,13 @@ iso_ex_2segs|28
#1706.2|N||POINT(10 10)
#1706.2|E|LINESTRING(10 0,10 10)
#1706.2|E|LINESTRING(15 10,10 10)
+#1706.2|E|LINESTRING(9 12,15 10)
#1706.2|E|LINESTRING(10 10,9 12)
#1706.2|E|LINESTRING(20 10,15 10)
#1706.2|E|LINESTRING(9 12,10 20)
#1714.1|N|77
#1714.1|N|0|POINT(10 0)
-#1714.2|E*|74
+#1714.2|E*|75
#1714.2|N||POINT(0 20)
#1714.2|E|LINESTRING(10 0,0 20)
Topology 'city_data' dropped
@@ -197,7 +198,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
@@ -209,3 +210,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 | 2 +
liblwgeom/lwgeom_topo.c | 196 +++++++++++++--------
topology/test/regress/topogeo_addlinestring.sql | 10 ++
.../test/regress/topogeo_addlinestring_expected | 12 +-
4 files changed, 145 insertions(+), 75 deletions(-)
hooks/post-receive
--
PostGIS
More information about the postgis-tickets
mailing list