bezier.hazmat.curve_helpers module¶
Pure Python implementations of helper methods for Bézier curves.

bezier.hazmat.curve_helpers.
make_subdivision_matrices
(degree)¶ Make the matrix used to subdivide a curve.
Note
This is a helper for
subdivide_nodes()
. It does not have a Fortran speedup because it is only used by a function which has a Fortran speedup. Parameters
degree (int) – The degree of the curve.
 Returns
The matrices used to convert the nodes into left and right nodes, respectively.
 Return type

bezier.hazmat.curve_helpers.
subdivide_nodes
(nodes)¶ Subdivide a curve into two subcurves.
Does so by taking the unit interval (i.e. the domain of the curve) and splitting it into two subintervals by splitting down the middle.
Note
There is also a Fortran implementation of this function, which will be used if it can be built.
 Parameters
nodes (numpy.ndarray) – The nodes defining a Bézier curve.
 Returns
The nodes for the two subcurves.
 Return type

bezier.hazmat.curve_helpers.
evaluate_multi
(nodes, s_vals)¶ Computes multiple points along a curve.
Does so via a modified Horner’s method for each value in
s_vals
rather than using the de Casteljau algorithm.Note
There is also a Fortran implementation of this function, which will be used if it can be built.
 Parameters
nodes (numpy.ndarray) – The nodes defining a curve.
s_vals (numpy.ndarray) – Parameters along the curve (as a 1D array).
 Returns
The evaluated points on the curve as a two dimensional NumPy array, with the columns corresponding to each
s
value and the rows to the dimension. Return type

bezier.hazmat.curve_helpers.
evaluate_multi_barycentric
(nodes, lambda1, lambda2)¶ Evaluates a Bézier typefunction.
Of the form
\[B(\lambda_1, \lambda_2) = \sum_j \binom{n}{j} \lambda_1^{n  j} \lambda_2^j \cdot v_j\]for some set of vectors \(v_j\) given by
nodes
.Does so via a modified Horner’s method for each pair of values in
lambda1
andlambda2
, rather than using the de Casteljau algorithm.Note
There is also a Fortran implementation of this function, which will be used if it can be built.
 Parameters
nodes (numpy.ndarray) – The nodes defining a curve.
lambda1 (numpy.ndarray) – Parameters along the curve (as a 1D array).
lambda2 (numpy.ndarray) – Parameters along the curve (as a 1D array). Typically we have
lambda1 + lambda2 == 1
.
 Returns
The evaluated points as a two dimensional NumPy array, with the columns corresponding to each pair of parameter values and the rows to the dimension.
 Return type

bezier.hazmat.curve_helpers.
vec_size
(nodes, s_val)¶ Compute \(\B(s)\_2\).
Note
This is a helper for
compute_length()
and does not have a Fortran speedup.Intended to be used with
functools.partial()
to fill in the value ofnodes
and create a callable that only acceptss_val
. Parameters
nodes (numpy.ndarray) – The nodes defining a curve.
s_val (float) – Parameter to compute \(B(s)\).
 Returns
The norm of \(B(s)\).
 Return type

bezier.hazmat.curve_helpers.
compute_length
(nodes)¶ Approximately compute the length of a curve.
If
degree
is \(n\), then the Hodograph curve \(B'(s)\) is degree \(d = n  1\). Using this curve, we approximate the integral:\[\int_{B\left(\left[0, 1\right]\right)} 1 \, d\mathbf{x} = \int_0^1 \left\lVert B'(s) \right\rVert_2 \, ds\]using QUADPACK (via SciPy).
Note
There is also a Fortran implementation of this function, which will be used if it can be built.
 Parameters
nodes (numpy.ndarray) – The nodes defining a curve.
 Returns
The length of the curve.
 Return type
 Raises
ValueError – If
nodes
has zero columns.

bezier.hazmat.curve_helpers.
elevate_nodes
(nodes)¶ Degreeelevate a Bézier curve.
Does this by converting the current nodes \(v_0, \ldots, v_n\) to new nodes \(w_0, \ldots, w_{n + 1}\) where
\[\begin{split}\begin{align*} w_0 &= v_0 \\ w_j &= \frac{j}{n + 1} v_{j  1} + \frac{n + 1  j}{n + 1} v_j \\ w_{n + 1} &= v_n \end{align*}\end{split}\]Note
There is also a Fortran implementation of this function, which will be used if it can be built.
 Parameters
nodes (numpy.ndarray) – The nodes defining a curve.
 Returns
The nodes of the degreeelevated curve.
 Return type

bezier.hazmat.curve_helpers.
de_casteljau_one_round
(nodes, lambda1, lambda2)¶ Perform one round of de Casteljau’s algorithm.
Note
This is a helper for
specialize_curve()
. It does not have a Fortran speedup because it is only used by a function which has a Fortran speedup.The weights are assumed to sum to one.
 Parameters
nodes (numpy.ndarray) – Control points for a curve.
lambda1 (float) – First barycentric weight on interval.
lambda2 (float) – Second barycentric weight on interval.
 Returns
