bezier.hazmat.triangle_intersection module

Pure Python helper methods for bezier.triangle.

bezier.hazmat.triangle_intersection.newton_refine_solve(jac_both, x_val, triangle_x, y_val, triangle_y)

Helper for newton_refine().

We have a system:

[A C][ds] = [E]
[B D][dt]   [F]

This is not a typo, A->B->C->D matches the Fortran-ordering of the data in jac_both. We solve directly rather than using a linear algebra utility:

ds = (D E - C F) / (A D - B C)
dt = (A F - B E) / (A D - B C)

Parameters:

jac_both (numpy.ndarray) – A 4 x 1 matrix of entries in a Jacobian.
x_val (float) – An x-value we are trying to reach.
triangle_x (float) – The actual x-value we are currently at.
y_val (float) – An y-value we are trying to reach.
triangle_y (float) – The actual y-value we are currently at.

Returns:

The pair of values the solve the linear system.

Return type:

Tuplefloat, float

bezier.hazmat.triangle_intersection.newton_refine(nodes, degree, x_val, y_val, s, t)

Refine a solution to \(B(s, t) = p\) using Newton’s method.

Note

There is also a Fortran implementation of this function, which will be used if it can be built.

Computes updates via

\[\begin{split}\left[\begin{array}{c} 0 \\ 0 \end{array}\right] \approx \left(B\left(s_{\ast}, t_{\ast}\right) - \left[\begin{array}{c} x \\ y \end{array}\right]\right) + \left[\begin{array}{c c} B_s\left(s_{\ast}, t_{\ast}\right) & B_t\left(s_{\ast}, t_{\ast}\right) \end{array}\right] \left[\begin{array}{c} \Delta s \\ \Delta t \end{array}\right]\end{split}\]

For example, (with weights \(\lambda_1 = 1 - s - t, \lambda_2 = s, \lambda_3 = t\)) consider the triangle

\[\begin{split}B(s, t) = \left[\begin{array}{c} 0 \\ 0 \end{array}\right] \lambda_1^2 + \left[\begin{array}{c} 1 \\ 0 \end{array}\right] 2 \lambda_1 \lambda_2 + \left[\begin{array}{c} 2 \\ 0 \end{array}\right] \lambda_2^2 + \left[\begin{array}{c} 2 \\ 1 \end{array}\right] 2 \lambda_1 \lambda_3 + \left[\begin{array}{c} 2 \\ 2 \end{array}\right] 2 \lambda_2 \lambda_1 + \left[\begin{array}{c} 0 \\ 2 \end{array}\right] \lambda_3^2\end{split}\]

and the point \(B\left(\frac{1}{4}, \frac{1}{2}\right) = \frac{1}{4} \left[\begin{array}{c} 5 \\ 5 \end{array}\right]\).

Starting from the wrong point \(s = \frac{1}{2}, t = \frac{1}{4}\), we have

\[\begin{split}\begin{align*} \left[\begin{array}{c} x \\ y \end{array}\right] - B\left(\frac{1}{2}, \frac{1}{4}\right) &= \frac{1}{4} \left[\begin{array}{c} -1 \\ 2 \end{array}\right] \\ DB\left(\frac{1}{2}, \frac{1}{4}\right) &= \frac{1}{2} \left[\begin{array}{c c} 3 & 2 \\ 1 & 6 \end{array}\right] \\ \Longrightarrow \left[\begin{array}{c} \Delta s \\ \Delta t \end{array}\right] &= \frac{1}{32} \left[\begin{array}{c} -10 \\ 7 \end{array}\right] \end{align*}\end{split}\]

../../_images/newton_refine_triangle.png

>>> import bezier
>>> import numpy as np
>>> nodes = np.asfortranarray([
...     [0.0, 1.0, 2.0, 2.0, 2.0, 0.0],
...     [0.0, 0.0, 0.0, 1.0, 2.0, 2.0],
... ])
>>> triangle = bezier.Triangle(nodes, degree=2)
>>> bool(triangle.is_valid)
True
>>> (x_val,), (y_val,) = triangle.evaluate_cartesian(0.25, 0.5)
>>> float(x_val), float(y_val)
(1.25, 1.25)
>>> s, t = 0.5, 0.25
>>> new_s, new_t = newton_refine(nodes, 2, x_val, y_val, s, t)
>>> float(32 * (new_s - s))
-10.0
>>> float(32 * (new_t - t))
7.0

