Subtract operation results in open path

[iconexperience]

It looks like 3348fb7 has introduced a regression. The following rather simple case now throws a Boolean operation resulted in open path message.

var p1 = new paper.Path({segments:[
    [352, 280, 0, -26.5, 0, 0],
    [352, 356, 0, 0, 0, 2.1999999999999886],
    [348, 360, 2.1999999999999886, 0, -72, 0]
    ], closed:true});
var p2 = new paper.Path({segments:[
   [352, 344, 0, 0, 0, 0],
   [352, 356, 0, 0, 0, 2.1999999999999886], 
   [348, 360, 2.1999999999999886, 0, 0, 0], 
   [232, 360, 0, 0, -2.1999999999999886, 0]
   ], closed:true});

p1.strokeColor = "green";
p2.strokeColor = "red";

var res = p1.subtract(p2);

res.fullySelected = true;

The result actually looks fine, but still the error message indicated that something is wrong.

[lehni]

This will just never end, will it : /

[iconexperience]

Yes, it's getting a bit frustrating. Everything is working so well, but then a new case appears that fails. I always have the feeling that we are really close, but I had this already a few months ago...

[lehni]

Exactly. And changes become tough. I spent almost the whole of yesterday on that transition...

[iconexperience]

Actually, I can live with this issue (not really causing problems), 953 #964 (a real edge case) and #904 (more a theoretical issue than a real world problem) unfixed.

We want to make it perfect, but maybe that is not possible? Anyway, I would still like to make this as stable as possible and whenever I have time I will continue working on these issues.

[lehni]

You mean #964? That one we should really fix... I think something strange is going on in isCrossings() there still.

[iconexperience]

Yes, sorry.

[iconexperience]

From the first glance it seems that with the new code you are now doing the check for identical paths for each child in a compound path. If so, there must be a small error in the new implementation, because my example does not even have a compound path. But then again I may be completely wrong with my interpretation of your changes.

[lehni]

There were some other necessary changes, and I actually solved a few undetected edge cases for which the unit tests where using wrong data for the results. I'll look into it.

[lehni]

First of all, it doesn't actually fail, it just reports that it had to abandon an open path, that's not a problem by itself.The reason why it now produces this error is that all the valid segments of the red path are overlaps, and we have to handle this case specially: Normally we don't allow a path to start in an overlap, but if the only valid segments are overlaps, we have to start in one. Which brings us to the more confusing part:

The winding calculations produce 1 for two of the overlapping segments that are not part of the solution, and that is wrong. I am not sure why yet. Here the output of the debug-boolean code. The segments in question are the red 5.1 and 5.2, which both have a wi: 1(winding), while it should really be 0.

@iconexperience would you want to help out with debugging this one?

[iconexperience]

Yes. So you mention wrong winding calculation. That sounds pretty much like my part to investigate.

[lehni]

Cool : ) Note that we handle winding for subtraction operations separately in propagateWinding()

[iconexperience]

Do you mean the getWinding() calculation is wrong? If I remove my isOnCurve check in getWinding() this test case does not fail anymore. This makes sure that the winding is always at least 1 if the point is on a curve. Is it doing the wrong thing here?

[lehni]

Well, since these are overlaps, they are on two curves. And I believe propagateWinding() should handle that... For subtraction, the result then should become 0. But maybe, the isOnCurvecode only works correctly for one of the two paths? But you need to look into what exactly it's doing, I haven't written that part of the code...

[iconexperience]

Well, but I have written that part of the code.

Maybe the current implementation of getWinding() is still flawed. If there are several paths, we should probably calculate the winding for each path (not a problem), but we should also detect the orientation of the path (a bit tricky). If the point is on a curve but winding for the path is zero, we will add +1/-1 or -1/+1 to the leftWind/rightWind, depending on the path's orientation.

Detecting the path's orientation is quite simple. We use the winding of the lefmost non-horizontal curve that is crossed by the horizontal ray. If that curve's winding is negative (going up), the path is clockwise, if it is positive, the path is counter-clockwise.

I will give it a try.

[iconexperience]

This is complicated and I am glad you have some many unit tests.

So this is my algorithm that seems to work:

We calculate the windings as we did before. But for each loop we check if we are on a curve. At the end of a loop we add +1/-1 or -1/+1 to new leftWindOnCurve and rightWindOnCurve variables, depending on the path's orientation. We get the orientation has explained in my comment above.

After running through all loops, we check if windLeft and windRight are zero. If so, we use the windLeftOnCurve/windRightOnCurve values. These can be zero if a point is on two paths with opposite directions.

[iconexperience]

What worries me a little bit is handling the cases for horizontal == true. We have not worked on that case at all while completely overhauling the cases for horizontal == false. Well, it worked so far...

[lehni]

Sounds like we need specific unit tests for those cases too...

[iconexperience]

Yes, that would be nice. But the overall proplem in some cases is to know what the correct result is. Here is a little discussion about the winding number for points on a path, and it seems we have come further than they did.

http://stackoverflow.com/questions/8452078/integer-winding-number-algorithm-with-edge-cases

[iconexperience]

To get a better understanding about the problems that we are facing here, please take a look at these examples.

In both cases the correct winding number of the red point is 1. But at the left we have to ignore the touching with the smaller circle, in the right example we have to count it. And this is a very basic example.

[lehni]

Wow, yeah... How bad is it going to be?

[iconexperience]

I was thinking about this all the time and it really makes my head spinning. This is pobably because striktly speaking the points on the path are not defined, but that does not help us. We need a solution.

So I tested my implementation and it looks alright. Not sure if you agree with my code, but I will send the PR in a few minutes.