search

w8r / martinez

Martinez-Rueda polygon clipping algorithm, does boolean operation on polygons (multipolygons, polygons with holes etc): intersection, union, difference, xor
https://w8r.github.io/martinez/demo/#geo
MIT License
695 stars 77 forks source link

intersection of polygon with hole results in the hole flipping orientation and causing self-intersection #128

Open mglasgow opened 4 years ago

mglasgow commented 4 years ago

I have found another edge case while dividing up OpenStreetMap country boundaries into QuadTiles.

I have attached the geojson in the "genericTestCase" format that @bluenote10 put together.

I am intersecting a polygon of Spain's border, which has an enclave cut out for Gibraltar, with a square tile. The Gibraltar hole is completely contained within the square tile, so should be a straight forward intersection.

This is what I expect:

expected result

This is what I get. Note the internal hole is coloured red, as it is now a part of the multipolygon

actual result

Here are is the generic test case geojson:

issue128.geojson.txt

And here is the actual geojson result I get from the intersection:

actual-output.geojson.txt

Perhaps the winding order of the interior ring is reversing?

I am using the master branch of this repo, and I have also applied the #125 pull request too.

@bluenote10 If you get a chance, would you mind running this through your Rust implementation to see how it handles it?

bluenote10 commented 4 years ago

Indeed, this shows up on Rust side as well:

image

Need to have a closer look -- looks indeed like a straightforward case.

mglasgow commented 4 years ago

Thanks for confirming this is a bug. I have a workaround I am using at the moment. For polygons which have interior holes, I am now running intersect manually on each of the rings of the polygon. I then combine the results by using Diff to subtract the interior rings from the outer ring. This is working well, except for an issue where Diff doesn't seem to set the orientation of holes properly. I have raised a separate issue for this (#129) and am manually correcting the orientation for interior rings.