Allow self-crossing rings

[mfogel]

Self-crossing rings are ambiguous because they could be interpreted using either the non-zero rule or the even-odd rule. As such, the algorithm throws an exception, by design, when given a self-crossing ring. This behavior is covered by the test suite.

Right now, checking for the self-crossing rings is done by a separate loop over the output segments before the algorithm attempts to glue them together into output shapes.

It may be possible to eliminate this loop by doing this check right when a segment is split by another segment, and at that point if the two segments are from the same ring, and they do cross (not just touch) then throw the error there.

[rowanwins]

Hi @mfogel

I was under the impression that the martinez algorithm was able to process polygons with self-intersections. Or is this about where holes cross the external boundary of the polygon?

Tied with all of this is and perhaps more overarching concern is how to cater for degenerate inputs... you could make the algorithm attempt to handle them by running a zillion checks, the downside being that it slows down performance for everyone. Or you could assume people pass in decent inputs and things run a bit quickly because minimal checks are done. Perhaps a middle of the road option is to provide some sort of clean function which people can use if their first pass throws an error...

[mfogel]

good point @rowanwins - specifically "attempt to handle them (degenerate inputs) by running a zillion checks, the downside being that it slows down performance for everyone". It's definitely possible to go to far to the side of trying to protect developers from themselves. In this particular case, this is probably currently a step too far in protecting developers from themselves - as there's a whole O(n) loop there just to make sure a nice error is thrown in this case.

The wikipedia page for non-zero rule has a nice image that shows how some self-crossing rings enclose different area depending on whether you interpret the ring using the non-zero rule or the even-odd rule. And if it's not clear what area the input rings enclose, then when forming the output rings at the end of the algorithm, it's not clear what area should be enclosed.

Another option would be to just choose either the even-odd rule or the non-zero rule, put that choice in the documentation and be done with it. That's probably the right answer if this error check can't be reduced from O(n) to O(1).

[mfogel]

I can't see any way to perform this check in anything less than O(n). As such, I'm changing to this issue to permit self-crossing rings, and just going to document in the README how they'll be interpreted.