InvalidBoundingBox

A constant for representing an invalid rectangle, i.e. a rectangle with NaN endpoints.

InvalidBoundingInterval

A constant for representing an invalid intervaBoundingInterval, i.e. an interval with NaN endpoints.

abstract type AbstractBoundingShape

Abstract type for representing a bounding box.

AbstractEachEdge{E}

An abstract type for an iterator over edges in a triangulation.

AbstractEachTriangle{T}

An abstract type for an iterator over triangles in a triangulation.

AbstractEachVertex{V}

An abstract type for an iterator over vertices in a triangulation.

abstract type AbstractNode end

Abstract type for representing a node in an R-tree.

abstract type AbstractParametricCurve <: Function end

Abstract type for representing a parametric curve parametrised over 0 ≤ t ≤ 1. The curves represented by this abstract type should not be self-intersecting, with the exception of allowing for closed curves.

The structs that subtype this abstract type must implement are:

• differentiate.
• twice_differentiate.
• thrice_differentiate (only if you have not manually defined total_variation).
• The struct must be callable so that c(t), where c an instance of the struct, returns the associated value of the curve at t.
• If the struct does not implement point_position_relative_to_curve, then the struct must implement get_closest_point. Alternatively, rather than implementing get_closest_point, the struct should have a lookup_table field as a Vector{NTuple{2,Float64}}, which returns values on the curve at a set of points, where lookup_table[i] is the value of the curve at t = (i - 1) / (length(lookup_table) - 1).

Functions that are defined for all AbstractParametricCurve subtypes are:

• arc_length
• curvature
• total_variation

Adjacent{IntegerType, EdgeType}

Struct for storing adjacency relationships for a triangulation.

Fields

• adjacent::Dict{EdgeType, IntegerType}

The map taking edges (u, v) to w such that (u, v, w) is a positively oriented triangle in the underlying triangulation.

Constructors

Adjacent{IntegerType, EdgeType}()
Adjacent(adjacent::Dict{EdgeType, IntegerType})

Adjacent2Vertex{IntegerType, EdgesType}

Struct for connectivity information about edges relative to vertices for a triangulation.

Fields

• adjacent2vertex::Dict{IntegerType, EdgesType}

The map taking w to the set of all (u, v) such that (u, v, w) is a positively oriented triangle in the underlying triangle.

Constructors

Adjacent2Vertex{IntegerType, EdgesType}()
Adjacent2Vertex(adj2v::Dict{IntegerType, EdgesType})

BSpline <: AbstractParametricCurve

Curve for representing a BSpline, parametrised over 0 ≤ t ≤ 1. This curve can be evaluated using b_spline(t) and returns a tuple (x, y) of the coordinates of the point on the curve at t.

See also BezierCurve and CatmullRomSpline.

Our implementation of a BSpline is based on https://github.com/thibauts/b-spline.

Fields

• control_points::Vector{NTuple{2,Float64}}: The control points of the BSpline. The curve goes through the first and last control points, but not the intermediate ones.
• knots::Vector{Int}: The knots of the BSpline. You should not modify or set this field directly (in particular, do not expect any support for non-uniform B-splines).
• cache::Vector{NTuple{2,Float64}}: A cache of the points on the curve. This is used to speed up evaluation of the curve using de Boor's algorithm.
• lookup_table::Vector{NTuple{2,Float64}}: A lookup table for the B-spline curve, used for finding the point on the curve closest to a given point. The ith entry of the lookup table corresponds to the t-value i / (length(lookup_table) - 1).
• orientation_markers::Vector{Float64}: The orientation markers of the curve. These are defined so that the orientation of the curve is monotone between any two consecutive markers. The first and last markers are always 0 and 1, respectively. See orientation_markers.

Constructor

You can construct a BSpline using

BSpline(control_points::Vector{NTuple{2,Float64}}; degree=3, lookup_steps=5000, kwargs...)

The keyword argument lookup_steps is used to build the lookup table for the curve. Note that the default degree=3 corresponds to a cubic B-spline curve. The kwargs... are keyword arguments passed to orientation_markers.

mutable struct BalancedBST{K}

Struct representing a balanced binary search tree.

Fields

• root::Union{Nothing,BalancedBSTNode{K}}: The root of the tree.
• count::Int32: The number of nodes in the tree.

BalancedBST{K}() where {K}

Constructs a new empty balanced binary search tree.

mutable struct BalancedBSTNode{K}

Struct representing a node in a balanced binary search tree.

Fields

• key::K: The key associated with the node.
• height::Int8: The height of the node.
• count::Int32: The number of nodes in the subtree rooted at this node, including this node.
• parent::Union{Nothing,BalancedBSTNode{K}}: The parent of the node.
• left::Union{Nothing,BalancedBSTNode{K}}: The left child of the node.
• right::Union{Nothing,BalancedBSTNode{K}}: The right child of the node.

Constructor

BalancedBSTNode(key::K) where {K}

Constructs a new node with key key, height 1, and count 1. The parent, left child, and right child are set to nothing.

BezierCurve <: AbstractParametricCurve

Curve for representing a Bezier curve, parametrised over 0 ≤ t ≤ 1. This curve can be evaluated using bezier_curve(t) and returns a tuple (x, y) of the coordinates of the point on the curve at t.

A good reference on Bezier curves is this.

See also BSpline and CatmullRomSpline.

Fields

• control_points::Vector{NTuple{2,Float64}}: The control points of the Bezier curve. The curve goes through the first and last control points, but not the intermediate ones.
• cache::Vector{NTuple{2,Float64}}: A cache of the points on the curve. This is used to speed up evaluation of the curve using de Casteljau's algorithm.
• lookup_table::Vector{NTuple{2,Float64}}: A lookup table for the Bezier curve, used for finding the point on the curve closest to a given point. The ith entry of the lookup table corresponds to the t-value i / (length(lookup_table) - 1).
• orientation_markers::Vector{Float64}: The orientation markers of the curve. These are defined so that the orientation of the curve is monotone between any two consecutive markers. The first and last markers are always 0 and 1, respectively. See orientation_markers.

Constructor

You can construct a BezierCurve using

BezierCurve(control_points::Vector{NTuple{2,Float64}}; lookup_steps=5000, kwargs...)

The keyword argument lookup_steps=100 controls how many time points in [0, 1] are used for the lookup table. The kwargs... are keyword arguments passed to orientation_markers.

BoundaryEnricher{P,B,C,I,BM,S}

Struct used for performing boundary enrichment on a curve-bounded boundary.

See also enrich_boundary!.

Fields

• points::P: The point set.
• boundary_nodes::B: The boundary nodes.
• segments::S: The segments.
• boundary_curves::C: The boundary curves.
• polygon_hierarchy::PolygonHierarchy{I}: The polygon hierarchy.
• parent_map::Dict{NTuple{2,I},I}: A map from an edge, represented as a Tuple, to the index of the parent curve in boundary_curves.
• curve_index_map::Dict{I,I}: A map from a curve index to the index of the curve in boundary_curves.
• boundary_edge_map::B: A map from a boundary node to the index of the curve in boundary_curves that it belongs to. See construct_boundary_edge_map.
• spatial_tree::BoundaryRTree{P}: The BoundaryRTree used for spatial indexing.
• queue::Queue{I}: A queue used for processing vertices during enrichment.
• small_angle_complexes::Dict{I,Vector{SmallAngleComplex{I}}}: A map from an apex vertex to a list of all curves that define a small angle complex associated with that apex vertex.

The first three fields should be those associated with convert_boundary_curves!.

Constructor

BoundaryEnricher(points, boundary_nodes; IntegerType=Int, n=4096, coarse_n=0)

This constructor will use convert_boundary_curves! to convert points and boundary_nodes into a set of boundary curves and modified boundary nodes suitable for enrichment. The boundary nodes field will no longer aliased with the input boundary_nodes, although points will be. The polygon hierarchy is computed using construct_polygon_hierarchy. The argument n is used in polygonise for filling out the boundary temporarily in order to construct the PolygonHierarchy. The argument coarse_n defines the initial coarse discretisation through coarse_discretisation!; the default n=0 means that the coarse discretisation will be performed until the maximum total variation of a subcurve is less than π/2.

BoundaryRTree{P}

Type for representing an R-tree of a boundary with an associated point set. The rectangular elements of the R-tree are the bounding box of the diametral circles of the boundary edges.

Fields

• tree::RTree: The R-tree.
• points::P: The point set.

Constructors

BoundaryRTree(points)

BoundingBox <: AbstractBoundingShape

Type for representing an axis-aligned bounding box, represented as a pair of interval I and J so that the bounding box is I × J.

Fields

• x::BoundingInterval: The interval for the x-axis.
• y::BoundingInterval: The interval for the y-axis.

Constructors

BoundingBox(x::BoundingInterval, y::BoundingInterval)
BoundingBox(a::Float64, b::Float64, c::Float64, d::Float64) = BoundingBox(BoundingInterval(a, b), BoundingInterval(c, d))
BoundingBox(p::NTuple{2,<:Number}) = BoundingBox(p[1], p[1], p[2], p[2])

BoundingInterval <: AbstractBoundingShape

Type for representing a bounding interval [a, b].

Fields

• a::Float64: The left endpoint.
• b::Float64: The right endpoint.

mutable struct Branch <: AbstractNode

Type for representing a branch node in an R-tree.

Fields

• parent::Union{Branch, Nothing}: The parent of the branch node.
• bounding_box::BoundingBox: The bounding box of the branch node.
• children::Union{Vector{Branch},Vector{Leaf{Branch}}}: The children of the branch node.
• level::Int: The level of the branch node.

Constructor

Branch(parent::Union{Branch,Nothing}=nothing, ::Type{C}=Branch) where {C<:AbstractNode} = new(parent, InvalidBoundingBox, C[], 1)

BranchCache

Type for representing a cache of branch nodes.

CatmullRomSpline <: AbstractParametricCurve

Curve for representing a Catmull-Rom spline, parametrised over 0 ≤ t ≤ 1. This curve can be evaluated using catmull_rom_spline(t) and returns a tuple (x, y) of the coordinates of the point on the curve at t.

For information on these splines, see e.g. this article and this article. Additionally, this article lists some nice properties of these splines.

Fields

• control_points::Vector{NTuple{2,Float64}}: The control points of the Catmull-Rom spline. The curve goes through each point.
• knots::Vector{Float64}: The parameter values of the Catmull-Rom spline. The ith entry of this vector corresponds to the t-value associated with the ith control point. With an alpha parameter α, these values are given by knots[i+1] = knots[i] + dist(control_points[i], control_points[i+1])^α, where knots[1] = 0, and the vector is the normalised by dividing by knots[end].
• lookup_table::Vector{NTuple{2,Float64}}: A lookup table for the Catmull-Rom spline, used for finding the point on the curve closest to a given point. The ith entry of the lookup table corresponds to the t-value i / (length(lookup_table) - 1).
• alpha::Float64: The alpha parameter of the Catmull-Rom spline. This controls the type of the parametrisation, where alpha = 0 corresponds to uniform parametrisation, alpha = 1/2 corresponds to centripetal parametrisation, and alpha = 1 corresponds to chordal parametrisation. Must be in [0, 1]. For reasons similar to what we describe for tension below, we only support alpha = 1/2 for now. (If you do really want to change it, use the _alpha keyword argument in the constructor.)
• tension::Float64: The tension parameter of the Catmull-Rom spline. This controls the tightness of the spline, with tension = 0 being the least tight, and tension = 1 leading to straight lines between the control points. Must be in [0, 1]. You can not currently set this to anything except 0.0 due to numerical issues with boundary refinement. (For example, equivariation splits are not possible if tension=1 since the curve is piecewise linear in that case, and for tension very close to 1, the equivariation split is not always between the provided times. If you really want to change it, then you can use the _tension keyword argument in the constructor - but be warned that this may lead to numerical issues and potentially infinite loops.)
• left::NTuple{2,Float64}: The left extension of the spline. This is used to evaluate the spline on the first segment.
• right::NTuple{2,Float64}: The right extension of the spline. This is used to evaluate the spline on the last segment.
• lengths::Vector{Float64}: The lengths of the individual segments of the spline.
• segments::Vector{CatmullRomSplineSegment}: The individual segments of the spline.
• orientation_markers::Vector{Float64}: The orientation markers of the curve. These are defined so that the orientation of the curve is monotone between any two consecutive markers. The first and last markers are always 0 and 1, respectively. See orientation_markers.

Constructor

To construct a CatmullRomSpline, use

CatmullRomSpline(control_points::Vector{NTuple{2,Float64}}; lookup_steps=5000, kwargs...)

The keyword argument lookup_steps is used to build the lookup table for the curve, with lookup_steps giving the number of time points in [0, 1] used for the lookup table. The kwargs... are keyword arguments passed to orientation_markers.

CatmullRomSplineSegment <: AbstractParametricCurve

A single segment of a Camtull-Rom spline, representing by a cubic polynomial. Note that evaluating this curve will only draw within the two interior control points of the spline.

Based on this article.

Fields

• a::NTuple{2,Float64}: The coefficient on t³.
• b::NTuple{2,Float64}: The coefficient on t².
• c::NTuple{2,Float64}: The coefficient on t.
• d::NTuple{2,Float64}: The constant in the polynomial.
• p₁::NTuple{2,Float64}: The second control point of the segment.
• p₂::NTuple{2,Float64}: The third control point of the segment.

With these fields, the segment is parametrised over 0 ≤ t ≤ 1 by q(t), where

q(t) = at³ + bt² + ct + d,

and q(0) = p₁ and q(1) = p₂, where the segment is defined by four control points p₀, p₁, p₂, and p₃.

This struct is callable, returning the interpolated point (x, y) at t as a NTuple{2,Float64}.

Constructor

To construct this segment, use

catmull_rom_spline_segment(p₀, p₁, p₂, p₃, α, τ)

Here, p₀, p₁, p₂, and p₃ are the four points of the segment (not a, b, c, and d), and α and τ are the parameters of the spline. The parameter α controls the type of the parametrisation, where

• α = 0: Uniform parametrisation.
• α = 1/2: Centripetal parametrisation.
• α = 1: Chordal parametrisation.

The parameter τ is the tension, and controls the tightness of the segment. τ = 0 is the least tight, while τ = 1 leads to straight lines between the control points. Both α and τ must be in [0, 1].

Cell{T}

A cell in a grid. The cell is a square with side length 2half_width. The cell is centered at (x, y). The cell is assumed to live in a polygon.

Fields

• x::T

The x-coordinate of the center of the cell.

• y::T

The y-coordinate of the center of the cell.

• half_width::T

The half-width of the cell.

• dist::T

The distance from the center of the cell to the polygon.

• max_dist::T

The maximum distance from the center of the cell to the polygon. This is dist + half_width * sqrt(2).

Constructors

Cell(x::T, y::T, half_width::T, points, boundary_nodes)

Constructs a cell with center (x, y) and half-width half_width. The cell is assumed to live in the polygon defined by points and boundary_nodes.

CellQueue{T}

A struct representing the priority queue of Cells, used for sorting the cells in a grid according to their maximum distance.

Fields

• queue::MaxPriorityQueue{Cell{T},T}: The priority queue of cells, sorting according to maximum distance.

Constructors

CellQueue{T}()

Constructs a new CellQueue with elements of type Cell{T}.

CircularArc <: AbstractParametricCurve

Curve for representing a circular arc, parametrised over 0 ≤ t ≤ 1. This curve can be evaluated using circular_arc(t) and returns a tuple (x, y) of the coordinates of the point on the curve at t.

Fields

