Checking If Two Cubic BéZier Curves Intersect

Checking if two cubic Bézier curves intersect

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(B₁, B₂):

2. Does bbox(B₁) intersect bbox(B₂)?
   
   
   • No: Return false.
   • Yes: Continue.
3. Is area(bbox(B₁)) + area(bbox(B₂)) < threshold?
   
   
   • Yes: Return true.
   • No: Continue.
4. Split B₁ into B_1a and B_1b at t = 0.5
5. Split B₂ into B_2a and B_2b at t = 0.5
6. Return bezInt(B_1a, B_2a) ||
   bezInt(B_1a, B_2b) ||
   bezInt(B_1b, B_2a) ||
   bezInt(B_1b, B_2b).

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.

Detecting self crossing in closed Bezier curves

I have actually found a working solution which is using built in Java2D functions and is EXTREMELY fast...

Simply create a Path2D out of your curves, then create an area out of your Path2D and invoke the method Area.isSingular();

It works... See this small example.

import java.awt.Color;
import java.awt.Dimension;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.geom.Area;
import java.awt.geom.CubicCurve2D;
import java.awt.geom.Path2D;

import javax.swing.JFrame;
import javax.swing.JPanel;

public class Test {
@SuppressWarnings("serial")
public static void main(String[] args) {
    JFrame f = new JFrame("Test");
    JPanel c = new JPanel() {
        Area a;
        Path2D p;
        {
            p = new Path2D.Double();
            p.append(new CubicCurve2D.Double(0, 0, 100, 0, 150, 50, 200, 100), true);
            p.append(new CubicCurve2D.Double(200, 100, 200, 150, 150,0, 50, 100), true);
            p.append(new CubicCurve2D.Double(100, 100, 100, 50, 50, 50, 0, 0), true);
            a = new Area(p);
            setPreferredSize(new Dimension(300, 300));
        }
        @Override
        protected void paintComponent(Graphics g) {
            g.setColor(Color.black);
            ((Graphics2D)g).fill(p);
            System.out.println(a.isSingular());
        }
    };
    f.setContentPane(c);
    f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
    f.pack();
    f.setVisible(true);
}
}

Point of intersection between bezier curve and circle

The general problem is uneasy as the intersection equation is quartic ((X(t)-Xc)² + (Y(t)-Yc)²=R²), where X and Y are quadratic polynomials). If you have a quartic solver handy you can use it but you'll have to select the right root.

A more reasonable approach is just to intersect the circle with the line segment between the control points. This is approximate but probably unnoticeable if the circle radius is small.

If you want more accuracy, perform one or two Newton's iterations from this point.

How to detect, if a bezier curve intersects a specified ellipse?

You don't need that EllipseGeometry. Just check if the hit point is inside a widened path geometry of the original geometry (which may of course also be created once when _geometry is created):

protected override HitTestResult HitTestCore(PointHitTestParameters hitTestParameters)
{
    if (_geometry != null)
    {
        var widenedGeometry = _geometry.GetWidenedPathGeometry(new Pen(null, 20));

        if (widenedGeometry.FillContains(hitTestParameters.HitPoint))
        {
            return new PointHitTestResult(this, hitTestParameters.HitPoint);
        }
    }

    return null;
}

---

Related Topics