path.unite() fails on rather simple case

[iconexperience]

I have found a relatively simple example where path.unite()fails on the current build. The bug does not occur in version 0.9.25.

var p1 = new Path({segments:[
    [437.02857142857147, 121.64285714285714],
    [390.3571428571429, 74.97142857142856],
    [390.3571428571429, 437.02857142857147],
    [437.02857142857147, 390.3571428571429],
    [74.97142857142862, 390.3571428571429],
    [121.6428571428572, 437.02857142857147],
    [121.64285714285714, 74.97142857142858],
    [74.97142857142859, 121.64285714285714]
    ], closed:true});    
p1 = p1.unite();
p1.strokeColor = "red";    

The path consists only of lines and all intersections are found correctly and are recognized as crossings.

Also, if we simply round the coordinates to ensure that all lines are exactly horizontal, vertical or diagonal, the result is fine:

 var p2 = new Path({segments:[
    [437, 122],
    [390, 75],
    [390, 437],
    [437, 390],
    [75, 390],
    [122, 437],
    [122, 75],
    [75, 122]
    ], closed:true})
p2 = p2.unite();
p2.strokeColor = "green";

[iconexperience]

The first call to propagateWinding() calculates 2 in the first (broken) example, but 1 in the second (working) example.

[lehni]

Hmm! I wonder why it works on 0.9.25? Are you looking into it? Welcome back! ; )

[iconexperience]

Sorry for the silence recently, I was (and am) really busy.

As far as I can see in propagateWinding() one curve is not recognized as horizontal in the broken example, and for a point on this curve getWinding() returns 3, while in the working example the curve is recognized as horizontal and getWinding() returns 1.

As far as I can see in propagateWinding() one for one point getWinding() returns 3, while in the old version getWinding() returns 1.

So it seems like the problem is in getWinding(), which may have been caused by our changes for #819.

[iconexperience]

One point on which getWinding() return 3 is here:

I tried to find the correct winding number for this point and came up with this sketch, which shows the intersections if all horizonal lines are absolutely hozizontal:

The blue dot is our point, the red dot are intersections that will be counted to calculate the winding number. Since the point is one the vertical line, the intersection at the point is not counted.

To the left there is only one intersection, setting the left winding to +1. To the right there are two intersections which contribute -1 and +1, which sets the right winding to 0. The overall winding is calculated as

Math.max(abs(windLeft), abs(windRight))

In this case the overall winding number should be 1.

[lehni]

Oh gee. I have no clue! : ) That part was always a bit unclear to me. What's your guess? 2?

[iconexperience]

No, 2 means outside the path for even-odd winding rule. We are on the path, so it must be non-zero and odd.

[lehni]

Yes, 1 sounds right! So why do we get 3?

[iconexperience]

Our counting of the windings must be wrong somewhere. Below you can see how the mono curves are ordered. We have five loops here, which is alright.

[iconexperience]

The point is at 6428571428572, 390.3571428571429, and here are the segments of the mono curves:

0:  [390.3571428571429, 121.64285714285717], [390.3571428571429, 390.3571428571429]
1:  [390.3571428571429, 390.3571428571429], [121.6428571428572, 390.3571428571429]
2:  [121.6428571428572, 390.3571428571429], [121.64285714285717, 121.64285714285714]
3:  [121.64285714285717, 121.64285714285714], [390.3571428571429, 121.64285714285717]
4:  [121.6428571428572, 437.02857142857147], [74.97142857142862, 390.3571428571429]
5:  [74.97142857142862, 390.3571428571429], [121.6428571428573, 390.3571428571429]
6:  [121.6428571428573, 390.3571428571429], [121.6428571428572, 437.02857142857147]
7:  [390.35714285714283, 121.64285714285714], [390.3571428571429, 74.97142857142856]
8:  [390.3571428571429, 74.97142857142856], [437.02857142857147, 121.64285714285714]
9:  [437.02857142857147, 121.64285714285714], [390.35714285714283, 121.64285714285714]
10: [437.02857142857147, 390.3571428571429], [390.3571428571429, 437.02857142857147]
11: [390.3571428571429, 437.02857142857147], [390.3571428571429, 390.3571428571429]
12: [390.3571428571429, 390.3571428571429], [437.02857142857147, 390.3571428571429]
13: [74.97142857142859, 121.64285714285714], [121.64285714285714, 74.97142857142858]
14: [121.64285714285714, 74.97142857142858], [121.64285714285714, 121.64285714285717]
15: [121.64285714285714, 121.64285714285717], [74.97142857142859, 121.64285714285714]

