Third intersection found on partially overlapping linear curves.

[iconexperience]

In the following example, a third intersection is found between the two paths, where there should be only two intersections.

var path1 = new Path({segments:[[160.6075323767809, 330.85756555128285, 0, 0, 62.78549052923406, -23.18549160066485], [261.8383465819905, 262.07470247937476, -9.74481985788454, 21.733682765729938, 3.313092486907278, -7.389125928860111], [263.88935325438945, 244.19550800619407, 1.651523249297087, 4.207420633192619, 0, 0], [274.75095370188933, 239.93204418180093, 0, 0, 0, 0], [294.3629794398194, 193.7001742601214, 0, 0, 7.563190712050676, 3.2083818187949973], [319.740729241553, 222.27237409836766, -6.410840321333732, -16.33225681537532, 5.912463018702233, 15.062590798200258], [316.5868988511627, 286.622533838371, 11.8608907350936, -26.453114610111264, -13.413920693759984, 29.916807211880812], [181.3924676232191, 387.14243444871715, 86.42536270145004, -31.915248317855713, 0, 0]], closed:true});
var path2 = new Path({segments:[[268.3009827109457, 193.43046881012646, 0, 0, 7.359037047450392, -3.0624266286574136], [294.3629794398184, 193.70017426012097, -9.725038248996666, -4.12545935876628, 0, 0], [281.2635766386479, 224.57969147308265, 0, 0, 0, 0]], closed:true});

path1.fullySelected = true;
path2.fullySelected = true;

var ints = path1.getIntersections(path2);
console.log(ints.length);
for (var i = 0; i < ints.length; i++) {
  var p = new Path.Circle({radius: 2, fillColor: 'red'});
  p.position = ints[i].point;
}

See the Sketch here.

One linear segment of path2 is part of a linear segment of path1. Only the start and end point of the segment on path2 should be found as intersections, but a third intersection inbetween is found, too.

I think this problem may be the root cause for the majority of issues that I still see in the boolean operations.

[iconexperience]

The problem can be simplified to the intersection of two linear curves:

var path1 = new Path({segments:[[274.75095370188933, 239.93204418180093, 0, 0, 0, 0], [294.3629794398194, 193.7001742601214, 0, 0, 0, 0]]});
var path2 = new Path({segments:[[294.3629794398184, 193.70017426012097, 0, 0, 0, 0], [281.2635766386479, 224.57969147308265, 0, 0, 0, 0]]});
path1.strokeColor = "red";
path2.strokeColor = "green";
var ints = path1.firstCurve.getIntersections(path2.firstCurve);
console.log(ints.length);
for (var i = 0; i < ints.length; i++) {
  var p = new Path.Circle({radius: 2, fillColor: 'red'});
  p.position = ints[i].point;
}

Here ist the Sketch.

Two intersections are found. One of them is between the end points of path2, which obviously is wrong.

[iconexperience]

@lehni Unfortunately I will probably have not time to work on this today and tomorrow (but I will try). I suspect the fix should be really simple and maybe then we will have working boolean operations :pray:

[lehni]

No worries, I'm looking into it right now! :+1:

[lehni]

Are these paths overlapping? Should an overlap be discovered?

[iconexperience]

The problem is in Curve.js. In our case the distance between the point and the line is a whopping 1.1092571366020775e-12, but the limit is 1e-12. That's it!

[lehni]

YeahI just found the same : )

[lehni]

But it's weird... In my tests with above values I actually get a distance of 0....

[iconexperience]

But then the whole issue should not be reproducible.

[iconexperience]

In my case setting the limit higher almost removes the glitches entirely. I have almost run out of problems :smile:

[lehni]

wow!

[lehni]

I was using this:

var line1 = new Line(path1.firstSegment.point, path1.lastSegment.point);
var line2 = new Line(path1.firstSegment.point, path1.lastSegment.point);

var dist = line1.getDistance(line2.point);
console.log(line1.isCollinear(line2), dist);

Constructing the lines in this way I get the same distance. That's weird!

var v1 = path1.firstCurve.values,
    v2 = path2.firstCurve.values,
    line1 = new Line(v1[0], v1[1], v1[6], v1[7]),
    line2 = new Line(v2[0], v2[1], v2[6], v2[7]);

var dist = line1.getDistance(line2.point);
console.log(line1.isCollinear(line2), dist);

[iconexperience]

Well, in the first case the lines are identical, aren't they? I see no path2 in there.

[lehni]

Hahah, yes just saw that : ) No wonder it's 0.

[iconexperience]

Well, I have to go. This is a great ending for today.

[lehni]

So which limit did you change? Just that one there, or EPSILON in general?

[lehni]

And what did you change it to?

[iconexperience]

For testing I changed epsilon. Setting it to 1e-10 made things better, setting it to 1e-9 even more.

