8000 Fix DepthSegment compareTo method by dr-jts · Pull Request #920 · locationtech/jts · GitHub
[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to content

Fix DepthSegment compareTo method #920

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
Merged
merged 2 commits into from
Oct 18, 2022
Merged

Fix DepthSegment compareTo method #920

merged 2 commits into from
Oct 18, 2022

Conversation

dr-jts
Copy link
Contributor
@dr-jts dr-jts commented Oct 18, 2022

Fixes DepthSegment.compareTo method to obey contract for comparators.

Signed-off-by: Martin Davis mtnclimb@gmail.com

@dr-jts
Fix DepthSegment comparison method
8e703db 
Signed-off-by: Martin Davis <mtnclimb@gmail.com>
@dr-jts
Javadoc
56db9b6 
Signed-off-by: Martin Davis <mtnclimb@gmail.com>
@dr-jts dr-jts changed the title Fix DepthSegment comparison method Fix DepthSegment compareTo method Oct 18, 2022
@dr-jts dr-jts merged commit 0cabed9 into locationtech:master Oct 18, 2022
@dr-jts dr-jts deleted the fix-depthsegment-comparison branch October 18, 2022 15:56
@jodygarnett jodygarnett added this to the 1.20.0 milestone Aug 22, 2024
@maximusgrey
Copy link

Hello JTS Team,

We just updated from JTS 1.19 to 1.20 and a the zero buffer operation is not always working. I have tracked down the changes and this commit seems to have broken it for our use-case. The compareTo() method now early outs when segments "touch" (upwardSeg.minX() >= other.upwardSeg.maxX()). When replacing these four lines with ">" instead of ">=" as was done in the old compareTo() the buffer operations works fine.

Below a short example test where we buffer a collection and almost half of the collection is lost afterwards.

String wkt = "GEOMETRYCOLLECTION (MULTIPOLYGON (((24 0.217, 24 3, 24 6, 24 9, 24 12, 24 15, 24 18, 24 21, 24 24, 24 25.743, 24.923 30, 30 30, 30 27, 30 24, 30 21, 30 18, 30 15, 30 12, 30 9, 30 6, 30 3, 30 0, 25 0, 24 0.217)), ((21 11.912, 21 9, 21 6, 21 3, 21 0.868, 18.712 1.364, 21 11.912))), MULTIPOLYGON (((24 25.743, 24 27, 24 30, 24.923 30, 24 25.743)), ((3 19.051, 3 21, 3 24, 3 27, 3 30, 21 30, 21 27, 21 24, 21 23.512, 3 19.051))), MULTIPOLYGON (((24 0, 24 0.217, 25 0, 24 0)), ((3 16.491, 3 18, 3 19.051, 21 23.512, 21 21, 21 18, 21 15, 21 12, 21 11.912, 18.712 1.364, 21 0.868, 21 0, 15.874 0, 20.385 20.8, 3 16.491))), MULTIPOLYGON (((3 4.095, 3 6, 3 9, 3 12, 3 15, 3 16.491, 9.544 18.113, 9.544 0, 3.562 0, 4.532 4.475, 3 4.095))), MULTIPOLYGON (((9.544 18.113, 20.385 20.8, 15.874 0, 9.544 0, 9.544 18.113))), MULTIPOLYGON (((3 0, 3 3, 3 4.095, 4.532 4.475, 3.562 0, 3 0))), MULTIPOLYGON (((33 6.528, 33 9, 33 12, 33 15, 33 18, 33 21, 33 24, 33 27, 33 30, 38.091 30, 33 6.528))), MULTIPOLYGON (((38.091 30, 47.184 30, 37.575 27.619, 38.091 30))), MULTIPOLYGON (((54 29.086, 54 30, 57.687 30, 54 29.086)), ((50 30, 51 30, 51 27, 51 24, 51 21, 51 18, 51 15, 51 12, 51 9, 51 6, 51 3, 51 0, 50 0, 50 30))), MULTIPOLYGON (((54 0, 54 3, 54 6, 54 9, 54 12, 54 15, 54 18, 54 21, 54 24, 54 27, 54 28.721, 60 28.721, 60 27, 60 24, 60 21, 60 18, 60 15, 60 12, 60 9, 60 6, 60 3, 60 0, 54 0))), MULTIPOLYGON (((33 0, 33 3, 33 6, 33 6.528, 37.575 27.619, 47.183 30, 50 30, 50 0, 47.515 0, 47.515 27.522, 39.675 25.58, 34.127 0, 33 0))), MULTIPOLYGON (((34.127 0, 39.675 25.58, 45.641 27.058, 45.641 0, 34.127 0))), MULTIPOLYGON (((45.641 27.058, 47.515 27.522, 47.515 0, 45.641 0, 45.641 27.058))), MULTIPOLYGON (((63 0, 63 3, 63 6, 63 9, 63 12, 63 15, 63 18, 63 21, 63 24, 63 27, 63 28.721, 64.46 28.721, 64.46 19.383, 64.46 0, 63 0))), MULTIPOLYGON (((90 28.721, 90 27, 90 25.711, 88.329 25.297, 88.329 28.721, 90 28.721))), MULTIPOLYGON (((84 0, 84 3, 84 6, 84 9, 84 12, 84 15, 84 18, 84 21, 84 24, 84 24.224, 88.329 25.297, 90 25.711, 90 24, 90 21, 90 18, 90 15, 90 12, 90 9, 90 6, 90 3, 90 0, 84 0)), ((81 23.481, 81 21, 81 18, 81 15, 81 12, 81 9, 81 6, 81 3, 81 0, 64.46 0, 64.46 19.383, 76.395 22.34, 81 23.481))), MULTIPOLYGON (((84 24.224, 84 27, 84 28.721, 88.329 28.721, 88.329 25.297, 84 24.224)), ((81 28.721, 81 27, 81 24, 81 23.481, 76.395 22.34, 76.395 28.721, 81 28.721))), MULTIPOLYGON (((64.46 19.383, 64.46 28.721, 76.395 28.721, 76.395 22.34, 64.46 19.383))), MULTIPOLYGON (((93 26.455, 93 27, 93 28.721, 99 28.721, 99 27.942, 93 26.455))), MULTIPOLYGON (((93 0, 93 3, 93 6, 93 9, 93 12, 93 15, 93 18, 93 21, 93 24, 93 26.455, 99 27.942, 99 27, 99 24, 99 21, 99 18, 99 15, 99 12, 99 9, 99 6, 99 3, 99 0, 93 0))), MULTIPOLYGON (((30 53.404, 30 51, 30 48, 30 45, 30 42, 30 39, 30 36, 30 33, 30 30, 24.923 30, 30 53.404))), MULTIPOLYGON (((24 50, 24 51, 24 52.634, 27.138 52.634, 28.736 60, 30 60, 30 57, 30 54, 30 53.402, 29.262 50, 24 50)), ((3 50, 3 51, 3 52.634, 21 52.634, 21 51, 21 50, 3 50))), MULTIPOLYGON (((3 52.634, 3 54, 3 57, 3 60, 11.858 60, 11.858 52.634, 3 52.634))), MULTIPOLYGON (((11.858 60, 21 60, 21 57, 21 54, 21 52.634, 11.858 52.634, 11.858 60))), MULTIPOLYGON (((24 52.634, 24 54, 24 57, 24 60, 28.736 60, 27.138 52.634, 24 52.634))), MULTIPOLYGON EMPTY, MULTIPOLYGON (((24 30, 24 33, 24 36, 24 37.639, 26.727 38.315, 24.923 30, 24 30)), ((3 30, 3 32.435, 21 36.896, 21 36, 21 33, 21 30, 3 30))), MULTIPOLYGON (((24 37.639, 24 39, 24 40.199, 24.627 40.354, 26.18 47.515, 24 47.515, 24 48, 24 50, 29.262 50, 26.727 38.315, 24 37.639)), ((3 32.435, 3 33, 3 34.995, 21 39.455, 21 39, 21 36.896, 3 32.435)), ((3 47.515, 3 48, 3 50, 21 50, 21 48, 21 47.515, 3 47.515))), MULTIPOLYGON (((21 47.515, 21 45, 21 42, 21 39.455, 3 34.995, 9.544 36.617, 9.544 47.515, 21 47.515))), MULTIPOLYGON (((3 34.995, 3 36, 3 39, 3 42, 3 45, 3 47.515, 9.544 47.515, 9.544 36.617, 3 34.995))), MULTIPOLYGON (((24 40.199, 24 42, 24 45, 24 47.515, 26.18 47.515, 24.627 40.354, 24 40.199))), MULTIPOLYGON (((33 30, 33 33, 33 36, 33 39, 33 42, 33 45, 33 48, 33 51, 33 54, 33 57, 33 60, 44.599 60, 38.091 30, 33 30))), MULTIPOLYGON (((54 31.689, 54 33, 54 36, 54 39, 54 42, 54 45, 54 45.073, 60 46.56, 60 45, 60 42, 60 39, 60 36, 60 33.176, 54 31.689)), ((51 44.33, 51 42, 51 39, 51 36, 51 33, 51 30.946, 47.184 30, 38.091 30, 40.643 41.763, 51 44.33))), MULTIPOLYGON (((54 30, 54 31.689, 60 33.176, 60 33, 60 30.573, 57.687 30, 54 30)), ((51 30.946, 51 30, 50 30, 50 30.698, 51 30.946))), MULTIPOLYGON (((54 45.073, 54 48, 54 50, 60 50, 60 48, 60 46.56, 54 45.073)), ((51 50, 51 48, 51 45, 51 44.33, 50 44.082, 50 50, 51 50))), MULTIPOLYGON (((44.598 60, 47.148 60, 45.519 52.491, 47.509 52.491, 47.509 60, 50 60, 50 50, 42.429 50, 44.598 60))), MULTIPOLYGON (((54 50, 54 51, 54 52.676, 60 52.676, 60 51, 60 50, 54 50)), ((50 60, 51 60, 51 57, 51 54, 51 51, 51 50, 50 50, 50 60))), MULTIPOLYGON (((54 52.676, 54 54, 54 57, 54 60, 60 60, 60 57, 60 54, 60 52.676, 54 52.676))), MULTIPOLYGON (((50 30, 47.183 30, 50 30.698, 50 30)), ((42.429 50, 50 50, 50 44.082, 40.643 41.763, 41.289 44.743, 42.429 50), (47.515 46.026, 47.515 47.515, 44.433 47.515, 43.917 45.134, 47.515 46.026))), MULTIPOLYGON (((43.917 45.134, 44.433 47.515, 47.515 46.847, 47.515 46.026, 43.917 45.134))), MULTIPOLYGON (((47.148 60, 47.509 60, 47.509 52.491, 45.519 52.491, 47.148 60))), MULTIPOLYGON (((84 39.123, 84 42, 84 45, 84 48, 84 51, 84 52.507, 90 53.994, 90 51, 90 48, 90 45, 90 42, 90 40.61, 84 39.123)), ((63 33.919, 63 36, 63 39, 63 42, 63 45, 63 47.303, 81 51.764, 81 51, 81 48, 81 45, 81 42, 81 39, 81 38.38, 63 33.919))), MULTIPOLYGON (((84 36.52, 84 39, 84 39.123, 90 40.61, 90 39, 90 38.007, 84 36.52)), ((63 31.316, 63 33, 63 33.919, 81 38.38, 81 36, 81 35.777, 63 31.316))), MULTIPOLYGON (((63 47.303, 63 48, 63 50, 73.883 50, 67.373 48.387, 63 47.303))), MULTIPOLYGON (((84 52.507, 84 54, 84 55.264, 90 56.751, 90 54, 90 53.994, 84 52.507)), ((63 50, 63 51, 63 52.676, 73.556 52.676, 81 54.521, 81 54, 81 51.764, 73.883 50, 63 50))), MULTIPOLYGON (((63 52.676, 63 54, 63 57, 63 60, 64.599 60, 64.599 52.676, 63 52.676))), MULTIPOLYGON (((64.599 60, 76.522 60, 76.522 53.411, 73.556 52.676, 64.599 52.676, 64.599 60))), MULTIPOLYGON (((84 55.264, 84 57, 84 60, 88.446 60, 88.446 56.366, 84 55.264)), ((76.522 60, 81 60, 81 57, 81 54.521, 76.522 53.411, 76.522 60))), MULTIPOLYGON (((88.446 60, 90 60, 90 57, 90 56.751, 88.446 56.366, 88.446 60))), MULTIPOLYGON (((93 41.353, 93 42, 93 45, 93 48, 93 51, 93 54, 93 54.737, 98.438 56.085, 99 53.816, 99 51, 99 48, 99 45, 99 42.84, 93 41.353))), MULTIPOLYGON (((93 38.75, 93 39, 93 41.353, 99 42.84, 99 42, 99 40.237, 93 38.75))), MULTIPOLYGON (((93 54.737, 93 57, 93 57.494, 99 58.981, 99 57, 99 54, 99 53.816, 98.438 56.085, 93 54.737))), MULTIPOLYGON (((93 57.494, 93 60, 99 60, 99 58.981, 93 57.494))), MULTIPOLYGON (((30 65.829, 30 63, 30 60, 28.736 60, 30 65.829))), MULTIPOLYGON (((3 60, 3 63, 3 64.732, 11.858 64.732, 11.858 60, 3 60))), MULTIPOLYGON (((21 81.408, 21 81, 21 78, 21 75, 21 72, 21 69, 21 66, 21 63, 21 60, 11.858 60, 11.858 64.732, 17.383 64.732, 21 81.408))), MULTIPOLYGON (((24 60, 24 63, 24 66, 24 69, 24 72, 24 75, 24 78, 24 81, 24 84, 24 87, 24 90, 30 90, 30 87, 30 84, 30 81, 30 78, 30 75, 30 72, 30 69, 30 66, 30 65.829, 28.736 60, 24 60))), MULTIPOLYGON EMPTY, MULTIPOLYGON (((3 64.732, 3 66, 3 69, 3 72, 3 75, 3 78, 3 81, 3 84, 3 87, 3 90, 21 90, 21 87, 21 84, 21 81.408, 17.383 64.732, 11.858 64.732, 3 64.732))), MULTIPOLYGON (((33 60, 33 63, 33 66, 33 67.235, 37.938 90, 51 90, 51 89.512, 44.599 60, 33 60))), MULTIPOLYGON (((33 67.234, 33 69, 33 72, 33 75, 33 78, 33 79.659, 35.243 90, 37.938 90, 33 67.234))), MULTIPOLYGON (((33 79.661, 33 81, 33 84, 33 87, 33 90, 35.243 90, 33 79.661))), MULTIPOLYGON (((33 79.659, 33 79.661, 35.243 90, 33 79.659))), MULTIPOLYGON (((50 60, 47.509 60, 47.509 61.666, 47.148 60, 44.598 60, 49.614 83.124, 50 84.902, 50 60))), MULTIPOLYGON (((51 89.512, 51 87, 51 84, 51 81, 51 78, 51 75, 51 72, 51 69, 51 66, 51 63, 51 60, 50 60, 50 84.902, 51 89.512))), MULTIPOLYGON (((54 60, 54 63, 54 66, 54 69, 54 72, 54 75, 54 78, 54 81, 54 84, 54 84.615, 60 84.615, 60 84, 60 81, 60 78, 60 75, 60 72, 60 69, 60 66, 60 63, 60 60, 54 60))), MULTIPOLYGON (((47.509 60, 47.148 60, 47.509 61.666, 47.509 60))), MULTIPOLYGON (((63 60, 63 63, 63 66, 63 69, 63 72, 63 75, 63 78, 63 81, 63 84, 63 84.615, 64.599 84.615, 64.599 83.337, 64.599 64.599, 64.599 60, 63 60))), MULTIPOLYGON (((76.522 60, 64.599 60, 64.599 64.599, 72.101 64.599, 76.522 65.695, 76.522 60))), MULTIPOLYGON (((84 60, 84 63, 84 66, 84 67.548, 88.446 68.65, 88.446 60, 84 60)), ((81 66.805, 81 66, 81 63, 81 60, 76.522 60, 76.522 65.695, 81 66.805))), MULTIPOLYGON (((90 69.035, 90 69, 90 66, 90 63, 90 60, 88.446 60, 88.446 68.65, 90 69.035))), MULTIPOLYGON (((84 67.548, 84 69, 84 72, 84 75, 84 78, 84 81, 84 84, 84 87, 84 90, 90 90, 90 87, 90 84, 90 81, 90 78, 90 75, 90 72, 90 69.035, 88.446 68.65, 84 67.548)), ((66.044 90, 81 90, 81 87, 81 84, 81 81, 81 78, 81 75, 81 72, 81 69, 81 66.805, 76.522 65.695, 72.101 64.599, 64.599 64.599, 64.599 83.337, 66.044 90))), MULTIPOLYGON (((64.599 83.337, 64.599 84.615, 64.876 84.615, 64.599 83.337))), MULTIPOLYGON (((93 60, 93 63, 93 66, 93 69, 93 69.778, 99 71.265, 99 69, 99 66, 99 63, 99 60, 93 60))), MULTIPOLYGON (((93 69.778, 93 72, 93 75, 93 78, 93 81, 93 84, 93 87, 93 90, 99 90, 99 87, 99 84, 99 81, 99 78, 99 75, 99 72, 99 71.265, 93 69.778))), MULTIPOLYGON (((24 90, 24 93, 24 95.239, 24.816 99, 30 99, 30 96, 30 93, 30 90, 24 90))), MULTIPOLYGON (((24 95.239, 24 96, 24 99, 24.816 99, 24 95.239)), ((3 90, 3 93, 3 96, 3 99, 21 99, 21 96, 21 93, 21 90, 3 90))), MULTIPOLYGON (((39.89 99, 51 99, 51 96, 51 93, 51 90, 37.938 90, 39.89 99))), MULTIPOLYGON (((37.195 99, 39.89 99, 37.938 90, 35.243 90, 37.195 99))), MULTIPOLYGON (((33 90, 33 93, 33 96, 33 99, 36.054 99, 36.054 93.741, 35.243 90, 33 90))), MULTIPOLYGON (((36.054 99, 37.195 99, 35.243 90, 36.054 93.741, 36.054 99))), MULTIPOLYGON (((54 90.719, 54 93, 54 96, 54 99, 55.796 99, 54 90.719))), MULTIPOLYGON (((84 90, 84 93, 84 96, 84 99, 90 99, 90 96, 90 93, 90 90, 84 90)), ((67.996 99, 81 99, 81 96, 81 93, 81 90, 66.044 90, 67.996 99))), MULTIPOLYGON (((93 90, 93 93, 93 96, 93 99, 99 99, 99 96, 99 93, 99 90, 93 90))))";

WKTReader reader = new WKTReader();
GeometryCollection collection = (GeometryCollection) reader.read(wkt);
assertEquals(collection.getArea(), BufferOp.bufferByZero(collection, true).getArea(), 1);

Red part of the collection is lost after the buffer operation.

difference

@dr-jts
Copy link
Contributor Author
dr-jts commented May 13, 2025

Below a short example test where we buffer a collection and almost half of the collection is lost afterwards.

Weird. The behaviour of losing elements produces different results for different subsets of the input. This may be difficult to track down.

@maximusgrey
Copy link

I understand that it is difficult to track down, we have been using JTS for many years and this was not something we where able to find by our-self. The only thing that seems to fix it for our use-case is replacing:

if (upwardSeg.minX() >= other.upwardSeg.maxX()
|| upwardSeg.maxX() <= other.upwardSeg.minX()
|| upwardSeg.minY() >= other.upwardSeg.maxY()
|| upwardSeg.maxY() <= other.upwardSeg.minY()) {
return upwardSeg.compareTo(other.upwardSeg);
};

with:
if (upwardSeg.minX() > other.upwardSeg.maxX()
|| upwardSeg.maxX() < other.upwardSeg.minX()
|| upwardSeg.minY() > other.upwardSeg.maxY()
|| upwardSeg.maxY() < other.upwardSeg.minY()) {
return upwardSeg.compareTo(other.upwardSeg);
};

But that breaks the comparison contract?

@dr-jts dr-jts mentioned this pull request May 21, 2025
Closed
@dr-jts
Copy link
Contributor Author
dr-jts commented May 21, 2025

@maximusgrey I created a separate issue for your problem: #1131

@dr-jts dr-jts mentioned this pull request May 26, 2025
Merged
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers
No reviews
Assignees
No one assigned
Labels
jts-core type-bug
Projects
None yet
Milestone
1.20.0
Development

Successfully merging this pull request may close these issues.
3 participants
@dr-jts @maximusgrey @jodygarnett
0