Predicates

The predicates that we use in this package are all built from ExactPredicates.jl, avoiding degeneracies from predicates owing to floating point arithmetic. The results from predicates are based on certificates, coming from a Certificate type defined with EnumX.jl. The definition of this is below.

DelaunayTriangulation.CertificateModule
Certificate

An Enum type that represents results from a geometric predicate. Below we provide a list of available certificates, along with the function that can be used for testing if a given Certificate matches that certificate.

• Inside: is_inside
• Degenerate: is_degenerate
• Outside: is_outside
• On: is_on
• Left: is_left
• Right: is_right
• PositivelyOriented: is_positively_oriented
• NegativelyOriented: is_negatively_oriented
• Collinear: is_collinear
• None: is_none or has_no_intersections
• Single: is_single or has_one_intersection
• Multiple: is_multiple or has_multiple_intersections
• Touching: is_touching
• Legal: is_legal
• Illegal: is_illegal
• Closer: is_closer
• Further: is_further
• Equidistant: is_equidistant
• Obtuse: is_obtuse
• Acute: is_acute
• Right: is_right
• SuccessfulInsertion: is_successful_insertion
• FailedInsertion: is_failed_insertion
• PrecisionFailure: is_precision_failure
• EncroachmentFailure: is_encroachment_failure

General

Below we list some general predicates. The core ones that all other predicates are based on are:

DelaunayTriangulation.orient_predicateFunction
orient_predicate(p, q, r)

Returns ExactPredicates.orient(p, q, r), in particular we return:

• 1: (p, q, r) is positively oriented.
• 0: (p, q, r) is collinear / degenerate.
• -1: (p, q, r) is negatively oriented.
Note

The orient predicate is defined by the determinant

$$$\text{orient}(p, q, r) = \text{sgn} \det \begin{vmatrix} p_x & p_y & 1 \\ q_x & q_y & 1 \\ r_x & r_y & 1 \end{vmatrix} = \text{sgn} \det \begin{vmatrix} p_x-r_x & p_y-r_y \\ q_x-r_x & q_y-r_y \end{vmatrix}.$$$
DelaunayTriangulation.incircle_predicateFunction
incircle_predicate(a, b, c, p)

Returns ExactPredicates.incircle(a, b, c, p), in particular we return:

• 1: If p is inside the circle defined by (a, b, c).
• 0: If p is on the circle defined by (a, b, c).
• -1: If p is outside the circle defined by (a, b, c).
Note

The incircle predicate is defined by the determinant

$$$\text{incircle}(a, b, c, d) = \text{sgn} \det \begin{vmatrix} a_x & a_y & a_x^2 + a_y^2 & 1 \\ b_x & b_y & b_x62 + b_y^2 & 1 \\ c_x & c_y & c_x^2 + c_y^2 & 1 \\ d_x & d_y & d_x^2 + d_y^2 & 1 \end{vmatrix} = \text{sgn} \det \begin{vmatrix} a_x - d_x & a_y - d_y & (a_x - d_x)^2 + (a_y - d_y)^2 \\ b_x - d_x & b_y - d_y & (b_x - d_x)^2 + (b_y - d_y)^2 \\ c_x - d_x & c_y - d_y & (c_x - d_x)^2 + (c_y - d_y)^2 \end{vmatrix}.$$$
DelaunayTriangulation.parallelorder_predicateFunction
parallelorder_predicate(a, b, p, q)

Returns ExactPredicates.parallelorder(a, b, p, q), in particular we return:

• 1: q is closer to the line (a, b) than p.
• 0: p and q are equidistant from the line (a, b).
• -1: p is closer to the line (a, b) than q.
Note

The parallelorder predicate is the same as orient_predicate(b-a, q-p, 0).

In code, these predicates could be defined by (the actual definition with ExactPredicates.jl is much more involved):