• center::NTuple{2,Float64}: The center of the arc.
• radius::Float64: The radius of the arc.
• start_angle::Float64: The angle of the initial point of the arc, in radians.
• sector_angle::Float64: The angle of the sector of the arc, in radians. This is given by end_angle - start_angle, where end_angle is the angle at last, and so might be negative for negatively oriented arcs.
• first::NTuple{2,Float64}: The first point of the arc.
• last::NTuple{2,Float64}: The last point of the arc.
• pqr::NTuple{3, NTuple{2, Float64}}: Three points on the circle through the arc. This is needed for point_position_relative_to_curve.

Constructor

You can construct a CircularArc using

CircularArc(first, last, center; positive=true)

It is up to you to ensure that first and last are equidistant from center - the radius used will be the distance between center and first. The positive keyword argument is used to determine if the arc is positively oriented or negatively oriented.

ConvexHull{PointsType, IntegerType}

Struct for representing a convex hull. See also convex_hull.

Fields

• points::PointsType: The underlying point set.
• vertices::Vector{IntegerType}: The vertices of the convex hull, in counter-clockwise order. Defined so that vertices[begin] == vertices[end].

Constructors

ConvexHull(points, vertices)
convex_hull(points; IntegerType=Int)

DiametralBoundingBox

Type for representing a bounding box generated from an edge's diametral circle.

Fields

• bounding_box::BoundingBox: The bounding box.
• edge::NTuple{2,Int}: The generator edge.

EachGhostEdge{E,T}

An iterator over all ghost edges in a triangulation.

Fields

• edges::E: The iterator over all edges in the triangulation.
• tri::T: The triangulation.

EachGhostTriangle{V,T}

An iterator over all ghost triangles in a triangulation.

Fields

• triangles::V: The iterator over all triangles in the triangulation.
• tri::T: The triangulation.

EachGhostVertex{V,T}

An iterator over all ghost vertices in a triangulation.

Fields

• vertices::V: The iterator over all vertices in the triangulation.
• tri::T: The triangulation.

EachSolidEdge{E,T}

An iterator over all solid edges in a triangulation.

Fields

• edges::E: The iterator over all edges in the triangulation.
• tri::T: The triangulation.

EachSolidTriangle{V,T}

An iterator over all solid triangles in a triangulation.

Fields

• triangles::V: The iterator over all triangles in the triangulation.
• tri::T: The triangulation.

EachSolidVertex{V,T}

An iterator over all solid vertices in a triangulation.

Fields

• vertices::V: The iterator over all vertices in the triangulation.
• tri::T: The triangulation.

EllipticalArc <: AbstractParametricCurve

Curve for representing an elliptical arc, parametrised over 0 ≤ t ≤ 1. This curve can be evaluated using elliptical_arc(t) and returns a tuple (x, y) of the coordinates of the point on the curve at t.

Fields

• center::NTuple{2,Float64}: The center of the ellipse.
• horz_radius::Float64: The horizontal radius of the ellipse.
• vert_radius::Float64: The vertical radius of the ellipse.
• rotation_scales::NTuple{2,Float64}: If θ is the angle of rotation of the ellipse, then this is (sin(θ), cos(θ)).
• start_angle::Float64: The angle of the initial point of the arc measured from center, in radians. This angle is measured from the center prior to rotating the ellipse.
• sector_angle::Float64: The angle of the sector of the arc, in radians. This is given by end_angle - start_angle, where end_angle is the angle at last, and so might be negative for negatively oriented arcs.
• first::NTuple{2,Float64}: The first point of the arc.
• last::NTuple{2,Float64}: The last point of the arc.

Constructor

You can construct an EllipticalArc using

EllipticalArc(first, last, center, major_radius, minor_radius, rotation; positive=true)

where rotation is the angle of rotation of the ellipse, in degrees. The positive keyword argument is used to determine if the arc is positively oriented or negatively oriented.

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)

Graph{IntegerType}

Struct for storing neighbourhood relationships between vertices in a triangulation. This is an undirected graph.

Fields

• vertices::Set{IntegerType}

The set of vertices in the underlying triangulation.

• edges::Set{NTuple{2, IntegerType}}

The set of edges in the underlying triangulation.

• neighbours::Dict{IntegerType, Set{IntegerType}}

The map taking vertices u to the set of all v such that (u, v) is an edge in the underlying triangulation.

Constructors

Graph{IntegerType}()
Graph(vertices::Set{IntegerType}, edges::Set{NTuple{2, IntegerType}}, neighbours::Dict{IntegerType, Set{IntegerType}})

IndividualTriangleStatistics{T}

Struct storing statistics of a single triangle.

Fields

• area::T: The area of the triangle.
• lengths::NTuple{3,T}: The lengths of the edges of the triangle, given in sorted order.
• circumcenter::NTuple{2,T}: The circumcenter of the triangle.
• circumradius::T: The circumradius of the triangle.
• angles::NTuple{3, T}: The angles of the triangle, given in sorted order.
• radius_edge_ratio::T: The ratio of the circumradius to the shortest edge length.
• edge_midpoints::NTuple{3,NTuple{2,T}}: The midpoints of the edges of the triangle.
• aspect_ratio::T: The ratio of the inradius to the circumradius.
• inradius::T: The inradius of the triangle.
• perimeter::T: The perimeter of the triangle.
• centroid::NTuple{2,T}: The centroid of the triangle.
• offcenter::NTuple{2,T}: The offcenter of the triangle with radius-edge ratio cutoff β=1. See this paper.
• sink::NTuple{2,T}: The sink of the triangle relative to the parent triangulation. See this paper.

Constructors

The constructor is

IndividualTriangleStatistics(p, q, r, sink = (NaN, NaN))

where p, q, and r are the coordinates of the triangle given in counter-clockwise order. sink is the triangle's sink. This must be provided separately since it is only computed relative to a triangulation, and so requires vertices rather than coordinates; see triangle_sink.

Extended help

The relevant functions used for computing these statistics are

• squared_triangle_lengths
• triangle_area
• triangle_circumcenter
• triangle_circumradius
• triangle_radius_edge_ratio
• triangle_edge_midpoints
• triangle_perimeter
• triangle_inradius
• triangle_aspect_ratio
• triangle_centroid
• triangle_angles
• triangle_offcenter
• triangle_sink.

InsertionEventHistory{T,E}

A data structure for storing the changes to the triangulation during the insertion of a point.

Fields

• added_triangles::Set{T}: The triangles that were added.
• deleted_triangles::Set{T}: The triangles that were deleted.
• added_segments::Set{E}: The interior segments that were added.
• deleted_segments::Set{E}: The interior segments that were deleted.
• added_boundary_segments::Set{E}: The boundary segments that were added.
• deleted_boundary_segments::Set{E}: The boundary segments that were deleted.

Constructor

The default constructor is available, but we also provide

InsertionEventHistory(tri::Triangulation)

which will initialise this struct with empty, appropriately sizehint!ed, sets.

InsertionEventHistory(tri::Triangulation) -> InsertionEventHistory

Initialises an InsertionEventHistory for the triangulation tri.

mutable struct Leaf <: AbstractNode

Type for representing a leaf node in an R-tree.

Fields

• parent::Union{Branch, Nothing}: The parent of the leaf node.
• bounding_box::BoundingBox: The bounding box of the leaf node.
• children::Vector{DiametralBoundingBox}: The children of the leaf node.

Constructor

Leaf(parent::Union{Branch,Nothing}=nothing) = Leaf{Branch}(parent, InvalidBoundingBox, DiametralBoundingBox[])

LeafCache

Type for representing a cache of leaf nodes.

LineSegment <: AbstractParametricCurve

Curve for representing a line segment, parametrised over 0 ≤ t ≤ 1. This curve can be using line_segment(t) and returns a tuple (x, y) of the coordinates of the point on the curve at t.

Fields

• first::NTuple{2,Float64}: The first point of the line segment.
• last::NTuple{2,Float64}: The last point of the line segment.
• length::Float64: The length of the line segment.

Constructor

You can construct a LineSegment using

LineSegment(first, last)

MaxPriorityQueue{K, V}

Struct for a max priority queue.

Fields

• data::Vector{Pair{K, V}}: The data of the queue, stored in a vector of key-value pairs mapping elements to their priority.
• map::Dict{K, Int}: A dictionary mapping elements to their index in the data vector.

NodeCache{Node,Child}

Type for representing a cache of nodes whose children are of type Child. This is used for caching nodes that are detached from the R-tree, e.g. when a node is split.

Fields

• cache::Vector{Node}: The cache of nodes.
• size_limit::Int: The maximum number of nodes that can be cached.

Constructor

NodeCache{Node,Child}(size_limit::Int) where {Node,Child} = new{Node,Child}(Node[], size_limit)

PiecewiseLinear <: AbstractParametricCurve

Struct for representing a piecewise linear curve. This curve should not be interacted with or constructed directly. It only exists so that it can be an AbstractParametricCurve. Instead, triangulations use this curve to know that its boundary_nodes field should be used instead.

PointLocationHistory{T,E,I}

History from using jump_and_march.

Fields

• triangles::Vector{T}: The visited triangles.
• collinear_segments::Vector{E}: Segments collinear with the original line pq using to jump.
• collinear_point_indices::Vector{I}: This field contains indices to segments in collinear_segments that refer to points that were on the original segment, but there is no valid segment for them. We use manually fix this after the fact. For example, we could add an edge (1, 14), when really we mean something like (7, 14) which isn't a valid edge.
• left_vertices::Vector{I}: Vertices from the visited triangles to the left of pq.
• right_verices::Vector{I}: Vertices from the visited triangles to the right of pq.

Polygon{T,V,P} <: AbstractVector{T}

A struct for representing a polygon. The vertices are to be a counter-clockwise list of integers, where the integers themselves refer to points in points.

Fields

• vertices::V: A list of integers that refer to points in points. The last vertex shokuld not be the same as the first.
• points::P: A list of points.

PolygonHierarchy{I}

Struct used to define a polygon hierarchy. The hierarchy is represented as a forest of PolygonTrees.

Fields

• polygon_orientations::BitVector: A BitVector of length n where n is the number of polygons in the hierarchy. The ith entry is true if the ith polygon is positively oriented, and false otherwise.
• bounding_boxes::Vector{BoundingBox}: A Vector of BoundingBoxs of length n where n is the number of polygons in the hierarchy. The ith entry is the BoundingBox of the ith polygon.
• trees::Dict{I,PolygonTree{I}}: A Dict mapping the index of a polygon to its PolygonTree. The keys of trees are the roots of each individual tree, i.e. the outer-most polygons.
• reorder_cache::Vector{PolygonTree{I}}: A Vector used for caching trees to be deleted in [reorder_subtree!`](@ref).

Constructor

PolygonHierarchy{I}() where {I}

Constructs a PolygonHierarchy with no polygons.

mutable struct PolygonTree{I}

A tree structure used to define a polygon hierarchy.

Fields

• parent::Union{Nothing,PolygonTree{I}}: The parent of the tree. If nothing, then the tree is the root.
• children::Set{PolygonTree{I}}: The children of the tree.
• index::I: The index of the tree. This is the index associated with the polygon.
• height::Int: The height of the tree. This is the number of polygons in the tree that index is inside of. The root has height 0.

Constructor

PolygonTree{I}(parent::Union{Nothing,PolygonTree{I}}, index, height) where {I}

Constructs a PolygonTree with parent, index, and height, and no children.

Queue{T}

Struct for a first-in first-out queue.

mutable struct RTree

Type for representing an R-tree with linear splitting.

Fields

• root::Union{Branch,Leaf{Branch}}: The root of the R-tree.
• num_elements::Int: The number of elements in the R-tree.
• branch_cache::BranchCache: The cache of branch nodes.
• twig_cache::TwigCache: The cache of twig nodes.
• leaf_cache::LeafCache: The cache of leaf nodes.
• fill_factor::Float64: The fill factor of the R-tree, i.e. the percentage of a node's capacity that should be filled after splitting.
• free_cache::BitVector: A bit vector for keeping track of which indices in detached_cache are free.
• detached_cache::Vector{Union{Branch,Leaf{Branch}}}: A cache of detached nodes, i.e. nodes that have been split from the R-tree. This is used for deleting nodes.
• intersection_cache::NTuple{2,IntersectionCache}: Cache used for identifying intersections. Each element of the Tuple is its own cache, allowing for up to two intersection queries to be performed simultaneously. Note that this makes the R-tree non-thread-safe, and even non-safe when considering three or more intersection queries simultaneously.

Constructor

    RTree(; size_limit=100, fill_factor=0.7)

The size_limit is the node capacity. All node types have the same capacity.

RTreeIntersectionCache

Type for representing a cache used for identifying intersections in an R-tree.

Fields

• node_indices::Vector{Int}: A cache of indices used for identifying intersections.
• need_tests::BitVector: A BitVector cache for keeping track of which indices in node_indices need to be tested for intersections.

RTreeIntersectionIterator

Type for representing an iterator over the elements in an R-tree that intersect with a bounding box.

Fields

• tree::RTree: The R-tree.
• bounding_box::BoundingBox: The bounding box to test for intersections with.
• cache::RTreeIntersectionCache: The cache used for identifying intersections.

RTreeIntersectionIteratorState

The state of an RTreeIntersectionIterator.

Fields

• leaf::Leaf{Branch}: The current leaf node.
• node_indices::Vector{Int}: The indices of the current node at each level.
• need_tests::BitVector: A BitVector cache for keeping track of which indices in node_indices need to be tested for intersections.

RefinementArguments{Q,C,H,I,E,T,R}

A struct for storing arguments for mesh refinement.

Fields

• queue::Q: The RefinementQueue.
• constraints::C: The RefinementConstraints.
• events::H: The InsertionEventHistory.
• min_steiner_vertex::I: The minimum vertex of a Steiner point. All vertices greater than or equal to this can be considered as Steiner vertices.
• segment_list::Set{E}: The set of segments in the triangulation before refinement.
• segment_vertices::Set{I}: Set of vertices that are vertices of segments in segment_list.
• midpoint_split_list::Set{I}: Set of vertices that are centre-splits of encroached edges.
• offcenter_split_list::Set{I}: Set of vertices that are off-centre splits of encroached edges.
• use_circumcenter::Bool: Whether to use circumcenters for Steiner points, or the more general approach of Erten and Üngör (2009).
• use_lens::Bool: Whether to use diametral lens (true) or diametral circles (false) for the defining encroachment.
• steiner_scale::T: The factor by which to scale the Steiner points closer to the triangle's shortest edge.
• locked_convex_hull::Bool: Whether the convex hull of the triangulation had to be locked for refinement.
• had_ghosts::Bool: Whether the triangulation initially had ghost triangles or not.
• rng::R: The random number generator.
• concavity_protection::Bool: Whether to use concavity protection or not for jump_and_march. Most likely not needed, but may help in pathological cases.

Constructors

In addition to the default constructor, we provide

RefinementArguments(tri::Triangulation; kwargs...)

for constructing this struct. This constructor will lock the convex hull and add ghost triangles to tri if needed (refine! will undo these changes once the refinement is finished))

RefinementArguments(tri::Triangulation; kwargs...) -> RefinementArguments

Initialises the RefinementArguments for the given Triangulation, tri. The kwargs... match those from refine!.

RefinementConstraints{F}

A struct for storing constraints for mesh refinement.

Fields

• min_angle=0.0: The minimum angle of a triangle.
• max_angle=180.0: The maximum angle of a triangle.
• min_area=0.0: The minimum area of a triangle.
• max_area=Inf: The maximum area of a triangle.
• max_radius_edge_ratio=csd(min_angle) / 2: The maximum radius-edge ratio of a triangle. This is computed from min_angle - you cannot provide a value for it yourself.
• max_points=typemax(Int): The maximum number of vertices allowed in the triangulation. Note that this refers to num_solid_vertices, not the amount returned by num_points.
• seiditous_angle=20.0: The inter-segment angle used to define seditious edges in degrees. Should not be substantially smaller than 20.0° or any greater than 60.0°.
• custom_constraint::F=(tri, triangle) -> false: A custom constraint function. This should take a Triangulation and a triangle as arguments, and return true if the triangle violates the constraints and false otherwise.

RefinementQueue{T,E,F}

Struct defining a pair of priority queues for encroached segments and poor-quality triangles.

Fields

• segments::MaxPriorityQueue{E,F}: A priority queue of encroached segments, where the priorities are the squared edge lengths.
• triangles::MaxPriorityQueue{T,F}: A priority queue of poor-quality triangles, where the priorities are the radius-edge ratios.

Constructor

The default constructor is available, but we also provide

RefinementQueue(tri::Triangulation)

which will initialise this struct with empty queues with the appropriate types.

RepresentativeCoordinates{IntegerType, NumberType}

A mutable struct for representing the coordinates of a representative point of polygon or a set of points.

Fields

• x::NumberType: The x-coordinate of the representative point.
• y::NumberType: The y-coordinate of the representative point.
• n::IntegerType: The number of points represented by the representative point.

ShuffledPolygonLinkedList{I,T}

Data structure for representing a polygon as a doubly-linked list. In the descriptions below, π is used to denote the shuffled_indices vector.

Fields

• next::Vector{I}: The next vertices, so that next[π[i]] is the vertex after S[π[i]].
• prev::Vector{I}: The prev vertices, so that prev[π[i]] is the vertex before S[π[i]].
• shuffled_indices::Vector{I}: The shuffled indices of the vertices, so that S[π[i]] is the ith vertex.
• k::I: The number of vertices in the polygon.
• S::T: The vertices of the polygon. This should not be a circular vector, i.e. S[begin] ≠ S[end], and must use one-based indexing. Additionally, the vertices must be provided in counter-clockwise order - this is NOT checked.

Constructor

To construct this, use

ShuffledPolygonLinkedList(S::Vector; rng::AbstractRNG=Random.default_rng())

The argument rng is used for shuffling the shuffled_indices vector.

SmallAngleComplex{I}

Struct for representing a small-angle complex.

Fields

• apex::I: The apex vertex of the complex.
• members::Vector{SmallAngleComplexMember{I}}: The members of the complex.

Extended help

A small-angle complex is a set of curves that form a contiguous set of small angles, i.e. the angle between each consecutive pair of curves is less than 60°. The apex of the complex is the vertex that is shared by all of the curves.

SmallAngleComplexMember{I}

Struct for representing a member of a small-angle complex.

Fields

• parent_curve::I: The index of the parent curve in the boundary curves assoicated with the member. If this is 0, then this is instead a member of a complex around an interior segment.
• next_edge::I: The next vertex after the apex in the boundary nodes associated with the member.

Triangulation{P,T,BN,W,I,E,Es,BC,BCT,BEM,GVM,GVR,BPL,C,BE}

Struct representing a triangulation, as constructed by triangulate.

Fields

• points::P

The point set of the triangulation. Please note that this may not necessarily correspond to each point in the triangulation, e.g. some points may have been deleted - see each_solid_vertex for an iterator over each vertex in the triangulation.

• triangles::T

The triangles in the triangulation. Each triangle is oriented counter-clockwise. If your triangulation has ghost triangles, some of these triangles will contain ghost vertices (i.e., vertices negative indices). Solid triangles can be iterated over using each_solid_triangle.

• boundary_nodes::BN

The boundary nodes of the triangulation, if the triangulation is constrained; the assumed form of these boundary nodes is outlined in the docs. If your triangulation is unconstrained, then boundary_nodes will be empty and the boundary should instead be inspected using the convex hull field, or alternatively you can see lock_convex_hull!.

• interior_segments::Es

Constrained segments appearing in the triangulation. These will only be those segments appearing off of the boundary. If your triangulation is unconstrained, then segments will be empty.

• all_segments::Es

This is similar to segments, except this includes both the interior segments and the boundary segments. If your triangulation is unconstrained, then all_segments will be empty.

• weights::W

The weights of the triangulation. If you are not using a weighted triangulation, this will be given by ZeroWeight(). Otherwise, the weights must be such that get_weight(weights, i) is the weight for the ith vertex. The weights should be Float64.

• adjacent::Adjacent{I,E}

The Adjacent map of the triangulation. This maps edges (u, v) to vertices w such that (u, v, w) is a positively oriented triangle in triangles (up to rotation).

• adjacent2vertex::Adjacent2Vertex{I,Es}

The Adjacent2Vertex map of the triangulation. This maps vertices w to sets S such that (u, v, w) is a positively oriented triangle in triangles (up to rotation) for all (u, v) ∈ S.

• graph::Graph{I}

The Graph of the triangulation, represented as an undirected graph that defines all the neighbourhood information for the triangulation.

• boundary_curves::BC

Functions defining the boundary curves of the triangulation, incase you are triangulating a curve-bounded domain. By default, this will be an empty Tuple, indicating that the boundary is as specified in boundary_nodes - a piecewise linear curve. If you are triangulating a curve-bounded domain, then these will be the parametric curves (see AbstractParametricCurve) you provided as a Tuple, where the ith element of the Tuple is associated with the ghost vertex -i, i.e. the ith section as indicated by ghost_vertex_map. If the ith boundary was left was a sequence of edges, then the function will be a PiecewiseLinear().

• boundary_edge_map::BEM

This is a Dict from construct_boundary_edge_map that maps boundary edges (u, v) to their corresponding position in boundary_nodes.

• ghost_vertex_map::GVM

This is a Dict that maps ghost vertices to their corresponding section in boundary_nodes, constructed by construct_ghost_vertex_map.

• ghost_vertex_ranges::GVR

This is a Dict that maps ghost vertices to a range of all other ghost vertices that appear on the curve corresponding to the given ghost vertex, constructed by construct_ghost_vertex_ranges.

• convex_hull::ConvexHull{P,I}

The ConvexHull of the triangulation, which is the convex hull of the point set points.

• representative_point_list::BPL

The Dict of points giving RepresentativeCoordinates for each boundary curve, or for the convex hull if boundary_nodes is empty. These representative points are used for interpreting ghost vertices.

• polygon_hierarchy::PolygonHierarchy{I}

The PolygonHierarchy of the boundary, defining the hierarchy of the boundary curves, giving information about which curves are contained in which other curves.

• boundary_enricher::BE

The BoundaryEnricher used for triangulating a curve-bounded domain. If the domain is not curve-bounded, this is nothing.

• cache::C

A TriangulationCache used as a cache for add_segment! which requires a separate Triangulation structure for use. This will not contain any segments or boundary nodes. Also stores segments useful for lock_convex_hull! and unlock_convex_hull!.

Triangulation(points, triangles, boundary_nodes; kwargs...) -> Triangulation

Returns the Triangulation corresponding to the triangulation of points with triangles and boundary_nodes.

Arguments

• points: The points that the triangulation is of.
• triangles: The triangles of the triangulation. These should be given in counter-clockwise order, with vertices corresponding to points. These should not include any ghost triangles.
• boundary_nodes: The boundary nodes of the triangulation. These should match the specification given in the documentation or in check_args.

Keyword Arguments

• IntegerType=Int: The integer type to use for the triangulation. This is used for representing vertices.
• EdgeType=isnothing(segments) ? NTuple{2,IntegerType} : (edge_type ∘ typeof)(segments): The edge type to use for the triangulation.
• TriangleType=NTuple{3,IntegerType}: The triangle type to use for the triangulation.
• EdgesType=isnothing(segments) ? Set{EdgeType} : typeof(segments): The type to use for storing the edges of the triangulation.
• TrianglesType=Set{TriangleType}: The type to use for storing the triangles of the triangulation.
• weights=ZeroWeight(): The weights associated with the triangulation.
• delete_ghosts=false: Whether to delete the ghost triangles after the triangulation is computed. This is done using delete_ghost_triangles!.

Output

• tri: The Triangulation.

Triangulation(points; kwargs...) -> Triangulation

Initialises an empty Triangulation for triangulating points. The keyword arguments kwargs... match those of triangulate.

TriangulationCache{T,M,I,S}

A cache to be used as a field in Triangulation.

Fields

• triangulation::T: The cached triangulation. This will only refer to an unconstrained triangulation, meaning it cannot have any segments or boundary nodes. It will contain the weights. This is used for constrained triangulations.
• triangulation_2::T: An extra cached triangulation. This is needed for retriangulating fans for constrained triangulations.
• marked_vertices::M: Marked vertices cache for use in constrained triangulations.
• interior_segments_on_hull::I: Interior segments in the triangulation that also appear on the convex hull of tri. This is needed for lock_convex_hull! in case the convex hull also contains interior segments.
• surrounding_polygon::S: The polygon surrounding the triangulation. This is needed for delete_point!.
• fan_triangles::F: Triangles in a fan. This is needed for sorting fans for constrained triangulations.

TriangulationStatistics{T,V,I}

A struct containing statistics about a triangulation.

Fields

• num_vertices::I: The number of vertices in the triangulation.
• num_solid_vertices::I: The number of solid vertices in the triangulation.
• num_ghost_vertices::I: The number of ghost vertices in the triangulation.
• num_edges::I: The number of edges in the triangulation.
• num_solid_edges::I: The number of solid edges in the triangulation.
• num_ghost_edges::I: The number of ghost edges in the triangulation.
• num_triangles::I: The number of triangles in the triangulation.
• num_solid_triangles::I: The number of solid triangles in the triangulation.
• num_ghost_triangles::I: The number of ghost triangles in the triangulation.
• num_boundary_segments::I: The number of boundary segments in the triangulation.
• num_interior_segments::I: The number of interior segments in the triangulation.
• num_segments::I: The number of segments in the triangulation.
• num_convex_hull_vertices::I: The number of vertices on the convex hull of the triangulation.
• smallest_angle::V: The smallest angle in the triangulation.
• largest_angle::V: The largest angle in the triangulation.
• smallest_area::V: The smallest area of a triangle in the triangulation.
• largest_area::V: The largest area of a triangle in the triangulation.
• smallest_radius_edge_ratio::V: The smallest radius-edge ratio of a triangle in the triangulation.
• largest_radius_edge_ratio::V: The largest radius-edge ratio of a triangle in the triangulation.
• area::V: The total area of the triangulation.
• individual_statistics::Dict{T,IndividualTriangleStatistics{V}}: A map from triangles in the triangulation to their individual statistics. See IndividualTriangleStatistics.

Constructors

To construct these statistics, use statistics, which you call as statistics(tri::Triangulation).

TwigCache

Type for representing a cache of twig nodes, i.e. branch nodes at level 2.

VoronoiTessellation{Tr<:Triangulation,P,I,T,S,E}

Struct for representing a Voronoi tessellation.

See also voronoi.

Fields

• triangulation::Tr: The underlying triangulation. The tessellation is dual to this triangulation, although if the underlying triangulation is constrained then this is no longer the case (but it is still used).
• generators::Dict{I,P}: A Dict that maps vertices of generators to coordinates. These are simply the points present in the triangulation. A Dict is needed in case the triangulation is missing some points.
• polygon_points::Vector{P}: The points defining the coordinates of the polygons. The points are not guaranteed to be unique if a circumcenter appears on the boundary or you are considering a clipped tessellation. (See also get_polygon_coordinates.)
• polygons::Dict{I,Vector{I}}: A Dict mapping polygon indices (which is the same as a generator vertex) to the vertices of a polygon. The polygons are given in counter-clockwise order and the first and last vertices are equal.
• circumcenter_to_triangle::Dict{I,T}: A Dict mapping a circumcenter index to the triangle that contains it. The triangles are sorted such that the minimum vertex is last.
• triangle_to_circumcenter::Dict{T,I}: A Dict mapping a triangle to its circumcenter index. The triangles are sorted such that the minimum vertex is last.
• unbounded_polygons::Set{I}: A Set of indices of the unbounded polygons.
• cocircular_circumcenters::S: A Set of indices of circumcenters that come from triangles that are cocircular with another triangle's vertices, and adjoin said triangles.
• adjacent::Adjacent{I,E}: The adjacent map. This maps an oriented edge to the polygon that it belongs to.
• boundary_polygons::Set{I}: A Set of indices of the polygons that are on the boundary of the tessellation. Only relevant for clipped tessellations, otherwise see unbounded_polygons.

ZeroWeight

Struct used for indicating that a triangulation has zero weights. The weights are Float64.

intersect(r1::BoundingBox, r2::BoundingBox) -> BoundingBox
r1::BoundingBox ∩ r2::BoundingBox -> BoundingBox

Returns the intersection of r1 and r2. If the intersection is empty, returns InvalidBoundingBox.

intersect(I::BoundingInterval, J::BoundingInterval) -> BoundingInterval
I::BoundingInterval ∩ J::BoundingInterval -> BoundingInterval

Returns the intersection of I and J. If the intersection is empty, returns InvalidBoundingInterval.

union(r1::BoundingBox, r2::BoundingBox) -> BoundingBox
r1::BoundingBox ∪ r2::BoundingBox -> BoundingBox

Returns the union of r1 and r2, i.e. the smallest bounding box that contains both r1 and r2.

union(I::BoundingInterval, J::BoundingInterval) -> BoundingInterval
I::BoundingInterval ∪ J::BoundingInterval -> BoundingInterval

Returns the union of I and J, combining their bounds; i.e. the smallest interval that contains both I and J.

append!(complex::SmallAngleComplex, new_complex::SmallAngleComplex)

Appends the members of new_complex onto the members of complex.

append!(node::AbstractNode, child)

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

delete!(tree::BalancedBST{K}, key::K) -> BalancedBST{K}

Deletes the node in tree with key key if it exists. Returns tree.

delete!(tree::BoundaryRTree, i, j)

Deletes the bounding box of the diametral circle of the edge between i and j in tree.

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

Deletes id_bounding_box from tree.

eltype(queue::Queue{T}) -> Type{T}

Returns the type of elements stored in q.

empty!(events::InsertionEventHistory)

Empties events by emptying all of its fields.

empty!(cache::TriangulationCache)

Empties the cache by emptying the triangulation stored in it.

findfirst(tree::BalancedBST{K}, key::K) -> Union{Nothing,BalancedBSTNode{K}}

Returns the node in tree with key key. If no such node exists, returns nothing.

first(queue::MaxPriorityQueue) -> Pair{K, V}

Returns the element with the highest priority in a queue, without removing it from queue.

getindex(queue::MaxPriorityQueue, key) 
queue[key]

Returns the priority of the element with key key in a queue.

getindex(queue::RefinementQueue{T,E,F}, triangle::T) -> F
queue[triangle] -> F

Return the radius-edge ratio of triangle in queue.

haskey(tree::BalancedBST{K}, key::K) -> Bool

Returns true if tree has a node with key key, false otherwise.

haskey(queue::MaxPriorityQueue, key) -> Bool

Returns true if the queue has an element with key key.

haskey(queue::RefinementQueue{T,E,F}, segment::E) -> Bool

Return true if queue has segment or its reverse, and false otherwise.

haskey(queue::RefinementQueue{T,E,F}, triangle::T) -> Bool

Return true if queue has triangle or any of its counter-clockwise rotations, and false otherwise.

in(r1::BoundingBox, r2::BoundingBox) -> Bool
r1::BoundingBox ∈ r2::BoundingBox -> Bool

Tests whether r1 is in r2.

in(I::BoundingInterval, J::BoundingInterval) -> Bool
I::BoundingInterval ∈ J::BoundingInterval -> Bool

Tests whether the interval I is in the interval J.

in(a::Float64, I::BoundingInterval) -> Bool
a::Float64 ∈ I::BoundingInterval -> Bool

Tests whether a is in I.

in(p::NTuple{2,<:Number}, r::BoundingBox) -> Bool
p::NTuple{2,<:Number} ∈ r::BoundingBox -> Bool

Tests whether p is in r.

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.

insert!(tree::BoundaryRTree, i, j) -> Bool

Inserts the diametral circle of the edge between i and j into tree. Returns true if the tree's bounding boxes had to be adjusted and false otherwise.

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.

isempty(r::BoundingBox) -> Bool

Returns true if r is empty, i.e. if r.x or r.y is empty.

isempty(I::BoundingInterval) -> Bool

Returns true if I is empty, i.e. if I.a or I.b is NaN or if length(I) < 0.

isempty(queue::CellQueue) -> Bool

Returns true if the queue is empty, and false otherwise.

isempty(queue::MaxPriorityQueue) -> Bool

Returns true if the queue is empty.

isempty(cache::NodeCache) -> Bool

Returns true if cache is empty.

isempty(queue::Queue) -> Bool

Returns true if the queue is empty, false otherwise.

isempty(queue::RefinementQueue) -> Bool

Return true if queue has no segments or triangles, false otherwise.

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

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

length(I::BoundingInterval) -> Float64

Returns the length of the interval I.

Base.length(queue::MaxPriorityQueue) -> Int

Returns the number of elements in queue.

length(cache::NodeCache) -> Int

Returns the number of nodes in cache.

length(queue::Queue) -> Int

Returns the number of elements in the queue.

pop!(cache::NodeCache) -> Node

Removes and returns the last node in cache.

popfirst!(queue::MaxPriorityQueue{K, V}) where {K, V} -> Pair{K, V}

Removes and returns the element with the highest priority from the queue.

popfirst!(queue::Queue)

Removes the element from the front of the queue and returns it.

push!(tree::BalancedBST{K}, key::K)

Inserts key into tree if it is not already present.

push!(queue::MaxPriorityQueue, pair)

Adds the key-value pair pair to the queue.

push!(cache::NodeCache, node)

push!(queue::Queue, item)

Adds item to the end of the queue.

push!(complex::SmallAngleComplex, member::SmallAngleComplexMember)

Pushes member onto the members of complex.

setindex!(branch::Branch, child, i::Integer)
branch[i] = child

Sets the ith child of branch to be child, also updating the parent of child to be branch.

Bassetindex!(queue::RefinementQueue{T,E,F}, ρ::F, triangle::T) where {T,E,F}
queue[triangle] = ρ

Add a triangle to queue whose radius-edge ratio is ρ. If the triangle is already in the queue, its priority is updated to ρ.

setindex!(queue::RefinementQueue{T,E,F}, ℓ²::F, segment::E) where {T,E,F}
queue[segment] = ℓ²

Add a segment to queue whose squared length is ℓ². If the segment is already in the queue, its priority is updated to ℓ.

setindex!(queue::MaxPriorityQueue, priority, key)
queue[key] = priority

Sets the priority of the element with key key in a queue to priority, or adds the element to the queue if it is not already present.

_centroidal_smooth_itr(vorn::VoronoiTessellation, set_of_boundary_nodes, points, rng; kwargs...) -> (VoronoiTessellation, Number)

Performs a single iteration of the centroidal smoothing algorithm.

Arguments

• vorn: The VoronoiTessellation.
• set_of_boundary_nodes: The set of boundary nodes in the underlying triangulation.
• points: The underlying point set. This is a deepcopy of the points of the underlying triangulation.
• rng: The random number generator.

Keyword Arguments

• kwargs...: Extra keyword arguments passed to retriangulate.

Outputs

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

_get_interval_for_get_circle_intersection(c::AbstractParametricCurve, t₁, t₂, r) -> (Float64, Float64, NTuple{2, Float64})

Given a circle centered at c(t₁) with radius r, finds an initial interval for get_circle_intersection to perform bisection on to find a point of intersection. The returned interval is (tᵢ, tⱼ), where tᵢ is the parameter value of the first point in the interval and tⱼ is the parameter value of the last point in the interval. (The interval does not have to be sorted.) The third returned value is p = c(t₁).

_get_ray(vorn, i, ghost_vertex) -> (Point, Point)

Extracts the ray from the ith polygon of vorn corresponding to the ghost_vertex, where ghost_vertex here means that get_polygon(vorn, i)[ghost_vertex] is a ghost vertex.

Arguments

• vorn: The VoronoiTessellation.
• i: The index of the polygon.
• ghost_vertex: The index of the ghost vertex in the polygon.

Outputs

• p: The first point of the ray.
• q: A second point of the ray, so that pq gives the direction of the ray (which extends to infinity).

_getx(p) -> Float64

Get the x-coordinate of p as a Float64.

Examples

julia> using DelaunayTriangulation

julia> p = (0.37, 0.7);

julia> DelaunayTriangulation._getx(p)
0.37

julia> p = (0.37f0, 0.7f0);

julia> DelaunayTriangulation._getx(p)
0.3700000047683716

_getxy(p) -> NTuple{2, Float64}

Get the coordinates of p as a Tuple.

Examples

julia> using DelaunayTriangulation

julia> p = [0.3, 0.5];

julia> DelaunayTriangulation._getxy(p)
(0.3, 0.5)

julia> p = [0.3f0, 0.5f0];

julia> DelaunayTriangulation._getxy(p)
(0.30000001192092896, 0.5)

_gety(p) -> Float64

Get the y-coordinate of p as a Float64.

Examples

julia> using DelaunayTriangulation

julia> p = (0.5, 0.5);

julia> DelaunayTriangulation._gety(p)
0.5

julia> p = (0.5f0, 0.5f0);

julia> DelaunayTriangulation._gety(p)
0.5

_minimum(node::Union{BalancedBSTNode,Nothing}) -> Union{BalancedBSTNode,Nothing}

Returns the node with the minimum key in the subtree rooted at node. If node is nothing, returns nothing.

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

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

_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!.

_to_val(v) -> Val

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

add_adjacent!(adj::Adjacent, uv, w)
add_adjacent!(adj::Adjacent, u, v, w)

Adds the adjacency relationship (u, v, w) to adj.

Examples

julia> using DelaunayTriangulation

julia> adj = DelaunayTriangulation.Adjacent{Int64, NTuple{2, Int64}}();

julia> DelaunayTriangulation.add_adjacent!(adj, 1, 2, 3)
Adjacent{Int64, Tuple{Int64, Int64}}, with map:
Dict{Tuple{Int64, Int64}, Int64} with 1 entry:
  (1, 2) => 3

julia> DelaunayTriangulation.add_adjacent!(adj, (2, 3), 1)
Adjacent{Int64, Tuple{Int64, Int64}}, with map:
Dict{Tuple{Int64, Int64}, Int64} with 2 entries:
  (1, 2) => 3
  (2, 3) => 1

julia> DelaunayTriangulation.add_adjacent!(adj, 3, 1, 2)
Adjacent{Int64, Tuple{Int64, Int64}}, with map:
Dict{Tuple{Int64, Int64}, Int64} with 3 entries:
  (1, 2) => 3
  (3, 1) => 2
  (2, 3) => 1

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.

add_adjacent!(vor::VoronoiTessellation, ij, k)
add_adjacent!(vor::VoronoiTessellation, i, j, k)

Adds the adjacency relationship (i, j) ⟹ k between the oriented edge (i, j) and polygon index k to the Voronoi tessellation vor.

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

add_adjacent2vertex!(adj2v::Adjacent2Vertex, w, uv)
add_adjacent2vertex!(adj2v::Adjacent2Vertex, w, u, v)

Adds the edge uv to the set of edges E such that (u, v, w) is a positively oriented triangle in the underlying triangulation for each (u, v) ∈ E.

Examples

julia> using DelaunayTriangulation

julia> adj2v = DelaunayTriangulation.Adjacent2Vertex{Int64, Set{NTuple{2, Int64}}}()
Adjacent2Vertex{Int64, Set{Tuple{Int64, Int64}}} with map:
Dict{Int64, Set{Tuple{Int64, Int64}}}()

julia> DelaunayTriangulation.add_adjacent2vertex!(adj2v, 1, (2, 3))
Adjacent2Vertex{Int64, Set{Tuple{Int64, Int64}}} with map:
Dict{Int64, Set{Tuple{Int64, Int64}}} with 1 entry:
  1 => Set([(2, 3)])

julia> DelaunayTriangulation.add_adjacent2vertex!(adj2v, 1, 5, 7)
Adjacent2Vertex{Int64, Set{Tuple{Int64, Int64}}} with map:
Dict{Int64, Set{Tuple{Int64, Int64}}} with 1 entry:
  1 => Set([(5, 7), (2, 3)])

julia> DelaunayTriangulation.add_adjacent2vertex!(adj2v, 17, (5, -1))
Adjacent2Vertex{Int64, Set{Tuple{Int64, Int64}}} with map:
Dict{Int64, Set{Tuple{Int64, Int64}}} with 2 entries:
  17 => Set([(5, -1)])
  1  => Set([(5, 7), (2, 3)])

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.

add_boundary_information!(tri::Triangulation)

Updates tri so that the ghost triangle information defined by the boundary nodes in tri is added to the triangulation.

add_boundary_polygon!(vor::VoronoiTessellation, i)

Adds the index i to the set of boundary polygons of vor.

add_child!(node::AbstractNode, child)

Adds child to node, i.e. appends child to the children of node via push!.

add_child!(tree::PolygonTree, child::PolygonTree)

Adds child to tree.

add_edge!(E, e...)

Add the edges e... to E.

Examples

julia> using DelaunayTriangulation

julia> E = Set(((1,5),(17,10),(5,3)))
Set{Tuple{Int64, Int64}} with 3 elements:
  (5, 3)
  (17, 10)
  (1, 5)

julia> DelaunayTriangulation.add_edge!(E, (3, 2))

julia> E
Set{Tuple{Int64, Int64}} with 4 elements:
  (3, 2)
  (5, 3)
  (17, 10)
  (1, 5)

julia> DelaunayTriangulation.add_edge!(E, (1, -3), (5, 10), (1, -1))

julia> E
Set{Tuple{Int64, Int64}} with 7 elements:
  (3, 2)
  (5, 10)
  (1, -3)
  (1, -1)
  (5, 3)
  (17, 10)
  (1, 5)

add_edge!(events::InsertionEventHistory, e)

Add the edge e to the added_segments of events.

add_edge!(history::PointLocationHistory{T,E}, i, j)

Adds the edge (i, j) to the collinear_segments field of history.

add_edge!(G::Graph, u, v)

Adds the edge (u, v) to G.

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.

add_ghost_triangles!(tri::Triangulation)

Adds all the ghost triangles to tri.

add_index!(history::PointLocationHistory, i)

Adds the index i to the collinear_point_indices field of history.

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.

add_left_vertex!(history::PointLocationHistory, i)

Adds the vertex i to the left_vertices field of history.

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

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

add_neighbour!(G::Graph, u, v...)

Adds the neighbours v... to u in G.

add_new_triangles!(tri_original::Triangulation, tris)

Adds the triangles from tris to tri_original.

add_point!(c::RepresentativeCoordinates, p)

Treating c as an arithmetic average, updates the coordinates of c to include p.

add_point!(tri::Triangulation, x, y, w; kwargs...)

Adds the point (x, y) into tri with weight w. This function requires that add_weight! is defined on the weights stored in tri. The kwargs match those from add_point!(tri::Triangulation, ::Any).

add_point!(tri::Triangulation, new_point; kwargs...) -> Triangle
add_point!(tri::Triangulation, x, y; kwargs...) -> Triangle

Arguments

• tri::Triangulation: The Triangulation.
• new_point: The point to be added to the triangulation. The second method uses (x, y) to represent the new point instead. If new_point is an integer, then the point added is get_point(tri, new_point).

Keyword Arguments

• point_indices=each_solid_vertex(tri): The indices of the points to be used in the jump_and_march algorithm for selecting the initial point.
• m=default_num_samples(length(point_indices)): The number of samples (without replacement) to be used in the jump_and_march algorithm for selecting the initial point.
• try_points=(): Additional points to try for selecting the initial point, in addition to the m sampled.
• rng::AbstractRNG=Random.default_rng(): The random number generator to be used in jump_and_march.
• initial_search_point=integer_type(tri)(select_initial_point(tri, new_point; point_indices, m, try_points, rng)): The initial point to be used in jump_and_march.
• update_representative_point=false: Whether to update the representative point of the triangulation after adding the new point.
• store_event_history=Val(false): Whether to store the event history of the triangulation from adding the new point.
• event_history=nothing: The event history of the triangulation from adding the new point. Only updated if store_event_history is true, in which case it needs to be an InsertionEventHistory object.
• concavity_protection=false: Whether to use concavity protection for finding V below. See concavity_protection_check. This is only needed if your triangulation is not convex.
• V=jump_and_march(tri, get_point(tri, new_point); m=nothing, point_indices=nothing, try_points=nothing, k=initial_search_point, concavity_protection, rng): The positively oriented triangle containing the point being added.

• peek=Val(false): Whether the point should actually be added into the triangulation, or just 'peeked' at so that the events that would occur from its addition can be added into event_history.

Outputs

The triangulation is updated in-place, but we do return

• V: The triangle containing the point being added.

add_point_bowyer_watson!(tri::Triangulation, new_point, initial_search_point::I, rng::AbstractRNG=Random.default_rng(), update_representative_point=true, store_event_history=Val(false), event_history=nothing, peek::P=Val(false)) -> 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 jump_and_march at. See get_initial_search_point.
• rng::AbstractRNG: The random number generator to use.
• 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:

1. First, the triangle containing the new point, V, is found using jump_and_march.
2. Once the triangle is found, we call into add_point_bowyer_watson_and_process_after_found_triangle to properly insert the point.
3. 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.

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

Output

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

Extended help

This function works as follows:

1. To dig the cavity, we call dig_cavity! on each edge of V, stepping towards the adjacent triangles to excavate the cavity recursively.
2. 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.

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.

add_point_convex_triangulation!(tri::Triangulation, u, v, w, S)

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.

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.

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

1. 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.
2. The algorithm is recursive, recursively digging further through the polygon to find non-Delaunay edges to adjoins with u.

add_polygon!(vor::VoronoiTessellation, B, i)

Adds, or replaces, the polygon associated with the index i with B. B should be a counter-clockwise sequence of vertices, with B[begin] == B[end].

add_polygon_adjacent!(vorn::VoronoiTessellation, polygon)

Adds the adjacent polygons of the boundary edges of the polygon polygon to the adjacency list.

add_right_vertex!(history::PointLocationHistory, j)

Adds the vertex j to the right_vertices field of history.

add_segment!(tri::Triangulation, segment; rng::AbstractRNG=Random.default_rng())
add_segment!(tri::Triangulation, i, j; rng::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.

Outputs

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

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.

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

add_to_edges!(E, e)

Add the edge e to E.

Examples

julia> using DelaunayTriangulation

julia> E = Set(((1, 2),(3,5)))
Set{Tuple{Int64, Int64}} with 2 elements:
  (1, 2)
  (3, 5)

julia> DelaunayTriangulation.add_to_edges!(E, (1, 5))
Set{Tuple{Int64, Int64}} with 3 elements:
  (1, 2)
  (3, 5)
  (1, 5)

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.

add_to_triangles!(T, V)

Add the triangle V to the collection of triangles T.

Examples

julia> using DelaunayTriangulation

julia> T = Set(((1, 2, 3), (17, 8, 9)));

julia> DelaunayTriangulation.add_to_triangles!(T, (1, 5, 12))
Set{Tuple{Int64, Int64, Int64}} with 3 elements:
  (1, 5, 12)
  (1, 2, 3)
  (17, 8, 9)

julia> DelaunayTriangulation.add_to_triangles!(T, (-1, 3, 6))
Set{Tuple{Int64, Int64, Int64}} with 4 elements:
  (1, 5, 12)
  (1, 2, 3)
  (17, 8, 9)
  (-1, 3, 6)

add_triangle!(T, V...)
add_triangle!(T, i, j, k)

Add the triangles V... or V = (i, j, k) to the collection of triangles T.

Examples

julia> using DelaunayTriangulation

julia> T = Set(((1, 2, 3), (4, 5, 6)))
Set{Tuple{Int64, Int64, Int64}} with 2 elements:
  (4, 5, 6)
  (1, 2, 3)

julia> add_triangle!(T, (7, 8, 9));

julia> add_triangle!(T, (10, 11, 12), (13, 14, 15));

julia> add_triangle!(T, 16, 17, 18);

julia> T
Set{Tuple{Int64, Int64, Int64}} with 6 elements:
  (7, 8, 9)
  (10, 11, 12)
  (4, 5, 6)
  (13, 14, 15)
  (16, 17, 18)
  (1, 2, 3)

add_triangle!(adj::Adjacent, u, v, w)
add_triangle!(adj::Adjacent, T)

Adds the adjacency relationships defined from the triangle T = (u, v, w) to adj.

Examples

julia> using DelaunayTriangulation

julia> adj = DelaunayTriangulation.Adjacent{Int32, NTuple{2, Int32}}();

julia> add_triangle!(adj, 1, 2, 3)
Adjacent{Int32, Tuple{Int32, Int32}}, with map:
Dict{Tuple{Int32, Int32}, Int32} with 3 entries:
  (1, 2) => 3
  (3, 1) => 2
  (2, 3) => 1

julia> add_triangle!(adj, 6, -1, 7)
Adjacent{Int32, Tuple{Int32, Int32}}, with map:
Dict{Tuple{Int32, Int32}, Int32} with 6 entries:
  (1, 2)  => 3
  (3, 1)  => 2
  (6, -1) => 7
  (-1, 7) => 6
  (2, 3)  => 1
  (7, 6)  => -1

add_triangle!(adj2v::Adjacent2Vertex, u, v, w)
add_triangle!(adj2v::Adjacent2Vertex, T)

Adds the relationships defined by the triangle T = (u, v, w) into adj2v.

Examples

julia> using DelaunayTriangulation

julia> adj2v = DelaunayTriangulation.Adjacent2Vertex{Int32, Set{NTuple{2, Int32}}}()
Adjacent2Vertex{Int32, Set{Tuple{Int32, Int32}}} with map:
Dict{Int32, Set{Tuple{Int32, Int32}}}()

julia> add_triangle!(adj2v, 17, 5, 8)
Adjacent2Vertex{Int32, Set{Tuple{Int32, Int32}}} with map:
Dict{Int32, Set{Tuple{Int32, Int32}}} with 3 entries:
  5  => Set([(8, 17)])
  8  => Set([(17, 5)])
  17 => Set([(5, 8)])

julia> add_triangle!(adj2v, 1, 5, 13)
Adjacent2Vertex{Int32, Set{Tuple{Int32, Int32}}} with map:
Dict{Int32, Set{Tuple{Int32, Int32}}} with 5 entries:
  5  => Set([(8, 17), (13, 1)])
  13 => Set([(1, 5)])
  8  => Set([(17, 5)])
  17 => Set([(5, 8)])
  1  => Set([(5, 13)])

add_triangle!(G::Graph, u, v, w)
add_triangle!(G::Graph, T)

Adds the neighbourhood relationships defined by the triangle T = (u, v, w) to the graph G.

add_triangle!(events::InsertionEventHistory, T)

Add the triangle T to the added_triangles of events.

add_triangle!(history::PointLocationHistory, i, j, k)

Adds the triangle (i, j, k) to the triangles field of history.

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)

Adds the triangle T = (u, v, w) into tri. This won't add the points into tri, it will just update the fields so that its existence in the triangulation is known.

Arguments

• tri::Triangulation: The triangulation to add the triangle to.
• u, v, w: The vertices of the triangle to add.

Keyword Arguments

• protect_boundary=false: If true, then the boundary edges will not be updated. Otherwise, add_boundary_edges_single!, add_boundary_edges_double!, or add_boundary_edges_triple! will be called depending on the number of boundary edges in the triangle.
• update_ghost_edges=false: If true, then the ghost edges will be updated. Otherwise, the ghost edges will not be updated. Will only be used if protect_boundary=false.

Outputs

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

add_unbounded_polygon!(vor::VoronoiTessellation, i)

Adds the index i to the set of unbounded polygons of vor.

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

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

add_vertex!(G::Graph, u...)

Adds the vertices u... to G.

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

add_weight!(weights, w)

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

add_weight!(tri::Triangulation, w)

Pushes the weight w into the weights of tri.

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

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

all_ghost_vertices(tri::Triangulation) -> KeySet

Returns the set of all ghost vertices in tri.

angle_between(p, q) -> Float64

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

angle_between(c₁::AbstractParametricCurve, c₂::AbstractParametricCurve) -> Float64

Given two curves c₁ and c₂ such that c₁(1) == c₂(0), returns the angle between the two curves, treating the interior of the curves as being left of both.

angle_between(enricher::BoundaryEnricher, curve_index1, curve_index2) -> Float64

Evaluates angle_between on the curves with indices curve_index1 and curve_index2 in enricher.

angle_between(L₁::LineSegment, L₂::LineSegment) -> Float64

Returns the angle between L₁ and L₂, assuming that L₁.last == L₂.first (this is not checked). For consistency with If the segments are part of some domain, then the line segments should be oriented so that the interior is to the left of both segments.

arc_length(c::AbstractParametricCurve) -> Float64
arc_length(c::AbstractParametricCurve, t₁, t₂) -> Float64

Returns the arc length of the [AbstractParametricCurve] c. The second method returns the arc length in the interval [t₁, t₂], where 0 ≤ t₁ ≤ t₂ ≤ 1.

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.

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.

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

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

bounding_box(points, i, j) -> DiametralBoundingBox

Returns the bounding box of the diametral circle of the points points[i] and points[j] with generator edge (i, j), returned as an DiametralBoundingBox.

bounding_box(points) -> BoundingBox

Gets the bounding box for a set of points.

bounding_box(tree::BoundaryRTree, i, j) -> DiametralBoundingBox

Returns the bounding box of the diametral circle of the edge between i and j in tree.

bounding_box(p::NTuple, q::NTuple, r::NTuple) -> BoundingBox

Returns the bounding box of the points p, q and r.

bounding_box(center, radius) -> BoundingBox

Returns the bounding box of the circle (center, radius).

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

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

See also jump_and_march.

Arguments

• tri::Triangulation: The Triangulation.
• q: The point to be located.

Keyword Arguments

• itr = each_triangle(tri): The iterator over the triangles of the triangulation.

Output

• V: The triangle containing the point q.

brute_force_search_enclosing_circumcircle(tri::Triangulation, i) -> Triangle

Searches for a triangle in tri containing the vertex i in its circumcircle using brute force. If tri is a weighted Delaunay triangulation, the triangle returned instead has the lifted vertex i below its witness plane. If no such triangle exists, (0, 0, 0) is returned.

build_triangulation_from_data!(tri::Triangulation, triangles, boundary_nodes, delete_ghosts)

Given an empty triangulation, tri, adds all the triangles and boundary_nodes into it. Use delete_ghosts=true if you want to have all ghost triangles deleted afterwards.

cache_node!(tree::RTree, node::AbstractNode)

Caches node in into tree's node caches.

cache_node!(cache::NodeCache, node)

Caches node in cache if cache is not full. Otherwise, does nothing.

centroidal_smooth(vorn::VoronoiTessellation; maxiters=1000, tol=default_displacement_tolerance(vorn), rng=Random.default_rng(), 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.
• tol=default_displacement_tolerance(vorn): The displacement tolerance. See default_displacement_tolerance for the default.
• rng=Random.default_rng(): The random number generator.
• 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.

check_absolute_precision(x, y) -> Bool

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

check_args(points, boundary_nodes, hierarchy::PolygonHierarchy) -> Bool

Check that the arguments points and boundary_nodes to triangulate, and a constructed PolygonHierarchy given by hierarchy, are valid. In particular, the function checks:

• The points are all unique. If they are not, a DuplicatePointsError is thrown.
• There are at least three points. If there are not, an InsufficientPointsError is thrown.

If boundary_nodes are provided, meaning has_boundary_nodes, then the function also checks:

• If the boundary curves all connect consistently. Here, this means that each section of a boundary curve ends at the start of the next boundary section; for contiguous boundary curves, this means that the start and end boundary nodes are the same.
• If the orientation of the boundary curves are all consistent. This means that the curves are all positively oriented relative to the domain, so that e.g. the exterior boundary curves are all counter-clockwise (relative to just themselves), the next exterior-most curves inside those exteriors are all clockwise (again, relative to just themselves), and so on.

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:

1. vertex is a boundary node of tri.
2. vertex is a ghost vertex of tri.
3. vertex adjoins a segment of tri.

check_for_intersections_with_adjacent_boundary_edges(tri::Triangulation, k, q, ghost_vertex=𝒢) -> (Certificate, Certificate, Vertex, Certificate, Certificate)

Given a boundary vertex k, find a triangle adjacent to k to locate a triangle or edge containing q.

See also search_down_adjacent_boundary_edges, which uses this function to determine an initial direction to search along a straight boundary in case q is collinear with it.

Arguments

• tri::Triangulation: The Triangulation.
• k: The boundary vertex to start from.
• q: The query point.
• ghost_vertex=𝒢: The ghost vertex corresponding to the boundary that k resides on.

Outputs

• direction_cert: The direction of q relative to the vertex k along the boundary, given as a Certificate Left, Right, or Outside. If is_outside(direction_cert), then q is not collinear with either of the adjacent boundary edges.
• q_pos_cert: The position of q relative to the vertex k along the boundary, given as a Certificate Left, Right, On, Outside, or Degenerate. This is similar to direction_cert in that it will be Outside whenever direction_cert is, but this certificate can also be On to indicate that not only is q in the direction given by direction_cert, but it is directly on the edge in that direction. If is_degnerate(q_pos_cert), then q = get_point(tri, next_vertex).
• next_vertex: The next vertex along the boundary in the direction of q, or k if q is not collinear with either of the adjacent boundary edges.
• right_cert: The Certificate for the position of q relative to the boundary edge right of k.
• left_cert: The Certificate for the position of q relative to the boundary edge left of k.

check_for_intersections_with_interior_edges_adjacent_to_boundary_vertex(tri::Triangulation, k, q, right_cert, left_cert, store_history=Val(false), history=nothing, ghost_vertex=𝒢) -> (Bool, Vertex, Vertex, Certificate, Certificate)

Checks for intersections between the line pq, where p = get_point(tri, k), and the edges neighbouring p, assuming k is a boundary node. This function should only be used after using check_for_intersections_with_adjacent_boundary_edges.

Arguments

• tri::Triangulation: The Triangulation.
• k: The boundary vertex to start from.
• q: The query point.
• right_cert: The Certificate for the position of q relative to the boundary edge right of k, coming from check_for_intersections_with_adjacent_boundary_edges.
• left_cert: The Certificate for the position of q relative to the boundary edge left of k, coming from check_for_intersections_with_adjacent_boundary_edges.
• store_history=Val(false): Whether to store the history of the algorithm.
• history=nothing: The history of the algorithm. If store_history, then this should be a PointLocationHistory object.
• ghost_vertex=𝒢: The ghost vertex corresponding to the boundary that k resides on.

Outputs

The output takes the form (i, j, edge_cert, triangle_cert). Rather than defining each output individually, here are the possible froms of the output:

• (i, j, Single, Outside): The line pq intersects the edge pᵢpⱼ and (j, i, k) is a positively oriented triangle so that pᵢ is left of pq and pⱼ is right of pq.
• (i, j, None, Inside): The point q is inside the positively oriented triangle (i, j, k).
• (0, 0, None, Outside): The point q is outside of the triangulation.
• (i, j, On, Inside): The point q is on the edge pᵢpⱼ, and thus inside the positively oriented triangle (i, j, k).
• (i, j, Right, Outside):The pointqis collinear with the edgepᵢpⱼ`, but is off of it and further into the triangulation.

Extended help

This function works in two stages. Firstly, using check_for_intersections_with_single_interior_edge_adjacent_to_boundary_vertex, we check for the intersection of pq with the edges neighbouring the vertex k, rotating counter-clockwise until we find an intersection or reach the other side of the boundary, starting from the first edge counter-clockwise away from the boundary edge right of the vertex k. By keeping track of the positions of pq relative to the current vertex and the previous, we can identify when an intersection is found. If no intersection is found before reaching the boundary edge left of k, then check_for_intersections_with_triangle_left_to_boundary_vertex is used to check the remaining triangle.

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.

check_for_steiner_point_on_segment(tri::Triangulation, V, V′, new_point, flag) -> 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.

Output

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

check_precision(x) -> Bool

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

check_ratio_precision(x, y) -> Bool

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

check_relative_precision(x, y) -> Bool

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

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.

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.

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.

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

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

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

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

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

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

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

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

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.

clear_empty_features!(tri::Triangulation)

Clears all empty features from the triangulation tri.

clear_empty_keys!(adj2v::Adjacent2Vertex)

Deletes all vertices w from adj2v such that get_adjacent2vertex(adj2v, w) is empty.

Examples

julia> using DelaunayTriangulation

julia> adj2v = DelaunayTriangulation.Adjacent2Vertex{Int64, Set{NTuple{2, Int64}}}()
Adjacent2Vertex{Int64, Set{Tuple{Int64, Int64}}} with map:
Dict{Int64, Set{Tuple{Int64, Int64}}}()

julia> add_triangle!(adj2v, 1, 2, 3)
Adjacent2Vertex{Int64, Set{Tuple{Int64, Int64}}} with map:
Dict{Int64, Set{Tuple{Int64, Int64}}} with 3 entries:
  2 => Set([(3, 1)])
  3 => Set([(1, 2)])
  1 => Set([(2, 3)])

julia> delete_triangle!(adj2v, 2, 3, 1)
Adjacent2Vertex{Int64, Set{Tuple{Int64, Int64}}} with map:
Dict{Int64, Set{Tuple{Int64, Int64}}} with 3 entries:
  2 => Set()
  3 => Set()
  1 => Set()

julia> DelaunayTriangulation.clear_empty_keys!(adj2v)
Adjacent2Vertex{Int64, Set{Tuple{Int64, Int64}}} with map:
Dict{Int64, Set{Tuple{Int64, Int64}}}()

clear_empty_vertices!(G::Graph)

Deletes all empty vertices from G.

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

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.
• is_convex: Whether the boundary is convex or not. Not currently used.

Outputs

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

clip_bounded_polygon_to_bounding_box(vorn::VoronoiTessellation, i, bounding_box) -> Vector{NTuple{2,Number}}

Clips the ith polygon of vorn to bounding_box.

See also clip_polygon.

Arguments

• vorn: The VoronoiTessellation.
• i: The index of the polygon.
• bounding_box: The bounding box to clip the polygon to.

Outputs

• coords: The coordinates of the clipped polygon. This is a circular vector.

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

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.
• is_convex: Whether the boundary is convex or not. Not currently used.

Outputs

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

clip_polygon(vertices, points, clip_vertices, clip_points) -> Vector

Clip a polygon defined by (vertices, points) to a convex clip polygon defined by (clip_vertices, clip_points) with the Sutherland-Hodgman algorithm. The polygons should be defined in counter-clockwise order.

Arguments

• vertices: The vertices of the polygon to be clipped.
• points: The underlying point set that the vertices are defined over.
• clip_vertices: The vertices of the clipping polygon.
• clip_points: The underlying point set that the clipping vertices are defined over.

Output

• clipped_polygon: The coordinates of the clipped polygon, given in counter-clockwise order and clipped_polygon[begin] == clipped_polygon[end].

clip_unbounded_polygon_to_bounding_box(vorn::VoronoiTessellation, i, bounding_box) -> Vector{NTuple{2,Number}}

Clips the ith polygon of vorn to bounding_box. The polygon is assumed to be unbounded. See also clip_polygon.

clip_voronoi_tessellation!(vorn::VoronoiTessellation, is_convex=true)

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

Arguments

• vorn: The VoronoiTessellation.
• is_convex: Whether the boundary is convex or not. Not currently used.

Outputs

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

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.

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.

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.

compare_distance(current_dist, current_idx, pts, i, qx, qy) -> (Number, Vertex)

Computes the minimum of the distance between the ith point of pts and (qx, qy) and current_dist.

Arguments

• current_dist: The current value for the distance to the point (qx, qy).
• current_idx: The point of pts corresponding to the distance current_dist.
• pts: The point set.
• i: The vertex to compare with current_idx.
• qx: The x-coordinate of the query point.
• qy: The y-coordinate of the query point.

Outputs

• current_dist: The minimum of the distance between the ith point of pts and (qx, qy) and current_dist.
• current_idx: The point of pts corresponding to the distance current_dist, which will be either i or current_idx.

compare_triangle_collections(T, V) -> Bool

Compare the collections of triangles T and V by comparing their triangles according to compare_triangles.

Examples

julia> using DelaunayTriangulation

julia> T = Set(((1, 2, 3), (4, 5, 6), (7, 8, 9)));

julia> V = [[2, 3, 1], [4, 5, 6], [9, 7, 8]];

julia> DelaunayTriangulation.compare_triangle_collections(T, V)
true

julia> V[1] = [17, 19, 20];

julia> DelaunayTriangulation.compare_triangle_collections(T, V)
false

julia> V = [[1, 2, 3], [8, 9, 7]];

julia> DelaunayTriangulation.compare_triangle_collections(T, V)
false

compare_triangles(T, V) -> Bool

Compare the triangles T and V by comparing their vertices up to rotation.

Examples

julia> using DelaunayTriangulation

julia> T1 = (1, 5, 10);

julia> T2 = (17, 23, 20);

julia> DelaunayTriangulation.compare_triangles(T1, T2)
false

julia> T2 = (5, 10, 1);

julia> DelaunayTriangulation.compare_triangles(T1, T2)
true

julia> T2 = (10, 1, 5);

julia> DelaunayTriangulation.compare_triangles(T1, T2)
true

julia> T2 = (10, 5, 1);

julia> DelaunayTriangulation.compare_triangles(T1, T2)
false

compareunorientededge_collections(E, F) -> Bool

Tests if the edge collections E and F are equal, ignoring edge orientation.

compare_unoriented_edges(u, v) -> Bool

Compare the unoriented edges u and v, i.e. compare the vertices of u and v in any order.

Examples

julia> using DelaunayTriangulation

julia> u = (1, 3);

julia> v = (5, 3);

julia> DelaunayTriangulation.compare_unoriented_edges(u, v)
false

julia> v = (1, 3);

julia> DelaunayTriangulation.compare_unoriented_edges(u, v)
true

julia> v = (3, 1);

julia> DelaunayTriangulation.compare_unoriented_edges(u, v)
true

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

Outputs

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

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.

compute_balance(node::Union{Nothing,BalancedBSTNode{K}}) -> Int8

Computes the balance of the subtree rooted at node. This is the difference between the left and right heights.

compute_centroid!(c::RepresentativeCoordinates, points)

Computes the centroid of points and stores the result in c.

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.

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.

compute_count(node::Union{Nothing,BalancedBSTNode{K}}) -> Int32

Computes the count of the subtree rooted at node, i.e. the number of nodes in the subtree rooted at node, including node.

compute_height(node::Union{Nothing,BalancedBSTNode{K}}) -> Int8

Computes the height of the subtree rooted at node.

compute_representative_points!(tri::Triangulation; use_convex_hull=!has_boundary_nodes(tri), precision=one(number_type(tri)))

Computes a new set of representative points for tri.

Arguments

• tri::Triangulation: The Triangulation for which to compute the representative points.

Keyword Arguments

• use_convex_hull=!has_boundary_nodes(tri): If true, then the representative points are computed using the convex hull of the triangulation. Otherwise, the representative points are computed using the boundary nodes of the triangulation.
• precision=one(number_type(tri)): The precision to use when computing the representative points via pole_of_inaccessibility.

Output

There are no outputs as tri is updated in-place, but for each curve the representative point is computed using pole_of_inaccessibility.

compute_split_position(enricher::BoundaryEnricher, i, j) -> (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.

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.

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:

1. If e is not a subsegment, meaning it is an input segment, then its midpoint is returned.
2. 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.
3. 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.
4. Otherwise, the midpoint is returned.

concavity_protection_check(tri::Triangulation, concavity_protection, V, q) -> Bool

Check whether the jump_and_march algorithm needs to restart. This is only needed if tri is not convex.

Arguments

• tri::Triangulation: The Triangulation.
• concavity_protection: Whether this check is needed.
• V: The triangle that the algorithm has found.
• q: The query point.

Outputs

• need_to_restart: Whether the algorithm needs to restart. Will also be false if concavity_protection.

Extended help

This function uses dist to determine whether the query point q is inside or outside of the polygon defined by the triangulation, and also checks the position of q relative to V via point_position_relative_to_triangle. If q is outside of this triangle, then need_to_restart = true. If q is inside this triangle, then issues can still arise due to overlapping ghost triangles from the non-convexity. Thus, depending on the result from dist and whether V is a ghost triangle, need_to_restart will be set accordingly.

connect_circumcenters!(B, ci)

Add the circumcenter index ci to the array B.

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)

constrained_triangulation!(tri::Triangulation, segments, boundary_nodes, 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.
• 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.

construct_boundary_edge_map(boundary_nodes::A, IntegerType::Type{I}=number_type(boundary_nodes), EdgeType::Type{E}=NTuple{2,IntegerType}) where {A,I,E} -> Dict

Constructs a map that takes boundary edges in boundary_nodes to a Tuple giving the edge's position in boundary_nodes. In particular, if dict = construct_boundary_edge_map(boundary_nodes), then dict[e] = (pos, ℓ) so that bn = get_boundary_nodes(boundary_nodes, pos) gives the boundary nodes associated with the section that e lives on, and get_boundary_nodes(bn, ℓ) is the first vertex of e.

Examples

julia> using DelaunayTriangulation

julia> DelaunayTriangulation.construct_boundary_edge_map([17, 18, 15, 4, 3, 17])
Dict{Tuple{Int64, Int64}, Tuple{Vector{Int64}, Int64}} with 5 entries:
  (18, 15) => ([17, 18, 15, 4, 3, 17], 2)
  (3, 17)  => ([17, 18, 15, 4, 3, 17], 5)
  (17, 18) => ([17, 18, 15, 4, 3, 17], 1)
  (4, 3)   => ([17, 18, 15, 4, 3, 17], 4)
  (15, 4)  => ([17, 18, 15, 4, 3, 17], 3)

julia> DelaunayTriangulation.construct_boundary_edge_map([[5, 17, 3, 9], [9, 18, 13, 1], [1, 93, 57, 5]])
Dict{Tuple{Int64, Int64}, Tuple{Int64, Int64}} with 9 entries:
  (18, 13) => (2, 2)
  (17, 3)  => (1, 2)
  (9, 18)  => (2, 1)
  (13, 1)  => (2, 3)
  (3, 9)   => (1, 3)
  (93, 57) => (3, 2)
  (5, 17)  => (1, 1)
  (57, 5)  => (3, 3)
  (1, 93)  => (3, 1)

julia> DelaunayTriangulation.construct_boundary_edge_map([[[2, 5, 10], [10, 11, 2]], [[27, 28, 29, 30], [30, 31, 85, 91], [91, 92, 27]]])
Dict{Tuple{Int64, Int64}, Tuple{Tuple{Int64, Int64}, Int64}} with 12 entries:
  (92, 27) => ((2, 3), 2)
  (2, 5)   => ((1, 1), 1)
  (11, 2)  => ((1, 2), 2)
  (10, 11) => ((1, 2), 1)
  (30, 31) => ((2, 2), 1)
  (91, 92) => ((2, 3), 1)
  (29, 30) => ((2, 1), 3)
  (31, 85) => ((2, 2), 2)
  (27, 28) => ((2, 1), 1)
  (5, 10)  => ((1, 1), 2)
  (28, 29) => ((2, 1), 2)
  (85, 91) => ((2, 2), 3)

construct_curve_index_map!(enricher::BoundaryEnricher)

Constructs the curve index map for enricher, modifying the curve index map field in-place.

construct_edge(::Type{E}, i, j) where {E} -> E

Construct an edge of type E from vertices i and j.

Examples

julia> using DelaunayTriangulation

julia> DelaunayTriangulation.construct_edge(NTuple{2,Int}, 2, 5)
(2, 5)

julia> DelaunayTriangulation.construct_edge(Vector{Int32}, 5, 15)
2-element Vector{Int32}:
  5
 15

construct_ghost_vertex_map(boundary_nodes::A, IntegerType::Type{I}=number_type(boundary_nodes)) where {A,I} -> Dict

Given a set of boundary_nodes, returns a Dict that maps ghost vertices to their associated section in boundary_nodes. There are three cases:

• has_multiple_curves(boundary_nodes)

Returns dict::Dict{I, NTuple{2, I}}, mapping ghost vertices i to Tuples (m, n) so that get_boundary_nodes(boundary_nodes, m, n) are the boundary nodes associated with i, i.e. the nth section of the mth curve is associated with the ghost vertex i.

• has_multiple_sections(boundary_nodes)

Returns dict::Dict{I, I}, mapping ghost vertices i to n so that get_boundary_nodes(boundary_nodes, n) are the boundary nodes associated with i, i.e. the nth section of the boundary is associated with the ghost vertex i.

• otherwise

Returns dict::Dict{I, A}, mapping the ghost vertex i to boundary_nodes.

Examples

julia> using DelaunayTriangulation

julia> gv_map = DelaunayTriangulation.construct_ghost_vertex_map([1, 2, 3, 4, 5, 1])
Dict{Int64, Vector{Int64}} with 1 entry:
  -1 => [1, 2, 3, 4, 5, 1]

julia> gv_map = DelaunayTriangulation.construct_ghost_vertex_map([[17, 29, 23, 5, 2, 1], [1, 50, 51, 52], [52, 1]])
Dict{Int64, Int64} with 3 entries:
  -1 => 1
  -3 => 3
  -2 => 2

julia> gv_map = DelaunayTriangulation.construct_ghost_vertex_map([[[1, 5, 17, 18, 1]], [[23, 29, 31, 33], [33, 107, 101], [101, 99, 85, 23]]])
Dict{Int64, Tuple{Int64, Int64}} with 4 entries:
  -1 => (1, 1)
  -3 => (2, 2)
  -2 => (2, 1)
  -4 => (2, 3)

Extended help

This map can be useful for iterating over all boundary nodes. For example, you can iterate over all sections of a boundary using:

gv_map = construct_ghost_vertex_map(boundary_nodes)
for (ghost_vertex, section) in gv_map 
    nodes = get_boundary_nodes(boundary_nodes, section)
    # do something with nodes
end

This works for any form of boundary_nodes.

construct_ghost_vertex_ranges(boundary_nodes::A, IntegerType::Type{I}=number_type(boundary_nodes)) where {A,I} -> Dict

Given a set of boundary_nodes, returns a Dict that maps ghost vertices to the range of all ghost vertices that the corresponding boundary curve could correspond to.

Examples

julia> using DelaunayTriangulation

julia> boundary_nodes = [
                  [
                      [1, 2, 3, 4], [4, 5, 6, 1]
                  ],
                  [
                      [18, 19, 20, 25, 26, 30]
                  ],
                  [
                      [50, 51, 52, 53, 54, 55], [55, 56, 57, 58], [58, 101, 103, 105, 107, 120], [120, 121, 122, 50]
                  ]
              ]
3-element Vector{Vector{Vector{Int64}}}:
 [[1, 2, 3, 4], [4, 5, 6, 1]]
 [[18, 19, 20, 25, 26, 30]]
 [[50, 51, 52, 53, 54, 55], [55, 56, 57, 58], [58, 101, 103, 105, 107, 120], [120, 121, 122, 50]]

julia> DelaunayTriangulation.construct_ghost_vertex_ranges(boundary_nodes)
Dict{Int64, UnitRange{Int64}} with 7 entries:
  -5 => -7:-4
  -1 => -2:-1
  -7 => -7:-4
  -3 => -3:-3
  -2 => -2:-1
  -4 => -7:-4
  -6 => -7:-4

construct_parent_map!(enricher::BoundaryEnricher)

Constructs the parent map for enricher, modifying the parent map field in-place.

construct_polygon_hierarchy(points, boundary_nodes, boundary_curves; IntegerType=Int, n=4096) -> PolygonHierarchy{IntegerType}

Returns a PolygonHierarchy defining the polygon hierarchy for a given set of boundary_nodes that define a curve-bounded domain from the curves in boundary_curves. Uses polygonise to fill in the boundary curves.

Arguments

• points: The point set.
• boundary_nodes: The boundary nodes. These should be the output from convert_boundary_curves!.
• boundary_curves: The boundary curves. These should be the output from convert_boundary_curves!.

Keyword Arguments

• IntegerType=Int: The integer type to use for indexing the polygons.
• n=4096: The number of points to use for filling in the boundary curves in polygonise.

construct_polygon_hierarchy(points, boundary_nodes; IntegerType=Int) -> PolygonHierarchy{IntegerType}

Returns a PolygonHierarchy defining the polygon hierarchy for a given set of boundary_nodes that define a set of piecewise linear curves.

construct_polygon_hierarchy(points; IntegerType=Int) -> PolygonHierarchy{IntegerType}

Returns a PolygonHierarchy defining the polygon hierarchy for a given set of points. This defines a hierarchy with a single polygon.

construct_triangle(tri::Triangulation, i, j, k) -> Triangle

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

construct_positively_oriented_triangle(::Type{V}, i, j, k, points) where {V} -> V

Construct a triangle of type V from vertices i, j, and k such that the triangle is positively oriented, using points for the coordinates.

Examples

julia> using DelaunayTriangulation

julia> points = [(0.0, 0.0), (0.0, 1.0), (1.0, 0.0)];

julia> DelaunayTriangulation.construct_positively_oriented_triangle(NTuple{3, Int}, 1, 2, 3, points)
(2, 1, 3)

julia> DelaunayTriangulation.construct_positively_oriented_triangle(NTuple{3, Int}, 2, 3, 1, points)
(3, 2, 1)

julia> DelaunayTriangulation.construct_positively_oriented_triangle(NTuple{3, Int}, 2, 1, 3, points)
(2, 1, 3)

julia> DelaunayTriangulation.construct_positively_oriented_triangle(NTuple{3, Int}, 3, 2, 1, points)
(3, 2, 1)

julia> points = [(1.0, 1.0), (2.5, 2.3), (17.5, 23.0), (50.3, 0.0), (-1.0, 2.0), (0.0, 0.0), (5.0, 13.33)];

julia> DelaunayTriangulation.construct_positively_oriented_triangle(Vector{Int}, 5, 3, 2, points)
3-element Vector{Int64}:
 3
 5
 2

julia> DelaunayTriangulation.construct_positively_oriented_triangle(Vector{Int}, 7, 1, 2, points)
3-element Vector{Int64}:
 7
 1
 2

julia> DelaunayTriangulation.construct_positively_oriented_triangle(Vector{Int}, 7, 2, 1, points)
3-element Vector{Int64}:
 2
 7
 1

julia> DelaunayTriangulation.construct_positively_oriented_triangle(Vector{Int}, 5, 4, 3, points)
3-element Vector{Int64}:
 5
 4
 3

construct_segment_map(segments, points, IntegerType) -> Dict{IntegerType, Vector{IntegerType}}

Returns the segment map of segments. This is a map that maps a vertex to all vertices that share a segment with that vertex. Segments are stored twice. The vertices associated with a vertex are sorted counter-clockwise, using the points argument to define the coordinates.

construct_tree!(enricher::BoundaryEnricher)

Constructs the spatial tree for enricher, modifying the spatial tree field in-place. The parent map must be correctly configured in order for this to be valid.

construct_triangle(::Type{T}, i, j, k) where {T} -> Triangle

Construct a triangle of type T from vertices i, j, and k.

Examples

julia> using DelaunayTriangulation

julia> DelaunayTriangulation.construct_triangle(NTuple{3,Int}, 1, 2, 3)
(1, 2, 3)

julia> DelaunayTriangulation.construct_triangle(Vector{Int32}, 1, 2, 3)
3-element Vector{Int32}:
 1
 2
 3

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

Returns true if the boundary edge (i, j) is in tri, and false otherwise. Orientation matters here.

contains_edge(i, j, E) -> Bool
contains_edge(e, E) -> Bool

Check if E contains the edge e = (i, j).

Examples

julia> using DelaunayTriangulation

julia> E = Set(((1,3),(17,3),(1,-1)))
Set{Tuple{Int64, Int64}} with 3 elements:
  (1, -1)
  (17, 3)
  (1, 3)

julia> DelaunayTriangulation.contains_edge((1, 2), E)
false

julia> DelaunayTriangulation.contains_edge((17, 3), E)
true

julia> DelaunayTriangulation.contains_edge(3, 17, E) # order
false

julia> E = [[1,2],[5,13],[-1,1]]
3-element Vector{Vector{Int64}}:
 [1, 2]
 [5, 13]
 [-1, 1]

julia> DelaunayTriangulation.contains_edge(1, 2, E)
true

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

Returns true if (i, j) is a segment in tri, and false otherwise. Both (i, j) and (j, i) are checked.

contains_triangle(T, V) -> (Triangle, Bool)

Check if the collection of triangles V contains the triangle T up to rotation. The Triangle returned is the triangle in V that is equal to T up to rotation, or T if no such triangle exists. The Bool is true if V contains T, and false otherwise.

Examples

julia> using DelaunayTriangulation

julia> V = Set(((1, 2, 3), (4, 5, 6), (7, 8, 9)))
Set{Tuple{Int64, Int64, Int64}} with 3 elements:
  (7, 8, 9)
  (4, 5, 6)
  (1, 2, 3)

julia> DelaunayTriangulation.contains_triangle((1, 2, 3), V)
((1, 2, 3), true)

julia> DelaunayTriangulation.contains_triangle((2, 3, 1), V)
((1, 2, 3), true)

julia> DelaunayTriangulation.contains_triangle((10, 18, 9), V)
((10, 18, 9), false)

julia> DelaunayTriangulation.contains_triangle(9, 7, 8, V)
((7, 8, 9), true)

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.

contains_unoriented_edge(e, E) -> Bool

Check if E contains the unoriented edge e, i.e. check if E contains the edge e or reverse_edge(e).

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:

1. The function gets boundary_curves from to_boundary_curves.
2. 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.
3. 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.

convert_boundary_points_to_indices(x, y; existing_points = NTuple{2, Float64}[], check_args=true) -> (Vector, Vector)
convert_boundary_points_to_indices(xy; existing_points = NTuple{2, Float64}[], check_args=true) -> (Vector, Vector)

Converts a boundary represented by (x, y) or xy, where the points are combined rather than as separate sets of coordinates, into a set of boundary nodes for use in triangulate.

Arguments

• x, y: The x and y-coordinates for the boundary points. The individual vectors must match the specification required for boundaries outlined in the documentation.
• xy: As above, except the coordinates are combined rather than given as separate vectors.

Keyword Arguments

• existing_points: The existing points to append the boundary points to. This is useful if you have a pre-existing set of points.
• check_args: Whether to check that the arguments match the specification in the documentation.

Outputs

• boundary_nodes: The boundary nodes.
• points: The point set, which is the same as existing_points but with the boundary points appended to it.

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

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

convert_lookup_idx(b::AbstractParametricCurve, i) -> Float64

Converts the index i of the lookup table of the curve b to the corresponding t-value.

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.

See also is_boundary_edge.

convert_to_edge_adjoining_ghost_vertex(vorn::VoronoiTessellation, e) -> Edge

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

See also is_boundary_edge.

convex_hull!(tri::Triangulation; reconstruct=has_boundary_nodes(tri))

Updates the convex_hull field of tri to match the current triangulation.

Arguments

• tri::Triangulation: The Triangulation.

Keyword Arguments

• reconstruct=has_boundary_nodes(tri): If true, then the convex hull is reconstructed from scratch, using convex_hull on the points. Otherwise, computes the convex hull using the ghost triangles of tri. If there are no ghost triangles but reconstruct=true, then the convex hull is reconstructed from scratch.

convex_hull!(ch::ConvexHull{P,I}) where {P,I}

Using the points in ch, computes the convex hull in-place.

See also convex_hull.

convex_hull(points; IntegerType::Type{I}=Int) where {I} -> ConvexHull

Computes the convex hull of points. The monotone chain algorithm is used.

Arguments

• points: The set of points.

Output

• ch: The ConvexHull.

curvature(c::AbstractParametricCurve, t) -> Float64

Returns the curvature of the [AbstractParametricCurve] c at t.

decrement_num_elements!(tree::RTree)

Decrements the number of elements in tree by 1.

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.

default_num_samples(n) -> Integer

Given a number of points n, returns ∛n rounded up to the nearest integer. This is the default number of samples used in the jump-and-march algorithm.

delete_adjacent!(adj::Adjacent, uv)
delete_adjacent!(adj::Adjacent, u, v)

Deletes the edge uv from adj.

Examples

julia> using DelaunayTriangulation

julia> adj = DelaunayTriangulation.Adjacent(Dict((2, 7) => 6, (7, 6) => 2, (6, 2) => 2, (17, 3) => -1, (-1, 5) => 17, (5, 17) => -1));

julia> DelaunayTriangulation.delete_adjacent!(adj, 2, 7)
Adjacent{Int64, Tuple{Int64, Int64}}, with map:
Dict{Tuple{Int64, Int64}, Int64} with 5 entries:
  (-1, 5) => 17
  (17, 3) => -1
  (6, 2)  => 2
  (5, 17) => -1
  (7, 6)  => 2

julia> DelaunayTriangulation.delete_adjacent!(adj, (6, 2))
Adjacent{Int64, Tuple{Int64, Int64}}, with map:
Dict{Tuple{Int64, Int64}, Int64} with 4 entries:
  (-1, 5) => 17
  (17, 3) => -1
  (5, 17) => -1
  (7, 6)  => 2

julia> DelaunayTriangulation.delete_adjacent!(adj, 5, 17)
Adjacent{Int64, Tuple{Int64, Int64}}, with map:
Dict{Tuple{Int64, Int64}, Int64} with 3 entries:
  (-1, 5) => 17
  (17, 3) => -1
  (7, 6)  => 2

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

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

delete_adjacent!(vor::VoronoiTessellation, ij)
delete_adjacent!(vor::VoronoiTessellation, i, j)

Deletes the edge (i, j) from the adjacency map of vor.

delete_adjacent2vertex!(adj2v::Adjacent2Vertex, w, uv)
delete_adjacent2vertex!(adj2v::Adjacent2Vertex, w, u, v)

Deletes the edge uv from the set of edges E such that (u, v, w) is a positively oriented triangle in the underlying triangulation for each (u, v) ∈ E.

Examples

julia> using DelaunayTriangulation

julia> adj2v = DelaunayTriangulation.Adjacent2Vertex(Dict(1 => Set(((2, 3), (5, 7), (8, 9))), 5 => Set(((1, 2), (7, 9), (8, 3)))))
Adjacent2Vertex{Int64, Set{Tuple{Int64, Int64}}} with map:
Dict{Int64, Set{Tuple{Int64, Int64}}} with 2 entries:
  5 => Set([(1, 2), (8, 3), (7, 9)])
  1 => Set([(8, 9), (5, 7), (2, 3)])

julia> DelaunayTriangulation.delete_adjacent2vertex!(adj2v, 5, 8, 3)
Adjacent2Vertex{Int64, Set{Tuple{Int64, Int64}}} with map:
Dict{Int64, Set{Tuple{Int64, Int64}}} with 2 entries:
  5 => Set([(1, 2), (7, 9)])
  1 => Set([(8, 9), (5, 7), (2, 3)])

julia> DelaunayTriangulation.delete_adjacent2vertex!(adj2v, 1, (2, 3))
Adjacent2Vertex{Int64, Set{Tuple{Int64, Int64}}} with map:
Dict{Int64, Set{Tuple{Int64, Int64}}} with 2 entries:
  5 => Set([(1, 2), (7, 9)])
  1 => Set([(8, 9), (5, 7)])

delete_adjacent2vertex!(adj2v::Adjacent2Vertex, w)

Deletes the vertex w from adj2v.

Examples

julia> using DelaunayTriangulation

julia> adj2v = DelaunayTriangulation.Adjacent2Vertex(Dict(1 => Set(((2, 3), (5, 7))), 5 => Set(((-1, 2), (2, 3)))))
Adjacent2Vertex{Int64, Set{Tuple{Int64, Int64}}} with map:
Dict{Int64, Set{Tuple{Int64, Int64}}} with 2 entries:
  5 => Set([(-1, 2), (2, 3)])
  1 => Set([(5, 7), (2, 3)])

julia> DelaunayTriangulation.delete_adjacent2vertex!(adj2v, 1)
Adjacent2Vertex{Int64, Set{Tuple{Int64, Int64}}} with map:
Dict{Int64, Set{Tuple{Int64, Int64}}} with 1 entry:
  5 => Set([(-1, 2), (2, 3)])

julia> DelaunayTriangulation.delete_adjacent2vertex!(adj2v, 5)
Adjacent2Vertex{Int64, Set{Tuple{Int64, Int64}}} with map:
Dict{Int64, Set{Tuple{Int64, Int64}}}()

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

delete_adjacent2vertex!(tri::Triangulation, w)

Deletes the key w from the Adjacent2Vertex map of tri.

delete_all_exterior_triangles!(tri::Triangulation, triangles)

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

delete_boundary_node!(boundary_nodes, pos)

Deletes the boundary node at the position pos from boundary_nodes. Here, pos[1] is such that get_boundary_nodes(boundary_nodes, pos[1]) is the section that the node will be deleted from, and pos[2] gives the position of the array to delete from. In particular,

delete_boundary_node!(boundary_nodes, pos)

is the same as

deleteat!(get_boundary_nodes(boundary_nodes, pos[1]), pos[2])

Examples

julia> using DelaunayTriangulation

julia> boundary_nodes = [71, 25, 33, 44, 55, 10];

julia> DelaunayTriangulation.delete_boundary_node!(boundary_nodes, (boundary_nodes, 4))
5-element Vector{Int64}:
 71
 25
 33
 55
 10

julia> boundary_nodes = [[7, 13, 9, 25], [25, 26, 29, 7]];

julia> DelaunayTriangulation.delete_boundary_node!(boundary_nodes, (2, 3))
2-element Vector{Vector{Int64}}:
 [7, 13, 9, 25]
 [25, 26, 7]

julia> boundary_nodes = [[[17, 23, 18, 25], [25, 26, 81, 91], [91, 101, 17]], [[1, 5, 9, 13], [13, 15, 1]]];

julia> DelaunayTriangulation.delete_boundary_node!(boundary_nodes, ((2, 2), 2))
2-element Vector{Vector{Vector{Int64}}}:
 [[17, 23, 18, 25], [25, 26, 81, 91], [91, 101, 17]]
 [[1, 5, 9, 13], [13, 1]]

delete_boundary_node!(tri::Triangulation, pos)

Deletes the boundary node at the specified position pos in tri.

Arguments

• tri::Triangulation: The Triangulation.
• pos: The position to delete the node at, given as a Tuple so that delete_boundary_node!(tri, pos) is the same as deleteat!(get_boundary_nodes(tri, pos[1]), pos[2]).

Outputs

There are no outputs, but the boundary nodes of tri are updated in-place.

delete_child!(tree::PolygonTree, child::PolygonTree)

Deletes child from tree.

delete_edge!(E, e...)

Delete the edges e... from E.

Examples

julia> using DelaunayTriangulation

julia> E = Set(([1,2],[10,15],[1,-1],[13,23],[1,5]))
Set{Vector{Int64}} with 5 elements:
  [10, 15]
  [1, 5]
  [1, 2]
  [1, -1]
  [13, 23]

julia> DelaunayTriangulation.delete_edge!(E, [10,15])

julia> E
Set{Vector{Int64}} with 4 elements:
  [1, 5]
  [1, 2]
  [1, -1]
  [13, 23]

julia> DelaunayTriangulation.delete_edge!(E, [1,5], [1, -1])

julia> E
Set{Vector{Int64}} with 2 elements:
  [1, 2]
  [13, 23]

delete_edge!(boundary_enricher::BoundaryEnricher, i, j)

Deletes the edge (i, j) in boundary_enricher.

delete_edge!(events::InsertionEventHistory, e)

Add the edge e to the deleted_segments of events.

delete_edge!(G::Graph, u, v)

Deletes the edge (u, v) from G.

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.

delete_from_edges!(E, e)

Delete the edge e from E.

Examples

julia> using DelaunayTriangulation

julia> E = Set(([1,2],[5,15],[17,10],[5,-1]))
Set{Vector{Int64}} with 4 elements:
  [17, 10]
  [5, 15]
  [5, -1]
  [1, 2]

julia> DelaunayTriangulation.delete_from_edges!(E, [5, 15])
Set{Vector{Int64}} with 3 elements:
  [17, 10]
  [5, -1]
  [1, 2]

delete_from_triangles!(T, V)

Delete the triangle V from the collection of triangles T. Only deletes V if V is in T up to rotation.

Examples

julia> using DelaunayTriangulation

julia> V = Set(((1, 2, 3), (4, 5, 6), (7, 8, 9)))
Set{Tuple{Int64, Int64, Int64}} with 3 elements:
  (7, 8, 9)
  (4, 5, 6)
  (1, 2, 3)

julia> DelaunayTriangulation.delete_from_triangles!(V, (4, 5, 6))
Set{Tuple{Int64, Int64, Int64}} with 2 elements:
  (7, 8, 9)
  (1, 2, 3)

julia> DelaunayTriangulation.delete_from_triangles!(V, (9, 7, 8))
Set{Tuple{Int64, Int64, Int64}} with 1 element:
  (1, 2, 3)

delete_ghost_triangles!(tri::Triangulation)

Deletes all the ghost triangles from tri.

delete_ghost_vertices_from_graph!(tri::Triangulation)

Deletes all ghost vertices from the graph of tri.

delete_ghost_vertices!(G::Graph)

Deletes all ghost vertices from G.

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:

1. First, find_all_points_to_delete is used to identify all points in the exterior faces.
2. 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.
3. Once the correct set of triangles to delete has been found, they are deleted using delete_all_exterior_triangles!.

delete_intersected_triangles!(tri, triangles)

Deletes the triangles in triangles from tri.

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

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

delete_neighbour!(G::Graph, u, v...)

Deletes the neighbours v... from u in G.

delete_node!(node::Union{Nothing,BalancedBSTNode{K}}, key::K) -> Union{Nothing,BalancedBSTNode{K}}

Deletes the node with key key from the subtree rooted at node if it exists. Returns the new root of the subtree.

delete_point!(c::RepresentativeCoordinates, p)

Treating c as an arithmetic average, updates the coordinates of c to exclude p.

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.

Arguments

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

Keyword Arguments

• 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::AbstractRNG=Random.default_rng(): The random number generator to use for the triangulation.

delete_polygon!(vor::VoronoiTessellation, polygon)

Deletes the adjacent polygons of the boundary edges of the polygon polygon from the adjacency list.

delete_polygon_vertices_in_random_order!(list::ShuffledPolygonLinkedList, tri::Triangulation, u, v, rng::AbstractRNG)

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::AbstractRNG: The random number generator to use.

Outputs

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

delete_tree!(hierarchy::PolygonHierarchy, index)

Deletes the PolygonTree of the indexth polygon in hierarchy. The index must be associated with an exterior polygon.

delete_triangle!(V, T...)
delete_triangle!(V, i, j, k)

Delete the triangles T... from the collection of triangles V.

Examples

julia> using DelaunayTriangulation

julia> V = Set(((1, 2, 3), (4, 5, 6), (7, 8, 9), (10, 11, 12), (13, 14, 15)))
Set{Tuple{Int64, Int64, Int64}} with 5 elements:
  (7, 8, 9)
  (10, 11, 12)
  (4, 5, 6)
  (13, 14, 15)
  (1, 2, 3)

julia> delete_triangle!(V, (6, 4, 5))
Set{Tuple{Int64, Int64, Int64}} with 4 elements:
  (7, 8, 9)
  (10, 11, 12)
  (13, 14, 15)
  (1, 2, 3)

julia> delete_triangle!(V, (10, 11, 12), (1, 2, 3))
Set{Tuple{Int64, Int64, Int64}} with 2 elements:
  (7, 8, 9)
  (13, 14, 15)

julia> delete_triangle!(V, 8, 9, 7)
Set{Tuple{Int64, Int64, Int64}} with 1 element:
  (13, 14, 15)

delete_triangle!(adj::Adjacent, u, v, w)
delete_triangle!(adj::Adjacent, T)

Deletes the adjacency relationships defined from the triangle T = (u, v, w) from adj.

Examples

julia> using DelaunayTriangulation

julia> adj = DelaunayTriangulation.Adjacent{Int32, NTuple{2, Int32}}();

julia> add_triangle!(adj, 1, 6, 7);

julia> add_triangle!(adj, 17, 3, 5);

julia> adj
Adjacent{Int32, Tuple{Int32, Int32}}, with map:
Dict{Tuple{Int32, Int32}, Int32} with 6 entries:
  (17, 3) => 5
  (1, 6)  => 7
  (6, 7)  => 1
  (7, 1)  => 6
  (5, 17) => 3
  (3, 5)  => 17

julia> delete_triangle!(adj, 3, 5, 17)
Adjacent{Int32, Tuple{Int32, Int32}}, with map:
Dict{Tuple{Int32, Int32}, Int32} with 3 entries:
  (1, 6) => 7
  (6, 7) => 1
  (7, 1) => 6

julia> delete_triangle!(adj, 7, 1, 6)
Adjacent{Int32, Tuple{Int32, Int32}}, with map:
Dict{Tuple{Int32, Int32}, Int32}()

delete_triangle!(adj2v::Adjacent2Vertex, u, v, w)
delete_triangle!(adj2v::Adjacent2Vertex, T)

Deletes the relationships defined by the triangle T =(u, v, w) from adj2v.

Examples

julia> using DelaunayTriangulation

julia> adj2v = DelaunayTriangulation.Adjacent2Vertex{Int32, Set{NTuple{2, Int32}}}()
Adjacent2Vertex{Int32, Set{Tuple{Int32, Int32}}} with map:
Dict{Int32, Set{Tuple{Int32, Int32}}}()

julia> add_triangle!(adj2v, 1, 2, 3)
Adjacent2Vertex{Int32, Set{Tuple{Int32, Int32}}} with map:
Dict{Int32, Set{Tuple{Int32, Int32}}} with 3 entries:
  2 => Set([(3, 1)])
  3 => Set([(1, 2)])
  1 => Set([(2, 3)])

julia> add_triangle!(adj2v, 17, 5, 2)
Adjacent2Vertex{Int32, Set{Tuple{Int32, Int32}}} with map:
Dict{Int32, Set{Tuple{Int32, Int32}}} with 5 entries:
  5  => Set([(2, 17)])
  2  => Set([(3, 1), (17, 5)])
  17 => Set([(5, 2)])
  3  => Set([(1, 2)])
  1  => Set([(2, 3)])

julia> delete_triangle!(adj2v, 5, 2, 17)
Adjacent2Vertex{Int32, Set{Tuple{Int32, Int32}}} with map:
Dict{Int32, Set{Tuple{Int32, Int32}}} with 5 entries:
  5  => Set()
  2  => Set([(3, 1)])
  17 => Set()
  3  => Set([(1, 2)])
  1  => Set([(2, 3)])

julia> delete_triangle!(adj2v, 2, 3, 1)
Adjacent2Vertex{Int32, Set{Tuple{Int32, Int32}}} with map:
Dict{Int32, Set{Tuple{Int32, Int32}}} with 5 entries:
  5  => Set()
  2  => Set()
  17 => Set()
  3  => Set()
  1  => Set()

delete_triangle!(G::Graph, u, v, w)
delete_triangle!(G::Graph, T)

Deletes the neighbourhood relationships defined by the triangle T = (u, v, w) from the graph G.

delete_triangle!(events::InsertionEventHistory, T)

Add the triangle T to the deleted_triangles of events.

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)

Deletes the triangle T = (u, v, w) from tri. This won't delete the points from tri, it will just update the fields so that its non-existence in the triangulation is known.

Arguments

• tri::Triangulation: The triangulation to delete the triangle from.
• u, v, w: The vertices of the triangle to delete.

Keyword Arguments

• protect_boundary=false: If true, then the boundary edges will not be updated. Otherwise, delete_boundary_edges_single!, delete_boundary_edges_double!, or delete_boundary_edges_triple! will be called depending on the number of boundary edges in the triangle.
• update_ghost_edges=false: If true, then the ghost edges will be updated. Otherwise, the ghost edges will not be updated. Will only be used if protect_boundary=false.

Outputs

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

delete_unbounded_polygon!(vor::VoronoiTessellation, i)

Deletes the index i from the set of unbounded polygons of vor.

delete_unoriented_edge!(E, e)

Delete the unoriented edge e from E, i.e. delete both the edge e and reverse_edge(e).

delete_vertex!(list::ShuffledPolygonLinkedList, i)

Deletes the vertex S[πᵢ] from the linked list, where πᵢ = list.shuffled_indices[i]. This deletion is done symbolically rather than by mutating the vectors in list. In particular, we perform

• next[prev[πᵢ]] = next[πᵢ]
• prev[next[πᵢ]] = prev[πᵢ]

which is the same as removing S[πᵢ] from the linked list.

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

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

delete_vertex!(G::Graph, u...)

Deletes the vertices u... from G.

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

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::AbstractRNG: The random number generator used to shuffle the vertices of S.

Outputs

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

dequeue_and_process!(vorn, polygon_edge_queue, edges_to_process,
    intersected_edge_cache, left_edge_intersectors, right_edge_intersectors, current_edge_intersectors,
    processed_pairs, boundary_sites, segment_intersections, exterior_circumcenters, equal_circumcenter_mapping)

Dequeue an edge from polygon_edge_queue and process it. If polygon_edge_queue is empty, then we process the first edge in edges_to_process.

Arguments

• vorn: The VoronoiTessellation.
• polygon_edge_queue: The queue of edges that need to be processed.
• edges_to_process: The edges that need to be processed.
• intersected_edge_cache: A cache of intersected edges.
• left_edge_intersectors: The intersection points of left_edge with other edges.
• right_edge_intersectors: The intersection points of right_edge with other edges.
• current_edge_intersectors: The intersection points of current_edge with other edges.
• processed_pairs: A set of pairs of edges and polygons that have already been processed.
• boundary_sites: A dictionary of boundary sites.
• segment_intersections: A dictionary of segment intersections.
• exterior_circumcenters: A dictionary of exterior circumcenters.
• 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. Instead, the caches and queues are updated in-place.

Extended help

This function works as follows:

1. Firstly, if there are no edges queued in polygon_edge_queue, then we enqueue the first in edge in edges_to_process using enqueue_new_edge!.
2. We then dequeue the next edge to be processed. If the edge has already been processed, then we return early.
3. If we're still here, then we process the (edge, polygon) pair enqueued from polygon_edge_queue using process_polygon!. This function checks for intersections of the edge with the polygon.
4. Once the polygon has been processed, we then needed to classify all of the intersections using classify_intersections!, which determines, for each intersection, if the intersection is with edge, or with the edge left of edge, or to the edge right of edge.
5. Then, process_intersection_points! is used to process the intersection points, enqueueing new edges when needed.
6. We then delete the edge from edges_to_process if it is in there and return.

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.

diametral_circle(p, q) -> (NTuple{2,Float64}, Float64)

Returns the circle with diameter pq.

differentiate(c::AbstractParametricCurve, t) -> NTuple{2, Float64}

Evaluates the derivative of c at t.

dig_cavity!(tri::Triangulation, r, i, j, ℓ, flag, V, store_event_history=Val(false), event_history=nothing, peek::F=Val(false)) 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.

Output

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

Extended help

This function works as follows:

1. 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.
2. 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).
3. 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.

