-
Notifications
You must be signed in to change notification settings - Fork 1.2k
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Improve overlap detection. #1262
Comments
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 |
That's a very interesting thought. How would we then find the beginning / end of the overlap area? This could happen in addition to |
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. |
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 ((x-px) * vy - (y-py) * vx) / Math.sqrt(vx * vx + vy * vy);
((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 (2) My second idea was to improve the precision of 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. |
Here is another example case that should result in an overlap, but instead it finds 12 (or 14 in the current version) intersections. |
@iconexperience I've finally adopted your version of |
@iconexperience I think the code you submitted is not correct. When rewriting:
into:
The sign of
The fixed code should be:
|
@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 |
@roissard I'm testing your code with the example I posted in #1262 (comment) but I'm not seeing any change there? Are you sure this solves this issue here too? |
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.
The text was updated successfully, but these errors were encountered: