Opened 12 years ago

Closed 12 years ago

#1571 closed defect (fixed)

ST_ChangeEdgeGeom lets you break topology

Reported by: strk Owned by: strk
Priority: medium Milestone: PostGIS 2.0.0
Component: topology Version: master
Keywords: Cc:

Description

Changing the shape of one edge can introduce topology errors in a persistent topology. This happens for example if the new shape changes face containment of isolated nodes or edges or if it changes edge linking. See #982 for examples of this

Attachments (1)

motion.png (8.5 KB ) - added by strk 12 years ago.

Download all attachments as: .zip

Change History (14)

comment:1 by strk, 12 years ago

I'm thinking that we could add an invariant making sure that the EdgeStar of each node of the edge endpoints looks the same (ie: same edges going into and output of the node, in same order). The new GetNodeEdges function committed in r9219 would be handy for this.

The consequence of this would be you can't change order and you can't change face. It would remain the possibility to include or exclude isolated nodes and edges from one face.

comment:2 by strk, 12 years ago

We'll have to skip considering dangling edges in this check, or the limit would be overly paranoid

comment:3 by strk, 12 years ago

Wrong assumption completely, actually. There are cases in which edge end star doesn't change but ring winding still does :-/

Another use case for a fast ring winding computer…

comment:4 by strk, 12 years ago

Milestone: PostGIS 2.0.0PostGIS 2.1.0

I wonder if the semantic for this function should be: you should be able to drag the edge shape around hitting _no_ obstacle. Sounds like a topology prescription, although I'm not using correct terms.

comment:5 by strk, 12 years ago

Thanks Paul for helping with the concept: http://postgis.refractions.net/pipermail/postgis-devel/2012-February/018640.html

I think we're now clear for the semantic. Next step would be algorithmical: how to find out if the constraint gets broken by a movement ?

Here's some random examples for proving your mind over the concept:

Source:

o--------o
      o

Some Targets:

o        o
|     o  |       NOT VALID
'--------'



o  ,-----o
|  |  o          VALID
'--'

o  ,-----o
|  |  o .-.      VALID
|  `----' |
'---------'

   ,---------.
   `-------. |
o  ,-----o | |
|  |  o    | |   VALID
|  `-------' |
'------------'

in reply to:  5 comment:6 by strk, 12 years ago

Milestone: PostGIS 2.1.0PostGIS 2.0.0

Replying to strk:

Next step would be algorithmically: how to find out if the constraint gets broken by a movement ?

A night over it and here's the answer: form a polygon merging old and new edge, if the polygon contains any node then the movement broke the constraint. Corner case: a closed edge changing winding (must be treated specially)

I can do it for 2.0 !

by strk, 12 years ago

Attachment: motion.png added

comment:7 by strk, 12 years ago

It turns out it's not that easy. This image shows a case in which it is hard to find the "motion range polygon" (the polygon which should represent the movement taken from the original edge to become the new edge).

There we go from the RED edge to the YELLOW edge. Sounds like a motion planning problem in that there are multiple possible paths to get from one point to the other, go figure if there's at least _one_ path not resulting in collision with node 4…

comment:8 by strk, 12 years ago

Milestone: PostGIS 2.0.0PostGIS 2.1.0

postponing again, it'll take more sleeps…

comment:9 by strk, 12 years ago

I've solved the above by using the algorithm built into ST_MakeValid. It seems to give that black/white pattern which smells like fixing most cases. This is really a feeling more than a proved algorithm, but so far I didn't find breaking cases.

comment:10 by strk, 12 years ago

r9224 should be handling all cases of dangling or isolated edges, but there are still bogus cases, like taking one edge of a ring and pulling to turn the ring inside-out. A function to compute edge-rings (not looking at metadata) would help there.

comment:11 by strk, 12 years ago

r9226 fixes a case that r9224 wasn't fixing. It's a "closed edge" actually.

comment:12 by strk, 12 years ago

Milestone: PostGIS 2.1.0PostGIS 2.0.0

r9228 fixes the leftover cases of edges changing disposition around end nodes. It's been a long battle, but finally seeing the light…

Will reserve another day to check MBR and then close this.

comment:13 by strk, 12 years ago

Resolution: fixed
Status: newclosed

I think this is fixed. I've filed #1587 for the MBR thing.

Note: See TracTickets for help on using tickets.