Point of intersection between bezier curve and circle

3
votes

I am aiming to create the following (a directed arrow that connects two nodes) : Aim

At the moment I have this (a quadratic bezier curve drawn from the center point of one node to the center of another):

Current

(Note I have drawn the bezier above the nodes to show where it begins and ends)

I need a method - heuristic or otherwise - to calculate the point of intersection (circled in red, above) between the bezier curve and the node's (ellipse) circumference.

With this, I could calculate the angle between the node center and the point of intersection to draw the arrow head lines at the correct location and angle.

As a last resort, I could use the quadratic Bézier formula to generate a list of points that lie along the curve and also generate a list of points that lie on the circumference of the circle and use one of the two coordinates that have the least euclidian distance between each other as my intersection point. I'm hoping any answers can leverage geometry or whatever else to better solve it.

1
processinggeometrybezier
Does this help any? stackoverflow.com/q/1073336/2754173 – Geezer
@SkepticalEmpiricist That seems concerned with straight line intersection (rather than bezier curves) and is a more generic representation of the problem (it may find two, or zero, points of intersection). Since I know the bezier curve and the circle will always intersect once in the problem I raise, perhaps the solution for my question could be more simple. – micycle
Found this for the applied math: math.stackexchange.com/q/436216/93685 – Geezer
And here a JavaScript library with the functionality you're looking for (among other, as it supports all kind of shapes), from which to you can check the relevant code and usage examples: github.com/thelonious/kld-intersections/blob/development/… – Geezer
Note that you wouldn't have to use the formula yourself, as Processing provides a bezierPoint() function. More info in the reference. – Kevin Workman

1 Answers

6
votes

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. enter image description here

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