[GEOS] #1064: Topology preserve simplify: unexpected behavior on similar polygons

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
9 messages Options
Reply | Threaded
Open this post in threaded view
|

[GEOS] #1064: Topology preserve simplify: unexpected behavior on similar polygons

geos-2
#1064: Topology preserve simplify: unexpected behavior on similar polygons
------------------------+--------------------------
 Reporter:  uclaros     |      Owner:  geos-devel@…
     Type:  defect      |     Status:  new
 Priority:  minor       |  Milestone:
Component:  Default     |    Version:  master
 Severity:  Unassigned  |   Keywords:
------------------------+--------------------------
 When simplifying a polygon, the first/last vertex is not removed even when
 within the threshold.
 The following WKT polygons are essentially the same polygon, each time
 with a different first/last vertex:

 {{{
 Polygon((0 42, 0 100, 42 100, 100 42, 42 42, 0 42))
 Polygon((0 100, 42 100, 100 42, 42 42, 0 42, 0 100))
 Polygon((42 100, 100 42, 42 42, 0 42, 0 100, 42 100))
 Polygon((100 42, 42 42, 0 42, 0 100, 42 100, 100 42))
 Polygon((42 42, 0 42, 0 100, 42 100, 100 42, 42 42))
 }}}

 simplifying those polygons with a threshold of 1 should give the same
 result, ie remove the vertex at (42,42) but in the last case this does not
 happen and the input polygon is returned untouched.

 If we remove the vertex at (0,100) and rerun the test:
 {{{
 Polygon((0 42, 42 100, 100 42, 42 42, 0 42))
 Polygon((42 100, 100 42, 42 42, 0 42, 42 100))
 Polygon((100 42, 42 42, 0 42, 42 100, 100 42))
 Polygon((42 42, 0 42, 42 100, 100 42, 42 42))
 }}}
 then only the second polygon gives the correct result, all the others are
 returned untouched

 Tested in QGIS with geos 3.9.0dev :
 {{{
 QgsGeometry.fromWkt('Polygon((0 42, 42 100, 100 42, 42 42, 0
 42))').simplify(1)
 QgsGeometry.fromWkt('Polygon((42 100, 100 42, 42 42, 0 42, 42
 100))').simplify(1)
 QgsGeometry.fromWkt('Polygon((100 42, 42 42, 0 42, 42 100, 100
 42))').simplify(1)
 QgsGeometry.fromWkt('Polygon((42 42, 0 42, 42 100, 100 42, 42
 42))').simplify(1)

 QgsGeometry.fromWkt('Polygon((0 42, 0 100, 42 100, 100 42, 42 42, 0
 42))').simplify(1)
 QgsGeometry.fromWkt('Polygon((0 100, 42 100, 100 42, 42 42, 0 42, 0
 100))').simplify(1)
 QgsGeometry.fromWkt('Polygon((42 100, 100 42, 42 42, 0 42, 0 100, 42
 100))').simplify(1)
 QgsGeometry.fromWkt('Polygon((100 42, 42 42, 0 42, 0 100, 42 100, 100
 42))').simplify(1)
 QgsGeometry.fromWkt('Polygon((42 42, 0 42, 0 100, 42 100, 100 42, 42
 42))').simplify(1)
 }}}

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/1064>
GEOS <http://trac.osgeo.org/geos>
GEOS (Geometry Engine - Open Source) is a C++ port of the Java Topology Suite (JTS).

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: [GEOS] #1064: Topology preserve simplify: unexpected behavior on similar polygons

geos-2
#1064: Topology preserve simplify: unexpected behavior on similar polygons
------------------------+---------------------------
 Reporter:  uclaros     |       Owner:  geos-devel@…
     Type:  defect      |      Status:  new
 Priority:  minor       |   Milestone:  3.9.0
Component:  Default     |     Version:  master
 Severity:  Unassigned  |  Resolution:
 Keywords:              |
------------------------+---------------------------
Changes (by robe):

 * milestone:   => 3.9.0


