Clarify robustness / edge cases handling about simplepolygon HOT 2 CLOSED

Hi @mourner! I'm glad you're interested in this library.

I don't know if your question is on the Subramaniam algorithm or my implementation. Just for clarity: I'm not affiliated with the author of the paper, but I came across the article when I wanted to solve the elliptical buffers made by Turf and made an implementation. I wrote my implementation based on the article text, in stead of porting the provided C/C++ code over to JS.

Indeed, the article is not specific on degenerate cases such as multiple intersections at the same point and paralel lines (as it literally mentions).

Regarding the known limitations of my implementation: I talk a bit about this in the README under 'Some notes on the algorithm': currently the algorithm rejects input polygons with non-unique vertices, because in many of those cases it fails. I gave one example there, too. Generally, it found that it fails on most input polygons that are non-simple for another reason than self-intersection (with the exception of spikes).

For my immediate case of geodesic buffers, this was only a minor problem since the input polygons are rings created by buffering objects, which are quite smooth and, given the geodesic nature, don't tend to give rise to coinciding points or parallel lines. Hence, I could afford to leave this issue open. But for a rigorous implementation it's absolutely key to be able to deal with degeneracies.

Whilst writing the current code, I started thinking about about degenerate cases. I came to the conclusion that turning the algorithm on its head would result in a more elegant algorithm that could also handle all of these cases (as far as my mind could imagine them): in stead of walking from intersection to intersection, you could design an algorithm to walk from pseudo-vector to pseudo-vector. An intersection could then be linked to an (ordered) list of pseudo-vectors, in stead of the current 2 pseudo-vectors per intersection. This would allow to deal with multiple edges crossing at the same point, etc.
Since this would be a large rewrite and probably not result in a speedup, I didn't do it at the time.

Note that we're getting pretty close to the concept of a topology: ideally you want to be granted a topology as input in stead of a geometry, and use that to walk over. It will guarantee you to treat degenerate polygons correctly. I though about using e.g. topojson to preprocess the input, but it doesn't accept inputs with self-intersections.

Greetings!

from simplepolygon.

@mclaeysb thank you for the detailed response! To give you some context on this question — I'm currently working on a library for repairing polygons that will be 100% robust on ALL cases, including any kinds of degeneracies, and also handling finite precision (e.g. given an integer coords input, rounding intersection points to integers in a way that doesn't introduce new intersections).

I'm halfway there — currently the library can properly find and snap all intersections, and then produce a graph where each intersection point (or a junction) has a sorted circular linked list of its incoming/outcoming edges. The biggest remaining part is figuring out how to traverse this graph correctly, but handling collinear edges is very tricky. Hopefully I'll figure out how to do that. You're welcome to poke at the repo — I'll be glad to hear any feedback!

from simplepolygon.