Algorithm Internals

Here we give some functions that are used for some of the algorithms in this package.

Unconstrained Triangulations

Here are some of the internal functions used for the Bowyer-Watson algorithm, i.e. for the computation of an unconstrained triangulation.

DelaunayTriangulation.postprocess_triangulate! — Function

postprocess_triangulate!(tri; delete_ghosts=false, delete_empty_features=true, recompute_representative_points=true)

Postprocesses the triangulation tri after it has been constructed using triangulate. This includes:

Deleting ghost triangles using delete_ghost_triangles! if delete_ghosts is true.
Clearing empty features using clear_empty_features! if delete_empty_features is true.
Recomputing the representative points using compute_representative_points! if recompute_representative_points is true.

source

DelaunayTriangulation.add_point_bowyer_watson! — Method

add_point_bowyer_watson!(tri::Triangulation, new_point, initial_search_point::I, rng::Random.AbstractRNG=Random.default_rng(), update_representative_point=true, store_event_history=Val(false), event_history=nothing, peek::P=Val(false), predicates::AbstractPredicateKernel=AdaptiveKernel()) -> Triangle

Adds new_point into tri.

Arguments

tri: The triangulation.
new_point: The point to insert.
initial_search_point::I: The vertex to start the point location with find_triangle at. See get_initial_search_point.
rng::Random.AbstractRNG: The random number generator to use.
predicates::AbstractPredicateKernel=AdaptiveKernel(): Method to use for computing predicates. Can be one of FastKernel, ExactKernel, and AdaptiveKernel. See the documentation for a further discussion of these methods.
update_representative_point=true: If true, then the representative point is updated. See update_centroid_after_addition!.
store_event_history=Val(false): If true, then the event history from the insertion is stored.
event_history=nothing: The event history to store the event history in. Should be an InsertionEventHistory if store_event_history is true, and false otherwise.
peek=Val(false): Whether to actually add new_point into tri, or just record into event_history all the changes that would occur from its insertion.

Output

V: The triangle in tri containing new_point.

Extended help

This function works as follows:

First, the triangle containing the new point, V, is found using find_triangle.
Once the triangle is found, we call into add_point_bowyer_watson_and_process_after_found_triangle to properly insert the point.
Inside add_point_bowyer_watson_and_process_after_found_triangle, we first call into add_point_bowyer_watson_after_found_triangle to add the point into the cavity. We then call into add_point_bowyer_watson_onto_segment to make any changes necessary incase the triangulation is constrained and new_point lies on a segment, since the depth-first search of the triangles containing new_point in its circumcenter must be performed on each side of the segment that new_point lies on.

The function add_point_bowyer_watson_dig_cavities! is the main workhorse of this function from add_point_bowyer_watson_after_found_triangle. See its docstring for the details.

source

DelaunayTriangulation.add_point_bowyer_watson_dig_cavities! — Method

add_point_bowyer_watson_dig_cavities!(tri::Triangulation, new_point::N, V, q, flag, update_representative_point=true, store_event_history=Val(false), event_history=nothing, peek::F=Val(false), predicates::AbstractPredicateKernel=AdaptiveKernel()) where {N,F}

Deletes all the triangles in tri whose circumcircle contains new_point. This leaves behind a polygonal cavity, whose boundary edges are then connected to new_point, restoring the Delaunay property from new_point's insertion.

Arguments

tri: The Triangulation.
new_point::N: The point to insert.
V: The triangle in tri containing new_point.
q: The point to insert.
flag: The position of q relative to V. See point_position_relative_to_triangle.
update_representative_point=true: If true, then the representative point is updated. See update_centroid_after_addition!.
store_event_history=Val(false): If true, then the event history from the insertion is stored.
event_history=nothing: The event history to store the event history in. Should be an InsertionEventHistory if store_event_history is true, and false otherwise.
peek=Val(false): Whether to actually add new_point into tri, or just record into event_history all the changes that would occur from its insertion.
predicates::AbstractPredicateKernel=AdaptiveKernel(): Method to use for computing predicates. Can be one of FastKernel, ExactKernel, and AdaptiveKernel. See the documentation for a further discussion of these methods.

Output

There are no changes, but tri is updated in-place.

Extended help

This function works as follows:

To dig the cavity, we call dig_cavity! on each edge of V, stepping towards the adjacent triangles to excavate the cavity recursively.
Once the cavity has been excavated, extra care is needed in case is_on(flag), meaning new_point is on one of the edges of V. In particular, extra care is needed if: is_on(flag) && (is_boundary_triangle(tri, V) || is_ghost_triangle(V) && !is_boundary_node(tri, new_point)[1]). The need for this check is in case new_point is on a boundary edge already exists, since we need to fix the associated ghost edges. For example, a boundary edge (i, k) might have been split into the edges (i, j) and (j, k), which requires that the ghost triangle (k, i, g) be split into (j, i, g) and (k, j, g), where g is the ghost vertex. This part of the function will fix this case. The need for is_ghost_triangle(V) && !is_boundary_node(tri, new_point)[1] is in case the ghost edges were already correctly added. Nothing happens if the edge of V that new_point is on is not the boundary edge.

source

DelaunayTriangulation.dig_cavity! — Method

dig_cavity!(tri::Triangulation, r, i, j, ℓ, flag, V, store_event_history=Val(false), event_history=nothing, peek::F=Val(false), predicates::AbstractPredicateKernel=AdaptiveKernel()) where {F}

Excavates the cavity in tri through the edge (i, j), stepping towards the adjacent triangles to excavate the cavity recursively, eliminating all triangles containing r in their circumcircle.

Arguments

tri: The Triangulation.
r: The new point being inserted.
i: The first vertex of the edge (i, j).
j: The second vertex of the edge (i, j).
ℓ: The vertex adjacent to (j, i), so that the triangle being stepped into is (j, i, ℓ).
flag: The position of r relative to V. See point_position_relative_to_triangle.
V: The triangle in tri containing r.
store_event_history=Val(false): If true, then the event history from the insertion is stored.
event_history=nothing: The event history to store the event history in. Should be an InsertionEventHistory if store_event_history is true, and false otherwise.
peek=Val(false): Whether to actually add new_point into tri, or just record into event_history all the changes that would occur from its insertion.
predicates::AbstractPredicateKernel=AdaptiveKernel(): Method to use for computing predicates. Can be one of FastKernel, ExactKernel, and AdaptiveKernel. See the documentation for a further discussion of these methods.

Output

There are no changes, but tri is updated in-place.

Extended help

This function works as follows:

First, we check if ℓ is 0, which would imply that the triangle (j, i, ℓ) doesn't exist as it has already been deleted. If this is the check, we return and stop digging.
If the edge (i, j) is not a segment, r is inside of the circumcenter of (j, i, ℓ), and ℓ is not a ghost vertex, then we can step forward into the next triangles. In particular, we delete the triangle (j, i, ℓ) from tri and then call dig_cavity! again on two edges of (j, i, ℓ) other than (j, i).
If we did not do step 2, then this means that we are on the edge of the polygonal cavity; this also covers the case that ℓ is a ghost vertex, i.e. we are at the boundary of the triangulation. There are two cases to consider here. Firstly, if (i, j) is not a segment, we just need to add the triangle (r, i, j) into tri to connect r to this edge of the polygonal cavity. If (i, j) is a segment, then the situation is more complicated. In particular, r being on an edge of V might imply that we are going to add a degenerate triangle (r, i, j) into tri, and so this needs to be avoided. So, we check if is_on(flag) && contains_segment(tri, i, j) and, if the edge that r is on is (i, j), we add the triangle (r, i, j). Otherwise, we do nothing.

source

DelaunayTriangulation.enter_cavity — Function

enter_cavity(tri::Triangulation, r, i, j, ℓ, predicates::AbstractPredicateKernel=AdaptiveKernel()) -> Bool

Determines whether to enter the cavity in tri through the edge (i, j) when inserting r into the triangulation.

Arguments

tri: The Triangulation.
r: The new point being inserted.
i: The first vertex of the edge (i, j).
j: The second vertex of the edge (i, j).
ℓ: The vertex adjacent to (j, i), so that the triangle being stepped into is (j, i, ℓ).
predicates::AbstractPredicateKernel=AdaptiveKernel(): Method to use for computing predicates. Can be one of FastKernel, ExactKernel, and AdaptiveKernel. See the documentation for a further discussion of these methods.

Output

true if the cavity should be entered, and false otherwise. See also dig_cavity! and point_position_relative_to_circumcircle.

source

DelaunayTriangulation.get_initial_search_point — Method

get_initial_search_point(tri::Triangulation, num_points, new_point, insertion_order, num_sample_rule::F, rng, try_last_inserted_point) where {F} -> Vertex

For a given iteration of the Bowyer-Watson algorithm, finds the point to start the point location with find_triangle at.

Arguments

tri: The triangulation.
num_points: The number of points currently in the triangulation.
new_point: The point to insert.
insertion_order: The insertion order of the points. See get_insertion_order.
num_sample_rule::F: The rule to use to determine the number of points to sample. See default_num_samples for the default.
rng::Random.AbstractRNG: The random number generator to use.
try_last_inserted_point: If true, then the last inserted point is also considered as the start point.

Output

initial_search_point: The vertex to start the point location with find_triangle at.

source

DelaunayTriangulation.get_initial_triangle — Function

get_initial_triangle(tri::Triangulation, insertion_order, itr=0) -> Triangle

Gets the initial triangle for the Bowyer-Watson algorithm.

Arguments

tri: The triangulation.
insertion_order: The insertion order of the points. See get_insertion_order.
predicates::AbstractPredicateKernel=AdaptiveKernel(): Method to use for computing predicates. Can be one of FastKernel, ExactKernel, and AdaptiveKernel. See the documentation for a further discussion of these methods.
itr=0: To avoid issues with degenerate triangles and infinite loops, this counts the number of times insertion_order had to be shifted using circshift! to find an initial non-degenerate triangle.

Output

initial_triangle: The initial triangle.

source

DelaunayTriangulation.get_insertion_order — Method

get_insertion_order(points, randomise, skip_points, ::Type{I}, rng) where {I} -> Vector{I}
get_insertion_order(tri::Triangulation, randomise, skip_points, rng) -> Vector{I}

Gets the insertion order for points into a triangulation.

Arguments

points: The points to insert.
randomise: If true, then the insertion order is randomised. Otherwise, the insertion order is the same as the order of the points.
skip_points: The points to skip.
I::Type{I}: The type of the vertices.
rng::Random.AbstractRNG: The random number generator to use.

Output

order: The order to insert the points in.

Mutation of `order`

This order might be mutated (by circshift!) in get_initial_triangle.

source

DelaunayTriangulation.initialise_bowyer_watson! — Function

initialise_bowyer_watson!(tri::Triangulation, insertion_order, predicates::AbstractPredicateKernel=AdaptiveKernel()) -> Triangulation

Initialises the Bowyer-Watson algorithm.

Arguments

tri: The triangulation.
insertion_order: The insertion order of the points. See get_insertion_order.
predicates::AbstractPredicateKernel=AdaptiveKernel(): Method to use for computing predicates. Can be one of FastKernel, ExactKernel, and AdaptiveKernel. See the documentation for a further discussion of these methods.