Parameters:

nodes (numpy.ndarray) – Array of nodes in a triangle.
degree (int) – The degree of the triangle.
x_val (float) – The \(x\)-coordinate of a point on the triangle.
y_val (float) – The \(y\)-coordinate of a point on the triangle.
s (float) – Approximate \(s\)-value to be refined.
t (float) – Approximate \(t\)-value to be refined.

Returns:

The refined \(s\) and \(t\) values.

Return type:

Tuplefloat, float

bezier.hazmat.triangle_intersection.update_locate_candidates(candidate, next_candidates, x_val, y_val, degree)

Update list of candidate triangles during geometric search for a point.

Note

This is used only as a helper for locate_point().

Checks if the point (x_val, y_val) is contained in the candidate triangle. If not, this function does nothing. If the point is contained, the four subdivided triangles from candidate are added to next_candidates.

Parameters:

candidate (Tuplefloat, float, float, numpy.ndarray) –
A 4-tuple describing a triangle and its centroid / width. Contains
- Three times centroid x-value
- Three times centroid y-value
- ”Width” of parameter space for the triangle
- Control points for the triangle
next_candidates (list) – List of “candidate” sub-triangles that may contain the point being located.
x_val (float) – The x-coordinate being located.
y_val (float) – The y-coordinate being located.
degree (int) – The degree of the triangle.

bezier.hazmat.triangle_intersection.mean_centroid(candidates)

Take the mean of all centroids in set of reference triangles.

Note

This is used only as a helper for locate_point().

Parameters:

candidates (ListTuplefloat, float, float, numpy.ndarray) –

List of 4-tuples, each of which has been produced by locate_point(). Each 4-tuple contains

Three times centroid x-value
Three times centroid y-value
”Width” of a parameter space for a triangle
Control points for a triangle

We only use the first two values, which are triple the desired value so that we can put off division by three until summing in our average. We don’t use the other two values, they are just an artifact of the way candidates is constructed by the caller.

Returns:

The mean of all centroids.

Return type:

Tuplefloat, float

bezier.hazmat.triangle_intersection.locate_point(nodes, degree, x_val, y_val)

Locate a point on a triangle.

Note

There is also a Fortran implementation of this function, which will be used if it can be built.

Does so by recursively subdividing the triangle and rejecting sub-triangles with bounding boxes that don’t contain the point. After the sub-triangles are sufficiently small, uses Newton’s method to narrow in on the pre-image of the point.

Parameters:

nodes (numpy.ndarray) – Control points for Bézier triangle (assumed to be two-dimensional).
degree (int) – The degree of the triangle.
x_val (float) – The \(x\)-coordinate of a point on the triangle.
y_val (float) – The \(y\)-coordinate of a point on the triangle.

Returns:

The \(s\) and \(t\) values corresponding to x_val and y_val or None if the point is not on the triangle.

Return type:

OptionalTuplefloat, float

bezier.hazmat.triangle_intersection.same_intersection(intersection1, intersection2, wiggle=9.094947017729282e-13)

Check if two intersections are close to machine precision.

Note

This is a helper used only by verify_duplicates(), which in turn is only used by generic_intersect().

Parameters:

intersection1 (Intersection) – The first intersection.
intersection2 (Intersection) – The second intersection.
wiggle (Optionalfloat) – The amount of relative error allowed in parameter values.

Returns:

Indicates if the two intersections are the same to machine precision.

Return type:

bool

bezier.hazmat.triangle_intersection.verify_duplicates(duplicates, uniques)

Verify that a set of intersections had expected duplicates.

Note

This is a helper used only by generic_intersect().

Parameters:

duplicates (ListIntersection) – List of intersections corresponding to duplicates that were filtered out.
uniques (ListIntersection) – List of “final” intersections with duplicates filtered out.

Raises:

ValueError – If the uniques are not actually all unique.
ValueError – If one of the duplicates does not correspond to an intersection in uniques.
ValueError – If a duplicate occurs only once but does not have exactly one of s and t equal to 0.0.
ValueError – If a duplicate occurs three times but does not have exactly both s == t == 0.0.
ValueError – If a duplicate occurs a number other than one or three times.

bezier.hazmat.triangle_intersection.verify_edge_segments(edge_infos)

Verify that the edge segments in an intersection are valid.

Note

This is a helper used only by generic_intersect().

Parameters:

