-
Notifications
You must be signed in to change notification settings - Fork 448
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
Curve-curve intersection edge cases #3352
Comments
In this case, we are failing at the first test (bounding box intersection between the two curves), so we go home early and don't do any subdivision test: seg1 = [(0.0, 0.0), (0.0, 0.25), (0.0, 0.75), (0.0, 1.0)]
seg2 = [(0.0, 0.5), (0.25, 0.5), (0.75, 0.5), (1.0, 0.5)]
bounds1 = _curve_bounds(seg1)
bounds2 = _curve_bounds(seg2)
print(bounds1, bounds2)
# (0.0, 0.0, 0.0, 1.0) (0.0, 0.5, 1.0, 0.5)
print(sectRect(bounds1, bounds2))
# (False, (0, 0, 0, 0)) |
good catch! would it be enough to special-case this edge case when both curves's bounds are flattened to perperdicular lines? |
What I would suggest is that if a curve is sufficiently line-like (for some definition...), it gets turned into a line, and then either |
maybe it's our In the classic "Graphics Gems" IV book, the chapter about curve intersections, they have the code below in the routine that checks two beziers' bounds intersection (in particular, see the comment // Test bounding box of b against bounding box of a
if( ( minax > maxbx ) || ( minay > maxby ) // Not >= : need boundary case
|| ( minbx > maxax ) || ( minby > maxay ) )
return 0; // they don't intersect
else
return 1; // they intersect |
Possibly true. But if you can get away with treating curves as lines, the maths gets a lot simpler and less liable to go wrong, so we should do that. |
use '>' instead of '>=' when comparing intersection of two rectangles, so we don't skip boundary case when the two touch Fixes #3352
the fix you proposed in #3353 only addresses the issue when both curves (or either one) can be reduced to a line; what if two curves cannot be reduced to line-like and they (as well as their bounds) actually touch one another? E.g. take these two curves: seg1 = [(0, 0), (0, 100), (100, 100), (100, 0)]
seg2 = [(0, 150), (0, 50), (100, 50), (100, 150)] Both evaluate (50, 75) at t=0.5, however they don't cross one another, they simply "touch" at that point. Do we expect that our algorithm also covers these cases? My proposed #3354 would detect these. On the other end, I'm not 100% sure if |
Let's do both! |
ok |
use '>' instead of '>=' when comparing intersection of two rectangles, so we don't skip boundary case when the two touch Fixes #3352
use '>' instead of '>=' when comparing intersection of two rectangles, so we don't skip boundary case when the two touch Fixes #3352
These two "line-like" cubics have an intersection point at (0,0.5), but
curveCurveIntersections
does not find it:The text was updated successfully, but these errors were encountered: