Fix buffer to use largest enclosed area for invalid rings #655
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Signed-off-by: Martin Davis <mtnclimb@gmail.com>
Signed-off-by: Martin Davis <mtnclimb@gmail.com>
This was referenced Dec 23, 2020
jagill
added a commit
to jagill/presto
that referenced
this pull request
Dec 24, 2020
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
pramsey
added a commit
to pramsey/geos
that referenced
this pull request
Dec 30, 2020
…r invalid rings
strk
pushed a commit
to libgeos/geos
that referenced
this pull request
Dec 30, 2020
…r invalid rings Closes #732
strk
pushed a commit
to libgeos/geos
that referenced
this pull request
Dec 30, 2020
…a for invalid rings
mbasmanova
pushed a commit
to prestodb/presto
that referenced
this pull request
Jan 4, 2021
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
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
The buffer algorithm has a long-standing issue where a polygon with a small self-intersecting lobe at the top of the polygon gets reduced to just the small lobe, rather than the small lobe being removed. See for example #629. This issue can also occur in hole rings.
This issue also affects JTS algorithms which use the
buffer(0)trick to produce valid polygons (such asDouglasPeuckerSimplifier,VWSimplifierandDensifier). For example, #498.The issue occurs because
bufferhas to determine the interior of a ring to know which side to build the buffer offset curve on (which in the case of a zero-width buffer is just the ring linework). Currently buffer uses theOrientation.isCCWtest to do this. For efficiency this algorithm determines ring orientation by checking only the line segments incident on the uppermost vertex of the ring. For a valid ring (where the linework does not cross itself) this works fine. However, in a self-crossing ring (aka a "bow-tie") which lobe is chosen as the interior is not well-defined. The uppermost vertex approach can end up choosing a very small lobe to be the "interior" of the polygon.The fix is to use an orientation test which takes into account the entire ring. This is provided by the Signed-Area Orientation test. This effectively determines the orientation based on the largest area enclosed by the ring. This corresponds much more closely to user expectation based on visual assessment. It also minimizes the change in area and (usually) extent.
