[postgis-devel] Looking for a good ST_ChangeEdgeGeom semantic

[Sandro Santilli]

On Fri, Feb 17, 2012 at 07:21:13AM -0800, Paul Ramsey wrote:
> I think your concept works fine in my head. I worry that it might be
> brittle in practice since so many of these changes will be very minor
> single vertex shifts leading to test polygons that are very thin and
> narrow, precisely the thing that leads to topology failures in GEOS.
> However I don't let have a similar concept as easy to explain.

True, construction of the "motion range polygon" is the weak part.
But I'm still concerned about conceptual correctness.

> Also note you'll have to do more than just join up the edges due to
> the ease of constructing an invalid polygon that way (morph a straight
> line into an "S" shape, you get the classic invalid figure eight
> polygon).

Yup, first version used ST_MakeValid and ST_CollectionExtract, but
got to a failure with closed edges, forming rings on their own and
apparently breaking the nice even/odd picture. New version adds
a straight line between end node and start node, builds 2 rings
(using the rings that the old and the new edges form with the straight
line) and then uses their symdifference as the "motion range".

I still have to deal with other constraints, like a butterfly wing
becoming an hole in the other wing...

--strk;

> 
> P.
> 
> On Fri, Feb 17, 2012 at 12:30 AM, Sandro Santilli <strk at keybit.net> wrote:
> > Great, thanks a lot Paul.
> > I've slept over it and internalized that as well.
> >
> > And "Homeorpheus" came to the rescue !
> >
> > I woke up and while explaining the problem of "figuring out when
> > the restriction is violated" to my daughter I got enlightened by
> > this simple algorithm:
> >
> >  If the polygon formed by the _old_ and the _new_ edge
> >  contains any node, then the rule is violated.
> >
> > It seems to work pretty well. Only corner case is the closed edge
> > being reverted, but a single corner case I can live with :D
> >
> > So, for your delectation, and hoping your mail client uses monospace
> > fonts, here are the cases I've shown with the algorithm applied:
> >
> > Source:
> >
> >  o========o
> >       o
> >
> > Targets:
> >
> >  o========o
> >  |     o  |      NOT VALID (a node inside)
> >  '--------'
> >
> >
> >
> >  o==,-----o
> >  |  |  o         VALID
> >  '--'
> >
> >  o==,-----o
> >  |  |  o .-.     VALID
> >  |  `----' |
> >  '---------'
> >
> >    ,---------.
> >    `-------. |
> >  o==,-----o | |
> >  |  |  o    | |  VALID
> >  |  `-------' |
> >  '------------'
> >
> > Exciting !
> >
> > --strk;
> >
> >
> > On Thu, Feb 16, 2012 at 10:07:10AM -0800, Paul Ramsey wrote:
> >> The two odd cases you show are impossible without "lifting" the edge
> >> up off the paper and putting it down on the other side of the other
> >> edges. The deformation has to be done without leaving the manifold.
> >> The authors perhaps assumed the reader would internalize that
> >> restriction.
> >>
> >> P.
> >>
> >> On Thu, Feb 16, 2012 at 10:02 AM, Sandro Santilli <strk at keybit.net> wrote:
> >> > Someone might have been following the ST_ChangeEdgeGeom saga:
> >> > http://trac.osgeo.org/postgis/ticket/1571
> >> >
> >> > The problem is that ISO/SQL-MM specification don't tell
> >> > much about what's allowed and what not when it comes to
> >> > changing the geometry of an edge, except that its endpoints
> >> > must remain the same. So for example you can go from this:
> >> >
> >> >    o--------------o
> >> >
> >> > To this:
> >> >
> >> >    o---,      .---o
> >> >        |     /
> >> >        `----'
> >> >
> >> > Now my problem is, how far can we push this ?
> >> > Should we also allow going from this:
> >> >
> >> >    o--------------o
> >> >    |              |
> >> >    o------E1------o
> >> >    |              |
> >> >    o--------------o
> >> >
> >> > To this:
> >> >
> >> >  .--------E1--------,
> >> >  |                  |
> >> >  | o--------------o |
> >> >  | |              | |
> >> >  '-o              o-'
> >> >    |              |
> >> >    o--------------o
> >> >
> >> > And what about from this:
> >> >
> >> >    .--------------,
> >> >    |              |
> >> >    o------E1------o
> >> >
> >> > To this:
> >> >
> >> >  .--------E1--------,
> >> >  |                  |
> >> >  | .--------------, |
> >> >  | |              | |
> >> >  '-o              o-'
> >> >
> >> > I tend to think "NO", but I don't have a clear definition about it.
> >> >
> >> > It may have to do with considering the edge as made with
> >> > an elastic matter, taking it with your hand and morphing it
> >> > into the new position w/out hitting obstacles. And I think I've
> >> > read about this kind of concept somewhere, related to topology.
> >> >
> >> > Does anyone have better nomenclature for the concept ?
> >> >
> >> > --strk;
> >> >
> >> >  ,------o-.
> >> >  |   __/  |    Delivering high quality PostGIS 2.0 !
> >> >  |  / 2.0 |    http://strk.keybit.net
> >> >  `-o------'
> >> >
> >> > _______________________________________________
> >> > postgis-devel mailing list
> >> > postgis-devel at postgis.refractions.net
> >> > http://postgis.refractions.net/mailman/listinfo/postgis-devel
> >> _______________________________________________
> >> postgis-devel mailing list
> >> postgis-devel at postgis.refractions.net
> >> http://postgis.refractions.net/mailman/listinfo/postgis-devel
> >
> > --
> >
> >  ,------o-.
> >  |   __/  |    Delivering high quality PostGIS 2.0 !
> >  |  / 2.0 |    http://strk.keybit.net
> >  `-o------'
> >
> > _______________________________________________
> > postgis-devel mailing list
> > postgis-devel at postgis.refractions.net
> > http://postgis.refractions.net/mailman/listinfo/postgis-devel
> _______________________________________________
> postgis-devel mailing list
> postgis-devel at postgis.refractions.net
> http://postgis.refractions.net/mailman/listinfo/postgis-devel

-- 

  ,------o-. 
  |   __/  |    Delivering high quality PostGIS 2.0 !
  |  / 2.0 |    http://strk.keybit.net
  `-o------'