From a7487322ff861652de641b1a9b60c8ea679b75ef Mon Sep 17 00:00:00 2001 From: Sandro Santilli Date: Tue, 24 Jan 2012 17:29:14 +0000 Subject: [PATCH] Optimize ST_AddEdge*Face* detection of face split conditions (#1497) git-svn-id: http://svn.osgeo.org/postgis/trunk@8915 b70326c6-7e19-0410-871a-916f4a2858ee --- topology/sql/sqlmm.sql.in.c | 102 ++++++++++++++++++++---------------- 1 file changed, 56 insertions(+), 46 deletions(-) diff --git a/topology/sql/sqlmm.sql.in.c b/topology/sql/sqlmm.sql.in.c index d2a851a12..99529bda1 100644 --- a/topology/sql/sqlmm.sql.in.c +++ b/topology/sql/sqlmm.sql.in.c @@ -3164,21 +3164,6 @@ BEGIN RAISE EXCEPTION 'Could not derive edge face from linked primitives: invalid topology ?'; END IF; - ---------------------------------------------------------------------- - -- - -- Polygonize the current edges (to see later if the addition - -- of the new one created another ring) - -- - ---------------------------------------------------------------------- - - SELECT null::geometry as post, null::geometry as pre INTO fan; - - EXECUTE - 'SELECT ST_Polygonize(geom) FROM ' - || quote_ident(atopology) || '.edge_data WHERE left_face = ' - || newedge.left_face || ' OR right_face = ' || newedge.right_face - INTO STRICT fan.pre; - ---------------------------------------------------------------------- -- -- Insert the new edge, and update all linking @@ -3256,18 +3241,26 @@ BEGIN ---------------------------------------------------------------------- -- - -- Polygonize the new edges and see if the addition created a new ring + -- See if the addition splitted a face -- ---------------------------------------------------------------------- - EXECUTE 'SELECT ST_Polygonize(geom) FROM ' - || quote_ident(atopology) || '.edge_data WHERE left_face = ' - || newedge.left_face || ' OR right_face = ' || newedge.right_face - INTO STRICT fan.post; + SELECT null::geometry as post, null::geometry as pre, null::int[] as ring_left INTO fan; + + SELECT array_agg(edge) + FROM topology.getringedges(atopology, newedge.edge_id) + INTO STRICT fan.ring_left; - IF ST_NumGeometries(fan.pre) = ST_NumGeometries(fan.post) THEN - -- No splits, all done - RETURN newedge.edge_id; +#ifdef POSTGIS_TOPOLOGY_DEBUG + RAISE DEBUG 'l_ring: %', fan.ring_left; +#endif + + -- You can't get to the other side of an edge forming a ring + IF fan.ring_left @> ARRAY[-newedge.edge_id] THEN +#ifdef POSTGIS_TOPOLOGY_DEBUG + RAISE DEBUG 'no split'; +#endif + RETURN newedge.edge_id; -- no split ! END IF; #ifdef POSTGIS_TOPOLOGY_DEBUG @@ -3275,6 +3268,18 @@ BEGIN newedge.edge_id, newedge.left_face; #endif + -- + -- Update the left_face/right_face for the edges binding + -- the split faces + -- + -- TODO: optimize this by following edge links! + -- + + EXECUTE 'SELECT ST_Polygonize(geom) FROM ' + || quote_ident(atopology) || '.edge_data WHERE left_face = ' + || newedge.left_face || ' OR right_face = ' || newedge.right_face + INTO STRICT fan.post; + -- Call topology.AddFace for every face containing the new edge -- -- The ORDER serves predictability of which face is added first @@ -3855,21 +3860,6 @@ BEGIN RAISE EXCEPTION 'Could not derive edge face from linked primitives: invalid topology ?'; END IF; - ---------------------------------------------------------------------- - -- - -- Polygonize the current edges (to see later if the addition - -- of the new one created another ring) - -- - ---------------------------------------------------------------------- - - SELECT null::geometry as post, null::geometry as pre INTO fan; - - EXECUTE - 'SELECT ST_Polygonize(geom) FROM ' - || quote_ident(atopology) || '.edge_data WHERE left_face = ' - || newedge.left_face || ' OR right_face = ' || newedge.right_face - INTO STRICT fan.pre; - ---------------------------------------------------------------------- -- -- Insert the new edge, and update all linking @@ -3947,18 +3937,26 @@ BEGIN ---------------------------------------------------------------------- -- - -- Polygonize the new edges and see if the addition created a new ring + -- See if the addition splitted a face -- ---------------------------------------------------------------------- - EXECUTE 'SELECT ST_Polygonize(geom) FROM ' - || quote_ident(atopology) || '.edge_data WHERE left_face = ' - || newedge.left_face || ' OR right_face = ' || newedge.right_face - INTO STRICT fan.post; + SELECT null::geometry as post, null::geometry as pre, null::int[] as ring_left INTO fan; + + SELECT array_agg(edge) + FROM topology.getringedges(atopology, newedge.edge_id) + INTO STRICT fan.ring_left; - IF ST_NumGeometries(fan.pre) = ST_NumGeometries(fan.post) THEN - -- No splits, all done - RETURN newedge.edge_id; +#ifdef POSTGIS_TOPOLOGY_DEBUG + RAISE DEBUG 'l_ring: %', fan.ring_left; +#endif + + -- You can't get to the other side of an edge forming a ring + IF fan.ring_left @> ARRAY[-newedge.edge_id] THEN +#ifdef POSTGIS_TOPOLOGY_DEBUG + RAISE DEBUG 'no split'; +#endif + RETURN newedge.edge_id; -- no split ! END IF; #ifdef POSTGIS_TOPOLOGY_DEBUG @@ -3966,6 +3964,18 @@ BEGIN newedge.edge_id, newedge.left_face; #endif + -- + -- Update the left_face/right_face for the edges binding + -- the face on the left of the newly added edge + -- + -- TODO: optimize this by following edge links! + -- + + EXECUTE 'SELECT ST_Polygonize(geom) FROM ' + || quote_ident(atopology) || '.edge_data WHERE left_face = ' + || newedge.left_face || ' OR right_face = ' || newedge.right_face + INTO STRICT fan.post; + -- Call topology.AddFace for every face whose boundary contains the new edge -- -- TODO: in presence of holes every hole would share a boundary -- 2.40.0