Output

tri is updated in place to contain the initial triangle from which the Bowyer-Watson algorithm starts.

source

DelaunayTriangulation.unconstrained_triangulation! — Method

unconstrained_triangulation!(tri::Triangulation; kwargs...)

Computes the unconstrained Delaunay triangulation of the points in tri.

Arguments

tri: The triangulation.

Keyword Arguments

predicates::AbstractPredicateKernel=AdaptiveKernel(): Method to use for computing predicates. Can be one of FastKernel, ExactKernel, and AdaptiveKernel. See the documentation for a further discussion of these methods.
randomise=true: If true, then the insertion order is randomised. Otherwise, the insertion order is the same as the order of the points.
skip_points=(): The vertices to skip.
num_sample_rule::M=default_num_samples: The rule to use to determine the number of points to sample. See default_num_samples for the default.
rng::Random.AbstractRNG=Random.default_rng(): The random number generator to use.
insertion_order=get_insertion_order(tri, randomise, skip_points, rng): The insertion order of the points. See get_insertion_order.

Outputs

There is no output, but tri is updated in-place.

source

Triangulation Rectangular Domains

Here are some of the internal functions used for triangulate_rectangle.

DelaunayTriangulation.get_lattice_triangles — Function

get_lattice_triangles(nx, ny, Ts, V)

Computes the triangles defining a lattice with nx and ny points in the x- and y-directions, respectively.

See triangulate_rectangle.

Arguments

nx: The number of x points in the lattice.
ny: The number of y points in the lattice.
Ts: The type to use for representing a collection of triangles.
V: The type to use for representing an individual triangle.

Outputs

T: The collection of triangles.
sub2ind: A map that takes cartesian indices (i, j) into the associated linear index along the lattice. See LinearIndices.

source

DelaunayTriangulation.get_lattice_points — Function

get_lattice_points(a, b, c, d, nx, ny, sub2ind)

Returns the points on a lattice [a, b] × [c, d].

See triangulate_rectangle.

Arguments

a: The minimum x-coordinate.
b: The maximum x-coordinate.
c: The minimum y-coordinate.
d: The maximum y-coordinate.
nx: The number of points in the x-direction.
ny: The number of points in the y-direction.
sub2ind: The map returned from get_lattice_triangles.

Outputs

points: The points on the lattice, where points[sub2ind[CartesianIndex(i, j)]] is the point at the ith x point and the jth y point,

source

DelaunayTriangulation.get_lattice_boundary — Function

get_lattice_boundary(nx, ny, sub2ind, single_boundary, IntegerType)

Returns the boundary nodes defining a lattice.

See triangulate_rectangle.

Arguments

nx: The number of x points in the lattice.
ny: The number of y points in the lattice.
sub2ind: The map returned from get_lattice_triangles.
single_boundary: If true, then the boundary nodes are stored as a contiguous section. Otherwise, the boundary is split into four sections, in the order bottom, right, top, left.
IntegerType: The type used for representing vertices.

Outputs

boundary_nodes: The boundary nodes, returned according to single_boundary as described above.

source

Triangulating Convex Polygons

Here are some functions used in triangulate_convex for triangulating a convex polygon.

DelaunayTriangulation.add_point_convex_triangulation! — Function

add_point_convex_triangulation!(tri::Triangulation, u, v, w, S, predicates::AbstractPredicateKernel=AdaptiveKernel())

Adds the point u into the triangulation tri.

Arguments

tri::Triangulation: The Triangulation.
u: The vertex to add.
v: The vertex next to u.
w: The vertex previous to u.
S: The set of vertices of the polygon.
predicates::AbstractPredicateKernel=AdaptiveKernel(): Method to use for computing predicates. Can be one of FastKernel, ExactKernel, and AdaptiveKernel. See the documentation for a further discussion of these methods.

Outputs

There is no output, as tri is modified in-place.

Extended help

This function forms part of Chew's algorithm for triangulating a convex polygon. There are some important points to make.

Firstly, checking that x = get_adjacent(tri, w, v) is needed to prevent the algorithm from exiting the polygon.

This is important in case this algorithm is used as part of delete_point!. When you are just triangulating a convex polygon by itself, this checked is the same as checking edge_exists(tri, w, v).

For this method to be efficient, the set x ∈ S must be O(1) time. This is why we use a Set type for S.
The algorithm is recursive, recursively digging further through the polygon to find non-Delaunay edges to adjoins with u.

source

DelaunayTriangulation.delete_vertices_in_random_order! — Method

delete_vertices_in_random_order!(list::Triangulation, tri::ShuffledPolygonLinkedList, rng, predicates::AbstractPredicateKernel)

Deletes the vertices of the polygon represented by list in random order, done by switching the pointers of the linked list. Only three vertices will survive. If these these three vertices are collinear, then the deletion is attempted again after reshuffling the vertices.

Arguments

list::ShuffledPolygonLinkedList: The linked list representing the polygon to be deleted.
tri::Triangulation: The Triangulation.
rng::Random.AbstractRNG: The random number generator used to shuffle the vertices of S.
predicates::AbstractPredicateKernel: Method to use for computing predicates. Can be one of FastKernel, ExactKernel, and AdaptiveKernel. See the documentation for a further discussion of these methods.

Outputs

There is no output, as list is modified in-place.

source

DelaunayTriangulation.postprocess_triangulate_convex! — Method

postprocess_triangulate_convex!(tri::Triangulation, S; delete_ghosts, delete_empty_features)

Postprocesses the completed triangulation tri of the convex polygon S.

Arguments

tri::Triangulation: The Triangulation.
S: The vertices of the convex polygon, as in triangulate_convex.

Keyword Arguments

delete_ghosts=false: If true, the ghost triangles are deleted after triangulation.
delete_empty_features=true: If true, the empty features are deleted after triangulation.

Output

There are no output, as tri is modified in-place. The postprocessing that is done is:

The convex hull of tri is set to S.
The ghost triangles are deleted if delete_ghosts=true.
The empty features are deleted if delete_empty_features=true.
The representative points are set to the centroid of S.

source

DelaunayTriangulation.triangulate_convex! — Method

triangulate_convex!(tri::Triangulation, S; rng::Random.AbstractRNG=Random.default_rng(), predicates::AbstractPredicateKernel=AdaptiveKernel())

Triangulates the convex polygon S in-place into tri.

Arguments

tri::Triangulation: The triangulation to be modified.
S: A convex polygon represented as a vector of vertices. The vertices should be given in counter-clockwise order, and must not be circular so that S[begin] ≠ S[end].

Keyword Arguments

rng=Random.default_rng(): The random number generator used to shuffle the vertices of S before triangulation.
predicates::AbstractPredicateKernel=AdaptiveKernel(): Method to use for computing predicates. Can be one of FastKernel, ExactKernel, and AdaptiveKernel. See the documentation for a further discussion of these methods.

Outputs

There is no output, as tri is updated in-place. This function does not do any post-processing, e.g. deleting any ghost triangles. This is done by triangulate_convex or postprocess_triangulate_convex!.

source

DelaunayTriangulation.triangulate_convex — Method

triangulate_convex(points, S; delete_ghosts=false, delete_empty_features=true, rng=Random.default_rng(), predicates::AbstractPredicateKernel=AdaptiveKernel(), kwargs...) -> Triangulation

Triangulates the convex polygon S.

Arguments

points: The point set corresponding to the vertices in S.
S: A convex polygon represented as a vector of vertices. The vertices should be given in counter-clockwise order, and must not be circular so that S[begin] ≠ S[end].

Keyword Arguments

delete_ghosts=false: If true, the ghost triangles are deleted after triangulation.
delete_empty_features=true: If true, the empty features are deleted after triangulation.
rng=Random.default_rng(): The random number generator used to shuffle the vertices of S before triangulation.
predicates::AbstractPredicateKernel=AdaptiveKernel(): Method to use for computing predicates. Can be one of FastKernel, ExactKernel, and AdaptiveKernel. See the documentation for a further discussion of these methods.
kwargs...: Additional keyword arguments passed to Triangulation.

Output

tri::Triangulation: The triangulated polygon.

source

Constrained Triangulations

There are many functions to list for the computation of a constrained triangulation.

DelaunayTriangulation.add_segment! — Method

add_segment!(tri::Triangulation, segment; predicates::AbstractPredicateKernel=AdaptiveKernel(), rng::Random.AbstractRNG=Random.default_rng())
add_segment!(tri::Triangulation, i, j; predicates::AbstractPredicateKernel=AdaptiveKernel(), rng::Random.AbstractRNG=Random.default_rng())

Adds segment = (i, j) to tri.

Arguments

tri::Triangulation: The Triangulation.
segment: The segment to add. The second method uses (i, j) to represent the segment instead.

Keyword Arguments

predicates::AbstractPredicateKernel=AdaptiveKernel(): Method to use for computing predicates. Can be one of FastKernel, ExactKernel, and AdaptiveKernel. See the documentation for a further discussion of these methods.
rng::AbstractRNG=Random.default_rng(): The RNG object.

Outputs

There is no output, but tri will be updated so that it now contains segment.

source

DelaunayTriangulation.add_segment_to_list! — Method

add_segment_to_list!(tri::Triangulation, e)

Adds e to get_interior_segments(tri) and get_all_segments(tri) if it, or reverse_edge(e), is not already in the sets.

Arguments

tri::Triangulation: The Triangulation.
e: The edge to add.

Outputs

There is no output, but tri will be updated so that e is in get_interior_segments(tri) and get_all_segments(tri).

source

DelaunayTriangulation.fix_edge_order_after_rotation! — Method

fix_edge_order_after_rotation!(tri::Triangulation, segment, e)

Fixes the edge order in get_interior_segments(tri) after segment was rotated by optimise_edge_order.

Arguments

tri::Triangulation: The Triangulation.
segment: The segment that was arranged.
e: The arranged segment from optimise_edge_order.

Outputs

There is no output, but tri will be updated so that e is in get_interior_segments(tri) instead of segment.

source

DelaunayTriangulation.optimise_edge_order — Method

optimise_edge_order(tri::Triangulation, segment) -> Edge

Optimises the orientation of segment for inserting it into the triangulation.

Arguments

tri::Triangulation: The Triangulation.
segment: The segment to arrange.

Outputs

e: If segment is a boundary edge, then e = segment, Otherwise, e = sort_edge_by_degree(tri, segment) so that initial(e) has the smaller degree of the two vertices.

source

DelaunayTriangulation.add_new_triangles! — Method

add_new_triangles!(tri_original::Triangulation, tris)

Adds the triangles from tris to tri_original.

source

DelaunayTriangulation.add_point_cavity_cdt! — Function

add_point_cavity_cdt!(tri::Triangulation, u, v, w, marked_vertices)

Adds a point to the cavity V left behind when deleting triangles intersected in a triangulation by an edge, updating tri to do so.

Arguments

tri::Triangulation: The Triangulation to update.
u: The vertex to add.
v: The vertex along the polygon that is next to u.
w: The vertex along the polygon that is previous to u.
marked_vertices: Cache for marking vertices to re-triangulate during the triangulation. This gets mutated.

Outputs

