Fat line clipping fails and is slow if curves are very similar

[iconexperience]

I have started to investigate the curve pairs that create many calls to addCurveIntersecticions().

Initially I found this curve pair which creates 672 calls to addCurveIntersecticions(). As you can see, curve2 is almost identical to the first part of curve1, but of course not completely, because otherwise our function getOverlaps() would have filtered this curve pair.

So it seems like the problematic curve pairs are the ones where one curve is almost identical to part of the other curve. Therefore I decided to generate these curves artifically.

First we need a curve. Here is a function that creates a random standard curve.

var createRandomCurve = function(size) {
    var p1 = new Point(Math.random() * size + size, Math.random() * size + size);
    var p2 = new Point(Math.random() * size + size, Math.random() * size + size);
    var side = Math.random() > 0.5 ? 1 : -1
    var h1 = p1.add(p2.subtract(p1).multiply(0.2 + Math.random()*0.3)).rotate(side *  (10 + 40 * Math.random()), p1).subtract(p1);
    var h2 = p2.add(p1.subtract(p2).multiply(0.2 + Math.random()*0.3)).rotate(-side * (10 + 40 * Math.random()), p2).subtract(p2);
    return new Curve(p1, h1, h2, p2);
}

To create a pair of of almost identical curves that have do not cross, the curve is cloned and one end point is moved just very slightly in orthogonal direction. For creating a pair of curves with a crossing, both end points of the curve are moved, but in opposite direction.

Here is the code how I do it:

var createCurvePair(crossing) {
    var curve1 = createRandomCurve(1000);
    var curve2 = curve1.clone();
    curve2.segment1.point = curve2.segment1.point.add(curve1.getNormalAt(0, true).normalize(1 * Numerical.GEOMETRIC_EPSILON));
    if (crossing) {
        curve2.segment2.point = curve2.segment2.point.add(curve1.getNormalAt(1, true).normalize(-1 * Numerical.GEOMETRIC_EPSILON));
    }
return [curve1, curve2]
}

If you call crv1.getIntersections(crv2) on these two curves, things start to get very interesting. These curve pairs usually create more than 50,000 calls to addCurveIntersecticions(), in single cases up to 300,000 calls. And there are cases when more than the theoretically possible 9 intersections are found.

Another thing that I found is that the number of calls to crv1.getIntersections(crv2) and the maximum number of found intersections rises with larger curve sizes.

Now this sounds quite grim, but let's keep in mind that these curve pairs should be the worst of the worst cases that we can encounter, and I have never seen any similar pair in a real case scenario.

More to come soon

[iconexperience]

Here is a real world example of two curves that cross each other, but the crossing is not found and no overlap of the curves is reported.

var p1 = new paper.Path({segments:[
    [347.65684372173973, 270.4315945523045, 0, 0, 22.844385382059784, -25.115215946843847],
    [383.0588370772214, 178.9392357483178, -0.025514950166041217, 33.94338870431889, 0, 0], 
    ]});
var p2 = new paper.Path({segments:[
    [347.65684372173973, 270.4315945523045, 0, 0, 22.869900332225882, -25.136478405315614], 
    [383.0588370772214, 178.84568093104204, 0, 33.97740863787374, 0, -33.93913621262462], 
    ]});

var ints = p1.getIntersections(p2);
console.log(ints.length + " intersections found");
for (var i = 0; i < ints.length; i++) {
    console.log(ints[i].point);
}

Here is the sketch

The only intersection that is found is the start point, which is identical on both paths.

It turns our that addCurveIntersections() terminates after reaching the recusion limit of 26. If I raise the limit to 35, the crossing is found.

Of course we do not want to raise the recursion limit to high, because this may result in massive call trees for very similar curves. A limit of 35 could potentially result in 34359738368 calls.

Therefore I suggest another approach. I think that if curves are tangential but actually have an intersection, the number of recursions can be very high, but the call tree is not a massive as one may suspect (unlike parallel running curves, which also create a huge call tree). So if we use a limit on call tree size instead of the number of recursions we may catch more edge cases and actually have a lower limit on the call tree size that currently.

In my example the call tree size with 35 recursions is just 1200. So setting the limit to semthing like 4000 should be sufficient for now. If necessary we can raise this further if edgier edge cases are found.

The callCount argument would replace the recursions argument and be an array of length 1 (we cannot use a simple number, because we need to share the value between different call tree branches).

[lehni]

This makes a lot of sense. Are you sure we need to emulate a c-style variable / memory reference through an array though? Couldn't we just return the callCount from each recursive call and increase it accordingly?

[lehni]

@iconexperience 41e4c62 seems to have done it. Do you approve?

[lehni]

We could stop at 4096 calls. Programmers love powers of 2... Or maybe 2048 is enough?

[iconexperience]

Excellent, this works great. And yes, I would use 4096. I think a modern browser can easily handle this number of calls.