[lehni]

That has too many implications... Would be better to change only this local limit here and compare.

[iconexperience]

Let's keep this open for a few days and investigate a bit further. In any case having three intersections with two lines should not happen, that should be the goal.

[lehni]

If you could share your testing code that would be great.... Or is it just the offsetting code?

[iconexperience]

It's just the offsetting code, but I think if that works you will not find too many cases that won't. Sorry, no black magic involved here :space_invader: (there is no black magic emoji available, so a space invader will have to do the job meanwhile).

[iconexperience]

@lehni If I use tolerance instead of epsilon then all issues disappear. If I see it correctly we are using tolerance for the distance limit between two points (for example here). Then shouldn't the same value be used as a limit for the distance between a point and a line?

[lehni]

@iconexperience do they also all disappear with 1e-9 as implemented in fb5f8c011501a7b55ba2dd0e4c6abd1e288eb23e? Let's find the best value that's still small enough. 1e-6 is a bit much for my taste, but required for curve time comparisons... : ) I should start introducing other EPSILON values that are named more clearly, e.g. CURVETIME_EPSILON

[lehni]

Sorry, just seeing your second question now. The epsilon / tolerance values used in the library are not very clear right now. TOLERANCE (1e-6) is mainly used to compare curve time parameters, and is required to be that large, probably due to imprecisions resulting from solveCubic(), which is why I'd like to introduce the more explicitly named CURVETIME_EPSILON. the isCose() check you found could probably use a smaller tolerance, I shall check that. EPSILON (1e-12) is used for comparison against 0, e.g. in solveCubic(). The newly introduced GEOMETRIC_EPSILON is in between these two, and is hopefully just right : )

[iconexperience]

@lehni There are still issues when I use 1e-9, but only very few. I will isolate one case where this still happens and post it here. Currently I cannot test with the latest changes you made, so if we are lucky your resent changes already solved the remaining issues.

BTW, If I understand you correctly, GEOMETRIC_EPSILON should also be used in the part of the code I mentioned above? Namely Curve.js line 1708.

[iconexperience]

Here is a case that still seems to cause problems:

var path1 =  new Path({segments:[[168.8000567089184, 329.08077124128994, 0, 0, 45.085703067467385, -3.31512522554906], [246.33686792823391, 303.16131885896465, -9.424943807050076, 14.107093223223714, 5.726221388010804, -8.57090934346579], [247.34223273131477, 278.2312633515556, 2.2107588677303847, 6.684364225863651, 0, 0], [259.64767042555377, 274.1614139859896, 0, 0, 0, 0], [267.7626780758558, 251.43626362823542, 0, 0, 0, 0], [251.68805953263626, 226.10324590956716, 0, 0, 6.241342769068848, -3.9603337164340493], [277.85231394117926, 223.1813929028908, -11.302538869497758, -4.036065238363771, 0.31541574903722097, 0.11263297167094025], [304.3074647489336, 259.3908190579926, -8.031032631117423, -24.282316809746618, 6.86914948335215, 20.76929227282358], [296.22686534993073, 336.49280783355266, 17.79220305894143, -26.631062459095055, -15.417077147312723, 23.076014987387495], [173.1999432910816, 388.91922875871006, 73.75001662206573, -5.422795339857754, 0, 0]], closed:true});
var path2 = new Path({segments:[[237.93960036695705, 248.16175715622165, 0, 0, 1.283014792602909, -11.6854576912472], [251.68805953354808, 226.10324590898858, -6.209602129454726, 3.9401932543807994, 0, 0], [267.76263972980144, 251.43620319624014, 0, 0, 0, 0]], closed:true});
path3 = path1.unite(path2);
path3.unite();

The last unite() call results in a "Boolean operation results in open path" message.

[lehni]

With my latest changes, that error is gone. but the overlap is not detected, so you are right, we need different epsilons there. Perhaps we should keep using 1e-9 (or even 1e-10) for collinearity checks, as those seemed to work well, but use this lower epsilon for the distance checks (also in the location you pointed out, you're correct). In the end of the day, it's all a bit arbitrary and we can tweak until it works well in all tested cases. Doesn't mean there won't be others...

[lehni]

The fact that the error is gone is very good news, btw!

[iconexperience]

Yes, that's great news. How about this pair, does the error still persist?

var path1 = new Path({segments:[[276.6102398243069, 314.88455871046347, 2.8936584324391674, 3.659599723758504, -9.33295456194984, -11.803355072549799], [269.82373345394967, 292.5713176330515, -0.030197986407263285, 0.291629882377662, 0.9736561626761393, -9.402853165120998], [280.44382166126053, 272.62681693859514, -5.198684964907584, 4.337956574653306, 5.205687590589272, -4.343799795751392], [302.0119666310394, 265.752891633999, -9.450524020619941, -0.7417352203057621, 0, 0], [299.6645702605041, 295.6613068252565, 0, 0, 0, 0], [300.77623760011056, 295.77641888077403, 0, 0, 0, 0], [323.6750411585995, 277.6702539962334, 0, 0, 4.828818289681828, 6.1069896435922235], [363.90341441794766, 358.1465185107414, -3.5614605946089237, -31.767786849635986, 1.305886023271073, 11.648341385552252]], closed:true});
var path2 = new Path({segments:[[299.54442613440887, 297.192076530167, 0, 0, 0, 0], [302.01196663117565, 265.7528916340097, 0, 0, 0.24338588822110505, 0.01910242067377944], [322.95584271744264, 276.71006305664946, -10.46520820256235, -11.961975768405368, 0, 0]], closed:true});
path1 = path1.unite();

I cannot build the latest version, so I copied some of the latest changes by hand. The previous example does not result in an error message in my paper-version, but this pair of paths still does.

[iconexperience]

Here is a simplified version of the abobe paths, which still results in an error message:

var path1 = new Path({segments:[ [280, 343, 0, 0, 0, 0],[302.0119666310394, 265.752891633999, 0, 0, 0, 0], [299.6645702605041, 295.6613068252565, 0, 0, 0, 0], [340.77623760011056, 295.77641888077403, 0, 0, 0, 0]], closed:true});
var path2 = new Path({segments:[[299.54442613440887, 297.192076530167, 0, 0, 0, 0], [302.01196663117565, 265.7528916340097, 0, 0, 0, 0], [310, 280, 0, 0, 0, 0]], closed:true});

The paths only consist of linear segments and this time the intersections seem to be found correctly.

[lehni]

Indeed! Those are still causing trouble...

[lehni]

That's a tricky case... it seems that the two lines that appear to be overlapping aren't quite overlapping, and the code is rightly detecting that. But then the rest of the code is going wrong, maybe because of different precisions in the code that calculates winding contributions. Not quite sure yet!

[lehni]

Alright, I found it, and it's indeed due to wrong epsilons, but not in the winding code: The mistake happens in Curve.getParameterOf(), where beginnings and ends of curves where matched too loosely using TOLERANCE, eradicating that very light difference of the almost overlapping line when points where converted to curve time. Fix coming up!

[lehni]

With those changes in place, let's throw some more tests at it! : ) 4f04dae20f08f545becde5e58b1191ac8f4da493 fixed both cases that you posted above, @iconexperience

[iconexperience]

Hmm, I have the feeling that the problems have become rather more than less, but this problem has been solved.

I noticed that the found intersections between both paths are now 3, where previously only 2 were found.

Should I keep sending examples?

[lehni]

Oh that's not good! Yes please send new ones!

[lehni]

3 intersections between both paths is actually right.

[lehni]

I think the new issues are probably a case of our previous fuzziness covering up things that were handled wrongly. It's probably a good thing these come out now, and are handled right too.

[lehni]

Also, once we have enough things failing we can start tweaking those epsilons which I've now separated.

[iconexperience]

Here is another pair of paths, very similar to the previous ones. Again both paths only consist of linear curves.

var path1 = new Path({segments:[  [422.1528733184818, 324.6066041042774, 0, 0, 0, 0], [441.64559725379735, 301.7693687628332, 0, 0, 0, 0], [451, 418,0,0,0,0], [275.14600229974988, 388.83458847596137,0,0, 0, 0]], closed:true});
var path2 = new Path({segments:[[423.8734108205118, 294.61515905951745, 0, 0, 0, 0], [441.64559725361846, 301.76936876268053, 0, 0, 0, 0], [422.0347726101888, 324.74496822815644, 0, 0, 0, 0]], closed:true});

Three intersections are found, but a Boolean operation results in open path message is thrown.

[lehni]

Increasing GEOMETRIC_EPSILON to 1e-8 seems to work there...

[lehni]

I've tested a bit, the only place were the increase is necessary for this to work is in Line.isCollinear().

I guess what we're seeing is extreme edge cases where overlaps are detected or not, and where intersections are merged or not, based on these tolerances. The problem is that there is no easy way to make sure a point is only merged elsewhere in the code when the overlap was detected with some tolerance.

But that's just a guess. I need to analyze more what exactly is going wrong.

[iconexperience]

The problem with isCollinear() is certainly that other tolerance values should apply for shorter lines than for longer one. Maybe we should rething some calculations. For isCollinear we could take the longer vector and calculate the distance of the other vector from that line. Then, if the differences between these two is smaller thank geometrical tolerance, the lines are collinear.

This is just a though, but maybe it is necessary to rethink some of the calculations to ensure that toleance is not relative to the size of the paths/curves/lines.

[lehni]

Yeah I was thinking about similar approaches, but that will still not solve it. The issue is that regardless of the approach, we will have one type of tolerance when comparing collinearity or overlaps, and a completely different one when deciding that two found intersections are in fact one, because at the moment, parameters are compared with CURVETIME_EPSILON tolerance there... I think comparing the points of intersections instead will improve things since precision is not dependent on curve length. I will have to go through all code and find other places where similar issues might arise.

The thing is: Even if the code decides that two lines are not collinear because of some arbitrary threshold, the code should still be able to produce correct results, just without the two lines merged. But with your example above it does't, because I believe that when the overlap is not found, two intersections that are very close to each other are wrongly merged. The overlap being found doesn't fix this issue, it's just hides it.

I hope I managed to get my point across : )

[lehni]

I believe I found the source of the "open-path" errors, but more testing is required:

There was code that sorted segments based on wether they had intersections or not in them, in order to more easily propagate winding contributions across curve chains. I think this sometimes lead to situations where the sequence of segment processing was wrong. I have now changed the code to still correctly propagate winding contributions but keep segment sequence the same, and the above issue has disappeared regardless of what tolerances are used, it just means that the overlapping line is either merged or not.

I believe this is good news, as it hints at a solution for the often occurring "open-path" errors in edge cases... This is not confirmed yet and more testing is required, but it may be solved : )

[iconexperience]

I understood your first comment, but I am not sure how to understand your last comment (not sure if the problems are supposed to be fixed or if you only have an idea), but I am still seeing about the same number of error messages as before.

Anyhow, here is something that I noticed: In addOverlap() in the case of two linear curves we are checking if the curves are collinear and close to each other. But even if this condition is fulfilled, we sometimes do not recognize the overlap, because getParameterOf() does not recognize that the point is on the other line. I took a look at Curve.getParameterOf() and noticed that it does not handle linear curves differently. Maybe we should implement this, which would probably give an performance improvement and maybe give us better results for linear curves, which are giving me headaches at the moment.

I will take a closer look at this tomorrow.

[iconexperience]

Here is a pair of paths that still causes problems, not directly, but when mergin the result with another path. In this case, we get three intersections between two lines the lines have one common end point, and another intersection, which is not the end point of any line. I consider this a bug, because if two lines share an end point, they cannot intersect.

No matter how sophisticated the boolean operations become, making sense of the three these intersections would be difficult. Therefore I would see this as an issue on intersection finding, not really a boolean op problem.

Here are the paths:

var path1 = new Path({segments:[ [294.2617134041458, 281.36315535651687, 0, 0, 0, 0], [293.07686572475166, 249.8809707928622, 0, 0, 0, 0],  [320, 260, 0, 0, 0, 0]], closed:true});
var path2 = new Path({segments:[[275, 256, 0, 0, 0, 0], [293.0768657247189, 249.88097079286345, 0, 0, 0, 0], [294.21396377280934, 280.09441614832053, 0, 0, 0, 0]], closed:true});
path1.fullySelected = true;
path2.fullySelected = true;
var ints = path1.getIntersections(path2);
console.log(ints.length);
var colors = ["red", "green", "orange"];
for (var i = 0; i < ints.length; i++) {
  var p = new Path.Circle({radius: 1, fillColor: colors[i]});
  p.position = ints[i].point;
}

And here is the Sketch You will have to zoom in a lot to see the problem.

[iconexperience]

One problem that I have found during investigation of the above path pair is that the result of Line.intersect() depends on the order of parameters. Here is an example (taken from the path pairs above):

var l1 = new Line(294.2617134041458, 281.36315535651687, 293.07686572475166, 249.8809707928622);
var l2 = new Line(293.0768657247189, 249.88097079286345, 294.21396377280934, 280.09441614832053);
var intersection1 = l1.intersect(l2);
var intersection2 = l2.intersect(l1);
console.log(intersection1.getDistance(intersection2));

The distance between both points is 0.00005673926, much larger than the geometric precision. Of course it may be very difficult to find the precise intersection point with almost collinear lines, but IMHO the result should be the same, independent of the parameter order.

[iconexperience]

To make the results from Line.intersect()indepenent from the parameter order we could simply build the average intersection point. At Line.jsline 141 we could simply use this:

if (isInfinite || 0 <= ta && ta <= 1 && 0 <= tb && tb <= 1)
    return new Point(
        (apx + ta * avx + bpx + tb * bvx) / 2,
        (apy + ta * avy + bpy + tb * bvy) / 2);

But next to a tiny performance impact that could result in points that are neither on line 1 nor on line 2, while currently the point is at least on one line.

And I just found that the new calculation does not seem to improve the boolean algorithm at all.

[lehni]

Yeah I think we should find a better formula for more precise results there... Or use a root-solver to improve the accuracy at the end?