quadratic – PHP & More

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.

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 P₀ and P₁. The function is:
(1 – t)B_P₀ + tB_P₁

For n>1, Be P₀, P₁ … P_n the list of the curve’s points. Then the curve’s function is defined as
B_{P₀P₁…P_n}(t) = (t – 1)B_{P₀P₁…P_n-1}(t) + tB_{P₁P₂…P_n}(t)

Or, in its explicit form:

(Not a very precise definition because 0⁰ 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:
TB_{P₁,P₂,…P_n} = B_{TP₁,TP₂,…TP_n}

About Tangents

Now, in a Bézier curve, B_{P₀P₁…P_n}(t), The line P₀ – P₁ is tangent to the curve at point P₀, and P_n – P_n-1 is tangent to the curve at point P_n

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 P₁ and P₀, and between P_n and P_n-1.
That scalar is n.

For n=1;
B_P₀,P₁ = (1 – t)P₀ + tP₁
Let’s derive:
B’_P₀,P₁ = -P₀ + P₁

Good!

Let’s assume it’s correct for n, and prove for n+1
B_{P₀,P₁…,P_n+1}(t) = (1 – t)B_{P₀,P₁…,P_n}(t) + tB_{P₁,P₂…,P_n+1}(t)
Let’s derive:
B’_{P₀,P₁…,P_n+1}(t) = -B_{P₀,P₁…,P_n}(t) + (1-t)B’_{P₀,P₁…,P_n}(t) + B_{P₁,P₂…,P_n+1}(t) + tB’_{P₁,P₂…,P_n+1}(t)

Now, to get the tangent to the curve at p₀, let;s assign t=0:
B’_{P₀,P₁…,P_n+1}(0) = -B_{P₀,P₁…,P_n}(0) + B’_{P₀,P₁…,P_n}(0) + B_{P₁,P₂…,P_n+1}(0) =
= – P₀ + n(P₁ – P₀) + P₁ = (n+1)(P₁ – P₀)

Good!
Now, to get the tangent to the curve at p₀, let;s assign t=1:
B’_{P₀,P₁…,P_n+1}(1) = -B_{P₀,P₁…,P_n}(1) + B_{P₁,P₂…,P_n+1}(1) + B’_{P₁,P₂…,P_n+1}(1) =
= – P_n + P_n+1 + n(P_n+1 – P_n) + P₁ = (n+1)(P_n+1 – P_n)

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.

Tag: quadratic

Cubic Equations And The Complex Field