Cubic Equations And The Complex Field

One thing I wish to see in languages such as PHP is to find them supporting the complex type. Complex numbers are more than vectors in 2D, and I wish to see expression containing them parsed just like the ones with real numbers. Python supports them, and you have to import ‘cmath’ to use functions of a complex variable. To import cmath type

import cmath

For example, complex numbers are useful in solving cubic equations even if all its roots are real. And cubic equations can be used for Bézier curve manipulations.

Following is the Cardan formula for solving a cubic equation

Be x^3 + ax^2 + bx + c=0 a cubic equation.

Step 1

Convert the equation to the form latex y^3 + py + q = 0
Use the Taylor series formula, to find a k, such that y=x-k:
Be P(x) = x^3 + ax^2 + bx + c
Then, P(x) = P(k) + P'(k)x + {P''(k)x^2 \over 2} + {P'''(k)x^3 \over 6}
P(k) = k^3 + ak^2 + bk + c
P'(k) = 3k^2 + 2ak + b
P''(k) = 6k + 2a
P'''(k) = 6

Because P”(k)=0, 6k + 2a=0, thus:
k= - {a \over 3} .
p=P'(k) = b - {a^2 \over 3}
q=P(k) = {2a^3 \over 27}  - {ba \over 3} + c

For example,
x^3 - 7x^2 +14x - 8 = 0
will become
y^3 -2{1 \over 3}y - {20 \over 27} = 0
In Python:

a = -7
b = 14
c = -8
p = b - a**2 / 3.
q = 2*a**3 / 27. - b*a/3. - 8

Step 2

Find 2 numbers u and v that will help us solve the equation. If y=u+v , then the new equation will be:
u^3 + v^3 + (p + 3uv)(u + v) + q = 0
We can find u,v such that (p + 3uv) = 0,
Thus,

and latex u^3 + v^3 = -q
Since p+3uv=0, u^3{v^3} = {-p^3 \over 27}
From both equations, we get that latex u^3 and latex v^3 are the roots of the quadratic equations
t^2 +qt - {q^3 \over 27} = 0
The roots of the quadratic equations are:
(1) u^3 = - {q \over 2} + \sqrt{{q^2 \over 4} + {p^3 \over 27}}
(2) v^3 = - {q \over 2} - \sqrt{{q^2 \over 4} + {p^3 \over 27}}
In Python, the inner root can be computed using:

innerRoot = cmath.sqrt(q**2 / 4. + p**3/27.)

Now, u and v are cubic roots of (1) and (2) respectively. They must satisfy 3uv=-p.
In Python, you get your initial u using:

u=(-q / 2. + innerRoot) ** (1/3.)

If the pair u,v does not satisfy 3uv = -p, you can multiply your v by
$latex-1 + i \sqrt 3 \over 2 $
until the pair satisfies the condition.
Now, having a solution, get the next by multiplying u by $latex-1 + i \sqrt 3 \over 2 and v by latex-1 – i \sqrt 3 \over 2

In our example:
u^3 = {20 \over 54} + \sqrt{{-263 \over 729}}
v^3 = {20 \over 54} - \sqrt{{-263 \over 729}}

Let’s find our three solutions:
u_1= (0.8333333333333335+0.28867513459481187j), v_1=(0.8333333333333335-0.28867513459481187j)
Thus, latex $y_1 = (1.666666666666667+0j)$
u_2 = (-0.6666666666666659+0.5773502691896264j), v_2=(-0.6666666666666657-0.5773502691896264j)
Thus, y_2 = (-1.3333333333333317+0j)
u_3 = (-0.1666666666666676-0.8660254037844383j), v_3=(-0.1666666666666677+0.866025403784438j)
Thus, y_3 = (-0.3333333333333353-2.220446049250313e-16j)

(The above values are output from Python script. The real results look much better.)
Now, to get the roots of the original equation, add k={-a \over 3} to each y.
In our example,
k = 2{1 \over 3}
Thus,
x_1 = 4, x_2=1, x_3=2

Writing expressions is much easier and more readable when the language supports the complex type.

Advertisements

Bézier Curves

The Bézier curve is a popular way to draw curves in graphic editors such as GIMP and Inkscape. A curve of degree n is defined using n+1 points, where the first and last are the start and end points of the curve, respectively, and the rest are control points.
For example:
fff
The curve in the image above is a cubic Bézier curve. It has start and end points (filled with blue) and two control points (with no fill).
Each control point is attached by a straight line to a start or an end point, for a reason:

  • The control points allows the user to control the curve intuitively.
  • The straight line between the start(or end) point and its control point is tangent to the curve at the start(or end) point.

The Definition

A Bézier curve is defined as the collection of points that are the result of the function
B(t) for every t in [0,1].
A linear Bézier is simply a straight line between to points P0 and P1. The function is:
(1 – t)BP0 + tBP1

For n>1, Be P0, P1 … Pn the list of the curve’s points. Then the curve’s function is defined as
BP0P1…Pn(t) = (t – 1)BP0P1…Pn-1(t) + tBP1P2…Pn(t)

Or, in its explicit form:

(Not a very precise definition because 00 is not a number, so use the value 1 instead.)

This equation can be proved easily using the Pascal triangle.
From the explicit definition, you can see that the translation is done by adding the same coordinates to which of the curves start, end and control points.
because:
Rotations and translations are done by a transform matrix. So, if T is a transform matrix:
TBP1,P2,…Pn = BTP1,TP2,…TPn

About Tangents

Now, in a Bézier curve, BP0P1…Pn(t), The line P0 – P1 is tangent to the curve at point P0, and Pn – Pn-1 is tangent to the curve at point Pn

To prove this we’ll have to show that the derivative of a Bézier curve of degree n at the start and end points is a non-zero scalar multiplied by the difference between P1 and P0, and between Pn and Pn-1.
That scalar is n.

For n=1;
BP0,P1 = (1 – t)P0 + tP1
Let’s derive:
B’P0,P1 = -P0 + P1

Good!

Let’s assume it’s correct for n, and prove for n+1
BP0,P1…,Pn+1(t) = (1 – t)BP0,P1…,Pn(t) + tBP1,P2…,Pn+1(t)
Let’s derive:
B’P0,P1…,Pn+1(t) = -BP0,P1…,Pn(t) + (1-t)B’P0,P1…,Pn(t) + BP1,P2…,Pn+1(t) + tB’P1,P2…,Pn+1(t)

Now, to get the tangent to the curve at p0, let;s assign t=0:
B’P0,P1…,Pn+1(0) = -BP0,P1…,Pn(0) + B’P0,P1…,Pn(0) + BP1,P2…,Pn+1(0) =
= – P0 + n(P1 – P0) + P1 = (n+1)(P1 – P0)

Good!
Now, to get the tangent to the curve at p0, let;s assign t=1:
B’P0,P1…,Pn+1(1) = -BP0,P1…,Pn(1) + BP1,P2…,Pn+1(1) + B’P1,P2…,Pn+1(1) =
= – Pn + Pn+1 + n(Pn+1 – Pn) + P1 = (n+1)(Pn+1 – Pn)

QED

SVG supports Bézier curves of up to the third degree. A path consisting of such curves are good approximations of shapes provided that you have enough points.