edge_infos (Optionallist) – List of “edge info” lists. Each list represents a curved polygon and contains 3-tuples of edge index, start and end (see the output of ends_to_curve()).

Raises:

ValueError – If two consecutive edge segments lie on the same edge index.
ValueError – If the start and end parameter are “invalid” (they should be between 0 and 1 and start should be strictly less than end).

bezier.hazmat.triangle_intersection.add_edge_end_unused(intersection, duplicates, intersections)

Add intersection that is classified as “unused” and on an edge end.

This is a helper for add_intersection() for intersections classified as COINCIDENT_UNUSED. It assumes that

intersection will have at least one of s == 0.0 or t == 0.0
A “misclassified” intersection in intersections that matches intersection will be the “same” if it matches both index_first and index_second and if it matches the start index exactly

Parameters:

intersection (Intersection) – An intersection to be added.
duplicates (ListIntersection) – List of duplicate intersections.
intersections (ListIntersection) – List of “accepted” (i.e. non-duplicate) intersections.

bezier.hazmat.triangle_intersection.check_unused(intersection, duplicates, intersections)

Check if a “valid” intersection is already in intersections.

This assumes that

intersection will have at least one of s == 0.0 or t == 0.0
At least one of the intersections in intersections is classified as COINCIDENT_UNUSED.

Parameters:

intersection (Intersection) – An intersection to be added.
duplicates (ListIntersection) – List of duplicate intersections.
intersections (ListIntersection) – List of “accepted” (i.e. non-duplicate) intersections.

Returns:

Indicates if the intersection is a duplicate.

Return type:

bool

bezier.hazmat.triangle_intersection.add_intersection(index1, s, index2, t, interior_curve, edge_nodes1, edge_nodes2, duplicates, intersections)

Create an Intersection and append.

The intersection will be classified as either a duplicate or a valid intersection and appended to one of duplicates or intersections depending on that classification.

Parameters:

index1 (int) – The index (among 0, 1, 2) of the first edge in the intersection.
s (float) – The parameter along the first curve of the intersection.
index2 (int) – The index (among 0, 1, 2) of the second edge in the intersection.
t (float) – The parameter along the second curve of the intersection.
interior_curve (OptionalIntersectionClassification) – The classification of the intersection, if known. If None, the classification will be computed.
edge_nodes1 (Tuplenumpy.ndarray, numpy.ndarray, numpy.ndarray) – The nodes of the three edges of the first triangle being intersected.
edge_nodes2 (Tuplenumpy.ndarray, numpy.ndarray, numpy.ndarray) – The nodes of the three edges of the second triangle being intersected.
duplicates (ListIntersection) – List of duplicate intersections.
intersections (ListIntersection) – List of “accepted” (i.e. non-duplicate) intersections.

bezier.hazmat.triangle_intersection.classify_coincident(st_vals, coincident)

Determine if coincident parameters are “unused”.

Note

This is a helper for triangle_intersections().

In the case that coincident is True, then we’ll have two sets of parameters \((s_1, t_1)\) and \((s_2, t_2)\).

If one of \(s_1 < s_2\) or \(t_1 < t_2\) is not satisfied, the coincident segments will be moving in opposite directions, hence don’t define an interior of an intersection.

Warning

In the “coincident” case, this assumes, but doesn’t check, that st_vals is 2 x 2.

Parameters:

st_vals (numpy.ndarray) – 2 X N array of intersection parameters.
coincident (bool) – Flag indicating if the intersections are the endpoints of coincident segments of two curves.

Returns:

The classification of the intersections.

Return type:

OptionalIntersectionClassification

bezier.hazmat.triangle_intersection.should_use(intersection)

Check if an intersection can be used as part of a curved polygon.

Will return True if the intersection is classified as FIRST, SECOND or COINCIDENT or if the intersection is classified is a corner / edge end which is classified as TANGENT_FIRST or TANGENT_SECOND.

Parameters:: intersection (Intersection) – An intersection to be added.
Returns:: Indicating if the intersection will be used.
Return type:: bool

bezier.hazmat.triangle_intersection.triangle_intersections(edge_nodes1, edge_nodes2, all_intersections)

Find all intersections among edges of two triangles.

This treats intersections which have s == 1.0 or t == 1.0 as duplicates. The duplicates may be checked by the caller, e.g. by verify_duplicates().

Parameters:

