2

By defining a set of control points $P_i$ a smooth Bézier curve can be constructed. Imagine we have two sets of control points $A={P_i}$ and $B={Q_i}$ that each define a different curve, can we determine if these points collide just based on the sets $A$ and $B$? Or do we have to compute the actual curve?

enter image description here

  • You can't call both sets of points $P$! Make one of them $Q$, please! – TonyK Sep 29 '21 at 10:08
  • @TonyK changed it! – Thomas Wagenaar Sep 29 '21 at 11:05
  • OK, I suppose changing the diagram too would be hard work :-) BTW, I like the question, but I have no idea how to answer it. – TonyK Sep 29 '21 at 12:00
  • The numerical approach I've seen involves being able to calculate bounding boxes exactly (https://youtu.be/aVwxzDHniEw?t=665) and being able to subdivide a bezier curve and work out the control points of the halves. Continually subdivide, throwing out bits whose bounding boxes don't intersect until you have less than a pixel of overlap. Otherwise you're solving two degree 3 polynomial equations in two variables, which apparently amounts to solving a degree 9 polynomial equation in one variable. – TomKern Sep 29 '21 at 12:03
  • 4
    This question has been asked already: Reliable test for intersection of two Bezier curves. But I wouldn't say it has been definitively answered. – TonyK Sep 29 '21 at 12:05

1 Answers1

0

No.

If the convex hulls of the two curves’ control points do not intersect, then you can conclude that the curves themselves do not intersect (because each curve is contained within the convex hull of its control points).

But if the convex hulls do intersect, you can not make any conclusion about the intersection of the curves — maybe they intersect, or maybe they don’t. You have to do some more serious calculations to decide.

It’s easy to move around the two curves in your picture so that the convex hulls intersect but the curves don’t.

Thank you for spelling Pierre Bézier’s name correctly. Nice to see.

bubba
  • 43,483
  • 3
  • 61
  • 122