Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

SimplifyDP produces wrong result for polygon at specific distance #498

Closed
dr-jts opened this issue Nov 24, 2019 · 4 comments
Closed

SimplifyDP produces wrong result for polygon at specific distance #498

dr-jts opened this issue Nov 24, 2019 · 4 comments
Assignees
@dr-jts
Labels
jts-core type-bug

Comments

@dr-jts
Copy link
Contributor

dr-jts commented Nov 24, 2019 •
edited
Loading

As noted in GEOS 1004, the following polygon produces a VERY incorrect result for simplify tolerance = 0.0036.

Interestingly, using tolerance = 0.00365 produces a reasonable result.

Input:

POLYGON ((21.44786 47.65323,21.38886 47.66023,21.37386 47.65123,21.36586 47.66323,21.34886 47.66423,21.33286 47.65623,21.32186 47.66123,21.30886 47.65923,21.30186 47.66623,21.30786 47.66823,21.30286 47.67523,21.26786 47.67823,21.25586 47.69623,21.23886 47.70023,21.25186 47.70123,21.25186 47.70523,21.24486 47.71023,21.23286 47.70723,21.23286 47.71123,21.25186 47.71523,21.23886 47.72223,21.24186 47.72523,21.23586 47.73023,21.24286 47.73023,21.23586 47.73123,21.23686 47.73523,21.24986 47.73423,21.24486 47.73323,21.24986 47.72423,21.26586 47.71823,21.25886 47.72923,21.26086 47.73723,21.24986 47.74023,21.25986 47.74823,21.25386 47.75123,21.27786 47.75423,21.28086 47.76323,21.26786 47.76123,21.29286 47.77723,21.28086 47.78123,21.26086 47.77623,21.28986 47.78523,21.29486 47.78123,21.29586 47.78623,21.32086 47.77123,21.32686 47.78723,21.31686 47.79023,21.31186 47.80023,21.32386 47.79023,21.34186 47.79223,21.34886 47.78723,21.34686 47.78323,21.35686 47.78223,21.33886 47.79923,21.32886 47.80523,21.32186 47.80223,21.31486 47.81023,21.32786 47.81123,21.33986 47.80223,21.33886 47.81123,21.32686 47.82023,21.32586 47.82723,21.32786 47.82323,21.33886 47.82623,21.34186 47.82123,21.36386 47.82223,21.36786 47.81823,21.36086 47.81423,21.37386 47.81423,21.37386 47.81023,21.37486 47.81423,21.38686 47.81423,21.39486 47.80723,21.39586 47.81423,21.40686 47.81723,21.42286 47.80823,21.42286 47.81323,21.43586 47.81623,21.44486 47.80723,21.44486 47.81723,21.44986 47.80523,21.46386 47.81023,21.46186 47.80323,21.47986 47.80723,21.48186 47.80223,21.47686 47.80123,21.49486 47.80123,21.50486 47.78523,21.48686 47.78023,21.49386 47.77023,21.50686 47.77223,21.49986 47.76623,21.49686 47.75123,21.50486 47.75323,21.50686 47.74623,21.50986 47.75223,21.50886 47.74123,21.51286 47.74623,21.51986 47.74223,21.51386 47.72323,21.52586 47.71723,21.52586 47.71123,21.51886 47.70823,21.51986 47.71223,21.51386 47.71223,21.50886 47.70723,21.50686 47.69223,21.49686 47.69023,21.50286 47.68823,21.50186 47.67323,21.48586 47.66623,21.48386 47.65623,21.45386 47.65423,21.45686 47.65923,21.44786 47.65323))

JTS simplifyDP with tolerance = 0.0036 produces following incorrect output:

POLYGON ((21.328068201892744 47.823286782334385, 21.32786 47.82323, 21.32586 47.82723, 21.328068201892744 47.823286782334385))

The expected output is more like this (produced from QGIS):

