Incorrect union on small example

[agersant]

Hi and thanks for maintaining this very useful library.

I ran into some incorrect results while computing the union of a large number of polygons, and I think I managed to isolate a simple example out of my larger data set.

This is the two polygons (blue and green) being merged. Note the shared horizontal edge in the middle.

Here is the resulting union:

Repro code:

#[macro_use]
extern crate geo_types;

use geo_booleanop::boolean::BooleanOp;

fn main() {
    let big = polygon![
        (x: 416., y: 256.),
        (x: 432., y: 240.),
        (x: 432., y: 224.),
        (x: 448., y: 280.),
        (x: 480., y: 208.),
        (x: 480., y: 256.),
    ];

    let small = polygon![
        (x: 400., y: 272.),
        (x: 416., y: 256.),
        (x: 480., y: 256.),
        (x: 480., y: 272.),
    ];

    let union = small.union(&big);
    for p in union.into_iter() {
        dbg!(p);
    }
}

/*
Output:

[src\main.rs:27] p = Polygon {
    exterior: LineString(
        [
            Coordinate {
                x: 400.0,
                y: 272.0,
            },
            Coordinate {
                x: 416.0,
                y: 256.0,
            },
            Coordinate {
                x: 432.0,
                y: 240.0,
            },
            Coordinate {
                x: 432.0,
                y: 224.0,
            },
            Coordinate {
                x: 441.14285714285717,
                y: 256.0,
            },
            Coordinate {
                x: 458.66666666666663,
                y: 256.0,
            },
            Coordinate {
                x: 480.0,
                y: 208.0,
            },
            Coordinate {
                x: 480.0,
                y: 256.0,
            },
            Coordinate {
                x: 480.0,
                y: 272.0,
            },
            Coordinate {
                x: 451.55555555555554,
                y: 272.0,
            },
            Coordinate {
                x: 448.0,
                y: 280.0,
            },
            Coordinate {
                x: 445.7142857142857,
                y: 272.0,
            },
            Coordinate {
                x: 400.0,
                y: 272.0,
            },
        ],
    ),
    interiors: [],
}
*/

[bluenote10]

Hi @agersant , I'm currently working on making the algorithm more robust, so further test cases are more than welcome.

I was running this example through the test case plotting:

So it looks like there is already a coordinate hiccup in the input. Comparing to the numbers in the screenshot I noticed that there is one y value of 280 which probably should be 208. Changing it gives:

If you have trouble isolating your error, feel free to post the coordinates of the full problem, preferably just as list of coordinates or GeoJSON.

I'm currently working on further fixes e.g. for w8r/martinez#110 and w8r/martinez#114, maybe that also helps in your case.

Test case GeoJSON

{
  "features": [
    {
      "geometry": {
        "coordinates": [
          [
            [416, 256],
            [432, 240],
            [432, 224],
            [448, 208],
            [480, 208],
            [480, 256],
            [416, 256]
          ]
        ],
        "type": "Polygon"
      },
      "properties": {},
      "type": "Feature"
    },
    {
      "geometry": {
        "coordinates": [
          [
            [400, 272],
            [416, 256],
            [480, 256],
            [480, 272],
            [400, 272]
          ]
        ],
        "type": "Polygon"
      },
      "properties": {},
      "type": "Feature"
    },
    {
      "geometry": {
        "coordinates": [
          [
            [
              [400, 272],
              [416, 256],
              [432, 240],
              [432, 224],
              [448, 208],
              [480, 208],
              [480, 256],
              [480, 272],
              [400, 272]
            ]
          ]
        ],
        "type": "MultiPolygon"
      },
      "properties": {
        "operation": "union"
      },
      "type": "Feature"
    }
  ],
  "type": "FeatureCollection"
}

[agersant]

Sorry about that, I'm a potato and I shouldn't write bug reports late at night.

It is difficult to post my entire dataset as the issue arise within a iterative process which merges and simplifies a large number of polygons into gradually bigger chunks. I did take a closer look and I am confident that the union() I see are correct - I believe simplify() is where problems are. I will open an issue over there (after carefully proof reading it).

[agersant]

Sorry for all the flip flopping on this. I think I finally cornered it.

Here is a zip file with two serialized MultiPolygons (A.json and B.json). A is a fairly complex and one of its polygons is the blue polygon from my original example. B is the green polygon from the original example.

The zip file also contains union.json which is the union of A and B. Notice that (400, 272) which was the bottom-left corner of B is missing in the union.

polys.zip

Some pictures:

A:

B:

Union:

(there is also a strange doodad near the top-right corner which appears earlier in the calculations of these shapes but that's a problem for another day)

[bluenote10]

No problem at all, and thanks again for investigating. I can reproduce the issue now:

Also, the problem seems to be independent of the issues I'm currently fixing, so it is quite a valuable test case. I'll probably do some deeper debugging on the weekend.

(there is also a strange doodad near the top-right corner which appears earlier in the calculations of these shapes but that's a problem for another day)

Actually this kind of self-overlap might be the cause of the issue. Note that the x-coordinate of the self-overlap goes from 400 to 416. The start x of the segment that disappears is 400. Setting it to <400 or >=416 avoids the problem. As a temporary work-around you could try adding a polygon simplification to the intermediate results in your incremental logic.

[agersant]

I think you are correct. I do run a simplification step on the intermediate results for performance benefits, and I only run into all these issues when using simplify as opposed to simplifyvw. With simplifyvw, the weird 400 -> 416 segment gets removed and the 400, 272 vertex isn't lost during subsequent unions.

I also isolated the union operation which creates the overlapping edge in the first place (in earlier iterations), this might be a useful test case too. Here is another zip file with A.json (a rectangle), B.json (an adjacent triangle) and union.json (the resulting union).
doodad.zip

Picture of the resulting union w/ self-overlapping edge:

[bluenote10]

Okay this is "almost" fixed by #13: The original test case works now, and also the doodad case (I had almost the same on my branch already ;)).

The thing that doesn't work is to swap the roles of the subject and clipping polygon in your main example. Will have to look into that in the next bug fixing round.

[agersant]

Fantastic news, thank you so much!!