Utility Functions

number_type(x) -> DataType

Given a container x, returns the number type used for storing coordinates.

Examples

julia> using DelaunayTriangulation

julia> DelaunayTriangulation.number_type([1, 2, 3])
Int64

julia> DelaunayTriangulation.number_type((1, 2, 3))
Int64

julia> DelaunayTriangulation.number_type([1.0 2.0 3.0; 4.0 5.0 6.0])
Float64

julia> DelaunayTriangulation.number_type([[[1, 2, 3, 4, 5, 1]], [[6, 8, 9], [9, 10, 11], [11, 12, 6]]])
Int64

julia> DelaunayTriangulation.number_type((1.0f0, 2.0f0))
Float32

julia> DelaunayTriangulation.number_type(Vector{Float64})
Float64

julia> DelaunayTriangulation.number_type(Vector{Vector{Float64}})
Float64

julia> DelaunayTriangulation.number_type(NTuple{2, Float64})
Float64

_to_val(v) -> Val

Wraps v in a Val, or if v isa Val simply returns v.

adjust_θ(θ₁, θ₂, positive) -> (Number, Number)

Given two angles θ₁ and θ₂ in radians, adjusts the angles to new angles θ₁′, θ₂′ so that θ₁′ ≤ θ₂′ if positive is true, and θ₁′ ≥ θ₂′ if positive is false.

check_absolute_precision(x, y) -> Bool

Returns true if abs(x - y) is less than or equal to sqrt(eps(Float64)).

check_precision(x) -> Bool

Returns true if abs(x) is less than or equal to sqrt(eps(number_type(eps))).

check_ratio_precision(x, y) -> Bool

Returns true if abs(x/y) is bounded between 0.99 and 1.01.

check_relative_precision(x, y) -> Bool

Returns true if abs(x - y)/max(abs(x), abs(y)) is less than or equal to sqrt(eps(Float64)).

choose_uvw(e1, e2, e3, u, v, w) -> (Vertex, Vertex, Vertex)

Choose values for (u, v, w) based on the Booleans (e1, e2, e3), assuming only one is true. The three cases are:

• If e1, returns (u, v, w).
• If e2, returns (v, w, u).
• If e3, returns (w, u, v).

circular_equality(A, B, by=isequal) -> Bool

Compares the two circular vectors A and B for equality up to circular rotation, using by to compare individual elements.

dist(p, q) -> Number

Assuming p and q are two-dimensional, computes the Euclidean distance between p and q.

dist(tri::Triangulation, p) -> Number

Given a point p, returns the distance from p to the triangulation, using the conventions from distance_to_polygon:

• δ > 0: If the returned distance is positive, then p is inside the triangulation.
• δ < 0: If the returned distance is negative, then p is outside the triangulation.
• δ = 0: If the returned distance is zero, then p is on the boundary of the triangulation.

Where we say distance, we are referring to the distance from p to the boundary of the triangulation.

dist_sqr(p, q) -> Number

Assuming p and q are two-dimensional, computes the square of the Euclidean distance between p and q.

edge_length(tri::Triangulation, u, v) -> Number
edge_length(tri::Triangulation, e) -> Number

Computes the length of the edge e = (u, v).

edge_length_sqr(tri::Triangulation, u, v) -> Number
edge_length_sqr(tri::Triangulation, e) -> Number

Computes the square of the length of the edge e = (u, v).

eval_fnc_at_het_tuple_element(f, tup, idx)

Evaluates f(tup[idx]) in a type-stable way. If idx > length(tup), then f is evaluated on the last element of tup. If length(tup) > 32, then the function is not type-stable; note that, in this case, idx > length(tup) leads to a BoundsError.

eval_fnc_at_het_tuple_element_with_arg(f, tup, arg, idx)

Evaluates f(tup[idx], arg...) in a type-stable way. If idx > length(tup), then f is evaluated on the last element of tup. If length(tup) > 32, then the function is not type-stable; note that, in this case, idx > length(tup) leads to a BoundsError.

eval_fnc_at_het_tuple_element_with_arg_and_prearg(f, tup, prearg, arg, idx)

Evaluates f(prearg, tup[idx], arg...) in a type-stable way. If idx > length(tup), then f is evaluated on the last element of tup. If length(tup) > 32, then the function is not type-stable; note that, in this case, idx > length(tup) leads to a BoundsError.

eval_fnc_at_het_tuple_two_elements(f, tup, idx1, idx2)