POLYGON ((21.44786 47.65323, 21.38886 47.66023, 21.37386 47.65123, 21.36586 47.66323, 21.34886 47.66423, 21.33286 47.65623, 21.30886 47.65923, 21.30186 47.66623, 21.30786 47.66823, 21.30286 47.67523, 21.26786 47.67823, 21.25586 47.69623, 21.23886 47.70023, 21.25186 47.70123, 21.25186 47.70523, 21.24486 47.71023, 21.23286 47.70723, 21.23286 47.71123, 21.25186 47.71523, 21.23886 47.72223, 21.24186 47.72523, 21.23586 47.73023, 21.24286 47.73023, 21.23586 47.73123, 21.23686 47.73523, 21.24986 47.73423, 21.24486 47.73323, 21.24986 47.72423, 21.26586 47.71823, 21.25886 47.72923, 21.26086 47.73723, 21.24986 47.74023, 21.25986 47.74823, 21.25386 47.75123, 21.27786 47.75423, 21.28086 47.76323, 21.26786 47.76123, 21.29286 47.77723, 21.28086 47.78123, 21.26086 47.77623, 21.28986 47.78523, 21.29486 47.78123, 21.29586 47.78623, 21.32086 47.77123, 21.32686 47.78723, 21.31686 47.79023, 21.31186 47.80023, 21.32386 47.79023, 21.34186 47.79223, 21.34886 47.78723, 21.34686 47.78323, 21.35686 47.78223, 21.33886 47.79923, 21.32886 47.80523, 21.32186 47.80223, 21.31486 47.81023, 21.32786 47.81123, 21.33986 47.80223, 21.33886 47.81123, 21.32686 47.82023, 21.32586 47.82723, 21.32786 47.82323, 21.33886 47.82623, 21.34186 47.82123, 21.36386 47.82223, 21.36786 47.81823, 21.36086 47.81423, 21.37386 47.81423, 21.37386 47.81023, 21.38686 47.81423, 21.39486 47.80723, 21.39586 47.81423, 21.40686 47.81723, 21.42286 47.80823, 21.42286 47.81323, 21.43586 47.81623, 21.44486 47.80723, 21.44486 47.81723, 21.44986 47.80523, 21.46386 47.81023, 21.46186 47.80323, 21.47986 47.80723, 21.48186 47.80223, 21.47686 47.80123, 21.49486 47.80123, 21.50486 47.78523, 21.48686 47.78023, 21.49386 47.77023, 21.50686 47.77223, 21.49986 47.76623, 21.49686 47.75123, 21.50486 47.75323, 21.50686 47.74623, 21.50986 47.75223, 21.50886 47.74123, 21.51286 47.74623, 21.51986 47.74223, 21.51386 47.72323, 21.52586 47.71723, 21.52586 47.71123, 21.51386 47.71223, 21.50886 47.70723, 21.50686 47.69223, 21.49686 47.69023, 21.50286 47.68823, 21.50186 47.67323, 21.48586 47.66623, 21.48386 47.65623, 21.45386 47.65423, 21.45686 47.65923, 21.44786 47.65323))
@dr-jts
Copy link
Contributor Author

dr-jts commented Nov 24, 2019 •
edited
Loading

The bug is caused by the fact that DouglasPeuckerSimplifier ensures valid output for areas. It does this by using the buffer(0) trick. That has the unfortunate issue of sometimes choosing the "wrong" lobe of a self-crossing polygon to output. That's what is happening in this case.

The QGIS output appears that it is using TopologyPreservingSimplfier, so it is correct.

@dr-jts
Copy link
Contributor Author

dr-jts commented Nov 24, 2019 •
edited
Loading

Not sure what the fix should be here. It's not easy to fix the buffer code. Ideally JTS should get a MakeValid routine of some form, to eliminate the use of buffer(0)

The problem can be avoided by using DouglasPeuckerSimplifier.setEnsureValid(false), and producing invalid output. Or, by using TopologyPreservingSimplfier. This is the recommended pattern going forward.

In fact, I think that the default behaviour for DouglasPeuckerSimplifier should be changed to not validify output, since this cannot currently be done robustly.

@dr-jts
Copy link
Contributor Author

dr-jts commented Nov 24, 2019 •
edited
Loading

One thing I notice is that the DouglasPeuckerSimplifier code should test validity before applying buffer(0). That should produce a slight performance improvement, and avoid unnecessary side-effects of buffering for valid output.
(It won't resolve this issue, however).

@dr-jts dr-jts mentioned this issue Dec 21, 2020
Merged
@dr-jts
Copy link
Contributor Author

dr-jts commented Dec 23, 2020

Fixed by #655

@dr-jts dr-jts closed this as completed Dec 23, 2020
@dr-jts dr-jts self-assigned this Dec 24, 2020
jagill added a commit to jagill/presto that referenced this issue Dec 24, 2020
@jagill
Upgrade JTS to 1.18.0
03c47f2 
Relevant parts:
* Vastly improved overlay operations (intersection, union, etc).  This
  will allow us to use JTS operations (currently using ESRI).
  + TopologicalExceptions have been mostly eliminated.
  + Performance is improved.  For geometries that intersect in a small
    fraction of their area, performance is greatly improved.
  + More accurate in some cases.
  + https://locationtech.github.io/jts/javadoc/org/locationtech/jts/operation/overlayng/package-summary.html
* Fix for `buffer` and `DouglasPeuckerSimplifier`: in some cases, the
   majority of the polygon would be dropped:
  + locationtech/jts#655
  + locationtech/jts#498
* `WKBWriter` writes empty polygons in a fashion consistent with other
  libraries/tools.

More details: https://github.com/locationtech/jts/releases/tag/jts-1.18.0
@jagill jagill mentioned this issue Dec 24, 2020
Merged
mbasmanova pushed a commit to prestodb/presto that referenced this issue Jan 4, 2021
@jagill @mbasmanova
Upgrade JTS to 1.18.0
6f4e444 
Relevant parts:
* Vastly improved overlay operations (intersection, union, etc).  This
  will allow us to use JTS operations (currently using ESRI).
  + TopologicalExceptions have been mostly eliminated.
  + Performance is improved.  For geometries that intersect in a small
    fraction of their area, performance is greatly improved.
  + More accurate in some cases.
  + https://locationtech.github.io/jts/javadoc/org/locationtech/jts/operation/overlayng/package-summary.html
* Fix for `buffer` and `DouglasPeuckerSimplifier`: in some cases, the
   majority of the polygon would be dropped:
  + locationtech/jts#655
  + locationtech/jts#498
* `WKBWriter` writes empty polygons in a fashion consistent with other
  libraries/tools.

More details: https://github.com/locationtech/jts/releases/tag/jts-1.18.0
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@dr-jts dr-jts

Labels
jts-core type-bug
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
1 participant
@dr-jts