There is no output, but tri is updated in-place, as is marked_vertices if necessary.

source

DelaunayTriangulation.connect_segments! — Method

connect_segments!(segments)

Connects the ordered vector of segments so that the endpoints all connect, preserving order.

Example

julia> using DelaunayTriangulation

julia> segments = [(7, 12), (12, 17), (17, 22), (32, 37), (37, 42), (42, 47)];

julia> DelaunayTriangulation.connect_segments!(segments)
7-element Vector{Tuple{Int64, Int64}}:
 (7, 12)
 (12, 17)
 (17, 22)
 (22, 32)
 (32, 37)
 (37, 42)
 (42, 47)

source

DelaunayTriangulation.constrained_triangulation! — Method

constrained_triangulation!(tri::Triangulation, segments, boundary_nodes, predicates::AbstractPredicateKernel, full_polygon_hierarchy; rng=Random.default_rng(), delete_holes=true) -> Triangulation

Creates a constrained triangulation from tri by adding segments and boundary_nodes to it. This will be in-place, but a new triangulation is returned to accommodate the changed types.

Arguments

tri::Triangulation: The Triangulation.
segments: The interior segments to add to the triangulation.
boundary_nodes: The boundary nodes to add to the triangulation.
predicates::AbstractPredicateKernel: Method to use for computing predicates. Can be one of FastKernel, ExactKernel, and AdaptiveKernel. See the documentation for a further discussion of these methods.
full_polygon_hierarchy: The PolygonHierarchy defining the boundary. This will get copied into the existing polygon hierarchy.

Keyword Arguments

rng=Random.default_rng(): The random number generator to use.
delete_holes=true: Whether to delete holes in the triangulation. See delete_holes!.

Outputs

new_tri: The new triangulation, now containing segments in the interior_segments field and boundary_nodes in the boundary_nodes field, and with the updated PolygonHierarchy. See also remake_triangulation_with_constraints and replace_ghost_vertex_information.

source

DelaunayTriangulation.delete_intersected_triangles! — Method

delete_intersected_triangles!(tri, triangles)

Deletes the triangles in triangles from tri.

source

DelaunayTriangulation.delete_polygon_vertices_in_random_order! — Method

delete_polygon_vertices_in_random_order!(list::ShuffledPolygonLinkedList, tri::Triangulation, u, v, rng::Random.AbstractRNG, predicates::AbstractPredicateKernel)

Deletes vertices from the polygon defined by list in a random order.

Arguments

list::ShuffledPolygonLinkedList: The linked list of polygon vertices.
tri::Triangulation: The Triangulation.
u, v: The vertices of the segment (u, v) that was inserted in order to define the polygon V = list.S.
rng::Random.AbstractRNG: The random number generator to use.
predicates::AbstractPredicateKernel: Method to use for computing predicates. Can be one of FastKernel, ExactKernel, and AdaptiveKernel. See the documentation for a further discussion of these methods.

Outputs

There is no output, but list is updated in-place.

source

DelaunayTriangulation.extend_segments! — Method

extend_segments!(segments, segment)

Given an ordered vector of segments, ensures that they also represent the replacement of segment. In particular, suppose segments represents the sequence of edges

    ---(i₁, i₂)---(i₂, i₃)---(⋯, ⋯)---(iₙ₋₁, iₙ)---

and segment is (i₀, iₙ₊₁). Then the extended sequence becomes

    ---(i₀, i₁)---(i₁, i₂)---(i₂, i₃)---(⋯, ⋯)---(iₙ₋₁, iₙ)---(iₙ, iₙ₊₁)---

Example

julia> using DelaunayTriangulation

julia> segments = [(2, 7), (7, 12), (12, 49)];

julia> segment = (1, 68);

julia> DelaunayTriangulation.extend_segments!(segments, segment)
5-element Vector{Tuple{Int64, Int64}}:
 (1, 2)
 (2, 7)
 (7, 12)
 (12, 49)
 (49, 68)

source

DelaunayTriangulation.fix_segments! — Method

fix_segments!(segments, bad_indices)

Fixes the overlapping segments in segments, referred to via bad_indices, by connecting consecutive edges where needed.

Arguments

segments: The segments to fix.
bad_indices: The indices of the segments to fix.

Outputs

There are no outputs as segments is updated in-place.

Example

julia> using DelaunayTriangulation

julia> segments = [(2, 15), (2, 28), (2, 41)]; # the edges all start with 2, so they are not actual segments in the triangulation, and so must be fixed

julia> bad_indices = [1, 2, 3];

julia> DelaunayTriangulation.fix_segments!(segments, bad_indices)
3-element Vector{Tuple{Int64, Int64}}:
 (2, 15)
 (15, 28)
 (28, 41)

julia> segments = [(2, 7), (2, 12), (12, 17), (2, 22), (2, 27), (2, 32), (32, 37), (2, 42), (42, 47)];

julia> bad_indices = [2, 4, 5, 6, 8]
5-element Vector{Int64}:
 2
 4
 5
 6
 8

julia> DelaunayTriangulation.fix_segments!(segments, bad_indices)
9-element Vector{Tuple{Int64, Int64}}:
 (2, 7)
 (7, 12)
 (12, 17)
 (17, 22)
 (22, 27)
 (27, 32)
 (32, 37)
 (37, 42)
 (42, 47)

source

DelaunayTriangulation.is_vertex_closer_than_neighbours — Method

is_vertex_closer_than_neighbours([predicates::AbstractPredicateKernel=AdaptiveKernel(),] tri::Triangulation, u, v, jᵢ, jᵢ₋₁, jᵢ₊₁) -> Bool
is_vertex_closer_than_neighbours([predicates::AbstractPredicateKernel=AdaptiveKernel(),] tri::Triangulation, list::ShuffledPolygonLinkedList, u, v, j) -> Bool

Tests if the vertex jᵢ is closer to the line (u, v) than its neighbours jᵢ₋₁ and jᵢ₊₁, assuming all these vertices are to the left of the line.

Weighted Triangulations

DelaunayTriangulation.add_weight! — Method

add_weight!(weights, w)

Pushes the weight w into weights. The default definition for this is push!(weights, w).

source

DelaunayTriangulation.add_weight! — Method

add_weight!(tri::Triangulation, w)

Pushes the weight w into the weights of tri.

source

DelaunayTriangulation.get_distance_to_witness_plane — Method

" getdistancetowitnessplane([kernel::AbstractPredicateKernel = AdaptiveKernel(), ] tri::Triangulation, i, V; cache = nothing) -> Number

Computes the distance between the lifted companion of the vertex i and the witness plane to the triangle V. If V is a ghost triangle and i is not on its solid edge, then the distance is -Inf if it is below the ghost triangle's witness plane and Inf if it is above. If V is a ghost triangle and i is on its solid edge, then the distance returned is the distance associated with the solid triangle adjoining V.

In general, the distance is positive if the lifted vertex is above the witness plane, negative if it is below, and zero if it is on the plane.

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 cache keyword argument is passed to [point_position_relative_to_circumcircle]. Please see the documentation for that function for more information.

source

DelaunayTriangulation.get_lifted_point — Method

get_lifted_point(p, w) -> NTuple{3, Number}

Returns the lifted companion of the point p, in particular (x, y, x^2 + y^2 - w), where (x, y) is p.

source

DelaunayTriangulation.get_lifted_point — Method

get_lifted_point(tri::Triangulation, i) -> NTuple{3, Number}

Returns the lifted companion of the ith vertex of tri, in particular (x, y, x^2 + y^2 - w), where w is the ith weight of tri and (x, y) is the ith point of tri.

source

DelaunayTriangulation.get_power_distance — Method

get_power_distance(tri::Triangulation, i, j) -> Number

Returns the power distance between vertices i and j, defined by ||pᵢ - pⱼ||^2 - wᵢ - wⱼ, where wᵢ and wⱼ are the respective weights.

source

DelaunayTriangulation.get_weight — Method

get_weight(weights, i) -> Number

Gets the ith weight from weights. The default definition for this is weights[i], but this can be extended - e.g., ZeroWeight uses get_weight(weights, i) = 0.0.

If i is not an integer, then the default definition is is_point3(i) ? i[3] : zero(number_type(weights)).

source

DelaunayTriangulation.get_weight — Method

get_weight(tri::Triangulation, i) -> Number

Gets the ith weight from tri.

source

DelaunayTriangulation.get_weighted_nearest_neighbour — Function

get_weighted_nearest_neighbour(tri::Triangulation, i, j = rand(each_solid_vertex(tri))) -> Vertex

Using a greedy search, finds the closest vertex in tri to the vertex i (which might not already be in tri), measuring distance in lifted space (i.e., using the power distance - see get_power_distance). The search starts from the vertex j which should be in tri.

source

DelaunayTriangulation.is_submerged — Function

is_submerged([kernel::AbstractPredicateKernel = AdaptiveKernel(), ] tri::Triangulation, i; cache = nothing) -> Bool 
is_submerged([kernel::AbstractPredicateKernel = AdaptiveKernel(), ] tri::Triangulation, i, V; cache = nothing) -> Bool

Returns true if the vertex i is submerged in tri and false otherwise. In the second method, V is a triangle containing tri.

The cache keyword argument is passed to [point_position_relative_to_circumcircle]. Please see the documentation for that function for more information.

source

DelaunayTriangulation.is_weighted — Method

is_weighted(weights) -> Bool

Returns true if weights represents a set of weights that are not all zero, and false otherwise. Note that even for vectors like zeros(n), this will return true; by default, false is returned only for weights = ZeroWeight().

source

Here are some functions involved with mesh refinement.

DelaunayTriangulation._split_subsegment_curve_bounded! — Method

_split_subsegment_curve_bounded!(tri::Triangulation, args::RefinementArguments, e)

Splits a subsegment e of tri at a position determined by split_subcurve! for curve-bounded domains. See split_subsegment!. See also _split_subsegment_curve_bounded_standard! and _split_subsegment_curve_bounded_small_angle!, as well as the original functions _split_subsegment_curve_standard! and _split_subcurve_complex!, respectively, used during boundary enrichment.

source

DelaunayTriangulation._split_subsegment_piecewise_linear! — Method

_split_subsegment_piecewise_linear!(tri::Triangulation, args::RefinementArguments, e)

Splits a subsegment e of tri at a position determined by compute_split_position for piecewise linear domains. See split_subsegment!.

source

DelaunayTriangulation.assess_added_triangles! — Method

assess_added_triangles!(args::RefinementArguments, tri::Triangulation)

Assesses the quality of all triangles in args.events.added_triangles according to assess_triangle_quality, and enqueues any bad quality triangles into args.queue.

source

DelaunayTriangulation.assess_triangle_quality — Method

assess_triangle_quality(tri::Triangulation, args::RefinementArguments, T) -> Float64, Bool

Assesses the quality of a triangle T of tri according to the RefinementArguments.

Arguments

tri::Triangulation: The Triangulation.
args::RefinementArguments: The RefinementArguments.
T: The triangle.

Output

ρ: The radius-edge ratio of the triangle.
flag: Whether the triangle is bad quality.

A triangle is bad quality if it does not meet the area constraints, violates the custom constraint, or if it is skinny but neither seditious or nestled.