--
Ticket URL: <https://trac.osgeo.org/geos/ticket/1064#comment:1>
GEOS <http://trac.osgeo.org/geos>
GEOS (Geometry Engine - Open Source) is a C++ port of the Java Topology Suite (JTS).

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: [GEOS] #1064: Topology preserve simplify: unexpected behavior on similar polygons

geos-2
In reply to this post by geos-2
#1064: Topology preserve simplify: unexpected behavior on similar polygons
------------------------+---------------------------
 Reporter:  uclaros     |       Owner:  geos-devel@…
     Type:  defect      |      Status:  new
 Priority:  minor       |   Milestone:  3.9.0
Component:  Default     |     Version:  master
 Severity:  Unassigned  |  Resolution:
 Keywords:              |
------------------------+---------------------------
Changes (by strk):

 * cc: mbdavis (added)


Comment:

 I guess one option here would be to pick the leftmost-upmost and the
 rightmost-bottommost points of a ring, split the ring in two parts, merge
 the lines which remain split by the origina vertex, then perform the
 simplification on the two parts and join them back togheter.

 What do you think Martin ?

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/1064#comment:2>
GEOS <http://trac.osgeo.org/geos>
GEOS (Geometry Engine - Open Source) is a C++ port of the Java Topology Suite (JTS).

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: [GEOS] #1064: Topology preserve simplify: unexpected behavior on similar polygons

geos-2
In reply to this post by geos-2
#1064: Topology preserve simplify: unexpected behavior on similar polygons
------------------------+---------------------------
 Reporter:  uclaros     |       Owner:  geos-devel@…
     Type:  defect      |      Status:  new
 Priority:  minor       |   Milestone:  3.9.0
Component:  Default     |     Version:  master
 Severity:  Unassigned  |  Resolution:
 Keywords:              |
------------------------+---------------------------

Comment (by mdavis):

 Replying to [comment:2 strk]:
 > I guess one option here would be to pick the leftmost-upmost and the
 rightmost-bottommost points of a ring, split the ring in two parts, merge
 the lines which remain split by the origina vertex, then perform the
 simplification on the two parts and join them back togheter.
 >
 > What do you think Martin ?

 I don't see how that works.  The problem with the current simplification
 algorithm is that it is essentially working on a line, not a ring - which
 is why it doesn't remove the endpoint even if it should be.  Doesn't
 splitting the ring just introduce one more endpoint?

 Not sure of what a solution could be ATM.  The simplification algorithm
 being used is Douglas-Peucker, and I don't know if that can be generalized
 to work on true rings.

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/1064#comment:3>
GEOS <http://trac.osgeo.org/geos>
GEOS (Geometry Engine - Open Source) is a C++ port of the Java Topology Suite (JTS).

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: [GEOS] #1064: Topology preserve simplify: unexpected behavior on similar polygons

geos-2
In reply to this post by geos-2
#1064: Topology preserve simplify: unexpected behavior on similar polygons
------------------------+---------------------------
 Reporter:  uclaros     |       Owner:  geos-devel@…
     Type:  defect      |      Status:  new
 Priority:  minor       |   Milestone:  3.9.0
Component:  Default     |     Version:  master
 Severity:  Unassigned  |  Resolution:
 Keywords:              |
------------------------+---------------------------

Comment (by mdavis):

 Not a net new problem; here's some
 [https://stackoverflow.com/questions/8877257/finding-good-starting-points-
 for-douglas-peucker-algorithm-for-closed-polygons ideas] about it.  Not
 sure I totally agree with the suggestions, but they do have some ideas
 that are a starting point.

 How about this: find the vertex for which the triangle formed with the
 adjacent vertices has maximum height, and rotate the ring to use it as the
 starting point?  (Height being the perpendicular distance to the line
 between the adjacent points.  In the case of a regular polygon this is
 arbitrary, so no need to rotate).

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/1064#comment:4>
GEOS <http://trac.osgeo.org/geos>
GEOS (Geometry Engine - Open Source) is a C++ port of the Java Topology Suite (JTS).

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: [GEOS] #1064: Topology preserve simplify: unexpected behavior on similar polygons

