Checking if two cubic Bézier curves intersect

by

Intersection of Bezier curves is done by the (very cool) Asymptote vector graphics language: look for intersect() here.

Although they don’t explain the algorithm they actually use there, except to say that it’s from p. 137 of “The Metafont Book”, it appears that the key to it is two important properties of Bezier curves (which are explained elsewhere on that site though I can’t find the page right now):

  • A Bezier curve is always contained within the bounding box defined by its 4 control points
  • A Bezier curve can always be subdivided at an arbitrary t value into 2 sub-Bezier curves

With these two properties and an algorithm for intersecting polygons, you can recurse to arbitrary precision:

bezInt(B1, B2):

  1. Does bbox(B1) intersect bbox(B2)?
    • No: Return false.
    • Yes: Continue.
  2. Is area(bbox(B1)) + area(bbox(B2)) < threshold?
    • Yes: Return true.
    • No: Continue.
  3. Split B1 into B1a and B1b at t = 0.5
  4. Split B2 into B2a and B2b at t = 0.5
  5. Return bezInt(B1a, B2a) ||
    bezInt(B1a, B2b) ||
    bezInt(B1b, B2a) ||
    bezInt(B1b, B2b).

This will be fast if the curves don’t intersect — is that the usual case?

[EDIT] It looks like the algorithm for splitting a Bezier curve in two is called de Casteljau’s algorithm.

More Related Contents:

  1. c++ Making a code that displays equations and keep getting the “expression must have integral or unscoped enum type” error
  2. Pointers with c++ [duplicate]
  3. No member named ” in ”. Why did it happen and how do I fix it?
  4. What does the namespace std add? (C++) [closed]
  5. How do I print the content of a file?
  6. When can I use a forward declaration?
  7. to_string is not a member of std, says g++ (mingw)
  8. What are inline namespaces for?
  9. Are “anonymous structs” standard? And, really, what *are* they?
  10. Initializing a two dimensional std::vector
  11. Arrow operator (->) in function heading
  12. How to declare a vector of atomic in C++
  13. Intrinsics for CPUID like informations?
  14. Does a c++ struct have a default constructor?
  15. Conditional operator used in cout statement
  16. How to copy contents of a directory into build directory after make with CMake?
  17. How does weak_ptr work?
  18. How to fix .pch file missing on build?
  19. sine wave that slowly ramps up frequency from f1 to f2 for a given time
  20. Can C++ code be valid in both C++03 and C++11 but do different things?
  21. What is the maximum length in chars needed to represent any double value?
  22. How to use libraries compiled with MingW in MSVC?
  23. Uses for negative zero floating point value?
  24. C++11 is_same type trait for templates
  25. Why doesn’t C++ make the structure tighter?
  26. How serious is the new/delete operator mismatch error?
  27. Why doesn’t c++ have &&= or ||= for booleans?
  28. Linear index upper triangular matrix
  29. How to convert a const char * to std::string [duplicate]
  30. C / C++ How to copy a multidimensional char array without nested loops?

Leave a Comment