_det(a, b, c, d) = a * d - b * c
_det(a, b, c, d, e, f, g, h, i) = a * _det(e, f, h, i) - d * _det(b, c, h, i) + g * _det(b, c, e, f) # cofactor expansion
function orient_predicate(a, b, c)
ax, ay = getxy(a)
bx, by = getxy(b)
cx, cy = getxy(c)
o = _det(ax - cx, ay - cy, bx - cx, by - cy)
return Int(sign(o)) # need Int for xor
end
function incircle_predicate(a, b, c, d)
ax, ay = getxy(a)
bx, by = getxy(b)
cx, cy = getxy(c)
dx, dy = getxy(d)
o = _det(ax - dx, ay - dy, (ax - dx)^2 + (ay - dy)^2,
bx - dx, by - dy, (bx - dx)^2 + (by - dy)^2,
cx - dx, cy - dy, (cx - dx)^2 + (cy - dy)^2)
return Int(sign(o)) # need Int for xor
end
function parallelorder_predicate(a, b, p, q)
return orient_predicate(b .- a, q .- p, (0.0, 0.0))
end

You could use this as a reference if you want to disconnect from using ExactPredicates.jl (or e.g. use the predicates also defined in GeometricalPredicates.jl). This could be useful if you are not too worried about robustness (although you should typically care about this, so be careful - proceed at your own peril) and just want fast code.

The other predicates are:

DelaunayTriangulation.sameside_predicateFunction
sameside_predicate(a, b, p)

Returns ExactPredicates.sameside(p, a, b) (but we redefine it here).

Note

The difference in the argument order to ExactPredicates.jl is to match the convention that the main point being tested is the last argument.

DelaunayTriangulation.opposite_signsFunction
opposite_signs(x,y)

From ExactPredicates.jl, returns true if x and y have opposite signs, and false otherwise.

DelaunayTriangulation.triangle_orientationMethod
triangle_orientation(p, q, r)

Given a triangle with coordinates (p, q, r), computes its orientation, returning:

• Certificate.PositivelyOriented: The triangle is positively oriented.
• Certificate.Degenerate: The triangle is degenerate, meaning the coordinates are collinear.
• Certificate.NegativelyOriented: The triangle is negatively oriented.

See also orient_predicate.

DelaunayTriangulation.point_position_relative_to_circleMethod
point_position_relative_to_circle(a, b, c, p)

Given a circle through the coordinates (a, b, c), assumed to be positively oriented, computes the position of p relative to the circle. In particular, returns:

• Certificate.Inside: p is inside the circle.
• Certificate.On: p is on the circle.
• Certificate.Outside: p is outside the triangle.

See also incircle_predicate.

DelaunayTriangulation.point_position_relative_to_lineMethod
point_position_relative_to_line(a, b, p)

Given a point p and the oriented line (a, b), computes the position of p relative to the line, returning:

• Certificate.Left: p is to the left of the line.
• Certificate.Collinear: p is on the line.
• Certificate.Right: p is to the right of the line.

See also orient_predicate.

DelaunayTriangulation.point_closest_to_lineMethod
point_closest_to_line(a, b, p, q)

Given a line ℓ through a and b, tests if p is closer to ℓ than q is, returning:

• Certificate.Closer: p is closer to ℓ.
• Certificate:Further: q is closer to ℓ.
• Certificate.Equidistant: p and q are the same distance from ℓ.

It is assumed that p and q are to the left of ℓ.

Note

Note that this function is same as computing numerical values for o₁ = orient(a, p, b) and o₂ = orient(a, q, b) (the determinants, not the signs) and seeing if o₁ < o₂. If indeed o₁ < o₂, then p is closer to ℓ then q. We cannot obtain values for o₁ and o₂ such that the difference o₁ - o₂ is reliable, but notice that, letting ∧ denote the exterior product, o₁ = (a - b) ∧ (p - b) and o₂ = (a - b) ∧ (q - b). Thus, o₁ - o₂ = (a - b) ∧ (p - q) = orient(b - a, p - q, 0). These differences b - a and p - q cannot be computed reliably, but we can use the relationship between orient and parallelorder_predicate to write orient(b - a, p - q, 0) = parallelorder(a, b, q, p). Thus, o₁ < o₂ if parallelorder(a, b, q, p) == -1.

DelaunayTriangulation.point_position_on_line_segmentMethod
point_position_on_line_segment(a, b, p)

Given a point p and the line segment (a, b), assuming p to be collinear with a and b, computes the position of p relative to the line segment. In particular, returns:

• Certificate.On: p is on the line segment, meaning between a and b.
• Certificate.Degenerate: Either p == a or p == b, i.e. p is one of the endpoints.
• Certificate.Left: p is off and to the left of the line segment.
• Certificate.Right: p is off and to the right of the line segment.

See also sameside_predicate.

DelaunayTriangulation.line_segment_intersection_typeMethod
line_segment_intersection_type(p, q, a, b)

Given the coordinates (p, q) and (a, b) defining two line segments, tests the number of intersections between the two segments. In particular, we return:

• Certificate.None: The line segments do not meet at any points.
• Certificate.Multiple: The closed line segments [p, q] and [a, b] meet in one or several points.
• Certificate.Single: The open line segments (p, q) and (a, b) meet in a single point.
• Certificate.Touching: One of the endpoints is on [a, b], but there are no other intersections.

See also meet_predicate.

DelaunayTriangulation.point_position_relative_to_triangleMethod
point_position_relative_to_triangle(a, b, c, p)

Given a positively oriented triangle with coordinates (a, b, c), computes the position of p relative to the triangle. In particular, returns:

• Certificate.Outside: p is outside of the triangle.
• Certificate.On: p is on one of the edges.
• Certificate.Inside: p is inside the triangle.
DelaunayTriangulation.point_position_relative_to_oriented_outer_halfplaneMethod
point_position_relative_to_oriented_outer_halfplane(a, b, p)

Given an edge with coordinates (a, b) and a point p, tests the position of p relative to the oriented outer halfplane defined by (a, b). The returned values are:

• Cert.Outside: p is outside of the oriented outer halfplane, meaning to the right of the line (a, b) or collinear with a and b but not on the line segment (a, b).
• Cert.On: p is on the line segment [a, b].
• Cert.Inside: p is inside of the oriented outer halfplane, meaning to the left of the line (a, b).
Note

The oriented outer halfplane is the union of the open halfplane defined by the region to the left of the oriented line (a, b), and the open line segment (a, b).

DelaunayTriangulation.is_legalMethod
is_legal(p, q, r, s)

Given an edge pq, incident to two triangles pqr and qps, tests if the edge pq is legal, i.e. if s is not inside the triangle through p, q, and r.

DelaunayTriangulation.triangle_line_segment_intersectionMethod
triangle_line_segment_intersection(p, q, r, a, b)

Given a triangle (p, q, r) and a line segment (a, b), tests if (a, b) intersects the triangle's interior. Returns:

• Cert.Inside: (a, b) is entirely inside (p, q, r).
• Cert.Single: (a, b) has one endpoint inside (p, q, r), and the other is outside.
• Cert.Outside: (a, b) is entirely outside (p, q, r).
• Cert.Touching: (a, b) is on (p, q, r)'s boundary, but not in its interior.
• Cert.Multiple: (a, b) passes entirely through (p, q, r). This includes the case where a point is on the boundary of (p, q, r).

Boundaries and Ghosts

Below we list some predicates for working with boundaries and ghost triangles.

DelaunayTriangulation.is_boundary_edgeMethod
is_boundary_edge(ij, adj::Adjacent)
is_boundary_edge(i, j, adj::Adjacent{I,E}) where {I,E}

Tests if the edge (i, j) is a boundary edge, meaning get_adjacent(adj, i, j) is a boundary index.

Note

The orientation of (i, j) is important: even if (i, j) is an edge on the boundary, if there is a triangle (i, j, k) in the triangulation then (i, j) is not a boundary edge but (j, i) would be.

DelaunayTriangulation.is_boundary_triangleMethod
is_boundary_triangle(i, j, k, adj)
is_boundary_triangle(T, adj)

Given a triangle T = (i, j, k) and an adjacent map adj, returns true if T is a boundary triangle.

Note

A boundary triangle is still part of the triangulation, but it has at least one edge that forms part of the boundary (so that at least one of the edges (u, v) satisfies is_boundary_edge(v, u, adj)). This is similar to, but not the same as, a ghost triangle.

DelaunayTriangulation.is_ghost_edgeFunction
is_ghost_edge(i, j)

Given an edge (i, j), returns true if (i, j) is a ghost edge.

Note

A ghost edge is an edge in which either is_boundary_index(i) or is_boundary_index(j) is true.

DelaunayTriangulation.is_ghost_triangleFunction
is_ghost_triangle(i, j, k)
is_ghost_triangle(T)

Given a triangle T = (i, j, k), returns true if T is a ghost triangle and false otherwise.

Note

A ghost triangle is one in which any of the vertices (i, j, k) are a boundary index, as tested via is_boundary_index.

DelaunayTriangulation.is_interior_curveFunction
is_interior_curve(i)
is_interior_curve(i, boundary_map)

Given an index i, tests if the curve is an interior curve, i.e. if i > 1. Alternatively, if a boundary_map is provided from construct_boundary_map, i should be a boundary map so that is_interior_curve(j) is tested, where j = get_curve_index(boundary_map, i).

DelaunayTriangulation.is_outer_boundary_nodeMethod
is_outer_boundary_node(i, graph::Graph{I}, boundary_index_ranges) where {I}

Tests if i is a node appearing on the outermost boundary.

Arguments

Outputs

• is_outer_boundary_node: A Boolean indicating whether i is a node on the outermost boundary.

See also is_boundary_node.

DelaunayTriangulation.is_boundary_nodeMethod
is_boundary_node(i, graph::Graph{I}, boundary_index_ranges) where {I}

Tests if i is a node appearing on the boundary.

Arguments

Outputs

• is_boundary_node: A Boolean indicating whether i is a node on the boundary.
• boundary_index: The boundary index of the boundary to which i belongs. If there is no such boundary, boundary_index = I(DefaultAdjacentValue).

See also is_outer_boundary_node.

Index and Ghost Handling

Below we list methods for working with predicates that are used when we provide indices for points rather than points directly.

DelaunayTriangulation.triangle_orientationMethod
triangle_orientation(i, j, k, pts, representative_point_list, boundary_map)
triangle_orientation(T, pts, representative_point_list, boundary_map)

Given a triangle T = (i, j, k), with indices corresponding to points in pts, computes the orientation of the triangle, using boundary_map from construct_boundary_map to map boundary indices to their corresponding points in representative_point_list. We return:

• Certificate.PositivelyOriented: The triangle is positively oriented.
• Certificate.Degenerate: The triangle is degenerate, meaning the coordinates are collinear.
• Certificate.NegativelyOriented: The triangle is negatively oriented.
Note

A test is also made for the case that is_outer_ghost_triangle(T): If T is a ghost triangle, then the index corresponding to a boundary index points to a centroid, in which case one of the edges has its orientation flipped. This case will also be handled correctly. In case the boundary index corresponds to an interior curve, this flip is not necessary.

DelaunayTriangulation.point_position_relative_to_circumcircleMethod
point_position_relative_to_circumcircle(i, j, k, ℓ, pts, representative_point_list, boundary_map)
point_position_relative_to_circumcircle(T, ℓ, pts, representative_point_list, boundary_map)

Tests if the ℓth point of pts is inside the circumcircle of the triangle T = (i, j, k), using the boundary_map to map boundary indices to their corresponding points in representative_point_list, returning:

• Certificate.Outside: pₗ is outside of the circumcircle.
• Certificate.On: pₗ is on the circumcircle.
• Certificate.Inside: pₗ is inside the circumcircle.
Note

A test is also made for the case that is_ghost_triangle(T): When T is a ghost triangle, one of its indices is a boundary index, say i. Since this vertex is treated as being out at infinity, the circumcircle degenerates into the line through the other two vertices and out to infinity in that direction. Thus, we test that the ℓth point is inside this circumcircle by seeing if it is in the oriented outer halfplane defined by the other two vertices, accomplished via point_position_relative_to_oriented_outer_halfplane.

DelaunayTriangulation.point_position_relative_to_lineMethod
point_position_relative_to_line(i, j, u, pts, representative_point_list, boundary_map)

Computes the position of the uth point of pts relative to the line through the ith and jth points, respectively, of pts. Boundary indices are mapped to their corresponding points in representative_point_list via the boundary_map argument from construct_boundary_map. The returned values are:

• Certificate.Left: p is to the left of the line.
• Certificate.Collinear: p is on the line.
• Certificate.Right: p is to the right of the line,

where p is the uth point of pts.

Note

If is_outer_ghost_edge(i, j, boundary_map), the orientation of the line is flipped as the point corresponding to the boundary index will be a centroid which swaps the orientation.

DelaunayTriangulation.point_closest_to_lineMethod
point_closest_to_line(i, j, u, v, pts)

Let a, b, p, q be the points corresponding to the indices i, j, u, v, respectively, in pts, and let ℓ be the oriented line through a and b. This function tests if p is closer to ℓ than q is, returning:

• Certificate.Closer: p is closer to ℓ.
• Certificate:Further: q is closer to ℓ.
• Certificate.Equidistant: p and q are the same distance from ℓ.
Note

It is assumed that p and q are to the left of ℓ.

DelaunayTriangulation.point_position_on_line_segmentMethod
point_position_on_line_segment(i, j, u, pts)

Given indices i, j, and u corresponding to points a, b, and p in pts, respectively, computes the position of p relative to the oriented line segment (a, b), assuming that the three points are collinear. The returned values are:

• Certificate.On: p is on the line segment, meaning between a and b.
• Certificate.Degenerate: Either p == a or p == b, i.e. p is one of the endpoints.
• Certificate.Left: p is off and to the left of the line segment.
• Certificate.Right: p is off and to the right of the line segment.
DelaunayTriangulation.line_segment_intersection_typeMethod
line_segment_intersection_type(u, v, i, j, pts)

Let u, v, i, and j be indices corresponding to points p, q, a, and b, respectively, in pts. This function tests the number of intersections between the two line segments (p, q) and (a, b), returning:

• Certificate.None: The line segments do not meet at any points.
• Certificate.Multiple: The closed line segments [p, q] and [a, b] meet in one or several points.
• Certificate.Single: The open line segments (p, q) and (a, b) meet in a single point.
• Certificate.On: One of the endpoints is on [a, b], but there are no other intersections.
DelaunayTriangulation.point_position_relative_to_triangleMethod
point_position_relative_to_triangle(i, j, k, u, pts, representative_point_list, boundary_map)
point_position_relative_to_triangle(T, u, pts, representative_point_list, boundary_map)

Given a triangle T = (i, j, k), with indices referring to points in pts, computes the position of u, corresponding to a point p, relative to T, with any boundary indices mapped to their corresponding representative points in representative_point_list via the boundary_map argument from construct_boundary_map. The returned values are:

• Certificate.Outside: p is outside of the triangle.
• Certificate.On: p is on one of the edges.
• Certificate.Inside: p is inside the triangle.
DelaunayTriangulation.triangle_line_segment_intersectionMethod
triangle_line_segment_intersection(i, j, k, u, v, pts)

Given a triangle (i, j, k) and a line segment (u, v), with indices corresponding to points in pts, tests if (u, v) intersects the triangle's interior. Letting (p, q, r) be the coordinates corresponding to the triangle's vertices, and (a, b) those for the edge's vertices, returns:

• Cert.Inside: (a, b) is entirely inside (p, q, r).
• Cert.Single: (a, b) has one endpoint inside (p, q, r), and the other is outside.
• Cert.Outside: (a, b) is entirely outside (p, q, r).
• Cert.Touching: (a, b) is on (p, q, r)'s boundary, but not in its interior.
• Cert.Multiple: (a, b) passes entirely through (p, q, r). This includes the case where a point is on the boundary of (p, q, r).