Take the 2-minute tour ×

I've been working on a project where I use Bezier paths to draw the curves I need. Each basic shape in my project consists of three cubic Bezier curves arranged end to end so that the slopes match where they meet.

The basic problem I need to solve is whether the compound curve made of the three Bezier curves intersects with itself. After thinking about it for a while, I've figured out that given the constraints of the curves, I can simplify the task to something else:

The curvature of each of the three Bezier paths should be opposite in curvature direction relative to the curve it's abutted to. In other words, there should be an inflection point where one bezier curve abuts to another one. If that is not the case, I want to reject the parameter set that generated the curves and select a different set.

In any case, my basic question is how to detect whether there is an inflection point where the curves abut each other.

In the illustration, each of the three Bezier curves is shown using a different color. The left black curve curves in the opposite direction from the red curve at the point where they meet, but the right black curve curves in the same direction. There is an inflection point where the red and left black curve meet but not where the red and right black curve meet.

Looping Bezier Path

Edit: Below, I've added another image, showing the polygon enclosing the Bezier path. The crossing lines of the polygon, shown in the black curve, tests for an inflection point, not a loop. I'm guessing that one curve intersecting another can be tested by checking whether the enclosing polygons intersect, as illustrated by the red and blue curves. Bezier Path with control points polygon

P.S. Since there has been some question about the constraints, I will list some of them here:

  • The left most point and the rightmost point have the same y value.
  • The x value of the control point of the leftmost point is less than
    the x value of the control point of the rightmost point. This keeps
    the black and blue curves from intersecting each other.
  • The slope at the leftmost and rightmost points is within about +/- 10 degrees of horizontal.
  • The intersection of the black and red curves, and the intersection of the red and blue curves divide the full curve in approximately thirds. I don't have exact numbers, but a sample bound would be that the x value of the left end of the red curve is somewhere between 25% and 40% of the x value of the rightmost point.
  • The y value of the points of intersection are +/- some small fraction of the overall width.
  • The slope at the intersections is > 0.6 and < 3.0 (positive or negative).
share|improve this question
I'm not sure if your assumption re simpler solution is right because (a) it's possible that they do not intersect despite the absence of inflection point; and (b) it's possible that they do intersect despite the presence of inflection point. Unless you have some other significant constraints on your three bezier segments that you haven't shared with us, I'm pretty sure your "find inflection point" notion doesn't work. In answer to your question, you could look at second derivatives to identify inflection points (and Google could help you there), but I don't think that helps you. –  Rob Apr 22 '13 at 7:52
Perhaps this might be one approach: stackoverflow.com/questions/13394422/… –  Rob Apr 22 '13 at 8:05
see pomax.github.io/bezierinfo/#curveintersection as well as pomax.github.io/bezierinfo/#shapes since you're technically using poly-beziers. –  Mike 'Pomax' Kamermans Apr 22 '13 at 12:43
A friend of mine suggests that checking if a cubic Bézier loops is equivalent to asking if a line connecting its 4 control points, in order, cross. So that just leaves the intersection of abutting curves. He gave a solution to that, too, which I may share here after I get to a computer. It uses cross products of point differences of the control points. –  Victor Engel Apr 22 '13 at 15:19
@VictorEngel there are infinitely many crossings of control lines that do not actually result in loops, though, but merely result in cusps. As you do not want to perform any intersection-resolution, since there is no intersection, checking for crossings is necessary but not sufficient. –  Mike 'Pomax' Kamermans Apr 22 '13 at 18:27

2 Answers 2

One of the deterministic ways to check if a bezier curve has a double-point or self-intersection is to calculate the inverse equation and evaluate the root, since the inversion equation of a bezier curve is always zero at the point of self-intersection. As detailed in this example by T.W.Sederberg –course notes. Then for detecting whether two bezier curves (red and black in the question) intersect with each other, there are a few methods, binary subdivision (easier to implement) and bezier clipping (very good balance of efficiency and code complexity), implicitization (not worth it).

But a more efficient way to do it probably is to subdivide the curves into small line-segments and find the intersection. Here is one way to do it. Especially when you are interested in knowing whether the path self-intersect, but not in an accurate point of intersection.

If you have well defined assumptions about the locations of the CVs of the piece-wise bezier curves (or poly-bezier as @Pomax mentioned above), you can try out the curvature based method as you have mentioned in your question.

Here is a plot of the curvature on a similar path as in the question. Under similar circumstances, it seems this could give you the solution you are looking for. Also, in case of a cusp, it seems this quick and dirty method still works!

double-point cusp

share|improve this answer
Thanks for taking the time to post. I can see that my original question may have broader interest than my original purpose, which was to make "random" jigsaw puzzle shapes that made some sort of sense. This will be done on the fly, so the solution I needed had to be efficient. I resorted to using trial and error to determine a set of constraints. This doesn't answer my original question, but it does solve the problem I had with the project. Essentially, there are 14 degrees of freedom, and I impose constraints on them, some depending on others. –  Victor Engel Jun 17 '13 at 18:07
No worries. I was implementing curvature calculation for bezier path and for some other issues, I was looking through related questions here.. Anyway, good luck with the project! –  hkrish Jun 17 '13 at 19:45

The equation for curvature is moderately simple. You only need the sign of the curvature, so you can skip a little math. You are basically interested in the sign of the cross product of the first and second derivatives.

This simplification only works because the curves join smoothly. Without equal tangents a more complex test would be needed.

The sign of curvature of curve P:

ax = P[1].x - P[0].x;               //  a = P1 - P0
ay = P[1].y - P[0].y;
bx = P[2].x - P[1].x - ax;          //  b = P2 - P1 - a
by = P[2].y - P[1].y - ay;
cx = P[3].x - P[2].x - bx*2 - ax;   //  c = P3 - P2 - 2b - a
cy = P[3].y - P[2].y - by*2 - ay;

bc = bx*cy - cx*by;
ac = ax*cy - cx*ay;
ab = ax*by - bx*ay;

r = ab + ac*t + bc*t*t;

Note that r is the cross product of the first and second derivative and the sign indicate the direction of curvature. Calculate r at t=1 on the left curve and at t=0 on the right curve. If the product is negative, then there is an inflection point.

If you have curves U, V and W where U is the left black, V is the middle red, and W is the right black, then calculate bc, ac, and ab above for each. The following test will be true if both joins are inflection points:

(Uab+Uac+Ubc)*(Vab) < 0 && (Vab+Vac+Vbc)*(Wab) < 0

The equation for curvature has a denominator that I have ignored. It does not affect the sign of curvature and would only be zero if the curve was a line.

Math summary:

// start with the classic bezier curve equation
P = (1-t)^3*P0 + 3*(1-t)^2*t*P1 + 3*(1-t)*t^2*P2 + t^3*P3
// convert to polynomial
P = P0 + 3*t*(P1 - P0) + 3*t^2*(P2 - 2*P1 + P0) + t^3*(P3 - 3*P2 + 3*P1 - P0)
// rename the terms to a,b,c
P = P0 + 3at + 3btt + cttt
// find the derivatives
P' = 3a + 6bt + 3ctt
P" = 6b + act
// and the cross product after some reduction
P' x P" = ab + act + bctt
share|improve this answer
Thanks, but as explained in comments to my question, my idea on simplification or restating the problem is not valid. It's a useful answer, but I hesitate to mark it as the accepted answer because of my wrong assumption. –  Victor Engel Aug 10 '13 at 23:33

Your Answer


