STATUS: Draft

---

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:])))

De Casteljau's Algorithm and Splitting dCB Curves

---

Aim: To further explore the relationship between control points and related polynomials

---

Image("./Images/dCB1_1.PNG")

Observe: Recall that control points can be used to define the locus of a curve.

Observe: A natural next question is how to split the curve to find control points for the remaining portion

Observe Recall from a previous notebook that the points $P_0, P_1, P_2$ and $P_3$ have a linear combination that creates the same structure as Bernstein Basis Polynomials. A generating function for this is:

For $0 \le k \le n$:

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

Let $P0, P1, P2, P3$ and $P4$ be control points with unknown coordinates, and t be an unknown value between 0 and 1.

P0, P1, P2, P3, P4, t = sp.symbols('P0, P1, P2, P3, P4, t')

Let $F1$ be a representation of a dCB curve of control points $P0, P1, P2, P3, P$, and $t$, expressed with Bernstein Basis Polynomials, created from the above generating function.

F1 = (1 - t)**4 * P0 + 4 * (1 - t)**3 * t * P1 + 6 * (1 - t)**2 * t**2 * P2 + 4 * (1 - t) * t**3 * P3 + t**4 * P4
F1

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

Observe: It is possible to extend this to an example with known coordinates.

Let $P$ be a list of known control points.

P = np.array([[0,0], [1,2], [3,3], [4,-1], [6,1]])
renderListToLatex(P)

$$\mathtt{\text{[0 0]}}$$$$\mathtt{\text{[1 2]}}$$$$\mathtt{\text{[3 3]}}$$$$\mathtt{\text{[ 4 -1]}}$$$$\mathtt{\text{[6 1]}}$$

Let $F3$ be $F1$, now evaluated with the known control point values given by $P$.

F2 = (1 - t)**4 * P[0] + 4 * (1 - t)**3 * t * P[1] + 6 * (1 - t)**2 * t**2 * P[2] + 4 * (1 - t) * t**3 * P[3] + t**4 * P[4]
F3 = [sp.expand(i) for i in F2]

renderListToLatex(F3)

$$4 t^{4} - 8 t^{3} + 6 t^{2} + 4 t$$$$15 t^{4} - 16 t^{3} - 6 t^{2} + 8 t$$

Observe: Recall from the previous notebook, that an alternate way by which to find the values of $F3$ is to use the following matrix structures that generate the polynomials related to dCB curves

• An Inverted Pascal Matrix
• A matrix that creates a $n \times n$ matrix where all entries are $0$ escept the diagnonal which are the nth row of a Pascal matrix
• A matrix of the list of control points

Observe: It is possible to test this equivalence by creating these matrix structures, and using the known control points, $P$

Let $F4$ be a function that returns an $n \times n$ Pascal matrix, and $F5$ be $F4$ with the argument $n = 5$ and inverted

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 F4(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))

F5 = F4(5).inv()
F5

$\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 $F6$ be a function that returns an $n \times n$ matrix where all entries are $0$ escept the diagnonal which are the nth row of a Pascal matrix, and let $F7$ be $F6$ evaluated at $n = 5$

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

    return(diagonalMatrix)


F7 = F6(5)
F7

$\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]$

Let $F8$ be the product of F7 (the matrix of all zeros exept the values on the diagonal which are nth row of a pascal matrix), F5 (an inverted Pascal matrix) and P (the known coordinates of the control points from a cDB curve)

$$ \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] \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] \displaystyle \left[\begin{matrix}0 & 0\\1 & 2\\3 & 3\\4 & -1\\6 & 1\end{matrix}\right]$$

F8 = F7 * F5 * P
F8

$\displaystyle \left[\begin{matrix}0 & 0\\4 & 8\\6 & -6\\-8 & -16\\4 & 15\end{matrix}\right]$

Observe: $F8$ is equivalent to $F3$, demonstrating the relationship between control points seen in the context of the gnerating functions of Bernstein Basis Polynomials, and control points seen in the context of the inverted pascal matrix and diagonal Matrix.

Observe: The expression generated from the Bernstein Basis Polynomials can be seen in columns of $F8$, where each row represents increasing powers of $t$ starting from $t^0$. The values of the polynomials are reproduced below:

$4 t^{4} - 8 t^{3} + 6 t^{2} + 4 t $

$15 t^{4} - 16 t^{3} - 6 t^{2} + 8 $

---

Aim: Use the deCasteljau algorithm to cacluate the coordinates of the locus given the control points $P_i$

---

Observe: the point $T_0$ on the graph above is a linear combination of $S0$ and $S1$ and is a number a number between 0 and 1.

Observe: It is possible to obtain a value of the point $T_0$ by passing any value $\lambda$ the above polynomials, which will return coordinates.

Observe Using a a subsitution of a value between 0 and 1 for $t$ in the polynomials above may be problematic as the results may be computationally expensive and only approximate.

Observe: An alternative way to calculate this possible to use the other lines that comprise the dCB curve to get to the value of $T_0$ in a discrete way where, for example:

$$C(A, B) = (1 - t)A + tB$$

can be used to provide control points to generate control points of $P, Q, R, S$ and ultimately $T0$

Observe From the previous notebook, it can be seen to start with $P0, P1, P2, P3$ and $P4$, the following $Q_i, R_i$ and $S_i$ values can be created:

$$ (1 - t) P_0 + P_1 $$

Let $F9$ be a function to compute $C(A, B)$ above.

def F9(B, t):
    x = [B[i - 1] * (1 - t) + B[i] * t for i in range(1,len(B))]
    
    
    return(x)

Let $Q$ be $F1$ evaluated at the control points $P$

Q = F9(P, .4)
sp.Matrix(Q)

$\displaystyle \left[\begin{matrix}0.4 & 0.8\\1.8 & 2.4\\3.4 & 1.4\\4.8 & -0.2\end{matrix}\right]$

Let $R$ be $F1$ evaluated at $Q$

R = F9(Q, .4)
sp.Matrix(R)

$\displaystyle \left[\begin{matrix}0.96 & 1.44\\2.44 & 2.0\\3.96 & 0.76\end{matrix}\right]$

Let $S$ be $F1$ evaluated at $R$

S = F9(R, .4)
sp.Matrix(S)

$\displaystyle \left[\begin{matrix}1.552 & 1.664\\3.048 & 1.504\end{matrix}\right]$

Let $T$ be $F1$ evaluated at $S$

T = F9(S, .4)
sp.Matrix(T)

$\displaystyle \left[\begin{matrix}2.1504 & 1.6\end{matrix}\right]$

Todo: Need a recursive version of this.

Observe This is algebraic rendering of the visualisation below, an algorithm to calculuate all intermediete control points between $P_0$ and $P_4$.

Observe: It is linear and thus numerically stable, and provides all control points, $P_i$ through $T0$

Image("./Images/dCB1_1.PNG")

---

Aim A natural next step after being able to derive intermediete control points is to be able to split the curve at some point on the curve

---

Observe This relates to the investigation of splines, and how to join curves together using common tangents.

Let $T_0$ be a point at which the above curve will be split.

Observe Note that the control points to undertake this, $P_0, Q_0, R_0, S_0$ and $T_0$, are already available

Consider we have

Observe: the values of $P, Q, R, S, T$ can be used in conjunction with the Bernstein Basis Polynomials to split the curve at $T0$

F14 = (1 - t)**4 * P[0] + 4 * (1 - t)**3 * t * Q[0] + 6 * (1 - t)**2 * t**2 * R[0] + 4 * (1 - t)*t**3 * S[0] + t**4 * T[0]
renderListToLatex(F14)

$$2.1504 t^{4} + 1.552 t^{3} \left(4 - 4 t\right) + 5.76 t^{2} \left(1 - t\right)^{2} + 1.6 t \left(1 - t\right)^{3}$$$$1.6 t^{4} + 1.664 t^{3} \left(4 - 4 t\right) + 8.64 t^{2} \left(1 - t\right)^{2} + 3.2 t \left(1 - t\right)^{3}$$

F14 = (1 - t)**4 * P[0] + 4 * (1 - t)**3 * t * Q[0] + 6 * (1 - t)**2 * t**2 * R[0] + 4 * (1 - t)*t**3 * S[0] + t**4 * T[0]
F14[0].expand()

$\displaystyle 0.1024 t^{4} - 0.512000000000001 t^{3} + 0.960000000000001 t^{2} + 1.6 t$

F14[1].expand()

$\displaystyle 0.383999999999999 t^{4} - 1.024 t^{3} - 0.960000000000001 t^{2} + 3.2 t$

Observe: This is equivalent to passing a value of $\lambda t$ to the polynomials based on the control points $P$:

$4 t^{4} - 8 t^{3} + 6 t^{2} + 4 t, \text{ where } t = 0.4t$

$15 t^{4} - 16 t^{3} - 6 t^{2} + 8t, \text{ where } t = 0.4t $

Let $F15$ and $F16$ be the dCB curve polynomials evaluated at $t = 0.4t$

F15 = 4 * t**4 - 8 * t**3 + 6 * t**2 + 4 * t
F15 = F15.subs(t, 0.4 * t)
F15

$\displaystyle 0.1024 t^{4} - 0.512 t^{3} + 0.96 t^{2} + 1.6 t$

F16 = 15 * t**4 - 16 * t**3 - 6 * t**2 + 8 * t
F16 = F16.subs(t, .4 * t)
F16

$\displaystyle 0.384 t^{4} - 1.024 t^{3} - 0.96 t^{2} + 3.2 t$

Observe: this shows the interrelationship between dCB curves and how to split curves using basic linear operations.