dist(p, q) -> Number

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

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

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

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

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

dist_sqr(p, q) -> Number

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

distance_to_offcenter(β, ℓ) -> Number

Given a triangle with shortest edge length ℓ, computes the distance from the edge to the offcenter of the triangle with radius-edge ratio cutoff β.

distance_to_polygon(q, points, boundary_nodes) -> Number

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

See also dist.

each_added_boundary_segment(events::InsertionEventHistory) -> Iterator

Returns an iterator over the boundary segments that were added to the triangulation during the insertion of a point.

each_deleted_triangle(events::InsertionEventHistory) -> Iterator

Returns an iterator over the triangles that were deleted from the triangulation during the insertion of a point.

each_added_triangle(events::InsertionEventHistory) -> Iterator

Returns an iterator over the triangles that were added to the triangulation during the insertion of a point.

each_boundary_edge(enricher::BoundaryEnricher) -> KeySet

Returns the set of keys in the parent map of enricher, i.e. each boundary edge in enricher.

each_boundary_edge(tri::Triangulation) -> KeySet

Returns an iterator over the boundary edges of tri, in no specific order.

each_boundary_node(boundary_nodes) -> Iterator

Returns an iterator that goves over each node in boundary_nodes. It is assumed that boundary_nodes represents a single section or a single contiguous boundary; if you do want to loop over every boundary nodes for a boundary with multiple sections, you should to see the result from construct_ghost_vertex_map.

Examples

julia> using DelaunayTriangulation

julia> DelaunayTriangulation.each_boundary_node([7, 8, 19, 2, 17])
5-element Vector{Int64}:
  7
  8
 19
  2
 17

julia> DelaunayTriangulation.each_boundary_node([7, 8, 19, 2, 17, 7])
6-element Vector{Int64}:
  7
  8
 19
  2
 17
  7

each_edge(E) -> Iterator

Get an iterator over the edges in E.

Examples

julia> using DelaunayTriangulation

julia> E = Set(((1,2),(1,3),(2,-1)))
Set{Tuple{Int64, Int64}} with 3 elements:
  (1, 2)
  (1, 3)
  (2, -1)

julia> each_edge(E)
Set{Tuple{Int64, Int64}} with 3 elements:
  (1, 2)
  (1, 3)
  (2, -1)

each_edge(tri::Triangulation) -> Edges

Returns an iterator over all edges in tri. Note that, if has_ghost_triangles(tri), then some of these edges will be ghost edges.

See also each_solid_edge and each_ghost_edge.

each_boundary_polygon(vorn::VoronoiTessellation) -> KeySet

Returns an iterator over the boundary polygon indices of vorn.

each_ghost_edge(tri::Triangulation) -> Edges

Returns an iterator over all ghost edges in tri.