source

DelaunayTriangulation.balanced_power_of_two_quarternary_split — Method

balanced_power_of_two_quarternary_split(ℓ) -> Float

Returns the value of s ∈ [0, ℓ] that gives the most balanced quarternary split of the segment pq, so s is a power-of-two and s ∈ [ℓ / 4, ℓ / 2].

source

DelaunayTriangulation.balanced_power_of_two_ternary_split — Method

balanced_power_of_two_ternary_split(ℓ) -> Float64

Returns the value of s ∈ [0, ℓ] that gives the most balanced ternary split of the segment pq, so s is a power-of-two and s ∈ [ℓ / 3, 2ℓ / 3].

source

DelaunayTriangulation.check_for_invisible_steiner_point — Method

check_for_invisible_steiner_point(tri::Triangulation, V, T, flag, c) -> Point, Triangle

Determines if the Steiner point c's insertion will not affect the quality of T, and if so instead changes c to be T's centroid.

Arguments

tri::Triangulation: The Triangulation to split a triangle of.
V: The triangle that the Steiner point is in.
T: The triangle that the Steiner point is from.
flag: A Certificate which is Cert.On if the Steiner point is on the boundary of V, Cert.Outside if the Steiner point is outside of V, and Cert.Inside if the Steiner point is inside of V.
c: The Steiner point.

Output

c′: The Steiner point to use instead of c, which is T's centroid if c is not suitable.
V′: The triangle that the Steiner point is in, which is T if c is not suitable.

source

DelaunayTriangulation.check_for_steiner_point_on_segment — Method

check_for_steiner_point_on_segment(tri::Triangulation, V, V′, new_point, flag, predicates::AbstractPredicateKernel) -> Bool

Checks if the Steiner point with vertex new_point is on a segment. If so, then its vertex is pushed into the offcenter-split list from args, indicating that it should no longer be regarded as a free vertex (see is_free).

Arguments

tri::Triangulation: The Triangulation.
V: The triangle that the Steiner point was originally in prior to check_for_invisible_steiner_point.
V′: The triangle that the Steiner point is in.
new_point: The vertex associated with the Steiner point.
flag: A Certificate which is Cert.On if the Steiner point is on the boundary of V, Cert.Outside if the Steiner point is outside of V, and Cert.Inside if the Steiner point is inside of V.
predicates::AbstractPredicateKernel: Method to use for computing predicates. Can be one of FastKernel, ExactKernel, and AdaptiveKernel. See the documentation for a further discussion of these methods.

Output

onflag: Whether the Steiner point is on a segment or not.

source

DelaunayTriangulation.check_seditious_precision — Method

check_seditious_precision(ℓrp, ℓrq) -> Bool

Checks if there are precision issues related to the seditiousness of a triangle, returning true if so and false otherwise.

source

DelaunayTriangulation.check_split_subsegment_precision — Method

check_split_subsegment_precision(mx, my, p, q) -> Bool

Checks if there are precision issues related to the computed split position (mx, my) of a segment (p, q), returning true if so and false otherwise.

source

DelaunayTriangulation.check_steiner_point_precision — Method

check_steiner_point_precision(tri::Triangulation, T, c) -> Bool

Checks if the Steiner point c of a triangle T of tri can be computed without precision issues, returning true if there are precision issues and false otherwise.

source

DelaunayTriangulation.compute_concentric_shell_quarternary_split_position — Method

compute_concentric_shell_quarternary_split_position(p, q) -> Float64

Returns the value of t ∈ [0, 1] that gives the most balanced quarternary split of the segment pq, so that one of the segments has a power-of-two length between 1/4 and 1/2 of the length of pq.

source

DelaunayTriangulation.compute_concentric_shell_ternary_split_position — Method

compute_concentric_shell_ternary_split_position(p, q) -> Float64

Returns the value of t ∈ [0, 1] that gives the most balanced ternary split of the segment pq, so that one of the segments has a power-of-two length and both segments have lengths between 1/3 and 2/3 of the length of pq.

source

DelaunayTriangulation.compute_split_position — Method

compute_split_position(tri::Triangulation, args::RefinementArguments, e) -> NTuple{2, Float}

Computes the position to split a segment e of tri at in split_subsegment!.

Arguments

tri::Triangulation: The Triangulation to split a segment of.
args::RefinementArguments: The RefinementArguments for the refinement.
e: The segment to split.

Output

mx, my: The position to split the segment at.

This point is computed according to a set of rules:

If e is not a subsegment, meaning it is an input segment, then its midpoint is returned.
If e is a subsegment and the segment adjoins two other distinct segments (one for each vertex) at an acute angle, as determined by segment_vertices_adjoin_other_segments_at_acute_angle, then the point is returned so that e can be split such that one of the new subsegments has a power-of-two length between 1/4 and 1/2 of the length of e, computed using compute_concentric_shell_quarternary_split_position.
If e is a subsegment and the segment adjoins one other segment at an acute angle, as determined by segment_vertices_adjoin_other_segments_at_acute_angle, then the point is returned so that e can be split such that one of the new subsegments has a power-of-two length between 1/3 and 2/3 of the length of e, computed using compute_concentric_shell_ternary_split_position.
Otherwise, the midpoint is returned.

source

DelaunayTriangulation.delete_free_vertices_around_subsegment! — Method

delete_free_vertices_around_subsegment!(tri::Triangulation, args::RefinementArguments, e)

Deletes all free vertices (i.e., Steiner points) contained in the diametral circle of e.

Arguments

tri::Triangulation: The Triangulation.
args::RefinementArguments: The RefinementArguments.
e: The segment.

Output

The free vertices are deleted from tri in-place.

source

DelaunayTriangulation.encroaches_upon — Method

encroaches_upon(p, q, r, args::RefinementArguments) -> Bool

Determines if a point r encroaches upon a segment pq according to the RefinementArguments.

source

DelaunayTriangulation.enqueue_all_bad_triangles! — Method

enqueue_all_bad_triangles!(args::RefinementArguments, tri::Triangulation)

Enqueues all bad triangles in the triangulation into args.queue.

source

DelaunayTriangulation.enqueue_all_encroached_segments! — Method

enqueue_all_encroached_segments!(args::RefinementArguments, tri::Triangulation)

Enqueues all encroached segments in the triangulation into args.queue.

source

DelaunayTriangulation.enqueue_newly_encroached_segments! — Method

enqueue_newly_encroached_segments!(args::RefinementArguments, tri::Triangulation) -> Bool

Enqueues all segments that are newly encroached upon after a point insertion into the triangulation into args.queue.

Arguments

args::RefinementArguments: The RefinementArguments for the refinement.
tri::Triangulation: The Triangulation to enqueue newly encroached segments of.

Output

any_encroached: Whether any segments were newly encroached upon.

source

DelaunayTriangulation.finalise! — Method

finalise!(tri::Triangulation, args::RefinementArguments)

Finalises the triangulation after refinement, e.g. by deleting ghost triangles and unlocking the convex hull if needed.

source

DelaunayTriangulation.get_init_for_steiner_point — Method

get_init_for_steiner_point(tri::Triangulation, T) -> Vertex

Gets the initial vertex to start the search for the Steiner point of a triangle T of tri in get_steiner_point. The initial vertex is chosen so that it is opposite the longest edge.

source

DelaunayTriangulation.get_steiner_point — Method

get_steiner_point(tri::Triangulation, args::RefinementArguments, T) -> Certificate, Point

Computes the Steiner point for a triangle T of tri to improve its quality in split_triangle!.

Arguments

tri::Triangulation: The Triangulation to split a triangle of.
args::RefinementArguments: The RefinementArguments for the refinement.
T: The triangle to split.

Output

precision_flag: A Certificate which is Cert.PrecisionFailure if the Steiner point could not be computed due to precision issues, and Cert.None otherwise.
c: The Steiner point. If is_precision_failure(precision_flag), then this is just an arbitrary point of T to ensure type stability.

source

DelaunayTriangulation.is_encroached — Method

is_encroached(tri::Triangulation, args::RefinementArguments, edge) -> Bool

Determines if a segment edge of tri is encroached upon.

RTree

The RTrees we work with during boundary enrichment have several functions associated with them.

DelaunayTriangulation.EnlargementValues — Type

EnlargementValues

Type for representing the values used in the minimisation of enlargement.

Fields

enlargement::Float64: The enlargement of the bounding box of the child being compared with.
idx::Int: The index of the child being compared with.
area::Float64: The area of the child being compared with.
bounding_box::BoundingBox: The bounding box being compared with for enlargement.

Constructor

EnlargementValues(enlargement, idx, area, bounding_box)
EnlargementValues(bounding_box)

source

Base.append! — Method

append!(node::AbstractNode, child)

Appends child to node's children. Also updates node's bounding box.

source

Base.delete! — Method

delete!(tree::RTree, id_bounding_box::DiametralBoundingBox)

Deletes id_bounding_box from tree.

source

Base.insert! — Method

insert!(node::AbstractNode, child, tree::RTree) -> Bool

Inserts child into node in tree. Returns true if the tree's bounding boxes had to be adjusted and false otherwise.

source

Base.insert! — Method

insert!(tree::RTree, bounding_box[, level = 1]) -> Bool

Inserts bounding_box into tree. Returns true if the tree's bounding boxes had to be adjusted and false otherwise.

source

Base.iterate — Method

iterate(itr::RTreeIntersectionIterator, state...)

Iterate over the next state of itr to find more intersections with the bounding box in RTreeIntersectionIterator.

source

DelaunayTriangulation.collapse_after_deletion! — Method

collapse_after_deletion!(node::AbstractNode, tree::RTree, detached)

Condenses tree after a deletion of one of node's children. The detached argument will contain the nodes that were detached from tree during the condensing process.

source

DelaunayTriangulation.detach! — Method

detach!(node::AbstractNode, idx) -> Bool

Detaches the idxth child of node. Returns true if the node's bounding box had to be adjusted and false otherwise.

source

DelaunayTriangulation.find_bounding_box — Method

find_bounding_box(tree::RTree, id_bounding_box::DiametralBoundingBox) -> Tuple{Leaf{Branch}, Int}

Returns the leaf node and the index in the leaf node's children that id_bounding_box is associated with.

source

DelaunayTriangulation.find_subtree — Method

find_subtree(tree, bounding_box, level) -> Union{Branch,Leaf{Branch}}

Returns the subtree of tree at level that bounding_box should be inserted into.

source

DelaunayTriangulation.get_intersections — Method

get_intersections(tree::RTree, bounding_box::BoundingBox; cache_id=1) -> RTreeIntersectionIterator

Returns an RTreeIntersectionIterator over the elements in tree that intersect with bounding_box. cache_id must be 1 or 2, and determines what cache to use for the intersection query.

source

DelaunayTriangulation.get_intersections — Method

get_intersections(tree::RTree, point::NTuple{2,<:Number}; cache_id=1) -> RTreeIntersectionIterator

Returns an RTreeIntersectionIterator over the elements in tree that intersect with point, representing point as a BoundingBox with zero width and height centered at point. cache_id must be 1 or 2, and determines what cache to use for the intersection query.

source

DelaunayTriangulation.get_next_child — Method