geos-2
In reply to this post by geos-2
#1064: Topology preserve simplify: unexpected behavior on similar polygons
------------------------+---------------------------
 Reporter:  uclaros     |       Owner:  geos-devel@…
     Type:  defect      |      Status:  new
 Priority:  minor       |   Milestone:  3.9.0
Component:  Default     |     Version:  master
 Severity:  Unassigned  |  Resolution:
 Keywords:              |
------------------------+---------------------------

Comment (by uclaros):

 A simplistic solution would be to take the current resulting polygon, use
 its 0, 1, n-1 and n (same as 0) vertices to decide if 0 and n vertices
 should also be removed. If so, remove them and append vertex 1 to the end
 to close the ring.

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/1064#comment:5>
GEOS <http://trac.osgeo.org/geos>
GEOS (Geometry Engine - Open Source) is a C++ port of the Java Topology Suite (JTS).

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: [GEOS] #1064: Topology preserve simplify: unexpected behavior on similar polygons

geos-2
In reply to this post by geos-2
#1064: Topology preserve simplify: unexpected behavior on similar polygons
------------------------+---------------------------
 Reporter:  uclaros     |       Owner:  geos-devel@…
     Type:  defect      |      Status:  new
 Priority:  minor       |   Milestone:  3.9.0
Component:  Default     |     Version:  master
 Severity:  Unassigned  |  Resolution:
 Keywords:              |
------------------------+---------------------------

Comment (by mdavis):

 Replying to [comment:5 uclaros]:
 > take the current resulting polygon, use its 0, 1, n-1 and n (same as 0)
 vertices to decide if 0 and n vertices should also be removed.

 Good idea.

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/1064#comment:6>
GEOS <http://trac.osgeo.org/geos>
GEOS (Geometry Engine - Open Source) is a C++ port of the Java Topology Suite (JTS).

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: [GEOS] #1064: Topology preserve simplify: unexpected behavior on similar polygons

geos-2
In reply to this post by geos-2
#1064: Topology preserve simplify: unexpected behavior on similar polygons
------------------------+---------------------------
 Reporter:  uclaros     |       Owner:  geos-devel@…
     Type:  defect      |      Status:  new
 Priority:  minor       |   Milestone:  3.9.0
Component:  Default     |     Version:  master
 Severity:  Unassigned  |  Resolution:
 Keywords:              |
------------------------+---------------------------

Comment (by komzpa):

 Generally speaking Douglas-Peucker should be replaced with Visvalingam-
 Whyatt when doing anything about area. It is easily adaptable for rings.
 The epsilon will be an area then, it is usually ok to square the DP
 epsilon and run VW instead on areas.

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/1064#comment:7>
GEOS <http://trac.osgeo.org/geos>
GEOS (Geometry Engine - Open Source) is a C++ port of the Java Topology Suite (JTS).

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: [GEOS] #1064: Topology preserve simplify: unexpected behavior on similar polygons

geos-2
In reply to this post by geos-2
#1064: Topology preserve simplify: unexpected behavior on similar polygons
------------------------+---------------------------
 Reporter:  uclaros     |       Owner:  geos-devel@…
     Type:  defect      |      Status:  new
 Priority:  minor       |   Milestone:  GEOS Fund Me
Component:  Default     |     Version:  master
 Severity:  Unassigned  |  Resolution:
 Keywords:              |
------------------------+---------------------------
Changes (by pramsey):

 * milestone:  3.9.0 => GEOS Fund Me


--
Ticket URL: <https://trac.osgeo.org/geos/ticket/1064#comment:8>
GEOS <http://trac.osgeo.org/geos>
GEOS (Geometry Engine - Open Source) is a C++ port of the Java Topology Suite (JTS).

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel