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

9 messages
Open this post in threaded view
|

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

 #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: 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
Open this post in threaded view
|

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

 #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: 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
Open this post in threaded view
|

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

 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: 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
Open this post in threaded view
|

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

 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: 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
Open this post in threaded view
|

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

 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: 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
Open this post in threaded view
|

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

 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: 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
Open this post in threaded view
|

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

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