See also each_edge and each_solid_edge.

each_ghost_triangle(tri::Triangulation) -> Triangles

Returns an iterator over all ghost triangles in tri.

See also each_triangle and each_solid_triangle.

each_ghost_vertex(tri::Triangulation) -> Set{Vertex}

Returns an iterator over all ghost vertices in tri.

See also each_vertex and each_solid_vertex.

each_point(points) -> Iterator

Returns an iterator over each point in points.

Examples

julia> using DelaunayTriangulation

julia> points = [(1.0, 2.0), (5.0, 13.0)];

julia> DelaunayTriangulation.each_point(points)
2-element Vector{Tuple{Float64, Float64}}:
 (1.0, 2.0)
 (5.0, 13.0)

julia> points = [1.0 5.0 17.7; 5.5 17.7 0.0];

julia> DelaunayTriangulation.each_point(points)
3-element ColumnSlices{Matrix{Float64}, Tuple{Base.OneTo{Int64}}, SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true}}:
 [1.0, 5.5]
 [5.0, 17.7]
 [17.7, 0.0]

each_point(tri::Triangulation) -> Points

Returns an iterator over all points in tri.

each_point_index(points) -> Iterator

Returns an iterator over each point index in points.

Examples

julia> using DelaunayTriangulation

julia> points = [(1.0, 2.0), (-5.0, 2.0), (2.3, 2.3)];

julia> DelaunayTriangulation.each_point_index(points)
Base.OneTo(3)

julia> points = [1.0 -5.0 2.3; 2.0 2.0 2.3];

julia> DelaunayTriangulation.each_point_index(points)
Base.OneTo(3)

each_point_index(tri::Triangulation) -> Indices

Returns an iterator over all point indices in tri.

each_polygon(vor::VoronoiTessellation) -> ValueIterator

Returns an iterator over each set of polygon vertices of vor.

each_polygon_index(vor::VoronoiTessellation) -> KeySet

Returns an iterator over the polygon indices of vor.

each_polygon_vertex(vor::VoronoiTessellation) -> UnitRange

Returns an iterator over each polygon point index of vor.

each_segment(tri::Triangulation) -> Edges

Returns an iterator over all segments in tri. This includes both interior and boundary segments. If you only want interior segments, then see get_interior_segments,

each_solid_edge(tri::Triangulation) -> Edges

Returns an iterator over all solid edges in tri.

See also each_edge and each_ghost_edge.

each_solid_triangle(tri::Triangulation) -> Triangles

Returns an iterator over all solid triangles in tri.

See also each_triangle and each_ghost_triangle.

each_solid_vertex(tri::Triangulation) -> Set{Vertex}

Returns an iterator over all solid vertices in tri.

See also each_vertex and each_ghost_vertex.