get_next_child(node::AbstractNode, start_idx, need_tests, itr::RTreeIntersectionIterator) -> Int, QueryResult

Returns the index of the next child of node that intersects with the bounding box in itr and the QueryResult of the intersection.

source

DelaunayTriangulation.insert_detached! — Method

insert_detached!(tree::RTree, detached)

Given the detached nodes from collapse_after_deletion!, inserts them back into tree.

source

DelaunayTriangulation.minimise_enlargement — Method

minimise_enlargement(node, bounding_box) -> EnlargementValues

Returns the EnlargementValues associated with the child of node that minimises the enlargement, where enlargement is defined as the difference between the area of bounding_box and the area of the child's bounding box.

source

DelaunayTriangulation.overflow_insert! — Method

overflow_insert!(node, child, tree) -> Bool

Inserts child into node in tree when node is full. Returns true.

source

DelaunayTriangulation.replace! — Method

replace!(node::AbstractNode, left, right, original_bounding_box, tree::RTree)

Replaces the node in tree with left and right. Returns true if the tree's bounding boxes had to be adjusted and false otherwise.

source

DelaunayTriangulation.split! — Method

split!(node::AbstractNode, tree::RTree) -> Branch, Branch

Splits node into two other nodes using a linear splitting rule. Returns the two new nodes.

source

DelaunayTriangulation.split_seeds — Method

split_seeds(node::AbstractNode) -> NTuple{2, Int}

Returns the indices of two children in node used to initiate the split in split!.

source

DelaunayTriangulation.test_intersection — Method

test_intersection(node::AbstractNode, itr::RTreeIntersectionIterator) -> QueryResult

Tests whether node intersects with the bounding box in itr, returning a QueryResult.

source

DelaunayTriangulation.update_bounding_box! — Method

update_bounding_box!(node, idx, original_bounding_box, tree)

Updates the bounding box of node to be the union of its children's bounding boxes. If node has a parent, updates the bounding box of the parent as well if needed.

source

DelaunayTriangulation.update_bounding_box! — Method

update_bounding_box!(node)

Updates the bounding box of node to be the union of its children's bounding boxes.

source

DelaunayTriangulation.update_enlargement — Method

update_enlargement(values::EnlargementValues, child, idx) -> EnlargementValues

Compare the enlargement state in values with child and return the updated values if necessary.

source

Point Location

Here are some functions related to point location.

DelaunayTriangulation.brute_force_search — Method

brute_force_search(tri::Triangulation, q; itr = each_triangle(tri), predicates::AbstractPredicateKernel=AdaptiveKernel())

Searches for the triangle containing the point q by brute force. An exception will be raised if no triangle contains the point.

Triangulation Operations

Some of the triangulation operations have internal functions associated with them.

DelaunayTriangulation.delete_all_exterior_triangles! — Method

delete_all_exterior_triangles!(tri::Triangulation, triangles)

Deletes all the triangles in the set triangles from the triangulation tri.

source

DelaunayTriangulation.delete_holes! — Method

delete_holes!(tri::Triangulation)

Deletes all the exterior faces to the boundary nodes specified in the triangulation tri.

Extended help

This function works in several stages:

First, find_all_points_to_delete is used to identify all points in the exterior faces.
Once all the points to delete have been found, all the associated triangles are found using find_all_triangles_to_delete, taking care for any incorrectly identified triangles and points.
Once the correct set of triangles to delete has been found, they are deleted using delete_all_exterior_triangles!.

source

DelaunayTriangulation.find_all_points_to_delete! — Method

find_all_points_to_delete!(points_to_process, tri::Triangulation, seed, all_bn)

Starting at seed, finds more points to spread to and mark for deletion.

Arguments

points_to_process: The current list of points marked for deletion.
tri::Triangulation: The Triangulation.
seed: The seed vertex to start spreading from.
all_bn: All the boundary nodes in the triangulation, obtained from get_all_boundary_nodes.

Outputs

There are no outputs, as points_to_process is updated in-place.

Extended help

This function works by considering the neighbours around the vertex seed. For each neighbouring vertex, we designate that as a new seed, and consider if it needs to be added into points_to_process according to its distance from the triangulation computed from distance_to_polygon. We then call find_all_points_to_delete! recursively again on the new seed.

source

DelaunayTriangulation.find_all_points_to_delete — Method

find_all_points_to_delete(tri::Triangulation) -> Set{Int}

Returns a set of all the points that are in the exterior faces of the triangulation tri.

Extended help

This function works by 'spreading' from some initial vertex. In particular, starting at each boundary node, we spread outwards towards adjacent vertices, recursively spreading so that all exterior points are identified with the help of find_all_points_to_delete!.

source

DelaunayTriangulation.find_all_triangles_to_delete — Method

find_all_triangles_to_delete(tri::Triangulation, points_to_process) -> Set{Triangle}

Returns a set of all the triangles that are in the exterior faces of the triangulation tri.

Arguments

tri::Triangulation: The Triangulation.
points_to_process: The set of points that are in the exterior faces of the triangulation tri, obtained from find_all_points_to_delete.

Outputs

triangles_to_delete: The set of triangles that are in the exterior faces of the triangulation tri.

Extended help

This function works in two stages.

Firstly, all the non-boundary vertices, i.e. those from points_to_process, are processed. For each vertex v, the triangles adjoining it, given by get_adjacent2vertex(tri, v), aremarked for deletion.
Next, all the boundary vertices need to be processed and carefully analysed to determine if any other triangles need to be deleted since, for example, a triangle may be adjoining three vertices that are all boundary vertices, and it might not be obvious if it is inside or outside of the triangulation. By applying dist to compute the distance between the triangle's centroid and the triangulation, the triangle can be accurately marked for deletion if it is outside of the triangulation.

source

DelaunayTriangulation.check_delete_point_args — Method

check_delete_point_args(tri::Triangulation, vertex, S) -> Bool

Checks that the vertex vertex can be deleted from the triangulation tri. Returns true if so, and throws an InvalidVertexDeletionError otherwise. This will occur if:

vertex is a boundary node of tri.
vertex is a ghost vertex of tri.
vertex adjoins a segment of tri.

source

DelaunayTriangulation.delete_point! — Method

delete_point!(tri::Triangulation, vertex; kwargs...)

Deletes the vertex of tri, retriangulating the cavity formed by the surrounding polygon of vertex using triangulate_convex.

It is not possible to delete vertices that are on the boundary, are ghost vertices, or adjoin a segment of tri. See also check_delete_point_args.

Point deletion

This function will not actually delete the corresponding coordinates from get_points(tri), nor will it remove the associated weight from get_weights(tri).

Arguments

tri::Triangulation: Triangulation.
vertex: The vertex to delete.

Keyword Arguments

predicates::AbstractPredicateKernel=AdaptiveKernel(): Method to use for computing predicates. Can be one of FastKernel, ExactKernel, and AdaptiveKernel. See the documentation for a further discussion of these methods.
store_event_history=Val(false): Whether to store the event history of the triangulation from deleting the point.
event_history=nothing: The event history of the triangulation from deleting the point. Only updated if store_event_history is true, in which case it needs to be an InsertionEventHistory object.
rng::Random.AbstractRNG=Random.default_rng(): The random number generator to use for the triangulation.

source

DelaunayTriangulation.fix_edges_after_deletion! — Method

fix_edges_after_deletion!(tri::Triangulation, S)

Ensures that the edges in S surrounding a deleted vertex of tri are correctly updated.

source

DelaunayTriangulation.get_surrounding_polygon — Method

get_surrounding_polygon(tri::Triangulation, u; skip_ghost_vertices=false) -> Vector

Returns the counter-clockwise sequence of neighbours of u in tri.

Arguments

tri::Triangulation: Triangulation.
u: The vertex.

Keyword Arguments

skip_ghost_vertices=false: Whether to skip ghost vertices in the returned polygon.

Outputs

S: The surrounding polygon. This will not be circular, meaning S[begin] ≠ S[end]. In case u is an exterior ghost vertex, the returned polygon is a clockwise list of vertices for the associated boundary curve. If you do not have ghost triangles and you try to get the surrounding polygon of a ghost vertex, then this function may return an invalid polygon.

source

DelaunayTriangulation.complete_split_edge_and_legalise! — Function

complete_split_edge_and_legalise!(tri::Triangulation, i, j, r, store_event_history=Val(false), event_history=nothing; predicates::AbstractPredicateKernel=AdaptiveKernel())

Given a triangulation tri, an edge (i, j), and a point r, splits both (i, j) and (j, i) at r using split_edge! and then subsequently legalises the new edges with legalise_split_edge!.

Arguments

tri::Triangulation: The Triangulation.
i: The first vertex of the edge to split.
j: The second vertex of the edge to split.
r: The vertex to split the edge at.
store_event_history=Val(false): Whether to store the event history of the flip.
event_history=nothing: The event history. Only updated if store_event_history is true, in which case it needs to be an InsertionEventHistory object.

Keyword Arguments

predicates::AbstractPredicateKernel=AdaptiveKernel(): Method to use for computing predicates. Can be one of FastKernel, ExactKernel, and AdaptiveKernel. See the documentation for a further discussion of these methods.

Outputs

There is no output, as tri is updated in-place.

source

DelaunayTriangulation.get_edges_for_split_edge — Method

get_edges_for_split_edge(tri::Triangulation, i, j, r)

Returns the edges (i, j), (j, i), (i, r), (r, i), (r, j), and (j, r).

source

DelaunayTriangulation.legalise_split_edge! — Function

legalise_split_edge!(tri::Triangulation, i, j, k, r, store_event_history=Val(false), event_history=nothing; predicates::AbstractPredicateKernel=AdaptiveKernel())

Legalises the newly added edges in tri after the edge (i, j) was split using split_edge!.

Arguments

tri::Triangulation: The Triangulation.
i: The first vertex of the edge that was split.
j: The second vertex of the edge that was split.
k: The vertex that was originally adjacent to (i, j).
r: The vertex that (i, j) was split at.
store_event_history=Val(false): Whether to store the event history of the flip.
event_history=nothing: The event history. Only updated if store_event_history is true, in which case it needs to be an InsertionEventHistory object.

Keyword Arguments

predicates::AbstractPredicateKernel=AdaptiveKernel(): Method to use for computing predicates. Can be one of FastKernel, ExactKernel, and AdaptiveKernel. See the documentation for a further discussion of these methods.

Outputs

There is no output, as tri is updated in-place.

source

DelaunayTriangulation.split_edge! — Function

split_edge!(tri::Triangulation, i, j, r, store_event_history=Val(false), event_history=nothing)

Splits the edge (i, j) in tri at the vertex r. For the triangulation to be valid after this splitting, it is assumed that r is collinear with, or at least very close to collinear with, the edge (i, j).

Arguments

tri::Triangulation: The Triangulation.
i: The first vertex of the edge to split.
j: The second vertex of the edge to split.
r: The vertex to split the edge at.
store_event_history=Val(false): Whether to store the event history of the flip.
event_history=nothing: The event history. Only updated if store_event_history is true, in which case it needs to be an InsertionEventHistory object.

Outputs

There is no output, as tri is updated in-place.

Handling unoriented edges

