Error computing difference

[michaelkirk]

Hello! I've been testing your library (v1.7.0) against some of the edge cases captured in the JTS test suite and noticed a few failures that seem like errors.

For example:

// pseudo code
let a = POLYGON((60 160, 140 160, 140 60, 60 60, 60 160))
let b = POLYGON(
      (160 160, 100 160, 100 100, 160 100, 160 160), 
      (140 140, 120 140, 120 120, 140 120, 140 140))

a.difference(&b)

Input visualized (a is blue, b is red):

Expected output:

MULTIPOLYGON(((60 160,100 160,100 100,140 100,140 60,60 60,60 160)),((140 140,140 120,120 120,120 140,140 140)))

Actual output is missing the second little square:

MULTIPOLYGON(((60 60,60 160,100 160,100 100,140 100,140 60,60 60)))

I was running these tests in the context of georust/geo. If you'd like to run them yourself, see: https://github.com/georust/geo/compare/mkirk/i-overlay

And run: cargo test -p jts-test-runner

Here's the complete list of failures:

failed TestOverlayAA.xml case "mAmA - complex polygons touching" with error: op: Union, expected "MULTIPOLYGON(((220 140,60 140,60 240,220 240,320 240,320 140,220 140),(200 200,200 180,220 180,220 200,200 200),(240 220,240 180,240 160,260 160,300 160,300 200,300 220,280 220,240 220)),((240 180,280 220,300 200,260 160,240 180)))", actual: "MULTIPOLYGON(((60 140,60 240,320 240,320 140,60 140),(200 200,200 180,220 180,220 200,200 200)))"
failed TestOverlayAA.xml case "mAmA - complex polygons touching" with error: op: Difference, expected "MULTIPOLYGON(((100 180,100 200,120 200,120 180,100 180)),((220 140,60 140,60 240,220 240,220 220,160 220,160 200,200 200,200 180,160 180,160 160,220 160,220 140),(80 220,80 160,140 160,140 220,80 220)),((240 180,280 220,300 200,260 160,240 180)))", actual: "MULTIPOLYGON(((60 140,60 240,220 240,220 220,160 220,160 200,200 200,200 180,160 180,160 160,220 160,220 140,60 140),(80 220,80 160,140 160,140 220,80 220)))"
failed TestOverlayAA.xml case "mAmA - complex polygons touching" with error: op: Xor, expected "MULTIPOLYGON(((220 140,60 140,60 240,220 240,320 240,320 140,220 140),(200 200,200 180,220 180,220 200,200 200),(240 220,240 180,240 160,260 160,300 160,300 200,300 220,280 220,240 220)),((240 180,280 220,300 200,260 160,240 180)))", actual: "MULTIPOLYGON(((60 140,60 240,320 240,320 140,60 140),(80 220,80 160,140 160,140 220,80 220),(200 200,200 180,220 180,220 200,200 200),(280 220,240 180,260 160,300 200,280 220)))"
failed TestOverlayAA.xml case "AA - hole intersecting boundary to produce line" with error: op: Difference, expected "MULTIPOLYGON(((60 160,100 160,100 100,140 100,140 60,60 60,60 160)),((140 140,140 120,120 120,120 140,140 140)))", actual: "MULTIPOLYGON(((60 60,60 160,100 160,100 100,140 100,140 60,60 60)))"
failed TestOverlayAA.xml case "AA - hole intersecting boundary to produce line" with error: op: Xor, expected "MULTIPOLYGON(((60 160,100 160,100 100,140 100,140 60,60 60,60 160)),((140 140,140 160,160 160,160 100,140 100,140 120,120 120,120 140,140 140)))", actual: "MULTIPOLYGON(((60 60,60 160,100 160,100 100,140 100,140 60,60 60)),((140 100,140 160,160 160,160 100,140 100)))"

And the corresponding TestOverlayAA.xml: https://github.com/georust/geo/blob/main/jts-test-runner/resources/testxml/general/TestOverlayAA.xml

[NailxSharipov]

Hi!

I haven't look yet but it looks like wrong winding rule is set. By default solver use NonZero and at your example I see that all paths go in the same clockwise direction. You can try EvenOdd rule or change direction to counterclockwise order for the hole.

I will try your example later

[michaelkirk]

You're absolutely right! I just changed it and now all tests are passing.