edge_nodes1 (Tuplenumpy.ndarray, numpy.ndarray, numpy.ndarray) – The nodes of the three edges of the first triangle being intersected.
edge_nodes2 (Tuplenumpy.ndarray, numpy.ndarray, numpy.ndarray) – The nodes of the three edges of the second triangle being intersected.
all_intersections (Callablenumpy.ndarraynumpy.ndarray, Tuplenumpy.ndarray, bool) – A helper that intersects Bézier curves. Takes the nodes of each curve as input and returns an array (2 x N) of intersections.

Returns:

4-tuple of

The actual “unique” Intersection-s
Duplicate Intersection-s encountered (these will be corner intersections)
Intersections that won’t be used, such as a tangent intersection along an edge
All the intersection classifications encountered

Return type:

Tuplelist, list, list, set

bezier.hazmat.triangle_intersection.generic_intersect(nodes1, degree1, nodes2, degree2, verify, all_intersections)

Find all intersections among edges of two triangles.

This treats intersections which have s == 1.0 or t == 1.0 as duplicates. The duplicates will be checked by verify_duplicates() if verify is True.

Parameters:

nodes1 (numpy.ndarray) – The nodes defining the first triangle in the intersection (assumed in \(\mathbf{R}^2\)).
degree1 (int) – The degree of the triangle given by nodes1.
nodes2 (numpy.ndarray) – The nodes defining the second triangle in the intersection (assumed in \(\mathbf{R}^2\)).
degree2 (int) – The degree of the triangle given by nodes2.
verify (Optionalbool) – Indicates if duplicate intersections should be checked.
all_intersections (Callablenumpy.ndarraynumpy.ndarray, Tuplenumpy.ndarray, bool) – A helper that intersects Bézier curves. Takes the nodes of each curve as input and returns an array (2 x N) of intersections.

Returns:

3-tuple of

List of “edge info” lists. Each list represents a curved polygon and contains 3-tuples of edge index, start and end (see the output of ends_to_curve()).
”Contained” boolean. If not None, indicates that one of the triangles is contained in the other.
The nodes of three edges of the first triangle being intersected followed by the nodes of the three edges of the second.

Return type:

TupleOptionallist, Optionalbool, tuple

bezier.hazmat.triangle_intersection.geometric_intersect(nodes1, degree1, nodes2, degree2, verify)

Find all intersections among edges of two triangles.

Note

There is also a Fortran implementation of this function, which will be used if it can be built.

Uses generic_intersect() with the GEOMETRIC intersection strategy.

Parameters:

nodes1 (numpy.ndarray) – The nodes defining the first triangle in the intersection (assumed in \(\mathbf{R}^2\)).
degree1 (int) – The degree of the triangle given by nodes1.
nodes2 (numpy.ndarray) – The nodes defining the second triangle in the intersection (assumed in \(\mathbf{R}^2\)).
degree2 (int) – The degree of the triangle given by nodes2.
verify (Optionalbool) – Indicates if duplicate intersections should be checked.

Returns:

3-tuple of

List of “edge info” lists. Each list represents a curved polygon and contains 3-tuples of edge index, start and end (see the output of ends_to_curve()).
”Contained” boolean. If not None, indicates that one of the triangles is contained in the other.
The nodes of three edges of the first triangle being intersected followed by the nodes of the three edges of the second.

Return type:

TupleOptionallist, Optionalbool, tuple

bezier.hazmat.triangle_intersection.algebraic_intersect(nodes1, degree1, nodes2, degree2, verify)

Find all intersections among edges of two triangles.

Uses generic_intersect() with the ALGEBRAIC intersection strategy.

Parameters:

nodes1 (numpy.ndarray) – The nodes defining the first triangle in the intersection (assumed in \(\mathbf{R}^2\)).
degree1 (int) – The degree of the triangle given by nodes1.
nodes2 (numpy.ndarray) – The nodes defining the second triangle in the intersection (assumed in \(\mathbf{R}^2\)).
degree2 (int) – The degree of the triangle given by nodes2.
verify (Optionalbool) – Indicates if duplicate intersections should be checked.

Returns:

3-tuple of

List of “edge info” lists. Each list represents a curved polygon and contains 3-tuples of edge index, start and end (see the output of ends_to_curve()).
”Contained” boolean. If not None, indicates that one of the triangles is contained in the other.
The nodes of three edges of the first triangle being intersected followed by the nodes of the three edges of the second.

Return type:

TupleOptionallist, Optionalbool, tuple