Operations

We define some specific operations for acting on Triangulations directly. These are listed below.

DelaunayTriangulation.add_point!Method
add_point!(tri::Triangulation, new_point[, new_point_y];
    point_indices=get_vertices(tri),
    m=default_num_samples(length(point_indices)),
    try_points=(),
    rng::AbstractRNG=Random.default_rng(),
    initial_search_point=integer_type(tri)(select_initial_point(get_points(tri),new_point;point_indices,m,try_points,rng)),
    update_representative_point=false,
    store_event_history = Val(false),
    event_history = nothing,
    exterior_curve_index=1,
    V=jump_and_march(
        tri,
        new_point isa Integer ? get_point(tri, new_point) : new_point;
        m=nothing,
        point_indices=nothing,
        try_points=nothing,
        k=initial_search_point,
        rng,
        check_existence=Val(has_multiple_segments(tri)),
        exterior_curve_index
    ),
    peek = Val(false),
    )

Adds the point new_point to the triangulation tri.

Arguments

  • tri::Triangulation: The Triangulation.
  • new_point[, new_point_y]: The point to add. This new_point can be an integer, in which case get_point(tri, new_point) is added. If new_point is just a set of coordinates, we add that into tri via push_point! and then add that index into tri. Lastly, if we provide (new_point, new_point_y), then the point is treated as this Tuple and inserted.

Keyword Arguments

  • point_indices=each_solid_vertex(tri): The indices of the non-ghost points in the triangulation.
  • m=default_num_samples(length(point_indices)): The number of points to sample from point_indices to use as the initial search point.
  • try_points=(): A list of points to try as the initial search point in addition to those sampled.
  • rng::AbstractRNG=Random.default_rng(): The random number generator to use.
  • initial_search_point=integer_type(tri)(select_initial_point(tri,new_point;point_indices,m,try_points,rng)): The initial search point to use. If this is not provided, then we use select_initial_point to select one.
  • update_representative_point=false: Whether to update the representative point list after adding the new point.
  • store_event_history = Val(false): Whether to store the event history. See InsertionEventHistory.
  • event_history = nothing: The event history to store the events in. See InsertionEventHistory. Only needed if is_true(store_event_history). This object is not returned, instead we just mutate it inplace.
  • exterior_curve_index=1: The curve (or curves) corresponding to the outermost boundary.
  • V=jump_and_march(tri, new_point isa Integer ? get_point(tri, new_point) : new_point; m=nothing, point_indices=nothing, try_points=nothing, k=initial_search_point, rng, check_existence=Val(has_multiple_segments(tri)), exterior_curve_index=exterior_curve_index): The triangle that q is in.
  • peek=Val(false): If is_true(peek), then we don't actually add the point, but all operations that update the history will be run. (So you should only really want this if you are using event_history.)

Outputs

The triangulation is updated in-place with the new point, but we also return the triangle V containing new_point.

DelaunayTriangulation.add_edge!Method
add_edge!(tri::Triangulation, segment; rng::AbstractRNG=Random.default_rng())
add_edge!(tri::Triangulation, i, j; rng::AbstractRNG=Random.default_rng())

Adds the edge segment = (i, j) into the triangulation tri.

DelaunayTriangulation.delete_point!Method
delete_point!(tri::Triangulation, point; rng::AbstractRNG=Random.default_rng())

Deletes point from the triangulation tri using Chew's algorithm.

DelaunayTriangulation.add_boundary_information!Method
add_boundary_information!(tri::Triangulation)

Given a triangulation tri, adds boundary information into tri. In particular, the Adjacent, Adjacent2Vertex, and Graph fields are updated so that e.g. boundary edges map to their corresponding boundary indices, boundary indices map to their boundary edges via the Adjacent2Vertex map, and boundary indices are included in the Graph.

DelaunayTriangulation.delete_ghost_triangles!Method
delete_ghost_triangles!(tri::Triangulation; boundary_indices = all_boundary_indices(tri), delete_neighbours=false)

Deletes the ghost triangles from the triangulation tri.

Note

A ghost triangle is a triangle of the form (i, j, k) where only one of the indices, say i, satisfies is_boundary_index(i).

DelaunayTriangulation.add_ghost_triangles!Method
add_ghost_triangles!(tri::Triangulation; boundary_indices=all_boundary_indices(tri), add_neighbours=false

Given a Triangulation tri, adds the ghost triangles into tri. In particular, the triangles, Adjacent, and Adjacent2Vertex fields are updated so that ghost triangles are stored in them.

Note

A ghost triangle is a triangle of the form (i, j, k) where only one of the indices, say i, satisfies is_boundary_index(i).

DelaunayTriangulation.add_triangle!Method
add_triangle!(tri::Triangulation, u, v, w; protect_boundary=false, update_ghost_edges=false)
add_triangle!(tri::Triangulation, T; protect_boundary=false, update_ghost_edges=false)

Given a triangle T = (u, v, w), adds the triangle into the triangulation tri. To update the ghost triangles directly, set update_ghost_edges=true. The other parts of the boundary information will be handled, though, unless you set protect_boundary=true.

DelaunayTriangulation.delete_triangle!Method
delete_triangle!(tri::Triangulation, u, v, w; protect_boundary=false, update_ghost_edges=false)
delete_triangle!(tri::Triangulation, T; protect_boundary=false, update_ghost_edges=false)

Given a triangle T = (u, v, w), adds the triangle into the triangulation tri. To update the ghost triangles directly, set update_ghost_edges=true. The other parts of the boundary information will be handled, though, unless you set protect_boundary=true.

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

Given a triangulation tri and an edge (i, j), splits the edge at the point r so that the edges (i, r) and (r, j) now appear in tri (with the triangles updated accordingly). It is assumed that r is (at least very close to) collinear with (i, j).

If store_event_history is Val(true), then the event history is stored in event_history.

DelaunayTriangulation.legalise_split_edge!Function
legalise_split_edge!(tri::Triangulation, i, j, k, r, store_event_history=Val(false), event_history=nothing)

Given a triangulation tri, an edge (i, j) that has already been split by split_edge! at the point r, legalises the new edges using legalise_edge, letting k be the vertex that was originally adjacent to (i, j).

If store_event_history is Val(true), then the event history is stored in event_history.

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)

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 legalises the new edges using legalise_split_edge!.

If store_event_history is Val(true), then the event history is stored in event_history.

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

Given a triangulation tri, a triangle (i, j, k), and a point r inside the triangle, splits the triangle at r so that (i, j, k) is replaced by the three triangles (i, j, r), (j, k, r), and (k, i, r), respectively.

DelaunayTriangulation.flip_edge!Function
flip_edge!(tri::Triangulation, i, j, store_event_history=Val(false), event_history=nothing)
flip_edge!(tri::Triangulation, i, j, k, ℓ)

Given a triangulation tri and an edge (i, j) appearing in the triangulation, flips the edge (i, j) so that it becomes (ℓ, k), where ℓ = get_adjacent(tri, i, j) and k = get_adjacent(tri, j, i).

Warning

If (i, j, ℓ, k) is not a convex quadrilateral, than this edge flip makes the triangulation non-planar.

DelaunayTriangulation.legalise_edge!Function
legalise_edge!(tri::Triangulation, i, j, r, store_event_history=Val(false), event_history=nothing)

Given a triangulation tri, an edge (i, j), and a point r that was added into a triangle that (i, j) belongs to, legalises the edge (i, j) and other neighbouring edges recursively.

If store_event_history is Val(true), then the event history is stored in event_history.

Warning

Edge flipping can lead to final eventhistorys that have triangles both in addedtriangles and deleted_triangles

DelaunayTriangulation.lock_convex_hull!Function
lock_convex_hull!(tri::Triangulation)

Locks the convex hull of the triangulation tri by adding it to the constrained edges of tri in place of boundary_nodes. If has_boundary_nodes(tri) is already true, an error is thrown.

DelaunayTriangulation.unlock_convex_hull!Function
unlock_convex_hull!(tri::Triangulation)

Unlocks the convex hull of the triangulation tri by removing it from the constrained edges of tri. If has_boundary_nodes(tri) is already false or if get_boundary_nodes(tri) ≠ get_convex_hull_indices(tri), an error is thrown.