ST_ChangeEdgeGeom lets you break topology

[strk]

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

[strk]

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.

[strk]

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

[strk]

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...

[strk]

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.

[strk]

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
|  `-------' |
'------------'

[strk]

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 !

[strk]

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...

[strk]

postponing again, it'll take more sleeps...

[strk]

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.

[strk]

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.

[strk]

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

[strk]

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.

[strk]

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