## Introduction

I needed to find the distance from a Point to a Bezier Segment. Turns out you need lot of Math tools. A polynomial class which can do simple math, derivate and find its roots. As well as Complex arithmentics.

The source can also be found on GitHub:

https://github.com/superlloyd/Poly

## Using the code

There is a **Complex.cs** class which supports simple arithmetics. ex:

var c1 = 1 + 2 * Complex.I;
var c2 = c1 * c1;
var conjugate = !c1;
Assert.AreEquals(c2 / c1, c1);

There is a **Polynomial.cs** class which supports simple arithmetics, which is defined by listing its coefficient

var X = new Polynomial(0, 1);
var x2mx = X * (1 - X) + 1;
var x3 = new Polynomial(1,0,-1,2);

It also support Pow() Derivate() and Integrate()

var Xp1 = 1 + Polynomial.X();
var X2 = Xp1.Pow(2);
Assert.AreEquals(X1, new Polynomial(1,2,1))
var X = new Polynomial(0, 1);
var X2 = 1 + X + (X^3);
Assert.AreEquals(X2.Derivate(), 1+3*(X^2));
var X = new Polynomial(0, 1);
var X2 = 1 + X;
Assert.AreEquals(X2.Integrate(), X + (X^2)/2);

It also have its most interesting method: FindRoots()

public Complex[] FindRoots(int maxIteration = 10)

Which uses the Durand-Kerner algorithm:

http://en.wikipedia.org/wiki/Durand%E2%80%93Kerner_method

It's a very simple and quick algorithm which find all the root at once. The implementation is only 55 lines long!

It will be used later to calculate distance to a Bezier curves

I also added the Bezier curves equations:

http://en.wikipedia.org/wiki/B%C3%A9zier_curve

public static Polynomial LinearBezierCurve(double p0, double p1)
{
var T = new Polynomial(0, 1);
return p0 + T * (p1 - p0);
}
public static Polynomial QuadraticBezierCurve(double p0, double p1, double p2)
{
var T = new Polynomial(0, 1);
return (1 - T) * LinearBezierCurve(p0, p1) + T * LinearBezierCurve(p1, p2);
}
public static Polynomial CubicBezierCurve(double p0, double p1, double p2, double p3)
{
var T = new Polynomial(0, 1);
return (1 - T) * QuadraticBezierCurve(p0, p1, p2) + T * QuadraticBezierCurve(p1, p2, p3);
}

## Distance to Bezier Segment

Now that I have all these basic math tools I can finally find the distance from a point to a Bezier segment!

If the curve equations is: BC(t),

The distance from P to the curve is the minimal distance of P to all the points BC(t).

To find the mimums of the distance I need to find the root / 0 of D'(t) (of the derivate of D(t))

Also t is between 0,1 for this reason I should also consider the segment extremities.

Which leave me with this very simple C# implementation of the distance:

public static double DistanceToBezier(this Point p, Point start, Point cp1, Point cp2, Point end)
{
var BX = Polynomial.CubicBezierCurve(start.X, cp1.X, cp2.X, end.X);
var BY = Polynomial.CubicBezierCurve(start.Y, cp1.Y, cp2.Y, end.Y);
var dsquare = (BX - p.X) * (BX - p.X) + (BY - p.Y) * (BY - p.Y);
var deriv = dsquare.Derivate().Normalize();
var deriveRoots = deriv.FindRoots();
return deriveRoots
.Where(x => Math.Abs(x.Imaginary) < Polynomial.Epsilon && x.Real > 0 && x.Real < 1)
.Select(x => (double)x.Real)
.Concat(new double[] { 0, 1 })
.Select(x => Math.Sqrt(dsquare.Compute(x)))
.OrderBy(x => x)
.First();
}

## Points of Interest

Bezier curve and Polynomial.FindRoots() are implemented in a very clear and simple fashion. Thanks Wikipedia!

The code code with a Utility libray (including the unit tests) and a WPF application which show live calculated point and calculated distance.

I should thanks **Jeremy Alles**, as I used his application as the basis of my visual test application.

## History

First release fo now...

Code change on GitHub: https://github.com/superlloyd/Poly