## 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_triangle`

— Function`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.geti`

— Function`geti(T::F) where {F}`

From a triangle `T`

, extract the `i`

th 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.getj`

— Function`getj(T::F) where {F}`

From a triangle `T`

, extract the `j`

th 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.getk`

— Function`getk(T::F) where {F}`

From a triangle `T`

, extract the `k`

th 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_type`

— Function`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.indices`

— Function`DelaunayTriangulation.triangle_edges`

— Function```
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_triangle`

— Function`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_triangle`

— Method`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_triangles`

— Function`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_triangle`

— Function`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_triangles`

— Function`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_type`

— Function`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_triangles`

— Function`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_triangle`

— Function`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_triangles`

— Function`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 `Triangulation`

s also define `each_solid_triangle`

and `each_ghost_triangle`

.

### Generic Methods

`DelaunayTriangulation.contains_triangle`

— Function`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, V...)`

Given a collection of triangles `T`

, adds all the triangles `V...`

into it. To extend this method to other collections, see `add_to_triangles!`

.

`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.compare_triangle_collections`

— Function`compare_triangle_collections(T, V)`

Given two collections of triangles `T`

and `V`

, tests if they are equal, with equality defined according to `compare_triangles`

.

`DelaunayTriangulation.sort_triangles`

— Function`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.