DCB1

STATUS: Draft

These notes are based on Prof. Norman Wildberger's lectures on Algebraic Calculus and de Casteljau Bezier (dCB) curves found here. They are being hosted at ladatavita.com and available from my Github repo at: https://github.com/jgab3103/Jamie-Gabriel/tree/main/MathNotebooks

In [1]:

import numpy as np
import sympy as sp
from IPython.display import HTML, IFrame
import ipywidgets as widgets
import matplotlib as mpl
from mpl_toolkits.mplot3d import Axes3D
import matplotlib.pyplot as plt
mpl.rcParams['legend.fontsize'] = 10
import pandas as pd
import itertools
from IPython.display import Image
import math



# function to print latex
def renderListToLatex(e):
    latex_rendering = []

    for i in range(len(e)):
        latex_rendering.append("$$" + sp.latex(e[i]) + "$$")
    
    return(HTML("".join(latex_rendering[0:])))

Algebraic Calculus and dCB Curves (1)¶

Aim: Introduce de Casteljau Bezier (dCB) curves as fundamental objects of Algebraic Calculus

Observe: dCB curves can be characterised computional objects in Algebraic Calculus and it is possible to view the information they hold as polynumbers

Observe: dCB curves are also referred to as polynomial paramaterised curves

Observe: dCB curves can be described with lines and control points in an affine setting.

Observe: the locus of the dCB curve is created by linear operations.

Observe Affine combination of $(1 - t) P0 + P1(t)$ determines a locus of a point on the plane.

Observe: By adding more lines and control points, more complex curves can be created. For example, cubic dCB have more control points that quadratice dCB curves.

Observe: In the Quadriatic and Cubic case of dCB cuves, the control points are also tangent lines, so they can be joined to one another.

Aim: Introduce Polynumbers to allow an algebraic representation of dCB curves

Definition A Polynumber is a list of numbers with the following properties:

Polynumbers can be undestood as ordered lists (e.g. $[4,5,6]$
Scalar multiplication is possible (e.g. $3 \times [3, 4, 5] = [9, 12, 15]$)
Addition is position-wise (e.g. $[7,3] + [-4, 2 , 8] = [3, 5, 8]$)
Trailing zeros are ignored when ascertaining equivalence (e.g. $[3,4, 0, 0] = [3, 4])$
Multiplication is defined using a Cauchy Product (e.g $[1, 2] \times [5, 2] = [5, 12, 4]$)
$[1]$ is the identity polynumber
$\alpha$ is the polynumber $[0, 1]$. Note that powers of $\alpha$ will be $[0, 0, \ldots 1]$

Definition A Polynomially Parametrized Curve is a list of 2 polynumbers:

$$ \gamma = [p, q] $$

Let $P0, P1 P2 \ldots$ be an ongoing sequence of sequence of planar control points to arbitrary but finite length

In [5]:

P0, P1, P2, P3, Q0, Q1, Q2, Q3, R0, R1, R2, R3, S0, S1, S2, S3, t, p01, p02, p11, p12, p21, p22 = sp.symbols('P0, P1, P2, P3, Q0, Q1, Q2, Q3, R0, R1, R2, R3, S0, S1, S2, S3, t, p01, p02, p11, p12, p21, p22 ')

In [6]:

F1 = sp.Eq(Q0, (1 - t) * P0 + t * P1) 
F2 = sp.Eq(Q1, (1 - t) * P1 + t * P2)
F3 = sp.Eq(Q2, (1 - t) * P2 + t * P3) 

F4 = sp.Eq(R0, (1 - t) * Q0 + t * Q1) 
F5 = sp.Eq(R1, (1 - t) * Q1 + t * Q2)
F6 = sp.Eq(R2, (1 - t) * Q2 + t * Q3) 

F7 = sp.Eq(S0, (1 - t) * R0 + t * R1) 
F8 = sp.Eq(S1, (1 - t) * R1 + t * R2)
F9 = sp.Eq(S2, (1 - t) * R2 + t * R3) 

renderListToLatex([F1, F2, F3, F4, F5, F6, F7, F8, F9])

Out[6]:

$$Q_{0} = P_{0} \left(1 - t\right) + P_{1} t$$$$Q_{1} = P_{1} \left(1 - t\right) + P_{2} t$$$$Q_{2} = P_{2} \left(1 - t\right) + P_{3} t$$$$R_{0} = Q_{0} \left(1 - t\right) + Q_{1} t$$$$R_{1} = Q_{1} \left(1 - t\right) + Q_{2} t$$$$R_{2} = Q_{2} \left(1 - t\right) + Q_{3} t$$$$S_{0} = R_{0} \left(1 - t\right) + R_{1} t$$$$S_{1} = R_{1} \left(1 - t\right) + R_{2} t$$$$S_{2} = R_{2} \left(1 - t\right) + R_{3} t$$

Observe: In the case of $Q_i$, it relates to the affine combination of $P_i$ and $P_{i + 1}$ controlled by $t$.

Observe: Locus of $Q_0$ as $t$ varies is a linear dCB curve.Note that where $P_0$ and $P_1$ are equal, this will generate a point

Observe: $R$ is a quadratic dCB curve, and $S$ is a cubic dCB curve. This can be extended to other, higher degree curves

Observe: keep on going to get the S points, leads to cubic cDB curve. For example, quartic dcb curves from 5 control points; quintic dcb curves vrom 6 control points

Let $F10$ be the rhs fo F1, in terms of $t$

Observe: this expression can be written in terms of $P_0 = [p_{01}, p_{02}]$ and $P_1 = [p_{11}, p_{12}]$ leading to a solution to $Q_0$ in terms of $p_{01}, p_{02}, p_{11}$ and $p_{12}$

In [8]:

F11 = np.array([p01, p02]) - t * (np.array([p01, p02]) - (np.array([p11, p12])))
renderListToLatex([F11[0], F11[1]])

Out[8]:

$$p_{01} - t \left(p_{01} - p_{11}\right)$$$$p_{02} - t \left(p_{02} - p_{12}\right)$$

Observe: $F11$ can be manipulated to:

$$ p_{01} + t \left(p_{11} - p_{01}\right) $$$$ p_{02} + t \left( p_{12} - p_{02}\right) $$

Let: $c_{01}, c_{02}, c_{11}$ and $c_{12}$ have the following identities

$$c_{01} = p_{01}$$$$c_{11} = p_{11} - p_{01}$$$$c_{02} = p_{02}$$$$c_{12} = p_{12} - p_{02}$$

Let: $F12$ be an equation of matrices representing the relationship between $c_{01}, c_{02}, c_{11}$ and $c_{12}$ and $p_{01}, p_{02}, p_{11}$ and $p_{12}$

In [9]:

c01, c11, c02, c12, c21, c22 = sp.symbols('c01, c11, c02, c12,  c21, c22')
F12 = sp.Eq(sp.Matrix([[c01, c02], [c11, c12]]), sp.Matrix([[p01, p02], [p11 - p01, p12 - p02]]))
F12

Out[9]:

$\displaystyle \left[\begin{matrix}c_{01} & c_{02}\\c_{11} & c_{12}\end{matrix}\right] = \left[\begin{matrix}p_{01} & p_{02}\\- p_{01} + p_{11} & - p_{02} + p_{12}\end{matrix}\right]$

Let: F13 be a verfication of the following:

$$ \left[\begin{matrix}p_{01} & p_{02}\\- p_{01} + p_{11} & - p_{02} + p_{12}\end{matrix}\right] \equiv \left[\begin{matrix}1 & 0\\-1 & 1\end{matrix}\right] \left[\begin{matrix}p_{01} & p_{02}\\p_{11} & p_{12}\end{matrix}\right] $$

In [10]:

F13 = sp.Matrix([[1, 0], [-1, 1]]) *  sp.Matrix([[p01, p02], [p11, p12]])
F13

Out[10]:

$\displaystyle \left[\begin{matrix}p_{01} & p_{02}\\- p_{01} + p_{11} & - p_{02} + p_{12}\end{matrix}\right]$

Observe: this leads to the following identity:

$$ \left[\begin{matrix}c_{01} & c_{02}\\c_{11} & c_{12}\end{matrix}\right] \equiv \left[\begin{matrix}1 & 0\\-1 & 1\end{matrix}\right] \left[\begin{matrix}p_{01} & p_{02}\\p_{11} & p_{12}\end{matrix}\right] $$

Observe: This identity demonstrates that the matrix $\left[\begin{matrix}1 & 0\\-1 & 1\end{matrix}\right]$ and its inverse $\left[\begin{matrix}1 & 0\\1 & 1\end{matrix}\right]$ can be used to move between $p_{ij}$ and $c_{ij}$ points

Let: $F14$ be a function that transforms a matrix between the points $c_{01}, c_{02}, c_{11}$ and $c_{12}$ and $p_{01}, p_{02}, p_{11}$ and $p_{12}$

In [11]:

def F14(m, currentBasis = None):
    
    toP = sp.Matrix([[1, 0], [-1, 1]]) 
    toC = sp.Matrix([[1, 1], [1, 0]]) 
    
    if currentBasis == 'p':
        return m * toP
    else:
        return m * toC

In [12]:

F14(sp.Matrix([[p01, p02 ], [p11, p12]]), currentBasis="p")

Out[12]:

$\displaystyle \left[\begin{matrix}p_{01} - p_{02} & p_{02}\\p_{11} - p_{12} & p_{12}\end{matrix}\right]$

Observe: It is possible to extend this to the quadratic Case. Recall the values of $Q_0, Q_1$ and $R_0$.

In [13]:

renderListToLatex([F1, F2, F4])

Out[13]:

$$Q_{0} = P_{0} \left(1 - t\right) + P_{1} t$$$$Q_{1} = P_{1} \left(1 - t\right) + P_{2} t$$$$R_{0} = Q_{0} \left(1 - t\right) + Q_{1} t$$

Let: F15 be $F4$ with substitions of $Q_0$ and $Q_1$, expression in powers of $t$

In [14]:

F15 = F4.subs({Q0: P0 * ( 1 - t) + P1 * t,
              Q1: P1 * (1 - t) + P2 * t})
F16 = F15.expand().rhs.factor(t)
F16

Out[14]:

$\displaystyle P_{0} + t^{2} \left(P_{0} - 2 P_{1} + P_{2}\right) + t \left(- 2 P_{0} + 2 P_{1}\right)$

Observe: This is quadratic dependence on $t$

In [15]:

F16.subs(P0, np.array([3,4]))

Out[15]:

$\displaystyle P_{0} + t^{2} \left(P_{0} - 2 P_{1} + P_{2}\right) + t \left(- 2 P_{0} + 2 P_{1}\right)$

Observe: $F16$ be written in terms of $P_0 = [p_{01}, p_{02}], P_1 = [p_{11}, p_{12}]$ and $P_2 = [p_{21}, p_{22}]$

Let $F17$ be $F16$ with substitions for $P0, P1$ and $P2$.

In [17]:

F17 = P0 + t**2 * (P0 - 2 * P1 + P2) + t * (-2 * P0 + 2 * P1)
renderListToLatex([F17[0], F17[1]])

Out[17]:

$$p_{01} + t^{2} \left(p_{01} - 2 p_{11} + p_{21}\right) + t \left(- 2 p_{01} + 2 p_{11}\right)$$$$p_{02} + t^{2} \left(p_{02} - 2 p_{12} + p_{22}\right) + t \left(- 2 p_{02} + 2 p_{12}\right)$$

Observe: This can be written as a matrix of values where the rows are progressively higher powers of $t$:

$$ \displaystyle \left[\begin{matrix}p_{01} & p_{02}\\- 2 p_{01} + 2 p_{11} & - 2 p_{02} + 2 p_{12}\\p_{01} - 2 p_{11} + p_{21} & p_{02} - 2 p_{12} + p_{22}\end{matrix}\right] $$

Observe: It is possible to equate these with values of $c_i$:

$$ \displaystyle \left[\begin{matrix}c_{01} & c_{02}\\c_{11} & c_{12}\\c_{21} & c_{22}\end{matrix}\right] = \displaystyle \left[\begin{matrix}p_{01} & p_{02}\\- 2 p_{01} + 2 p_{11} & - 2 p_{02} + 2 p_{12}\\p_{01} - 2 p_{11} + p_{21} & p_{02} - 2 p_{12} + p_{22}\end{matrix}\right] $$

Let F18 and F19 be be a matrices.

In [18]:

F18 = sp.Matrix([[1, 0, 0], [-2, 2, 0], [1, -2, 1]]) 
F19 = sp.Matrix([[p01, p02], [p11, p12], [p21, p22]])
renderListToLatex([F18, " ", F19])

Out[18]:

$$\left[\begin{matrix}1 & 0 & 0\\-2 & 2 & 0\\1 & -2 & 1\end{matrix}\right]$$$$\mathtt{\text{ }}$$$$\left[\begin{matrix}p_{01} & p_{02}\\p_{11} & p_{12}\\p_{21} & p_{22}\end{matrix}\right]$$

Let $F20$ show that $F18 \times F19$ is equivalent to

$$ \displaystyle \left[\begin{matrix}c_{01} & c_{02}\\c_{11} & c_{12}\\c_{21} & c_{22}\end{matrix}\right] $$

Observe: This creates the following relation:

$$ \displaystyle \left[\begin{matrix}c_{01} & c_{02}\\c_{11} & c_{12}\\c_{21} & c_{22}\end{matrix}\right] = \left[\begin{matrix}1 & 0 & 0\\-2 & 2 & 0\\1 & -2 & 1\end{matrix}\right] \left[\begin{matrix}p_{01} & p_{02}\\p_{11} & p_{12}\\p_{21} & p_{22}\end{matrix}\right] $$

Observe: It is possible invert $\left[\begin{matrix}1 & 0 & 0\\-2 & 2 & 0\\1 & -2 & 1\end{matrix}\right]$ to go between the $c_i$ and $p_i$ values.

Let $F21$ be the inverse of $F18$

Let $F22$ be the matrix with $c_i$ values.

In [20]:

F22 = sp.Matrix([[c01, c02], [c11, c12], [c21, c22]])
F22

Out[20]:

$\displaystyle \left[\begin{matrix}c_{01} & c_{02}\\c_{11} & c_{12}\\c_{21} & c_{22}\end{matrix}\right]$

Observe: The original $p_i$ values can be recovered by multiplying the matrix of $c_i$ values with the inverse matrix.

In [21]:

F21 * F22

Out[21]:

$\displaystyle \left[\begin{matrix}c_{01} & c_{02}\\c_{01} + \frac{c_{11}}{2} & c_{02} + \frac{c_{12}}{2}\\c_{01} + c_{11} + c_{21} & c_{02} + c_{12} + c_{22}\end{matrix}\right]$

Aim: Extend to the cubic case

Aim Extend this to higher degrees

Method: Create a general process for higher degrees of $t$

Observe: Recall the relationship:

$$\displaystyle \left[\begin{matrix}c_{01} & c_{02}\\c_{11} & c_{12}\\c_{21} & c_{22}\end{matrix}\right] = \displaystyle \left[\begin{matrix}p_{01} & p_{02}\\- 2 p_{01} + 2 p_{11} & - 2 p_{02} + 2 p_{12}\\p_{01} - 2 p_{11} + p_{21} & p_{02} - 2 p_{12} + p_{22}\end{matrix}\right] $$

Let $F23$ be the rhs of this relationship.

In [23]:

F23 = sp.Matrix([[p01, p02], 
                 [-2 * p01 + 2 * p11, -2 * p02 + 2 * p12],
                [p01 - 2 * p11 + p21, p02 - 2 * p12 + p22]])
F23

Out[23]:

$\displaystyle \left[\begin{matrix}p_{01} & p_{02}\\- 2 p_{01} + 2 p_{11} & - 2 p_{02} + 2 p_{12}\\p_{01} - 2 p_{11} + p_{21} & p_{02} - 2 p_{12} + p_{22}\end{matrix}\right]$

Observe: For either column of $F23$, it is possible to view the column as a system of linear equations and convert these to matrix of numbers.

Let $F24$ and $F25$ be a matrix tha converts equations in $p_i$ to a number matrix

In [24]:

F24 = sp.linear_eq_to_matrix(F23[:,0], p01, p11, p21)[0]
F25 = sp.linear_eq_to_matrix(F23[:,1], p02, p12, p22)[0]

renderListToLatex([F24, " ", F25])

Out[24]:

$$\left[\begin{matrix}1 & 0 & 0\\-2 & 2 & 0\\1 & -2 & 1\end{matrix}\right]$$$$\mathtt{\text{ }}$$$$\left[\begin{matrix}1 & 0 & 0\\-2 & 2 & 0\\1 & -2 & 1\end{matrix}\right]$$

Let $F26$ be a matrix of $p_i$ values.

In [25]:

F26 = sp.Matrix([[p01, p02], [p11, p12], [p21, p22]])
F26

Out[25]:

$\displaystyle \left[\begin{matrix}p_{01} & p_{02}\\p_{11} & p_{12}\\p_{21} & p_{22}\end{matrix}\right]$

Observe that $F24 \times F26 = F23$.

In [26]:

 F24 * F26

Out[26]:

$\displaystyle \left[\begin{matrix}p_{01} & p_{02}\\- 2 p_{01} + 2 p_{11} & - 2 p_{02} + 2 p_{12}\\p_{01} - 2 p_{11} + p_{21} & p_{02} - 2 p_{12} + p_{22}\end{matrix}\right]$

Observe The above steps provide a compuational way to transform the matrix

$$ \displaystyle \left[\begin{matrix}p_{01} & p_{02}\\- 2 p_{01} + 2 p_{11} & - 2 p_{02} + 2 p_{12}\\p_{01} - 2 p_{11} + p_{21} & p_{02} - 2 p_{12} + p_{22}\end{matrix}\right] $$

into

$$ \left[\begin{matrix}1 & 0 & 0\\-2 & 2 & 0\\1 & -2 & 1\end{matrix}\right] \left[\begin{matrix}p_{01} & p_{02}\\p_{11} & p_{12}\\p_{21} & p_{22}\end{matrix}\right] $$

Observe: The points $p_i$ can have the following relationship, where $P_0 = [p_{01}, p_{02}], P_1 = [p_{11}, p_{12}]$ and $P_2 = [p_{21}, p_{22}]$

In [27]:

renderListToLatex([F1, F2, F3, F4, F5, F6, F7, F8, F9])

Out[27]:

Let $F27$ be a recursive function that caclulates these values.

Aim: Link the patterns found in these matrices to Bernstein Polynomials

Observe Coeffiencients here with respect to the points $P_0, P_1, P_2$ and $P_3$ are equivalent to the Bernstein basis polynomials. For the cubic case, this is $b_{k, 3}$ for $k = 0, 1, 2, 3$. It is defined as

$$ b_{v, n} = \binom{n}{v} x ^ v (1 - x)^{n - v}$$

where $v = 0, \ldots, n$ and $\binom{n}{v}$ is the binomial coefficient

For example:

$$ b_{2, 5}(x) = \binom{5}{2}x^2(1 - x)^3 = 10x^2(1 - x)^3 $$

The above is seen in powers of $t$

Observe: This matrix of numbers connects the coordinates of the contol points to the coefficients of polynomials when it is expanded in terms of $t$, and relates to the Berstein Polynomial generating function. They can be intuited as a change of basis from $p_i$ to $c_i$

Observe The matrices produced here are invertible

Observe The general case can be clarifed by introducting the triangular Pascal on-matrix (maxel) and its inverse. The inverse is equvalent to the matrix that can be generated by the Bernstein Polynomials

Let $F28$ be a function to create a $n \times n$ Pascal matrix

In [30]:

def combination(n, r):
    return int((sp.factorial(n)) / ((sp.factorial(r)) * sp.factorial(n - r)))


def pascals_triangle(rows):
    result = [] 
    for count in range(rows): 
        row = [] 
        for element in range(count + 1): 
            row.append(combination(count, element))
        result.append(row)
    return result



def F28(size = None):
    
    n = size
    m = []
    for row in pascals_triangle(n):
        arr = np.array(row).astype(int)
        fill = np.zeros(5).astype(int)
        filled = np.concatenate((arr, fill))
        m.append(filled[0:n])
    
    return(sp.Matrix(m))

Let $F29$ be a $5 \times 5$ Pascal Triangle

In [31]:

F29 = F28(5)
F29

Out[31]:

$\displaystyle \left[\begin{matrix}1 & 0 & 0 & 0 & 0\\1 & 1 & 0 & 0 & 0\\1 & 2 & 1 & 0 & 0\\1 & 3 & 3 & 1 & 0\\1 & 4 & 6 & 4 & 1\end{matrix}\right]$

Let $F30$ be the inverse of $F29$.

In [32]:

F30 = F29.inv()
F30

Out[32]:

$\displaystyle \left[\begin{matrix}1 & 0 & 0 & 0 & 0\\-1 & 1 & 0 & 0 & 0\\1 & -2 & 1 & 0 & 0\\-1 & 3 & -3 & 1 & 0\\1 & -4 & 6 & -4 & 1\end{matrix}\right]$

Observe $F30$ is identical to $F29$ is the same result, however with the presence of minus signs. Note having a strong pattern between a matrix and its inverse is powerful

Observe: In an ongoing sense matrices are inverses

Observe. The relationship that has been established between the Pascal Matrix and Bernstein Polynomial matrix but it still needs to be clarified in terms of how this relates to change of basis matrices:

$$ \left[\begin{matrix}1 & 0\\1 & 1\end{matrix}\right] $$

and

$$ \left[\begin{matrix}1 & 0 & 0\\-2 & 2 & 0\\1 & -2 & 1\end{matrix}\right] $$

Let $F31$ be a function that creates a $n \times n$ matrix where all entries are $0$ escept the diagnonal which are the nth row of a Pascal matrix

In [33]:

def F31(n = None):
    
    pascalMatrix = F28(n)
    lastRowOfMatrix = np.array(list(pascalMatrix[n - 1,:]))
    diagonalMatrix = sp.Matrix(np.diag(lastRowOfMatrix))

    return(diagonalMatrix)


F31(5)

Out[33]:

$\displaystyle \left[\begin{matrix}1 & 0 & 0 & 0 & 0\\0 & 4 & 0 & 0 & 0\\0 & 0 & 6 & 0 & 0\\0 & 0 & 0 & 4 & 0\\0 & 0 & 0 & 0 & 1\end{matrix}\right]$

Observe: If an diagonal matrix (from $F31$) of size $m$ is multiplied with a sub-matrix, $m \times m$ of an $n \times n$ inverted Pascal matrix $F30$ the change of basis matrices between $p_i$ and $c_i$ can be obtained.

Let Let $F32, F33$ and $F34$ be examples of this.

In [34]:

F32 = F31(2) * F28(2).inv() 
F33 = F31(3) * F28(3).inv() 
F34 = F31(4) * F28(4).inv() 

renderListToLatex([F32, " ", F33, " ", F34])

Out[34]:

$$\left[\begin{matrix}1 & 0\\-1 & 1\end{matrix}\right]$$$$\mathtt{\text{ }}$$$$\left[\begin{matrix}1 & 0 & 0\\-2 & 2 & 0\\1 & -2 & 1\end{matrix}\right]$$$$\mathtt{\text{ }}$$$$\left[\begin{matrix}1 & 0 & 0 & 0\\-3 & 3 & 0 & 0\\3 & -6 & 3 & 0\\-1 & 3 & -3 & 1\end{matrix}\right]$$

Observe: The results seen in $F32, F33$ and $F34$ suggest a general relationship between the properties of a Pascal Triangle and the change of basis from the control points of dCB curves to the coeffiencts of polynumbers.

Theorem: dCB Parametrization Theorem

A polynomially parametrized curve $\gamma$ is a dCB curve, and a dCB curve is a polynomially parametrized curve. Given a parametrization, the control points $P_0, P_1, P_2 \ldots$ are determined, and given the control points, the polynumbers $p$ and $q$ in $\gamma = [p, q]$ are determined. This provides a bridge from the algebraic/geometric side (a polynomially parametrized cuve) to a discrete object (the dCB control points)