[iconexperience]

And this is howt our horizontal ray through the point crosses the path

0:  cross at end
1:  horizontal same y
2:  cross at start
3:  -
4:  cross at end
5: horizontal same y
6: cross at end
7:  -
8:  -
9:  -
10: cross at start
11: cross end
12: horizonal, same y
13: -
14: -
15: -

[iconexperience]

I suspect that the problem is that we alway increment the left and right winding at an extremum in PathItem.Boolean.js line 404
Because we always increment, these cases behave different:

Actually the for the right case contains() returns false for winding rule evenodd, because the overall winding is 2, which is certainly wrong. Here is a little snipplet that you can use for testing:

var rect = new Rectangle(100, 100, 100, 100);
var pth = new Path.Rectangle(rect);
pth.reverse();
pth.setFillRule("evenodd");
console.log(pth.contains(rect.topLeft));
console.log(pth.contains(rect.topRight));
console.log(pth.contains(rect.bottomLeft));
console.log(pth.contains(rect.

If we replace PathItem.Boolean.js lines 401/402 with

windLeft += winding;
windRight += winding;

things seem to work.

[lehni]

My brain's not at all in boolean / winding mode at the moment, and it's hard to switch back into it. Are you comfortable working on this one?

[iconexperience]

I will try. Unfortunately there are cases where the fix above does not work. I will have to investigate further. Maybe we have a combination of flaws here.

But I think that I found a way to simplify getWinding() further. That's the only good news so far.

[iconexperience]

Here is a case that still fails, but it fails with the 0.9.25 release, too. So it may have a different cause, but I am posting it here to make sure it does not get lost.

var p = new Path({segments:[
    [384.0884708724184, 194.49096034834812, -66.07592496222571, -39.741588860234515], 
    [364.2895784370851, 164.00333956484477, 0, 0, 9.430248075502885, 76.52772155228502],
    [317.5090396516519, 384.0884708724184, 39.74158886023454, -66.07592496222564],
    [347.9966604351552, 364.2895784370851, 0, 0, -76.52772155228439, 9.430248075502845],
    [127.91152912758163, 317.50903965165196, 66.0759249622259, 39.74158886023463], 
    [147.71042156291495, 347.9966604351553, 0, 0, -9.43024807550288, -76.52772155228509], 
    [194.49096034834812, 127.91152912758156, -39.74158886023451, 66.07592496222576],
    [164.00333956484474, 147.7104215629149, 0, 0, 76.52772155228499, -9.430248075502845]
    ], closed:true});
p = p.unite();
p.strokeColor = "red";

And here is a very similar example that does not fail:

p = new Path({segments:[
    [384.65569490812175, 194.46652092866827, -66.62065765745916, -39.369751450156855],
    [364.5426157580749, 163.49509503108152, 0, 0, 8.868994950711965, 76.87411973170003],
    [317.5334790713317, 384.6556949081218, 39.36975145015684, -66.62065765745915],
    [348.5049049689185, 364.54261575807493, 0, 0, -76.87411973170015, 8.868994950711965],
    [127.34430509187821, 317.5334790713317, 66.62065765745923, 39.36975145015691],
    [147.45738424192507, 348.5049049689185, 0, 0, -8.868994950712015, -76.87411973169992],
    [194.46652092866822, 127.3443050918782, -39.369751450156876, 66.62065765745918],
    [163.4950950310815, 147.45738424192504, 0, 0, 76.87411973169984, -8.868994950711965]
    ], closed:true});
p = p.unite();
p.strokeColor = "green";

[lehni]

The first one also still fails even with your PR, right?

[lehni]

Oh, I see, it still fails with the fix posted above.

[iconexperience]

My PR is not supposed to fix anything, this was just a simplification.
The new example fails in all cases: the latest release, the current development build and my fix implemented. I had no time to look into this as I am still struggling with finding an implementation of getWinding() that will really handle all cases correctly.

[iconexperience]

Wow, I think I finally found a really robust implementation of getWinding(). More tomorrow.

[lehni]

That's just the bed-time story I wanted to hear! Very curious : )

[iconexperience]

Let's start with a simple test case:

If the result is correct (as it is in the image above), all points in the green area or on the grey stroke are green, all other points are red.

This is the code:

var points = [[250, 230], [200, 230], [200, 280], [190, 280], [175, 270], [175, 220], [175, 270], [160, 280], [150, 280], [150, 220], [150, 200], [100, 200], [100, 180], [150, 180], [150, 160],  [150, 100], [160, 100], [175, 110], [175, 160], [175, 110], [190, 100], [200, 100], [200, 150], [250, 150], [270, 120], [270, 90], [270, 120], [290, 150], [290, 230], [270, 260], [270, 290], [270, 260], [250, 230]];
var path = new Path({segments: points, strokeColor: 'tan', fillColor: 'palegreen', closed: true});
path.setWindingRule("evenodd");

var showPoint = function(p, xOffs, yOffs) {
    var pOffs = new Point(p.x + xOffs, p.y + yOffs);
    new Path.Circle({center: pOffs, radius: 3, fillColor: path.contains(pOffs) ? 'green' : 'red'});
};

for (var i = 0; i < points.length; i++) {
    var p = new Point(points[i]);
    showPoint(p, 0, 0);
    showPoint(p, 10, 0);
    showPoint(p, -10, 0);
    showPoint(p, 0, 10);
    showPoint(p, 0, -10);
}

And here is the sketch

Now let's look what the current develop branch and the 0.9.25 do with this test:

The blue arrows show some examples where contains() still fails in these versions.

[iconexperience]

My new idea is to count only intersections of the horizontal ray with a monocurve if the point is not on the curve or an adjacent horizontal curve. If the point is on a monocurve, we set a flag. At the end we make sure that the winding is odd if we previously found that the point is on a monocurve.

Here is an example of three curves and some points, showing for which points the intersection of the horizontal ray with the path is counted.

As before we have to treat intersections at curve ends/beginnings in a special way if the winding does not change. In this case we must prevent that the intersection gets counted twice, once for the curve end and once for the start of the next curve.

[iconexperience]

So I found a fix for the original example, but the other example still fails. I suspect the secons example fails for an entirely different reason. If this is the case, I will open a new issue for the second example.

[lehni]

Very impressive, and so quick, @iconexperience! I am trying to have a look at the changes as we speak. Fingers crossed!

[iconexperience]

Even if everything looks good from your side, maybe you should wait with accepting the PR until we know what causes the other example to fail,

[lehni]

Let's accept it. All tests pass, and we test a whole lot of boolean edge cases...

[lehni]

We can always revert a commit.

[iconexperience]

OK, it's the develop branch after all.

[iconexperience]

I found what causes the still failing example to fail. The problem is that Curve.getPoint() snaps to the start- or end point if t is very close to zero or one. Then this can happen:

The crossing of the horizontal ray and the y-monotone curve happens right of the point, but before tmin. Then we call Curve.getPoint(), which returns the start point of the curve, because of t<tmin. But the x-coordinate of the start point is left of point p, so we think that the line is crossed left of p, which is wrong.

To solve this it would be nice to have something like getPoint() that does not snap to the start or end point.

One way to achieve this without API changes is to replace

Curve.getPoint(values, roots[0]).x

with

Curve.subdivide(values, roots[0])[0][6]

which is a nice hack, but not really a clean solution.

[lehni]

@iconexperience yes this makes a lot of sense. And so you verified already that using the hack, the issue goes away?

We might only require the snapping for tangents and normals anyway, not points... I shall investigate.

[iconexperience]

Yes, the issue goes away and I am not able to create similar issues after implementing the workaround. Here is an image of how the situation actually looks in the example above (at the bottom right self intersection).

You can see that the horizontal line through p crosses just before tmin.

I will switch off snapping to the end points in evaluate for getting points (not for tangents and normals) and test if I can find any side effects.

[iconexperience]

Unfortunately there seem to be side effects, like in this example from the test cases:

var path1 = new paper.Path.Circle(new paper.Point(50, 50), 50);
var path2 = new paper.Path.Circle(new paper.Point(100, 100), 50);
console.log(path1.getIntersections(path2).length);

If I disable snapping to the end points, this finds 5 intersections, while there should be two.

If I only disable snapping to the end points in getWinding() this test case does not fail..

[iconexperience]

I have added some more points to my new test for Path.contains(). Points on any curve of the path are counted as being inside the path.

The visual result looks like this (red circles indicate the test for the point has failed):

Here is the Sketch

As the next step I will change this into unit test format (all that needs to be done is to remove the testPoint() function) and post a pull request on the winding-fix branch.

[lehni]

Regarding #936 (comment): I have looked into this a bit. The snapping is just masking an imprecision of the results from the fat-line clipping code, which are so far apart that they don't get merged (much more than GEOMETRIC_EPSILON)! So I don't think we should do the snapping necessarily, we should probably fix the imprecision instead. I've tested values of CLIPPING_EPSILON and realized that the issue disappears again when I set it to 1e-9, without the snapping. Do you think we get too many recursions with 1e-9?

[lehni]

@iconexperience I can't see any negative side-effects of decreasing CLIPPING_EPSILON to `1e-9 in any of the tests available. There's no measurable slow down resulting from it... It might be the way to go?

[iconexperience]

I do not think there is a measurable performance impact from this. The real problematic curve pairs are extremely rare (I still have not come across one in the wild), and I am not even sure if the CLIPPING_EPSILON makes a diffence for these cases.

So let's just do it. In the worst case we will have to revert the change and use the workaround mentioned above until we have a better solution.

[lehni]

@iconexperience this is quite interesting: I tried to further reduce CLIPPING_EPSILON and see what happens, but at 1e-11 a previous edge case (#899) starts failing again, because one valid intersection is not found anymore. Do you have an idea what that could be? Other than that, performance seems good even at 1e-12, so I think it would be nice to reduce it further and increase precision!

var path = new Path({segments:[[349.31714952528665, 176.97192499841802, 2.0667935742653185, -10.850610233997372, 0, 0], [308.23418424120047, 394.39737504104323, 0, 0, -0.3852007263769224, 2.0386172397749647], [273.60284923271973, 415.7138856106701, 9.194683617471242, 1.7373535056759692, 0, 0], [340.6967045975081, 152.3115389894092, -4.006231967752797, -3.6687868382265094, 5.694026309937783, 5.214418174126138], [349.72123243229134, 170.85618880187394, -0.36146393999291604, -6.612268801346318, 0.1110858449889065, 2.0320961120115726], [349.31714952528654, 176.97192499841861, 0.3852007263769224, -2.038617239775249, -2.0667935742656027, 10.850610233997315], [333.4126425432937, 153.58289639999975, -10.850610233997315, -2.0667935742653754, 10.850610233997372, 2.0667935742653754]], closed:true});
path.strokeColor = 'red';
var inters = path.getIntersections();
console.log(inters.length);
inters.forEach(function(inter) {
    console.log(inter, inter.time);
});

[lehni]

Oh, and I've played with decreasing all the epsilons, and I think we can increase precisions quite substantially all across now with the new code-base.

[lehni]

...but in order to be sure it would be good to reactivate your test suite... at the moment, here how it looks over here, and I can't figure out why! Also, those funky shapes appear to trigger a whole lot of open path errors, argh...

[iconexperience]

@lehni Maybe the intersection is not found anymore because we reach the recursion limit first? Just a guess, but it would make sense.

I hope to fine some time to look at that tomorrow and also find out why my test suite suddently developed artistic skills...

[iconexperience]

@lehni #899 works for me, it finds three crossings and one touching intersection. Also the curves in my test suite look fine. Am I using the wrong paper version? The snapping to the end points has been removed in my version, so I assume it is the new one.

[lehni]

Could you share your current version of the test suite with me? I'm not sure what's wrong with mine...

[iconexperience]

Which one do you mean? The test suite or paper.js?

[iconexperience]

I simply sent you everything, including the paper.js version that I am using.

[lehni]

Cool : )

[lehni]

Ok... I converted all calls with the old notation (passing , true for curve-time) to the new one, and made one mistake: a getNormal turned into a getPoint, so it was using points as normals and became all creative. This was then causing a rather big amount of edge cases, so I guess we're not fine yet... I'll send you my buggy file back.

[lehni]

Closing this again.