The triangulation will only be updated as if (i, j) has been split rather than also (j, i). You will need to call split_edge! again with (j, i) if you want to split that edge as well.

source

DelaunayTriangulation.complete_split_triangle_and_legalise! — Method

complete_split_triangle_and_legalise!(tri::Triangulation, i, j, k, r)

Splits the triangle (i, j, k) at the vertex r, assumed to be inside the triangle, and legalises the newly added edges in tri.

Arguments

tri::Triangulation: The Triangulation.
i: The first vertex of the triangle.
j: The second vertex of the triangle.
k: The third vertex of the triangle.
r: The vertex to split the triangle at.

Outputs

There is no output, as tri is updated in-place.

source

DelaunayTriangulation.legalise_split_triangle! — Method

legalise_split_triangle!(tri::Triangulation, i, j, k, r; predicates::AbstractPredicateKernel=AdaptiveKernel())

Legalises the newly added edges in tri after the triangle (i, j, k) was split using split_triangle!.

Arguments

tri::Triangulation: The Triangulation.
i: The first vertex of the triangle.
j: The second vertex of the triangle.
k: The third vertex of the triangle.
r: The vertex to split the triangle at.

Keyword Arguments

predicates::AbstractPredicateKernel=AdaptiveKernel(): Method to use for computing predicates. Can be one of FastKernel, ExactKernel, and AdaptiveKernel. See the documentation for a further discussion of these methods.

Outputs

There is no output, as tri is updated in-place.

source

DelaunayTriangulation.split_triangle! — Method

split_triangle!(tri::Triangulation, i, j, k, r)

Splits the triangle (i, j, k) at the vertex r, assumed to be inside the triangle.

Arguments

tri::Triangulation: The Triangulation.
i: The first vertex of the triangle.
j: The second vertex of the triangle.
k: The third vertex of the triangle.
r: The vertex to split the triangle at.

Outputs

There is no output, but tri will be updated so that it now contains the triangles (i, j, r), (j, k, r), and (k, i, r).

source

DelaunayTriangulation._safe_get_adjacent — Method

_safe_get_adjacent(tri::Triangulation, uv) -> Vertex

This is the safe version of get_adjacent, which is used when the triangulation has multiple sections, ensuring that the correct ghost vertex is returned in case uv is a ghost edge.

source

DelaunayTriangulation.add_adjacent! — Method

add_adjacent!(tri::Triangulation, uv, w)
add_adjacent!(tri::Triangulation, u, v, w)

Adds the key-value pair (u, v) ⟹ w to the adjacency map of tri.

source

DelaunayTriangulation.delete_adjacent! — Method

delete_adjacent!(tri::Triangulation, uv)
delete_adjacent!(tri::Triangulation, u, v)

Deletes the key (u, v) from the adjacency map of tri.

source

DelaunayTriangulation.get_adjacent — Method

get_adjacent(tri::Triangulation, uv) -> Vertex
get_adjacent(tri::Triangulation, u, v) -> Vertex

Returns the vertex w such that (u, v, w) is a positively oriented triangle in the underlying triangulation, or ∅ if no such triangle exists.

source

DelaunayTriangulation.add_adjacent2vertex! — Method

add_adjacent2vertex!(tri::Triangulation, w, uv)
add_adjacent2vertex!(tri::Triangulation, w, u, v)

Adds the edge (u, v) into the set of edges returned by get_adjacent2vertex(tri, w).

source

DelaunayTriangulation.delete_adjacent2vertex! — Method

delete_adjacent2vertex!(tri::Triangulation, w, uv)
delete_adjacent2vertex!(tri::Triangulation, w, u, v)

Deletes the edge (u, v) from the set of edges returned by get_adjacent2vertex(tri, w).

source

DelaunayTriangulation.delete_adjacent2vertex! — Method

delete_adjacent2vertex!(tri::Triangulation, w)

Deletes the key w from the Adjacent2Vertex map of tri.

source

DelaunayTriangulation.get_adjacent2vertex — Method

get_adjacent2vertex(tri::Triangulation, w) -> Edges

Returns the set of all edges (u, v) in tri such that (u, v, w) is a positively oriented triangle in tri.

source

DelaunayTriangulation.add_neighbour! — Method

add_neighbour!(tri::Triangulation, u, v...)

Adds the neighbours v... to u in the graph of tri.

source

DelaunayTriangulation.add_vertex! — Method

add_vertex!(tri::Triangulation, u...)

Adds the vertices u... into the graph of tri.

source

DelaunayTriangulation.delete_ghost_vertices_from_graph! — Method

delete_ghost_vertices_from_graph!(tri::Triangulation)

Deletes all ghost vertices from the graph of tri.

source

DelaunayTriangulation.delete_neighbour! — Method

delete_neighbour!(tri::Triangulation, u, v...)

Deletes the neighbours v... from u in the graph of tri.

source

DelaunayTriangulation.delete_vertex! — Method

delete_vertex!(tri::Triangulation, u...)

Deletes the vertices u... from the graph of tri.

source

DelaunayTriangulation.get_neighbours — Method

get_neighbours(tri::Triangulation, u) -> Set{Vertex}

Returns the set of neighbours of u in tri. Note that, if has_ghost_triangles(tri), then some of the neighbours and vertices will be ghost vertices.

source

DelaunayTriangulation.get_neighbours — Method

get_neighbours(tri::Triangulation) -> Dict{Vertex, Set{Vertex}}

Returns the neighbours map of tri. Note that, if has_ghost_triangles(tri), then some of the neighbours and vertices will be ghost vertices.

source

DelaunayTriangulation.has_ghost_vertices — Method

has_ghost_vertices(tri::Triangulation) -> Bool

Returns true if tri has ghost vertices, and false otherwise.

source

DelaunayTriangulation.has_vertex — Method

has_vertex(tri::Triangulation, u) -> Bool

Returns true if u is a vertex in tri, and false otherwise.

source

DelaunayTriangulation.num_edges — Method

num_edges(tri::Triangulation) -> Integer

Returns the number of edges in tri. Note that, if has_ghost_triangles(tri), then some of these edges will be ghost edges.

See also num_solid_edges and num_ghost_edges.

source

DelaunayTriangulation.num_ghost_edges — Method

num_ghost_edges(tri::Triangulation) -> Integer

Returns the number of ghost edges in tri.

See also num_solid_edges and num_edges.

source

DelaunayTriangulation.num_ghost_vertices — Method

num_ghost_vertices(tri::Triangulation) -> Integer

Returns the number of ghost vertices in tri.

See also num_solid_vertices and num_vertices.

source

DelaunayTriangulation.num_neighbours — Method

num_neighbours(tri::Triangulation, u) -> Integer

Returns the number of neighbours of u in tri. Note that, if has_ghost_triangles(tri), then some of the neighbours counted might be ghost vertices if u is a boundary vertex.

source

DelaunayTriangulation.num_solid_edges — Method

num_solid_edges(tri::Triangulation) -> Integer

Returns the number of solid edges in tri.

See also num_ghost_edges and num_edges.

source

DelaunayTriangulation.num_solid_vertices — Method

num_solid_vertices(tri::Triangulation) -> Integer

Returns the number of solid vertices in tri.

See also num_ghost_vertices and num_vertices.

source

DelaunayTriangulation.num_vertices — Method

num_vertices(tri::Triangulation) -> Integer

Returns the number of vertices in tri. Note that, if has_ghost_triangles(tri), then some of these vertices will be ghost vertices.

source

DelaunayTriangulation.sort_edge_by_degree — Method

sort_edge_by_degree(tri::Triangulation, e) -> Edge

Returns the edge e sorted so that initial(e) has the smaller degree of the two vertices.

source

DelaunayTriangulation.get_point — Method

get_point(tri::Triangulation, i) -> NTuple{2, Number}
get_point(tri::Triangulation, i...) -> NTuple{length(i), NTuple{2, Number}}

Returns the coordinates corresponding to the vertices i... of tri, given as a Tuple of the form (x, y) for each point. If i is a ghost vertex, then the coordinates of the representative point of the curve associated with i are returned instead.

source

DelaunayTriangulation.num_points — Method

num_points(tri::Triangulation) -> Integer

Returns the number of points in tri.

Danger

If tri has vertices that are not yet present in the triangulation, e.g. if you have deleted vertices or have some submerged vertices in a weighted triangulation, then the corresponding points will still be counted in this function. It is recommended that you instead consider num_vertices, num_solid_vertices, or num_ghost_vertices.

source

DelaunayTriangulation.pop_point! — Method

pop_point!(tri::Triangulation)

Pops the last point from the points of tri.

source

DelaunayTriangulation.push_point! — Method

push_point!(tri::Triangulation, x, y)
push_point!(tri::Triangulation, p)

Pushes the point p = (x, y) into the points of tri.

source

DelaunayTriangulation.set_point! — Method

set_point!(tri::Triangulation, i, x, y)
set_point!(tri::Triangulation, i, p)

Sets the ith point of tri to p = (x, y).

source

DelaunayTriangulation.construct_positively_oriented_triangle — Function

construct_triangle(tri::Triangulation, i, j, k, predicates::AbstractPredicateKernel=AdaptiveKernel()) -> Triangle

Returns a triangle in tri from the vertices i, j, and k such that the triangle is positively oriented.

You can use the predicates argument to determine how the orientation predicate is computed. Can be one of FastKernel, ExactKernel, and AdaptiveKernel. See the documentation for more discussion on these choices.

source

DelaunayTriangulation.contains_triangle — Method

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

Tests whether tri contains T = (i, j, k) up to rotation, returning

V: The rotated form of T that is in tri, or simply T if T is not in tri.
flag: true if T is in tri, and false otherwise.

source

DelaunayTriangulation.num_ghost_triangles — Method

num_ghost_triangles(tri::Triangulation) -> Integer

Returns the number of ghost triangles in tri.

source

DelaunayTriangulation.num_solid_triangles — Method

num_solid_triangles(tri::Triangulation) -> Integer

Returns the number of solid triangles in tri.

source

DelaunayTriangulation.num_triangles — Method

num_triangles(tri::Triangulation) -> Integer

Returns the number of triangles in tri. Note that, if has_ghost_triangles(tri), then some of these triangles will be ghost triangles.

source

Voronoi Tessellations

Here are some functions related to the computation of unbounded Voronoi tessellations.

DelaunayTriangulation.add_edge_to_voronoi_polygon! — Method

add_edge_to_voronoi_polygon!(B, vorn::VoronoiTessellation, i, k, S, m, encountered_duplicate_circumcenter) -> (Vertex, Bool, Vertex)

Add the next edge to the Voronoi polygon for the point i in the VoronoiTessellation vorn.

Arguments

B: The vector of circumcenters defining the polygon.
vorn: The VoronoiTessellation.
i: The polygon index.
k: The vertex to add.
S: The surrounding polygon of i. See get_surrounding_polygon.
m: The index of the next vertex in S.
encountered_duplicate_circumcenter: Whether or not a duplicate circumcenter has been encountered.

Outputs

ci: The index for the circumcenter of the triangle considered.
encountered_duplicate_circumcenter: Whether or not a duplicate circumcenter has been encountered.
k: The next vertex in S after the input k.

source

DelaunayTriangulation.add_voronoi_polygon! — Method

add_voronoi_polygon!(vorn::VoronoiTessellation, i) -> Vector

Add the Voronoi polygon for the point i to the VoronoiTessellation vorn.

Arguments

vorn: The VoronoiTessellation.
i: The polygon index.

Outputs

B: The vector of circumcenters defining the polygon. This is a circular vector, i.e. B[begin] == B[end].

source

DelaunayTriangulation.close_voronoi_polygon! — Method

close_voronoi_polygon!(vorn::VoronoiTessellation, B, i, encountered_duplicate_circumcenter, prev_ci)

Close the Voronoi polygon for the point i in the VoronoiTessellation vorn.

Arguments

vorn: The VoronoiTessellation.
B: The vector of circumcenters defining the polygon.
i: The polygon index.
encountered_duplicate_circumcenter: Whether or not a duplicate circumcenter has been encountered.
prev_ci: The previous circumcenter index.

Outputs

There are no outputs, as vorn and B are modified in-place.

source

DelaunayTriangulation.connect_circumcenters! — Method

connect_circumcenters!(B, ci)

Add the circumcenter index ci to the array B.

source

DelaunayTriangulation.get_next_triangle_for_voronoi_polygon — Method

get_next_triangle_for_voronoi_polygon(vorn::VoronoiTessellation, i, k, S, m) -> (Vertex, Vertex)

Get the next triangle for the Voronoi polygon for the point i in the VoronoiTessellation.

Arguments

vorn: The VoronoiTessellation.
i: The polygon index.
k: The vertex to add.
S: The surrounding polygon of i. See get_surrounding_polygon.
m: The index of the next vertex in S.

Outputs

ci: The index for the circumcenter of the next triangle.
k: The next vertex in S after the input k.

source

DelaunayTriangulation.initialise_voronoi_tessellation — Method

initialise_voronoi_tessellation(tri::Triangulation) -> VoronoiTessellation

Initialise a VoronoiTessellation from the triangulation tri.

Arguments

tri: The Triangulation.

Output

vorn: The VoronoiTessellation. This tessellation is not yet filled in, as all the polygons and other fields need to be properly defined. This simply defines all the initial objects that will be pushed into.

source

DelaunayTriangulation.prepare_add_voronoi_polygon — Method

prepare_add_voronoi_polygon(vorn::VoronoiTessellation, i) -> (Vector, Vector)

Prepare to add a Voronoi polygon for the vertex i to the Voronoi tessellation vorn.

Arguments

vorn: The VoronoiTessellation.
i: The vertex.

Outputs

S: The surrounding polygon of i. See get_surrounding_polygon.
B: The buffer for the circumcenters. This is an empty Vector{I}, where I = integer_type(tri).

source

Clipped Voronoi Tessellations

Here are some functions related to the computation of clipped Voronoi tessellations.

DelaunayTriangulation.add_all_boundary_polygons! — Method

add_all_boundary_polygons!(vorn::VoronoiTessellation, boundary_sites)

Add all of the boundary polygons to the Voronoi tessellation.

Arguments

vorn: The VoronoiTessellation.
boundary_sites: A dictionary of boundary sites.

Outputs

There are no outputs, but the boundary polygons are added in-place.

source

DelaunayTriangulation.add_intersection_points! — Method

add_intersection_points!(vorn::VoronoiTessellation, segment_intersections) -> Integer

Adds all of the segment_intersections into the polygon vertices of vorn.

Arguments

vorn: The VoronoiTessellation.
segment_intersections: The intersection points from find_all_intersections.

Outputs

n: The number of polygon vertices before the intersections were added.

source

DelaunayTriangulation.add_segment_intersection! — Method

add_segment_intersection!(segment_intersections, boundary_sites, intersection_point, incident_polygon::I) where {I} -> Integer

Adds the intersection_point into the list of segment_intersections.

Arguments

segment_intersections: The list of segment intersections.
boundary_sites: A mapping from boundary sites to the indices of the segment intersections that are incident to the boundary site.
intersection_point: The intersection point to add.
incident_polygon: The index of the polygon that is incident to the intersection point.

Outputs

idx: The index of the intersection point in the list of segment intersections. If the intersection point already exists in the list, then the index of the existing point is returned and used instead.

source

DelaunayTriangulation.add_to_intersected_edge_cache! — Method

add_to_intersected_edge_cache!(intersected_edge_cache, u, v, a, b)

Add the edge uv to the list of intersected edges.

Arguments

intersected_edge_cache: The list of intersected edges.
u: The first vertex of the edge of the Voronoi polygon intersecting the edge ab of the boundary.
v: The second vertex of the edge of the Voronoi polygon intersecting the edge ab of the boundary.
a: The first vertex of the edge of the boundary.
b: The second vertex of the edge of the boundary.

Outputs

There are no outputs, as intersected_edge_cache is modified in-place.

source

DelaunayTriangulation.classify_intersections! — Method

classify_intersections!(intersected_edge_cache, left_edge_intersectors, right_edge_intersectors, current_edge_intersectors, left_edge, right_edge, current_edge)

Classify the intersections in intersected_edge_cache into left_edge_intersectors, right_edge_intersectors, and current_edge_intersectors based on whether they intersect left_edge, right_edge, or current_edge, respectively.

Arguments

intersected_edge_cache: The list of intersected edges currently being considered.
left_edge_intersectors: The set of sites that intersect the edge to the left of an edge currently being considered.
right_edge_intersectors: The set of sites that intersect the edge to the right of an edge currently being considered.
current_edge_intersectors: The set of sites that intersect the current edge being considered.
left_edge: The edge to the left of e on the boundary.
right_edge: The edge to the right of e on the boundary.
current_edge: The edge on the boundary being considered.

Outputs

There are no outputs, but left_edge_intersectors, right_edge_intersectors, or current_edge_intersectors are updated all in-place depending on the type of intersection for each edge in intersected_edge_cache.

source

DelaunayTriangulation.cleanup_unbounded_polygons! — Method

cleanup_unbounded_polygons!(vorn::VoronoiTessellation)

Removes any remaining unbounded polygons from vorn after clipping. This is needed only for power diagrams.

source

DelaunayTriangulation.clip_all_polygons! — Method

clip_all_polygons!(vorn::VoronoiTessellation, n, boundary_sites, exterior_circumcenters, equal_circumcenter_mapping)

Clip all of the polygons in the Voronoi tessellation.

Arguments

vorn: The VoronoiTessellation.
n: The number of vertices in the tessellation before clipping.
boundary_sites: A dictionary of boundary sites.
exterior_circumcenters: Any exterior circumcenters to be filtered out.
equal_circumcenter_mapping: A mapping from the indices of the segment intersections that are equal to the circumcenter of a site to the index of the site.

Outputs

There are no outputs, but the polygons are clipped in-place.

source

DelaunayTriangulation.clip_polygon! — Method

clip_polygon!(vorn::VoronoiTessellation, n, points, polygon, new_verts, exterior_circumcenters, equal_circumcenter_mapping)

Clip the polygon polygon by removing the vertices that are outside of the domain and adding the new vertices new_verts to the polygon.

Arguments

vorn: The VoronoiTessellation.
n: The number of vertices in the tessellation before clipping.
points: The polygon points of the tessellation.
polygon: The index of the polygon to be clipped.
new_verts: The indices of the new vertices that are added to the polygon.
exterior_circumcenters: Any exterior circumcenters to be filtered out.
equal_circumcenter_mapping: A mapping from the indices of the segment intersections that are equal to the circumcenter of a site to the index of the site.

Outputs

There are no outputs, but the polygon is clipped in-place.

source

DelaunayTriangulation.clip_voronoi_tessellation! — Method

clip_voronoi_tessellation!(vorn::VoronoiTessellation; rng=Random.default_rng(), predicates::AbstractPredicateKernel=AdaptiveKernel())

Clip the Voronoi tessellation vorn to the convex hull of the generators in vorn.

Arguments

vorn: The VoronoiTessellation.

Keyword Arguments

clip_polygon=nothing: If clip=true, then this is the polygon to clip the Voronoi tessellation to. If nothing, the convex hull of the triangulation is used. The polygon should be defined as a Tuple of the form (points, boundary_nodes) where the boundary_nodes are vertices mapping to coordinates in points, adhering to the usual conventions for defining boundaries. Must be a convex polygon.
rng::Random.AbstractRNG=Random.default_rng(): The random number generator.
predicates::AbstractPredicateKernel=AdaptiveKernel(): Method to use for computing predicates. Can be one of FastKernel, ExactKernel, and AdaptiveKernel. See the documentation for a further discussion of these methods.

Outputs

There are no outputs, but the Voronoi tessellation is clipped in-place.

source

DelaunayTriangulation.convert_to_edge_adjoining_ghost_vertex — Method

convert_to_edge_adjoining_ghost_vertex(tri::Triangulation, e) -> Edge

Returns the edge e if it is not a boundary edge, and the edge reverse(e) if it is a boundary edge.

Centroidal Voronoi Tessellations

Here are some functions related to the computation of centroidal Voronoi tessellations.

DelaunayTriangulation._centroidal_smooth_itr — Function

_centroidal_smooth_itr(vorn::VoronoiTessellation, points, rng, predicates::AbstractPredicateKernel=AdaptiveKernel(); kwargs...) -> (VoronoiTessellation, Number)

Performs a single iteration of the centroidal smoothing algorithm.

Arguments

vorn: The VoronoiTessellation.
points: The underlying point set. This is a deepcopy of the points of the underlying triangulation.
rng: The random number generator.
predicates::AbstractPredicateKernel=AdaptiveKernel(): Method to use for computing predicates. Can be one of FastKernel, ExactKernel, and AdaptiveKernel. See the documentation for a further discussion of these methods.

Keyword Arguments

clip_polygon=nothing: If clip=true, then this is the polygon to clip the Voronoi tessellation to. If nothing, the convex hull of the triangulation is used. The polygon should be defined as a Tuple of the form (points, boundary_nodes) where the boundary_nodes are vertices mapping to coordinates in points, adhering to the usual conventions for defining boundaries.
kwargs...: Extra keyword arguments passed to retriangulate.

Outputs

vorn: The updated VoronoiTessellation.
max_dist: The maximum distance moved by any generator.

source

DelaunayTriangulation.centroidal_smooth — Method

centroidal_smooth(vorn::VoronoiTessellation; maxiters=1000, tol=default_displacement_tolerance(vorn), rng=Random.default_rng(), predicates::AbstractPredicateKernel=AdaptiveKernel(), kwargs...) -> VoronoiTessellation

Smooths vorn into a centroidal tessellation so that the new tessellation is of a set of generators whose associated Voronoi polygon is that polygon's centroid.

Arguments

vorn: The VoronoiTessellation.

Keyword Arguments

maxiters=1000: The maximum number of iterations.
clip_polygon=nothing: If clip=true, then this is the polygon to clip the Voronoi tessellation to. If nothing, the convex hull of the triangulation is used. The polygon should be defined as a Tuple of the form (points, boundary_nodes) where the boundary_nodes are vertices mapping to coordinates in points, adhering to the usual conventions for defining boundaries. Must be a convex polygon.
tol=default_displacement_tolerance(vorn): The displacement tolerance. See default_displacement_tolerance for the default.
rng=Random.default_rng(): The random number generator.
predicates::AbstractPredicateKernel=AdaptiveKernel(): Method to use for computing predicates. Can be one of FastKernel, ExactKernel, and AdaptiveKernel. See the documentation for a further discussion of these methods.
kwargs...: Extra keyword arguments passed to retriangulate.

Outputs

vorn: The updated VoronoiTessellation. This is not done in-place.

Extended help

The algorithm is simple. We iteratively smooth the generators, moving them to the centroid of their associated Voronoi polygon for the current tessellation, continuing until the maximum distance moved of any generator is less than tol. Boundary generators are not moved.

source

DelaunayTriangulation.default_displacement_tolerance — Method

default_displacement_tolerance(vorn::VoronoiTessellation) -> Number

Returns the default displacement tolerance for the centroidal smoothing algorithm. The default is given by max_extent / 1e4, where max_extent = max(width, height), where width and height are the width and height of the bounding box of the underlying point set.

Arguments

vorn: The VoronoiTessellation.

Outputs

tol: The default displacement tolerance.

source

DelaunayTriangulation.move_generator_to_centroid! — Method

move_generator_to_centroid!(points, vorn::VoronoiTessellation, generator) -> Number

Moves the generator generator to the centroid of its Voronoi cell. Returns the distance moved.

Arguments

points: The underlying point set. This is a deepcopy of the points of the underlying triangulation.
vorn: The VoronoiTessellation.
generator: The generator to move.

Outputs

dist: The distance moved.

source

Triangulating Curve-Bounded Domains

We have several functions related to the triangulation of curve-bounded domains.

DelaunayTriangulation.coarse_discretisation! — Method

coarse_discretisation!(points, boundary_nodes, boundary_curve; n=0)

Constructs an initial coarse discretisation of a curve-bounded domain with bonudary defines by (points, boundary_nodes, boundary_curves), where boundary_nodes and boundary_curves should come from convert_boundary_curves!. The argument n is the amount of times to split an edge. If non-zero, this should be a power of two (otherwise it will be rounded up to the next power of two). If it is zero, then the splitting will continue until the maximum total variation over any subcurve is less than π/2.

source

DelaunayTriangulation.compute_split_position — Function

compute_split_position(enricher::BoundaryEnricher, i, j, predicates::AbstractPredicateKernel=AdaptiveKernel()) -> (Float64, Float64, NTuple{2,Float64})

Gets the point to split the edge (i, j) at.

Arguments

enricher::BoundaryEnricher: The enricher.
i: The first point of the edge.
j: The second point of the edge.
predicates::AbstractPredicateKernel=AdaptiveKernel(): Method to use for computing predicates. Can be one of FastKernel, ExactKernel, and AdaptiveKernel. See the documentation for a further discussion of these methods.

Outputs

t: The parameter value of the split point.
Δθ: The total variation of the subcurve (i, t). If a split was created due to a small angle, this will be set to zero.
ct: The point to split the edge at.

source

DelaunayTriangulation.enrich_boundary! — Method

enrich_boundary!(enricher::BoundaryEnricher; predicates::AbstractPredicateKernel=AdaptiveKernel())

Enriches the initial boundary defined inside enricher, implementing the algorithm of Gosselin and Ollivier-Gooch (2007). At the termination of the algorithm, all edges will contain no other points inside their diametral circles.

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

source

DelaunayTriangulation.has_acute_neighbouring_angles — Method

has_acute_neighbouring_angles(predicates::AbstractPredicateKernel, enricher::BoundaryEnricher, i, j) -> Int, Vertex

Given a boundary edge (i, j), tests if the neighbouring angles are acute. The first returned value is the number of angles adjoining (i, j) that are acute (0, 1, or 2). The second returned value is the vertex that adjoins the edge (i, j) that is acute. If there are no such angles, or if there are two, then this returned vertex is 0.

(The purpose of this function is similar to segment_vertices_adjoin_other_segments_at_acute_angle.)

source

DelaunayTriangulation.split_subcurve! — Function

split_subcurve!(enricher::BoundaryEnricher, i, j, predicates::AbstractPredicateKernel=AdaptiveKernel()) -> Bool

Splits the curve associated with the edge (i, j) into two subcurves by inserting a point r between (i, j) such that the total variation of the subcurve is equal on (i, r) and (r, j). The returned value is a flag that is true if there was a precision issue, and false otherwise.

The predicate argument determines how predicates are computed, and should be one of ExactKernel, FastKernel, and AdaptiveKernel (the default). See the documentation for more information about these choices.

source

DelaunayTriangulation.test_visibility — Method

test_visibility(predicates::AbstractPredicateKernel, enricher::BoundaryEnricher, i, j, k) -> Certificate

Tests if the vertex k is visible from the edge (i, j). Returns a Certificate which is

Invisible: If k is not visible from (i, j).
Visible: If k is visible from (i, j).

For this function, k should be inside the diametral circle of (i, j).

We say that k is invisibile from (i, j) if the edges (i, k) or (j, k) intersect any other boundary edges, or there is a hole between (i, j) and k.

Definition incompatibility

This is not the same definition used in defining constrained Delaunay triangulations, where visibility means visible from ANY point on the edge instead of only from the endpoints.

source

DelaunayTriangulation.triangulate_curve_bounded — Method

triangulate_curve_bounded(points::P;
segments=nothing,
boundary_nodes=nothing,
predicates::AbstractPredicateKernel=AdaptiveKernel(),
IntegerType::Type{I}=Int,
polygonise_n=4096,
coarse_n=0,
check_arguments=true,
delete_ghosts=false,
delete_empty_features=true,
recompute_representative_points=true,
rng::Random.AbstractRNG=Random.default_rng(),
insertion_order=nothing, 
kwargs...) where {P,I} -> Triangulation

Triangulates a curve-bounded domain defined by (points, segments, boundary_nodes). Please see triangulate for a description of the arguments. The only differences are:

insertion_order=nothing: This argument is ignored for curve-bounded domains.
polygonise_n=4096: For generating a high-resolution discretisation of a boundary initially for the construction of a PolygonHierarchy, many points are needed. This number of points is defined by polygonise_n, and must be a power of 2 (otherwise, the next highest power of 2 is used). See polygonise.
coarse_n=0: This is the number of points to use for initialising a curve-bounded domain via coarse_discretisation!. The default coarse_n=0 means the discretisation is performed until the maximum variation over any subcurve is less than π/2.
skip_points: This is still used, but it is ignored during the enrichment phase (see enrich_boundary!).

Refinement

To refine the mesh further beyond its initial coarse discretisation, as produced from this function, please see refine!.

source

DelaunayTriangulation.convert_boundary_curves! — Method

convert_boundary_curves!(points, boundary_nodes, IntegerType) -> (NTuple{N, AbstractParametricCurve} where N, Vector)

Converts the provided points and boundary_nodes into a set of boundary curves and modified boundary nodes suitable for triangulation. In particular:

The function gets boundary_curves from to_boundary_curves.
boundary_nodes is replaced with a set of initial boundary nodes (from get_skeleton). These nodes come from evaluating each boundary curve at t = 0 and t = 1. In the case of a piecewise linear boundary, the vertices are copied directly. Note that not all control points of a CatmullRomSpline (which is_interpolating) will be added - only those at t = 0 and t = 1.
The points are modified to include the new boundary nodes. If a point is already in points, it is not added again.

Arguments

points: The point set. This is modified in place with the new boundary points.
boundary_nodes: The boundary nodes to be converted. This is not modified in place.
IntegerType: The type of integer to use for the boundary nodes.

Output

boundary_curves: The boundary curves associated with boundary_nodes.
boundary_nodes: The modified boundary nodes.

source

DelaunayTriangulation.is_curve_bounded — Function

is_curve_bounded(tri::Triangulation) -> Bool 
is_curve_bounded(boundary_nodes) -> Bool

Returns true if tri is curve bounded, and false otherwise; similarly for the boundary_nodes method.

source

DelaunayTriangulation.to_boundary_curves — Method

to_boundary_curves(points, boundary_nodes) -> NTuple{N, AbstractParametricCurve} where N

Returns the set of boundary curves associated with boundary_nodes and points.

source

DelaunayTriangulation.is_visible — Function

is_visible(cert::Certificate) -> Bool

Returns true if cert is Visible, and false otherwise.

source

DelaunayTriangulation.is_invisible — Function

is_invisible(cert::Certificate) -> Bool

Returns true if cert is Invisible, and false otherwise.

source

DelaunayTriangulation.test_visibility — Function

test_visibility([kernel::AbstractPredicateKernel = AdaptiveKernel(),] tri::Triangulation, q, i) -> Certificate

Tests if the vertex i and the point q can see each other. Here, visibility means that the line segment joining the two does not intersect any segments.

Arguments

kernel::AbstractPredicateKernel = AdaptiveKernel(): Method to use for computing predicates. Can be one of FastKernel, ExactKernel (the default), and AdaptiveKernel. See the documentation for a further discussion of these methods.
tri: The Triangulation.
q: The point from which we are testing visibility.
i: The vertex we are testing visibility of.

Outputs

cert: A Certificate. This will be Visible if i is visible from q, and Invisible otherwise.

source

test_visibility([kernel::AbstractPredicateKernel=AdaptiveKernel(),] tri::Triangulation, u, v, i; shift=0.0, attractor=get_point(tri,i)) -> Certificate

Tests if the edge (u, v) and the point i can see each other. Here, visibility means that any point in the interior of (u, v) can see i. To test this, we only check 10 points equally spaced between u and v, excluding u and v.

Arguments

kernel::AbstractPredicateKernel=AdaptiveKernel(): How predicates are computed. See the documentation for information on the choices between FastKernel, ExactKernel, and AdaptiveKernel.
tri: The Triangulation.
u: The first vertex of the edge.
v: The second vertex of the edge.
i: The vertex we are testing visibility of.

Keyword Arguments

shift=0.0: The amount by which to shift each point on the edge towards attractor, i.e. if p is a point on the edge, then p .+ shift .* (attractor - p) is the point used to test visibility rather than p itself.
attractor=get_point(tri,i): Related to shift; see above.
predicates::AbstractPredicateKernel=AdaptiveKernel(): Method to use for computing predicates. Can be one of FastKernel, ExactKernel, and AdaptiveKernel. See the documentation for a further discussion of these methods.

Outputs

cert: A Certificate. This will be Visible if i is visible from (u, v), and Invisible otherwise.

source

test_visibility(predicates::AbstractPredicateKernel, enricher::BoundaryEnricher, i, j, k) -> Certificate

Tests if the vertex k is visible from the edge (i, j). Returns a Certificate which is

Invisible: If k is not visible from (i, j).
Visible: If k is visible from (i, j).

For this function, k should be inside the diametral circle of (i, j).

We say that k is invisibile from (i, j) if the edges (i, k) or (j, k) intersect any other boundary edges, or there is a hole between (i, j) and k.

Definition incompatibility

This is not the same definition used in defining constrained Delaunay triangulations, where visibility means visible from ANY point on the edge instead of only from the endpoints.

source