Self intersecting polygon -- some sub regions not getting detected

[dan-reznik]

Dear Manuel, I am really excited about integrating simplepolygon into a locus-drawing js browser app I've been developing over the past few months. It draws loci of centers of families of triangles "mounted" on ellipses.

Browserifying simplepolygon worked like a charm.

However I am having a few issues with the results returned by simplepolygon. Consider first of all one 800-long sample polygon (it's actually a curve approximation), you can see it live here: https://bit.ly/2Zg7Mv1

As you can see, the above curve has 6 self intersections and 7 simple subregions. The coloring scheme below reveals the independent subregions returned by simplepolygon. unfortunately, only 3 are returned. Any idea why?

For your own testing I am attaching a zipped json w the 800 vertices:

vtx-X14.zip

[mclaeysb]

Hi there. Interesting question.

I'll try to take a look at this in the coming days!

[dan-reznik]

not sure if you had a chance to look at this bug yet, but we would truly appreciate if you could fix it. here is a simpler polygon, shaped as the infinity symbol, clearly with two separate simply-connected regions, where the algo returns a single region . a json with the vertices is attached. locus_json_13092020_103525.zip

[mclaeysb]

Thanks! Will look at this on friday!

[dan-reznik]

looking fwd to it. it is being used heavily on our app https://dan-reznik.github.io/ellipse-mounted-loci-p5js/

[mclaeysb]

Hi Dan

Super cool and crazy app you're building there!

I've tested simplepolygon on the last example you've posted. After including the vertex list in a geojson feature and running the algorithm, I got the error message

Error: The input polygon may not have duplicate vertices (except for the first and last vertex of each ring)

Indeed, [0, 0] is included twice in the input polygon.

If I tweak the input polygon a bit and remove both [0, 0] points, it runs, but returns only one connected shape (which is obviously wrong).

I don't remember if this uniqueness limitation comes from the original paper or not (it doesn't seem to be accessible anymore). In any case, I don't have the time or resources now to go and fix this problem - we're diving in some high-end math here, and this was a spare-time project from a couple of years ago.

It looks like you app has a lot of very symmetrical structures, so this problem will indeed often occur. So all I can do for now is to redirect you to some more robust geometric libraries such as JSTS which are better at handling degeneracies like this. I don't think this library has an equivalent algorithm, but it might have some other helpful tools that might help you to move on.

All the best with the app! Manuel

[dan-reznik]

Manuel, I perfectly understand and am really grateful for having looked at this from many angles! I will keep plowing along and check out JSTS. In a way the fact the algo is not always correct adds to the artistry. Here's a pic I created yesterday with your code

[image: image.png]

Dan

On Sat, Sep 26, 2020 at 2:14 PM Manuel Claeys Bouuaert < notifications@github.com> wrote:

Hi Dan

Super cool and crazy app you're building there!

I've tested simplepolygon on the last example you've posted. After including the vertex list in a geojson feature and running the algorithm, I got the error message

Error: The input polygon may not have duplicate vertices (except for the first and last vertex of each ring)

Indeed, [0, 0] is included twice in the input polygon.

If I tweak the input polygon a bit and remove both [0, 0] points, it runs, but returns only one connected shape (which is obviously wrong).

[image: Screen Shot 2020-09-26 at 19 09 28] https://user-images.githubusercontent.com/2920134/94346287-d873e600-002b-11eb-99fb-eec1739bc92a.png

I don't remember if this uniqueness limitation comes from the original paper or not (it doesn't seem to be accessible anymore). In any case, I don't have the time or resources now to go and fix this problem - we're diving in some high-end math here, and this was a spare-time project from a couple of years ago.

It looks like you app has a lot of very symmetrical structures, so this problem will indeed often occur. So all I can do for now is to redirect you to some more robust geometric libraries such as JSTS https://github.com/bjornharrtell/jsts which are better at handling degeneracies like this. I don't think this library has an equivalent algorithm, but it might have some other helpful tools that might help you to move on.

All the best with the app! Manuel

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/mclaeysb/simplepolygon/issues/17#issuecomment-699522707, or unsubscribe https://github.com/notifications/unsubscribe-auth/AD32VFRAAUUJM3TYCWTXZ3LSHYOQ3ANCNFSM4Q4ZJPKA .