Error creating unnecessary hole on union

[rowanwins]

Hi @mfogel

So I've encountered a new issue when union-ing a single polygon.

The polygon crosses over itself and should result in a single hole.

However it is resulting in two holes, the second of which is not required.

Grrr don't you hate edge cases :)

[mfogel]

Hi @rowanwins thanks for bug report

Are you thinking it would better for the output polygon to have one bow-tie shaped hole, instead of two holes that touch at one point? Right now the logic that forms the output favors making two rings instead of one ring that self-intersects. Is that what you're referring to or am I on the wrong track?

[rowanwins]

This is what I would've expected to get back, hope that helps clarify.

[rowanwins]

As some bonus context, I've been writing a buffer module, under the hood I'm using polygon-clipping to check for overlaps at the end. You can see the sort of error that I'm getting with the line feature that gets buffered.

[mfogel]

Ah, gotcha, I see what you mean. Yeah I can see how the current behavior isn't right for that situation.

I'm trying to think of a counter example of where the current behavior would be the desired behavior... so far no success.

[rowanwins]

Yeah I suspect the proposed is more common, I can't think of a case where you'd want to retain those holes.

As an aside one thing I've done elsewhere is setup tests which run against more established spatial libs, in particular shapely, which is a python lib. This was helpful for testing the outputs we were generating compared to a more established lib. If that's of any interest let me know.

[mfogel]

I think this is a case of where the non-zero rule and the even-odd rule differ. Basically, I think to count this area as inside the polygon, this lib should swtich from using the even-odd rule to the non-zero rule. Which sounds ok to me, I would agree that I think most if not all users of the lib would expect that area to be filled in your example.

I'd consider this to be a backwards-incompatible change since it is changing behavior that is documented in the README.

[mfogel]

A few tentative implementation plan notes:

• track winding direction of each segment as it appeared in input rings. Replace the array Segment.ringsIn with something like {<ring id:Int>: <is clockwise:Boolean>}
• adjust segment consuming and splitting to work with that changed Segment.ringsIn data structure
• expand the data structure returned by Segment.ringsAfter() from a simple array of rings to a dictionary of {<ring id:Int>: <clockwise count:Int>} where <clockwise count> starts at 0 and grows for clockwise segments and shrinks for counterclockwise segments. A value other than 0 indicates the given segment is inside that ring.
• adjust Segment.multiPolysAfter() to consume the above changed data structure from Segment.ringsAfter(). Shouldn't need to change the result format of Segment.multiPolysAfter()

[mfogel]

The SVG standard defaults to non-zero rule for filling polygons as well, this lib should probably mirror that behavior as this ticket suggests

[mfogel]

work progressing on this branch: https://github.com/mfogel/polygon-clipping/tree/feature/non-zero-rule