Improve overlap detection.

[lehni]

In order to improve the reliability of boolean operations when there are paths that are almost overlapping, we need to improve getOverlaps() to be more tolerant in the detection of such overlaps.

Here an example sketch where I believe the overlap should be detected, but isn't currently.

[iconexperience]

I fully agree (and did so before) that a more robuts overlaps detection would solve a lot of issues.

One approach that I thought of a while ago is to detect these overlaps inside the fat line clipping. If curves are almost identical, the progress in fat line clipping will become small. Right now we simply divide one of the curves and keep on trucking, but maybe we should include an overlaps detection before splitting. This would have to be done inside addCurveIntersections()

[lehni]

That's a very interesting thought. How would we then find the beginning / end of the overlap area? This could happen in addition to getOverlaps(), correct? Would you like to look into this?

[iconexperience]

I would like to, but currently I have so many really important things to do that I don't think I can really work on this at the moment. Also, while I think that this is a part in the boolean operations that should be improved, I do not see this as essetial at the moment.

This isn't a minor change and would require quite a refactoring in the whole control flow, therefore I think this isn't done in a day or two. If you can live with slow progress I can agree to work on this.

[iconexperience]

At the same time we could try to improve fat line clipping further, but I do not see much potential here anymore. I tried quite a few things already.

Here are two ideas, just as a reference for future generations :)

(1) It may be possible to improve pecision of Curve.getSignedDistance(). Currently the signed distance is calculated like this:

    ((x-px) * vy - (y-py) * vx) / Math.sqrt(vx * vx + vy * vy);

vx and vy can be very small values, so let's say they are both 1e-7, then we have to take the square root of 2e-14, which certainly isn't great for precision. Therefore I tried to find a way to improve this and came up with this alternative calculation:

((x-px) * vy - (y-py) * vx) / (vy > vx ? vy * Math.sqrt(1 + (vx * vx) / (vy * vy)) : vx * Math.sqrt(1 + (vy * vy) / (vx * vx)))

Here I calculate (vx*vx)/(vy*vy) (or (vy*vy)/(vx*vx) before calculating the square root. I have to admit that I am not really sure it this approach improves precision, but I have seen problems disappear AND appear by using this alternative calculation.

(2) My second idea was to improve the precision of Curve.subdivide(). Our current calculation is very elegant, but some steps can be combined. This makes it less elegant, but I was hoping to get better precision and therefore better results in fat line clipping. Here is the changed function:

subdivide: function(v, t) {
    var p1x = v[0], p1y = v[1],
      c1x = v[2], c1y = v[3],
      c2x = v[4], c2y = v[5],
      p2x = v[6], p2y = v[7];
    if (t === undefined)
      t = 0.5;
    var u = 1 - t, t2 = t * t, tu = t* u, u2 = u * u, t3 = t2 * t,
      p3x = u * p1x + t * c1x,
      p3y = u * p1y + t * c1y,
      p5x = u * c2x + t * p2x,
      p5y = u * c2y + t * p2y,
      p6x = t === 0.5 ? t2 * (p1x + 2 * c1x + c2x) : u2 * p1x + 2 * tu * c1x + t2 * c2x,
      p6y = t === 0.5 ? t2 * (p1y + 2 * c1y + c2y) : u2 * p1y + 2 * tu * c1y + t2 * c2y,
      p7x = t === 0.5 ? t2 * (c1x + 2 * c2x + p2x) : u2 * c1x + 2 * tu * c2x + t2 * p2x,
      p7y = t === 0.5 ? t2 * (c1y + 2 * c2y + p2y) : u2 * c1y + 2 * tu * c2y + t2 * p2y,
      p8x = t === 0.5 ? t3 * (p1x + 3 * (c1x + c2x) + p2x) : u2 * (u * p1x + 3 * t * c1x) + t2 * (3 * u * c2x + t * p2x),
      p8y = t === 0.5 ? t3 * (p1y + 3 * (c1y + c2y) + p2y) : u2 * (u * p1y + 3 * t * c1y) + t2 * (3 * u * c2y + t * p2y);
    return [
      [p1x, p1y, p3x, p3y, p6x, p6y, p8x, p8y],
      [p8x, p8y, p7x, p7y, p5x, p5y, p2x, p2y]
    ];
  },

For both ideas I had to realize that neither brought the break through that I was hoping for. Maybe they will be useful later.

[iconexperience]

Here is another example case that should result in an overlap, but instead it finds 12 (or 14 in the current version) intersections.

[lehni]

@iconexperience I've finally adopted your version of getSignedDistance() here, as it solves a few edge cases for me in the offsetting code. I was less lucky with the new subdivide(), which breaks quite a few of our existing tests.

[roissard]

@iconexperience I think the code you submitted is not correct.

When rewriting:

Math.sqrt(vx*vx+vy*vy)

into:

vy * Math.sqrt(1 + (vx * vx) / (vy * vy))

The sign of vy may break the equivalence, it should be:

Math.abs(vy) * Math.sqrt(1 + (vx * vx) / (vy * vy))

The fixed code should be:

((x - px) * vy - (y - py) * vx) / ( Math.abs(vy) > Math.abs(vx) ? Math.abs(vy) * Math.sqrt(1 + (vx * vx) / (vy * vy)) : Math.abs(vx) * Math.sqrt(1 + (vy * vy) / (vx * vx)) )

[lehni]

@roissard apologies for taking so long to look into this, and thank you for the submission of the PR! I am going to check this out now

[lehni]

@roissard I'm testing your code with the example I posted in https://github.com/paperjs/paper.js/issues/1262#issue-210273593 but I'm not seeing any change there? Are you sure this solves this issue here too?