# 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
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.

$\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} >>> 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)
>>> triangle.is_valid
True
>>> (x_val,), (y_val,) = triangle.evaluate_cartesian(0.25, 0.5)
>>> x_val, 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)
>>> 32 * (new_s - s)
-10.0
>>> 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
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
• 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

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
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
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
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
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 (Optional [ list ]) – 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
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
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
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
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
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
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
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
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 (Optional [ bool ]) – 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
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 (Optional [ bool ]) – 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