Evaluates f(tup[idx1], tup[idx2]) in a type-stable way. If length(tup) > 32, then the function is not type-stable.

eval_fnc_in_het_tuple(tup, arg, idx)

Evaluates tup[idx](arg...) in a type-stable way. If idx > length(tup), then tup[end](arg...) is evaluated.

get_area(tri::Triangulation) -> Number

Returns the area of tri.

get_boundary_chain(tri::Triangulation, i, j) -> Edges

Given two boundary vertices i and j on a boundary with ghost vertex ghost_vertex, walks counter-clockwise from i to j along the boundary and returns the collection of all vertices encountered in counter-clockwise order.

get_ghost_vertex(i, j, k) -> Vertex
get_ghost_vertex(i, j) -> Vertex

Given three vertices i, j, and k, returns the ghost vertex among them. If none of them are ghost vertices, returns k. The two-argument version is equivalent to get_ghost_vertex(i, j, j).

Examples

julia> using DelaunayTriangulation

julia> DelaunayTriangulation.get_ghost_vertex(1, 7, -2)
-2

julia> DelaunayTriangulation.get_ghost_vertex(-1, 2, 3)
-1

julia> DelaunayTriangulation.get_ghost_vertex(1, 5, 10)
10

julia> DelaunayTriangulation.get_ghost_vertex(1, -1)
-1

julia> DelaunayTriangulation.get_ghost_vertex(-5, 2)
-5

get_ordinal_suffix(i) -> String

Returns the ordinal suffix for the integer i.

Examples

julia> using DelaunayTriangulation

julia> DelaunayTriangulation.get_ordinal_suffix(1)
"st"

julia> DelaunayTriangulation.get_ordinal_suffix(2)
"nd"

julia> DelaunayTriangulation.get_ordinal_suffix(3)
"rd"

julia> DelaunayTriangulation.get_ordinal_suffix(4)
"th"

julia> DelaunayTriangulation.get_ordinal_suffix(5)
"th"

julia> DelaunayTriangulation.get_ordinal_suffix(6)
"th"

julia> DelaunayTriangulation.get_ordinal_suffix(11)
"th"

julia> DelaunayTriangulation.get_ordinal_suffix(15)
"th"

julia> DelaunayTriangulation.get_ordinal_suffix(100)
"th"

is_circular(A) -> Bool

Tests if A is circular, meaning that A[begin] == A[end].

is_true(b) -> Bool

Returns b represents a true value, and false otherwise.

Examples

julia> using DelaunayTriangulation

julia> DelaunayTriangulation.is_true(true)
true

julia> DelaunayTriangulation.is_true(false)
false

julia> DelaunayTriangulation.is_true(Val(true))
true

julia> DelaunayTriangulation.is_true(Val(false))
false

iterated_neighbourhood(tri::Triangulation, i, d) -> Set{Vertex}

Returns the set of vertices of tri in the iterated neighbourhood of the vertex i of depth d.

Extended help

The $d$-times iterated neighbourhood is defined by

\[N_i^d = \bigcup_{j \in N_i^{d-1}} N_j \setminus \{i\},\]

where $N_i^1 = N_i$ is the set of neighbours of $i$.

midpoint(p, q) -> Number or NTuple{2, Number}

Assuming p and q are either both numbers are both 2-vectors, computes their average.

midpoint(tri::Triangulation, u, v) -> NTuple{2, Number}
midpoint(tri::Triangulation, e) -> NTuple{2, Number}

Computes the midpoint of e = (u, v).

nextindex_circular(C, i) -> Integer

Returns the next index after i in the circular vector C.

norm(p) -> Number

Assuming p is two-dimensional, computes the Euclidean norm of p.

norm_sqr(p) -> Number

Assuming p is two-dimensional, computes the square of the Euclidean norm of p.

previndex_circular(C, i) -> Integer

Returns the previous index before i in the circular vector C.

replace_boundary_triangle_with_ghost_triangle(tri::Triangulation, V) -> Triangle

Given a boundary triangle V of tri, returns the adjacent ghost triangle. Note that for triangles in a corner of a domain, like a lattice triangulation, there are two choices of ghost triangle.

replace_ghost_triangle_with_boundary_triangle(tri::Triangulation, V) -> Triangle

Given a ghost triangle V of tri, returns the adjacent boundary triangle.

self_eval(f, args...)

Evaluates f(args...).

uniquetol(A::Vector{Float64}; tol=1e-12) -> Vector{Float64}

Returns the unique elements of A up to tolerance tol. We say that two values x and y are within tolerance if abs(u - v) ≤ M*tol, where M = maximum(abs.(A)). It is assumed that A is sorted - this is NOT checked.

angle_between(p, q) -> Number

Returns the angle between the vectors p and q in radians, treating q as the base. See this article. The returned angle is in [0, 2π).

classify_and_compute_segment_intersection([kernel::AbstractPredicateKernel,] a, b, c, d) -> (Certificate, Certificate, Certificate, NTuple{2, Number})

Given two line segments (a, b) and (c, d), classifies the intersection of the two segments. The returned value is (cert, cert_c, cert_d, p), where:

• cert: A Certificate indicating the intersection type.
• cert_c: A Certificate indicating the position of c relative to the line through (a, b).
• cert_d: A Certificate indicating the position of d relative to the line through (a, b).
• p: The intersection point if cert is Cert.Single or Cert.Touching, and (NaN, NaN) otherwise.

distance_to_polygon(q, points, boundary_nodes) -> Number

Given a query point q and a polygon defined by (points, boundary_nodes), returns the signed distance from q to the polygon. The boundary_nodes must match the specification in the documentation and in check_args.

See also dist.

get_distance_to_plane(a, b, c, p) -> Number

Returns the distance from the point p to the plane defined by the points (a, b, c). The distance is positive if p is above the plane.

get_plane_through_three_points(a, b, c) -> NTuple{4, Number}

Given three points (a, b, c) in ℝ³ represented as Tuples, computes the equation of the plane through the points. The result is given in the form (α, β, γ, δ), so that the plane is given by

αx + βy + γz + δ = 0.

Extended help

The equation of the plane is computed by expanding the equation

\[\det \begin{bmatrix} x & y & z & 1 \\ a_x & a_y & a_z & 1 \\ b_x & b_y & b_z & 1 \\ c_x & c_y & c_z & 1 \end{bmatrix} = 0.\]

From this, we find:

\[\begin{align*} \alpha &= a_y b_z - a_z b_y - a_y c_z + a_z c_y + b_y c_z - b_z c_y, \\ \beta &= a_z b_x - a_x b_z + a_x c_z - a_z c_x - b_x c_z + b_z c_x, \\ \gamma &= a_x b_y - a_y b_x - a_x c_y + a_y c_x + b_x c_y - b_y c_x, \\ \delta &= a_x b_z c_y - a_x b_y c_z + a_y b_x c_z - a_y b_z c_x - a_z b_x c_y + a_z b_y c_x. \end{align*}\]

get_steepest_descent_direction(a, b, c) -> NTuple{2, Number}

Given three points in ℝ³ defining a plane, returns the direction (x, y) of the steepest descent along the plane. In particular, if

αx + βy + γz + δ = 0

is the plane, then the steepest descent direction is (α, β)/γ. The returned value is given by (x, y) = sign(γ)(α, β).

See also get_plane_through_three_points.

get_vertical_distance_to_plane(a, b, c, p) -> Number

Returns the vertical distance from the point p to the plane defined by the points (a, b, c). The distance is positive if p is above the plane.

intersection_of_edge_and_bisector_ray([kernel::AbstractPredicateKernel=AdaptiveKernel(),] a, b, c; project=false) -> (Certificate, NTuple{2, Number})

Given an edge (a, b) and a ray emanating from c perpendicular with the edge and collinear with its midpoint (or, if project=true, the projection of c onto the edge), tests if c intersects the edge. The returned value is (cert, p), where:

• cert: A Certificate indicating the position of c relative to the line through (a, b).
• p: The intersection point if c intersects the edge, (NaN, NaN) otherwise.

The kernel argument determines how this result is computed, and should be one of ExactKernel, FastKernel, and AdaptiveKernel (the default). See the documentation for more information about these choices.

intersection_of_ray_with_bounding_box(p, q, a, b, c, d) -> NTuple{2, Number}

Compute the intersection of the ray emanating from p and passing through q with the box [a, b] × [c, d]. It is assumed that p is inside of the box.

polygon_bounds(points, boundary_nodes, check_all_curves=Val(false)) -> (Number, Number, Number, Number)

Computes the bounding box of the polygon defined by (points, boundary_nodes). The boundary_nodes must match the specification in the documentation and in check_args. If check_all_curves is true, then the bounding box of the union of all curves of the polygon is computed instead of just the first curve.

polygon_features(points, boundary_nodes) -> (Number, NTuple{2, Number})

Computes the signed area and centroid of the polygon defined by (points, boundary_nodes). The boundary_nodes must match the specification in the documentation and in check_args.

project_onto_line(p, q, r) -> NTuple{2, Number}

Projects the point r onto the line through p and q. It is possible that the projected point is not on the line segment [p, q].

segment_intersection_coordinates(a, b, c, d) -> NTuple{2, Number}

Given two segments (a, b) and (c, d) that are assumed to intersect, computes the coordinates of the intersection.

sort_convex_polygon!(vertices, points)

Sorts the vertices of a convex polygon in counter-clockwise order. The polygon is defined by (points, vertices), and the vertices are sorted in-place. It is assumed that the vertices are not circular, i.e. vertices[begin] ≠ vertices[end].

squared_distance_to_segment(x₁, y₁, x₂, y₂, x, y) -> Number

Given a line segment (x₁, y₁) → (x₂, y₂) and a query point (x, y), returns the squared distance from (x, y) to the line segment.

angle_is_acute([kernel::AbstractPredicateKernel,] p, q, r)

Tests if the angle opposite (p, q) in the triangle (p, q, r), meaning ∠prq, is acute, returning:

• 1: ∠prq is acute.
• 0: ∠prq is a right angle.
• -1: ∠prq is obtuse.

The kernel argument determines how this result is computed, and should be one of ExactKernel, FastKernel, and AdaptiveKernel (the default). See the documentation for more information about these choices.

det(a, b, c, d)

Computes ExactPredicates.det(a, b, c, d), i.e. returns a*d - b*c.

det(a, b, c, d, e, f, g, h, i)

Computes ExactPredicates.det(a, b, c, d, e, f, g, h, i), i.e. returns the determinant of

\[\det \begin{bmatrix} a & b & c \\ d & e & f \\ g & h & i \end{bmatrix}\]

ext(ux, uy, vx, vy)

Computes ExactPredicates.ext((ux, uy), (vx, vy)), i.e. returns ux * vy - uy * vx.

incircle_predicate([kernel::AbstractPredicateKernel,] a, b, c, p; cache = nothing) -> Integer

Assuming that (a, b, c) is a positively oriented triangle, returns

• 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).

The kernel argument determines how this result is computed, and should be one of ExactKernel, FastKernel, and AdaptiveKernel (the default). See the documentation for more information about these choices.

The optional cache keyword argument can be used for preallocating memory for intermediate results, passing the argument from AdaptivePredicates.incircleadapt_cache(T), where T is the number type of the input points. If nothing is passed, no cache is used. This is only needed if an AdaptiveKernel() is used.

inp(ux, uy, vx, vy)

Computes ExactPredicates.inp((ux, uy), (vx, vy)), i.e. returns ux * vx + uy * vy.

meet_predicate([kernel::AbstractPredicateKernel], p, q, a, b) -> Integer

Returns

• 1: The open line segments (p, q) and (a, b) meet in a single point.
• 0: The closed line segments [p, q] and [a, b] meet in one or several points.
• -1: Otherwise.

The kernel argument determines how this result is computed, and should be one of ExactKernel, FastKernel, and AdaptiveKernel (the default). See the documentation for more information about these choices.

opposite_signs(x, y) -> Bool

From ExactPredicates.jl, returns true if x and y have opposite signs, and false otherwise. Assumes that x and y are in [-1, 0, 1].

orient_predicate([kernel::AbstractPredicateKernel,] p, q, r) -> Integer

Returns

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

The kernel argument determines how this result is computed, and should be one of ExactKernel, FastKernel, and AdaptiveKernel (the default). See the documentation for more information about these choices.

orient_predicate([kernel::AbstractPredicateKernel,] p, q, r; cache = nothing) -> Integer

Returns

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

Here, a positively oriented tetrahedron (p, q, r, s) takes the form

                               z.
                             .
                           ,/
                         s
                       ,/|'\
                     ,/  |  '\
                   ,/    '.   '\
                 ,/       |     '\                 
               ,/         |       '\              
              p-----------'.--------q --> x
               '\.         |      ,/              
                  '\.      |    ,/                 
                     '\.   '. ,/    
                        '\. |/      
                           'r       
                             '\.

The kernel argument determines how this result is computed, and should be one of ExactKernel, FastKernel, and AdaptiveKernel (the default). See the documentation for more information about these choices.

The optional cache keyword argument can be used for preallocating memory for intermediate results, passing the argument from AdaptivePredicates.orient3adapt_cache(T), where T is the number type of the input points. If nothing is passed, no cache is used. This is only needed if an AdaptiveKernel() is used.

parallelorder_predicate([kernel::AbstractPredicateKernel,] a, b, p, q) -> Integer

Returns

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

The kernel argument determines how this result is computed, and should be one of ExactKernel, FastKernel, and AdaptiveKernel (the default). See the documentation for more information about these choices.

sameside_predicate(a, b, p) -> Integer

Assuming all of a, b, p are collinear, returns

• 1: a and b are on the same side of p on the line.
• 0: a == p or b == p.
• -1: a and b are on different sides of p on the line.

sgn(x) -> Int

Returns Int(sign(x)).

is_boundary_edge(tri::Triangulation, ij) -> Bool
is_boundary_edge(tri::Triangulation, i, j) -> Bool

Tests if the edge (i, j) is a boundary edge of tri, meaning (j, i) adjoins a ghost vertex.

is_boundary_node(tri::Triangulation, i) -> (Bool, Vertex)

Tests if the vertex i is a boundary node of tri.

Arguments

• tri::Triangulation: The Triangulation.
• i: The vertex to test.

Outputs

• flag: true if i is a boundary node, and false otherwise.
• g: Either the ghost vertex corresponding with the section that i lives on if flag is true, or 0 otherwise.

is_boundary_triangle(tri::Triangulation, T) -> Bool
is_boundary_triangle(tri::Triangulation, i, j, k) -> Bool

Returns true if the triangle T = (i, j, k) of tri has an edge on the boundary, and false otherwise.

is_exterior_boundary_node(tri::Triangulation, i) -> Bool

Tests if the vertex i is an exterior boundary node of tri.

is_exterior_ghost_edge(tri::Triangulation, i, j) -> Bool

Tests if the edge (i, j) is an exterior ghost edge of tri.

See also is_exterior_ghost_vertex.

is_exterior_ghost_triangle(tri::Triangulation, i, j, k) -> Bool

Tests if the triangle (i, j, k) is an exterior ghost triangle of tri.

See also is_exterior_ghost_vertex.

is_ghost_edge(ij) -> Bool 
is_ghost_edge(i, j) -> Bool

Tests if the edge (i, j) is a ghost edge, meaning i or j is a ghost vertex.

is_ghost_triangle(T) -> Bool
is_ghost_triangle(i, j, k) -> Bool

Tests if T = (i, j, k) is a ghost triangle, meaning i, j or k is a ghost vertex.

is_ghost_vertex(i) -> Bool

Tests if i is a ghost vertex, meaning i ≤ -1.

convert_certificate(cert::I, Cert1, Cert2, Cert3) -> Certificate

Given cert ∈ (-1, 0, 1), return Cert1, Cert2 or Cert3 depending on if cert == -1, cert == 0 or cert == 1, respectively.

DefaultAdjacentValue = 0

Default value used for representing an empty result from an adjacency query.

𝒢 = GhostVertex

Alias for GhostVertex.

GhostVertex = -1

Number used for representing initial ghost vertices. All other ghost vertices are derived from subtracting from this number. See https://juliageometry.github.io/DelaunayTriangulation.jl/stable/manual/ghost_triangles/.

ε(x) = sqrt(eps(number_type(x)))

Number used as a tolerance in certain functions, e.g. for mesh refinement when using check_precision to avoid degenerate circumcenters.

∅ = DefaultAdjacentValue

Alias for DefaultAdjacentValue.

fix_orient3_cache(tri::Triangulation, cache)

Returns cache if validate_orient3_cache(tri, cache) is true, otherwise returns nothing.

fix_incircle_cache(tri::Triangulation, cache)

Returns cache if validate_incircle_cache(tri, cache) is true, otherwise returns nothing.

validate_orient3_cache(tri::Triangulation, cache) -> Bool

Checks if the cache cache is of the correct type for cmoputing orient3 predicates for the triangulation tri. If isnothing(cache) or the cache is of the correct type, then true is returned. Otherwise, false is returned.

validate_incircle_cache(tri::Triangulation, cache) -> Bool

Checks if the cache cache is of the correct type for computing incircle predicates for the triangulation tri. If isnothing(cache) or the cache is of the correct type, then true is returned. Otherwise, false is returned.