Incorrect inner ring added to diff result.

[erikh2000]

This is similar to #68 but maybe different:

The code below attempts to subtract the square (with the hole) from the triangle.

var arg1 = [[[2, 0],[10, 10],[10, 0],[2, 0]]];
var arg2 = [[[5, 1],[12, 1],[12, 9],[5, 9],[5, 1]],[[6, 2],[11, 8],[6, 8],[6, 2]]];
var d = diff(arg1, arg2);
console.log(JSON.stringify(d));

Output of log above:

[[[[2,0],[10,0],[10,1],[5,1],[5,3.75],[2,0]],[[6,2],[10,6.800000000000001],[10,8],[8.399999999999999,8],[6,5],[6,2]]],[[[9.2,9],[10,9],[10,10],[9.2,9]]]]

This produces a nifty-looking multipolygon like this:

The middle shape is actually an inner ring, and it should be present in the result as a POLYGON--not an inner ring. As it stands, the inner ring is not contained by an outer ring, so makes objectively incorrect geoJson as well. My hunch is there is some bug with setting the status to "inside" or "outside" during sweep evaluation, but I am just learning how the Martinez algorithm works and reluctant to jump into the deeper code to make changes. (At least today, I am. :) )

[erikh2000]

Another case that produces a similar result--this one has no intersection between the two shapes. Green shape is first argument, blue is second. It's necessary to call union() (diff() with same params won't create OOB inner ring) to see the problem.

var arg1 = [[[-93.52965,42.04924],[-93.53626,42.04214],[-93.53914,42.04358],[-93.5313,42.04924],[-93.52965,42.04924]],[[-93.53419,42.04589],[-93.53449,42.04596],[-93.53434,42.04588],[-93.53419,42.04589]]];
var arg2 = [[[-93.5388,42.0484],[-93.5387,42.0476],[-93.53824,42.04826],[-93.5388,42.0484]]];
var u = union(arg1, arg2);

[rowanwins]

This is possibly related to my pull request around multipolys and comparing contour ids. Does it resolve itself if you undo my changes by any chance?

[erikh2000]

@rowanwins I'm happy to try it. Do you have PR# so I can see which changes to undo? I looked through the PRs a bit, and it wasn't obvious to me which one you meant.

[rowanwins]

#56

[erikh2000]

Ah, I already didn't have #56 merged in.

I was going to take a crack at making a fix, but it feels like the PRs are piling up a bit, so it's unclear what baseline to begin from. My PRs aren't that important, but whether to begin from #56+#57+#58+#64 or something else--that's a little tough. Trying not to have my local fork diverge so much that it's hard to contribute back or communicate bugs.

And I know that people just get busy, and that's the default reason why things don't happen. No worries.

[erikh2000]

Update: I don't think the current implementation is coded to handle the case of holes created by exterior ring edges. Inside of connectEdges(), there is this code for creating interior rings...

if (!resultEvents[i].isExteriorRing) {
      if (operation === operationType.DIFFERENCE && !resultEvents[i].isSubject && result.length === 0) {
        result.push(contour);
      } else if (result.length === 0) {
        result.push([[contour]]);
      } else {
        result[result.length - 1].push(contour[0]);
      }
    }

The trouble is that connectEdges() will only create an interior ring if the edges it's evaluating were originally from an interior ring in subject or clipping polygons. But the case we are evaluating is a new hole in the result shape that is created by edges from exterior rings. So there would need to be some new logic added that allows the algorithm to create interior rings for this case. I can think of inelegant, costly solutions, but I'm hoping a better understanding of the Martinez/Reuda algorithm would show a better way to handle it.

The sawtooth_rect.geojson test case demonstrates the problem as well. I noticed it's been excluded from the web demo and edge cases (maybe someone already noticed this issue?). Note that if you view sawtooth_rect in the web demo, Leaflet does something to clean up the result so that it looks visually correct. But the result output to browser console will show extra, incorrect polygons for "Union" operation. I am curious how Leaflet is figuring out that these extra polygons shouldn't be shown--it may be a clue to fixing them cheaply.

I had previously said in this comment that "Difference B - A" for sawtooth_rect was giving a bad result in browser console. Nope - that was the JSTS output. Congrats for doing better than JSTS here, actually.

[rowanwins]

Gday @erikh2000

This was code I added trying to get things to nest correctly so there is a chance there is a bug in there or a better way to do things. I'll try and take a look one night this week and report back.

Its also worth noting that sometimes leaflet does seem to struggle a bit with rendering multipolys with holes. I can't remember any specifics now but Im sure I've seen cases that have rendered weird. So check out the actual results as well as the visual results in one trick I've learnt.

Sorry things are slow at the moment - as you've probably worked out everyone involved in this lib is working on it in their spare time.

Cheers