The nodes for a “blended” curve one degree lower.
 Return type

bezier.hazmat.curve_helpers.
specialize_curve
(nodes, start, end)¶ Specialize a curve to a reparameterization
Note
This assumes the curve is degree 1 or greater but doesn’t check.
Note
There is also a Fortran implementation of this function, which will be used if it can be built.
 Parameters
nodes (numpy.ndarray) – Control points for a curve.
start (float) – The start point of the interval we are specializing to.
end (float) – The end point of the interval we are specializing to.
 Returns
The control points for the specialized curve.
 Return type

bezier.hazmat.curve_helpers.
evaluate_hodograph
(s, nodes)¶ Evaluate the Hodograph curve at a point \(s\).
The Hodograph (first derivative) of a Bézier curve degree \(d = n  1\) and is given by
\[B'(s) = n \sum_{j = 0}^{d} \binom{d}{j} s^j (1  s)^{d  j} \cdot \Delta v_j\]where each forward difference is given by \(\Delta v_j = v_{j + 1}  v_j\).
Note
There is also a Fortran implementation of this function, which will be used if it can be built.
 Parameters
nodes (numpy.ndarray) – The nodes of a curve.
s (float) – A parameter along the curve at which the Hodograph is to be evaluated.
 Returns
The point on the Hodograph curve (as a two dimensional NumPy array with a single row).
 Return type

bezier.hazmat.curve_helpers.
get_curvature
(nodes, tangent_vec, s)¶ Compute the signed curvature of a curve at \(s\).
Computed via
\[\frac{B'(s) \times B''(s)}{\left\lVert B'(s) \right\rVert_2^3}\]>>> nodes = np.asfortranarray([ ... [1.0, 0.75, 0.5, 0.25, 0.0], ... [0.0, 2.0 , 2.0, 2.0 , 0.0], ... ]) >>> s = 0.5 >>> tangent_vec = evaluate_hodograph(s, nodes) >>> tangent_vec array([[1.], [ 0.]]) >>> curvature = get_curvature(nodes, tangent_vec, s) >>> curvature 12.0
Note
There is also a Fortran implementation of this function, which will be used if it can be built.
 Parameters
nodes (numpy.ndarray) – The nodes of a curve.
tangent_vec (numpy.ndarray) – The already computed value of \(B'(s)\)
s (float) – The parameter value along the curve.
 Returns
The signed curvature.
 Return type

bezier.hazmat.curve_helpers.
newton_refine
(nodes, point, s)¶ Refine a solution to \(B(s) = p\) using Newton’s method.
Computes updates via
\[\mathbf{0} \approx \left(B\left(s_{\ast}\right)  p\right) + B'\left(s_{\ast}\right) \Delta s\]For example, consider the curve
\[\begin{split}B(s) = \left[\begin{array}{c} 0 \\ 0 \end{array}\right] (1  s)^2 + \left[\begin{array}{c} 1 \\ 2 \end{array}\right] 2 (1  s) s + \left[\begin{array}{c} 3 \\ 1 \end{array}\right] s^2\end{split}\]and the point \(B\left(\frac{1}{4}\right) = \frac{1}{16} \left[\begin{array}{c} 9 \\ 13 \end{array}\right]\).
Starting from the wrong point \(s = \frac{3}{4}\), we have
\[\begin{split}\begin{align*} p  B\left(\frac{1}{2}\right) &= \frac{1}{2} \left[\begin{array}{c} 3 \\ 1 \end{array}\right] \\ B'\left(\frac{1}{2}\right) &= \frac{1}{2} \left[\begin{array}{c} 7 \\ 1 \end{array}\right] \\ \Longrightarrow \frac{1}{4} \left[\begin{array}{c c} 7 & 1 \end{array}\right] \left[\begin{array}{c} 7 \\ 1 \end{array}\right] \Delta s &= \frac{1}{4} \left[\begin{array}{c c} 7 & 1 \end{array}\right] \left[\begin{array}{c} 3 \\ 1 \end{array}\right] \\ \Longrightarrow \Delta s &= \frac{2}{5} \end{align*}\end{split}\]>>> nodes = np.asfortranarray([ ... [0.0, 1.0, 3.0], ... [0.0, 2.0, 1.0], ... ]) >>> curve = bezier.Curve(nodes, degree=2) >>> point = curve.evaluate(0.25) >>> point array([[0.5625], [0.8125]]) >>> s = 0.75 >>> new_s = newton_refine(nodes, point, s) >>> 5 * (new_s  s) 2.0
On curves that are not “valid” (i.e. \(B(s)\) is not injective with nonzero gradient), Newton’s method may break down and converge linearly:
>>> nodes = np.asfortranarray([ ... [ 6.0, 2.0, 2.0, 6.0], ... [3.0, 3.0, 3.0, 3.0], ... ]) >>> curve = bezier.Curve(nodes, degree=3) >>> expected = 0.5 >>> point = curve.evaluate(expected) >>> point array([[0.], [0.]]) >>> s_vals = [0.625, None, None, None, None, None] >>> np.log2(abs(expected  s_vals[0])) 3.0 >>> s_vals[1] = newton_refine(nodes, point, s_vals[0]) >>> np.log2(abs(expected  s_vals[1])) 3.983... >>> s_vals[2] = newton_refine(nodes, point, s_vals[1]) >>> np.log2(abs(expected  s_vals[2])) 4.979... >>> s_vals[3] = newton_refine(nodes, point, s_vals[2]) >>> np.log2(abs(expected  s_vals[3])) 5.978... >>> s_vals[4] = newton_refine(nodes, point, s_vals[3]) >>> np.log2(abs(expected  s_vals[4])) 6.978... >>> s_vals[5] = newton_refine(nodes, point, s_vals[4]) >>> np.log2(abs(expected  s_vals[5])) 7.978...
Due to roundoff, the Newton process terminates with an error that is not close to machine precision \(\varepsilon\) when \(\Delta s = 0\).
>>> s_vals = [0.625] >>> new_s = newton_refine(nodes, point, s_vals[1]) >>> while new_s not in s_vals: ... s_vals.append(new_s) ... new_s = newton_refine(nodes, point, s_vals[1]) ... >>> terminal_s = s_vals[1] >>> terminal_s == newton_refine(nodes, point, terminal_s) True >>> 2.0**(31) <= abs(terminal_s  0.5) <= 2.0**(28) True
Due to roundoff near the cusp, the final error resembles \(\sqrt{\varepsilon}\) rather than machine precision as expected.
Note
There is also a Fortran implementation of this function, which will be used if it can be built.
 Parameters
nodes (numpy.ndarray) – The nodes defining a Bézier curve.
point (numpy.ndarray) – A point on the curve.
s (float) – An “almost” solution to \(B(s) = p\).
 Returns
The updated value \(s + \Delta s\).
 Return type

bezier.hazmat.curve_helpers.
locate_point
(nodes, point)¶ Locate a point on a curve.
Does so by recursively subdividing the curve and rejecting subcurves with bounding boxes that don’t contain the point. After the subcurves are sufficiently small, uses Newton’s method to zoom in on the parameter value.
Note
This assumes, but does not check, that
point
isD x 1
, whereD
is the dimension thatcurve
is in.Note
There is also a Fortran implementation of this function, which will be used if it can be built.
 Parameters
nodes (numpy.ndarray) – The nodes defining a Bézier curve.
point (numpy.ndarray) – The point to locate.
 Returns
The parameter value (\(s\)) corresponding to
point
orNone
if the point is not on thecurve
. Return type
 Raises
ValueError – If the standard deviation of the remaining start / end parameters among the subdivided intervals exceeds a given threshold (e.g. \(2^{20}\)).

bezier.hazmat.curve_helpers.
reduce_pseudo_inverse
(nodes)¶ Performs degreereduction for a Bézier curve.
Does so by using the pseudoinverse of the degree elevation operator (which is overdetermined).
Note
There is also a Fortran implementation of this function, which will be used if it can be built.
 Parameters
nodes (numpy.ndarray) – The nodes in the curve.
 Returns
The reduced nodes.
 Return type
 Raises
UnsupportedDegree – If the degree is not 1, 2, 3 or 4.

bezier.hazmat.curve_helpers.
projection_error
(nodes, projected)¶ Compute the error between
nodes
and the projected nodes.Note
This is a helper for
maybe_reduce()
, which is in turn a helper forfull_reduce()
. Hence there is no corresponding Fortran speedup.For now, just compute the relative error in the Frobenius norm. But, we may wish to consider the error per row / point instead.
 Parameters
nodes (numpy.ndarray) – Nodes in a curve.
projected (numpy.ndarray) – The
nodes
projected into the space of degreeelevated nodes.
 Returns
The relative error.
 Return type

bezier.hazmat.curve_helpers.
maybe_reduce
(nodes)¶ Reduce nodes in a curve if they are degreeelevated.
Note
This is a helper for
full_reduce()
. Hence there is no corresponding Fortran speedup.We check if the nodes are degreeelevated by projecting onto the space of degreeelevated curves of the same degree, then comparing to the projection. We form the projection by taking the corresponding (right) elevation matrix \(E\) (from one degree lower) and forming \(E^T \left(E E^T\right)^{1} E\).
 Parameters
nodes (numpy.ndarray) – The nodes in the curve.
 Returns
Pair of values. The first indicates if the
nodes
were reduced. The second is the resulting nodes, either the reduced ones or the original passed in. Return type
Tuple
[bool
,numpy.ndarray
] Raises
UnsupportedDegree – If the curve is degree 5 or higher.

bezier.hazmat.curve_helpers.
full_reduce
(nodes)¶ Apply degree reduction to
nodes
until it can no longer be reduced.Note
There is also a Fortran implementation of this function, which will be used if it can be built.
 Parameters
nodes (numpy.ndarray) – The nodes in the curve.
 Returns
The fully degreereduced nodes.
 Return type