Individual Triangles

Triangles are assumed to be of the form (i, j, k), with positive orientation, but we allow for customisation in the way these indices are represented. The following methods are used for working with triangles. First, we list the methods that must be defined, and then methods that extend these former methods.

Necessary Methods

DelaunayTriangulation.construct_triangleFunction
construct_triangle(::Type{T}, i, j, k) where {T}

Constructs a triangle with indices (i, j, k) with the type T. The following methods are currently defined:

construct_triangle(::Type{NTuple{3, I}}, i, j, k) where {I} 
construct_triangle(::Type{A}, i, j, k) where {I, A <: AbstractVector{I}}

You can extend this function as you need, ensuring you define it on the type rather than on an instance of the type.

DelaunayTriangulation.getiFunction
geti(T::F) where {F}

From a triangle T, extract the ith index, i.e. the first. The following methods are currently defined:

geti(T::NTuple{3, I})
geti(T::A) where {I,A<:AbstractVector{I}}

You can extend this function as you need.

DelaunayTriangulation.getjFunction
getj(T::F) where {F}

From a triangle T, extract the jth index, i.e. the second. The following methods are currently defined:

getj(T::NTuple{3, I})
getj(T::A) where {I,A<:AbstractVector{I}}

You can extend this function as you need.

DelaunayTriangulation.getkFunction
getk(T::F) where {F}

From a triangle T, extract the kth index, i.e. the third. The following methods are currently defined:

getk(T::NTuple{3, I})
getk(T::A) where {I,A<:AbstractVector{I}}

You can extend this function as you need.

DelaunayTriangulation.integer_typeFunction
integer_type(::Type{T}) where {T}

Returns the integer type used for representnig a triangle with indices (i, j, k) with the type T. The following methods are currently defined:

integer_type(::Type{NTuple{N, I}}) where {N, I} 
integer_type(::Type{A}) where {I, A <: AbstractVector{I}}

You can extend this function as you need, ensuring you define it on the type rather than on an instance of the type.

Generic Methods

DelaunayTriangulation.triangle_edgesFunction
triangle_edges(T)
triangle_edges(i, j, k)

Returns an iterator over each edge of the triangle T. In particular, returns ((geti(T), getj(T)), (getj(T), getk(T)), (getk(T), geti(T))). The latter method uses the indices directly.

DelaunayTriangulation.rotate_triangleFunction
rotate_triangle(T::V, i) where {V}

Given a triangle T, rotates the indices an amount i. In particular, if T = (i, j, k):

  • i = 0: Returns (i, j, k).
  • i = 1: Returns (j, k, i).
  • i = 2: Returns (k, i, j).
  • Otherwise, return rotate_triangle(T, i % 3).
DelaunayTriangulation.construct_positively_oriented_triangleMethod
construct_positively_oriented_triangle(::Type{V}, i, j, k, points) where {V}

Given a triangle type V, indices (i, j, k) corresponding to points in points, returns either construct_triangle(V, i, j, k) or construct_triangle(V, j, i, k), whichever is not negatively oriented.

DelaunayTriangulation.compare_trianglesFunction
compare_triangles(T, V)

Tests if the triangle T is equal to the triangle V, with equality defined on the indices. In particular, compare_triangles((i, j, k), (i, j, k)), compare_triangles((i, j, k), (j, k, i)), and compare_triangles((i, j, k), (k, i, j)) are all true.

DelaunayTriangulation.sort_triangleFunction
sort_triangle(T::V) where {V}

Given a triangle T = (i, j, k), sorts it so that the first index is the smallest, maintaining the orientation of T.

Collection of Triangles

A collection of triangles simply stores many triangles, and the collection itself must be mutable so that triangles can be added and deleted. The following methods are used for working with collections of triangles. First, we list the methods that must be defined, and then methods that extend these former methods.

Necessary Methods

DelaunayTriangulation.initialise_trianglesFunction
initialise_triangles(::Type{S})

For a given type S for some collection (e.g. a AbstractSet), returns an empty instance of that collection. The only method defined is

initialise_triangles(::Type{S}) where {T, S <: AbstractSet{T}}
initialise_triangles(::Type{V}) where {T,V<:AbstractVector{T}}

which returns a Set{T}(). You can extend this function as you need, making sure you extend it for the type rather than for instances of that type.

DelaunayTriangulation.triangle_typeFunction
triangle_type(::Type{S}) where {S}

For a given type S representing a collection of triangles, returns the type of triangle used inside S, e.g. NTuple{3, Int} if S = AbstractSet{NTuple{3, Int}}. The only methods defined are

triangle_type(::Type{S}) where {T, S <: AbstractSet{T}}
triangle_type(::Type{A}) where {T, A <: AbstractVector{E}}

which returns T. You can extend this function as you need, making sure you extend it for the type rather than for instances of that type.

DelaunayTriangulation.num_trianglesFunction
num_triangles(T::S) where {S}

Given a collection of triangles T, returns the number of triangles in T. The only method currently defined is

num_triangles(T::AbstractSet)
num_triangles(T::AbstractVector)

which returns length(T). You can extend this function as you need.

DelaunayTriangulation.add_to_triangles!Function
add_to_triangles!(T::S, V) where {S}

Given a collection of triangles T, pushes V into it. The only methods currently defined are

add_to_triangles!(T::AbstractSet{F}, V::F) where {F}
add_to_triangles!(T::AbstractSet{F}, V) where {F}

which simply call push!(T, V). The latter method reconstructs V using [indices] and construct_triangle. You can extend this function as you need.

DelaunayTriangulation.delete_from_triangles!Function
delete_from_triangles!(V::S, T::F) where {S}

Given a collection of triangles V of type S, containing triangles of type F, deletes the triangle T from V. The only method currently defined is

delete_from_triangles!(V::AbstractSet{F}, T::F) where {F}.

which just calls delete! on V. The function already assumes that T is already in V, and that T doesn't need to be rotated at all.

DelaunayTriangulation.each_triangleFunction
each_triangle(V::F) where {F}

For a given collection of triangles V, returns an iterator that goes over each triangle in the collection. The methods currently defined are

each_triangle(V::AbstractSet)
each_triangle(V::AbstractMatrix)
each_triangle(V::AbstractVector)

with the first method simply returning V, the second returning eachcol(V), and the third returning V. You can extend this function as you need.

DelaunayTriangulation.remove_duplicate_trianglesFunction
remove_duplicate_triangles(T::Ts) where {Ts}

Removes duplicate triangles from T. This procedure also sorts the triangles so that the first index of each triangle is the smallest. Orientations are preserved.

You must also provide definitions for Base.in and Base.sizehint! for your type. You need Base.unique! to use remove_duplicate_triangles, unless your collection is a Set. Note also that Triangulations also define each_solid_triangle and each_ghost_triangle.

Generic Methods

DelaunayTriangulation.contains_triangleFunction
contains_triangle(T::F, V::S) where {F, S}

Given a collection of triangles V of type S, containing triangles of type F, checks if V includes the triangle T. In particular, the returned value is

(rotate_triangle(T, m), true)

if V includes the triangle T, and m is the integer such that rotate_triangle(T, m) is the form of T that V contains. If there is no such m, the returned value is simply

(T, false).

To use this function, your type needs to only have a definition for T ∈ V for testing specific rotations of a triangle. This function then performs the checks by checking T, then rotate_triangle(T, 1), then rotate_triangle(T, 2), and if none of those succeed just returns (T, false). You can extend this function as you need. We also define

contains_triangle(i, j, k, V::Ts) where {Ts},

and this method just calls the two-argument method after constructing the triangle with construct_triangle.

DelaunayTriangulation.add_triangle!Method
add_triangle!(T::Ts, i::Integer, j::Integer, k::Integer) where {Ts}

Given a collection of triangles T, adds the triangle (i, j, k) into it.

DelaunayTriangulation.delete_triangle!Method
delete_triangle!(V, T...)

Given a collection of triangles V, deletes all the triangles T... from it. Checks are made for rotated forms of T that V includes. For example, if T = (i, j, k) but V contains (j, k, i), then (j, k, i) will be deleted. The function also checks to see if the triangle is in V at all prior to deleting it. To extend this method to other collections, see delete_from_triangles!.

DelaunayTriangulation.delete_triangle!Method
delete_triangle!(T::Ts, i::Integer, j::Integer, k::Integer) where {Ts}

Given a collection of triangles T, deletes the triangle (i, j, k) from it. Checks are made to see if T needs to be rotated, or if (i, j, k) is in T at all.

DelaunayTriangulation.sort_trianglesFunction
sort_triangles(T::Ts) where {Ts}

Sorts the triangles in the collection T so that each triangle's first vertex has the smallest value. The orientation of each triangle is preserved.