Data Structures

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.

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.

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

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

isempty(queue::MaxPriorityQueue) -> Bool

Returns true if the queue is empty.

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

Returns the number of elements in queue.

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

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

push!(queue::MaxPriorityQueue, pair)

Adds the key-value pair pair to the queue.

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.

fix_down!(queue::MaxPriorityQueue, k)

Fixes the queue after decreasing the value of one of its elements by percolating downwards.

fix_up!(queue::MaxPriorityQueue, k)

Fixes the queue after increasing the value of one of its elements by percolating upwards.

has_children(queue::MaxPriorityQueue, k) -> Bool

Returns true if the element at index k has children in the queue.

hchildren(k) -> Tuple{Int, Int}

Returns the indices of the children of the element at index k in a heap.

hleft(k) -> Int

Returns the index of the left child of the element at index k in a heap.

hparent(k) -> Int

Returns the index of the parent of the element at index k in a heap.

hright(k) -> Int

Returns the index of the right child of the element at index k in a heap.

is_root(k) -> Bool

Returns true if the element at index k is the root of a heap.

swap!(queue::MaxPriorityQueue, i, j)

Swaps the elements at indices i and j in queue.

Queue{T}

Struct for a first-in first-out queue.

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

Returns the type of elements stored in q.

isempty(queue::Queue) -> Bool

Returns true if the queue is empty, false otherwise.

length(queue::Queue) -> Int

Returns the number of elements in the queue.

popfirst!(queue::Queue)

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

push!(queue::Queue, item)

Adds item to the end of the queue.

enqueue_all!(queue::Queue, data)

Adds all data to the end of the queue.

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.

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

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

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.

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

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

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.

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

Inserts key into tree if it is not already present.

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

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.

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

Returns the count of node. If the node is nothing, returns 0.

get_count(tree::BalancedBST{K}) -> Int32

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

Returns the height of node. If the node is nothing, returns 0.

get_key(node::BalancedBSTNode{K}) -> K

Returns the key associated with node.

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

Returns the left child of node. If the node is nothing, returns nothing.

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

Returns the parent of node. If the node is nothing, returns nothing.

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

Returns the right child of node. If the node is nothing, returns nothing.

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

Returns the root of tree. If tree is empty, returns nothing.

has_left(node::BalancedBSTNode) -> Bool

Returns true if node has a left child, false otherwise.

has_parent(node::BalancedBSTNode) -> Bool

Returns true if node has a parent, false otherwise.

has_right(node::BalancedBSTNode) -> Bool

Returns true if node has a right child, false otherwise.

has_root(tree::BalancedBST{K}) -> Bool

Returns true if tree has a root, false otherwise.

inorder(tree::BalancedBST{K}) -> Vector{K}

Returns the inorder traversal of tree.

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

Inserts key into the subtree rooted at node if it is not already present. Returns the new root of the subtree.

rotate_left!(parent::BalancedBSTNode{K}) -> BalancedBSTNode{K}

Rotates a subtree rooted at parent to the left, returning the new root of the subtree. This local operation is used to preserve the binary search tree property after inserting or deleting a node.

rotate_right!(parent::BalancedBSTNode{K}) -> BalancedBSTNode{K}

Rotates a subtree rooted at parent to the right, returning the new root of the subtree. This local operation is used to preserve the binary search tree property after inserting or deleting a node.

set_count!(tree::BalancedBST{K}, count::Int32)

Sets the count of tree to count.

set_count!(node::BalancedBSTNode[, count = compute_count(node)])

Sets the count of node to count. If count is not provided, the count is computed using compute_count.

set_height!(node::BalancedBSTNode[, height = compute_height(node)])

Sets the height of node to height. If height is not provided, the height is computed using compute_height.

set_key!(node::BalancedBSTNode{K}, key::K)

Sets the key associated with node to key.

set_left!(node::BalancedBSTNode, left::Union{Nothing, BalancedBSTNode})

Sets the left child of node to left.

set_parent!(node::BalancedBSTNode, parent::Union{Nothing, BalancedBSTNode})

Sets the parent of node to parent.

set_right!(node::BalancedBSTNode, right::Union{Nothing, BalancedBSTNode})

Sets the right child of node to right.

set_root!(tree::BalancedBST{K}, root::Union{Nothing,BalancedBSTNode{K}})

Sets the root of tree to root.

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.

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.

abstract type AbstractNode end

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

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.

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.

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.

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)

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.

TwigCache

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

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.

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

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

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

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(cache::NodeCache) -> Bool

Returns true if cache is empty.

length(I::BoundingInterval) -> Float64

Returns the length of the interval I.

length(cache::NodeCache) -> Int

Returns the number of nodes in cache.

pop!(cache::NodeCache) -> Node

Removes and returns the last node in cache.

push!(cache::NodeCache, node)

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.

add_child!(node::AbstractNode, child)

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

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

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.

decrement_num_elements!(tree::RTree)

Decrements the number of elements in tree by 1.

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

Returns the circle with diameter pq.

expand(box::BoundingBox, perc=0.10) -> BoundingBox

Expands the bounding box box by a factor perc in each direction.

find_position_in_parent(node::AbstractNode) -> Int

Returns the position of node in its parent's children. If node has no parent, returns 0.

get_area(r::BoundingBox) -> Float64

Returns the area of r, i.e. hspan(r) * vspan(r).

get_bl_corner(r::BoundingBox) -> NTuple{2,Float64}

Returns the bottom-left corner of r.

get_bounding_box(node::AbstractNode) -> BoundingBox

Returns the bounding box of node.

get_bounding_box(id_bounding_box::DiametralBoundingBox) -> BoundingBox

Returns the bounding box of id_bounding_box.

get_bounding_box(tree::RTree) -> BoundingBox

Returns the bounding box of tree.

get_branch_cache(tree::RTree) -> BranchCache

Returns the branch cache of tree.

get_child(node::AbstractNode, i::Integer) -> AbstractNode

Returns the ith child of node.

get_child_type(node::AbstractNode) -> Union{Type{Leaf}, Type{Branch}}

Returns the type of the children of node.

get_children(node::AbstractNode) -> Vector

Returns the children of node.

get_detached_cache(tree::RTree) -> Vector{Union{Branch,Leaf{Branch}}}

Returns the detached cache of tree.

get_edge(id_bounding_box::DiametralBoundingBox) -> NTuple{2,Int}

Returns the generator edge of id_bounding_box.

get_fill_factor(tree::RTree) -> Float64

Returns the fill factor of tree.

get_free_cache(tree::RTree) -> BitVector

Returns the free cache of tree.

get_height(tree::RTree) -> Int

Returns the height of tree.

get_intersection_cache(tree::RTree) -> NTuple{2,RTreeIntersectionCache}

Returns the intersection cache of tree.

get_intersections(tree::BoundaryRTree, i, j, k; cache_id=1) -> RTreeIntersectionIterator

Returns an RTreeIntersectionIterator over the elements in tree that intersect with the bounding box of the triangle (i, j, k). cache_id must be 1 or 2, and determines what cache to use for the intersection query.

get_intersections(tree::BoundaryRTree, i, j; cache_id=1) -> RTreeIntersectionIterator

Returns an RTreeIntersectionIterator over the elements in tree that intersect with the diametral circle of the edge between i and j. cache_id must be 1 or 2, and determines what cache to use for the intersection query.

get_intersections(tree::BoundaryRTree, i; cache_id=1) -> RTreeIntersectionIterator

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

get_intersections(tree::BoundaryRTree, bbox::BoundingBox; cache_id=1) -> RTreeIntersectionIterator

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

get_leaf_cache(tree::RTree) -> LeafCache

Returns the leaf cache of tree.

get_level(node::AbstractNode) -> Int

Returns the level of node. If node is a leaf, returns 1.

get_min_nodes(tree::RTree) -> Int

Returns the minimum number of nodes that a node in tree can have.

get_need_tests(cache::RTreeIntersectionCache) -> BitVector

Returns the need_tests cache of tree.

get_node_indices(cache::RTreeIntersectionCache) -> Vector{Int}

Returns the node indices of cache.

get_parent(node::AbstractNode) -> Union{Branch, Nothing}

Returns the parent of node.

get_root(tree::RTree) -> Union{Branch,Leaf{Branch}}

Returns the root of tree.

get_size_limit(cache::NodeCache) -> Int

Returns the size limit of cache.

get_size_limit(tree::RTree) -> Int

Returns the size limit of tree.

get_state(state::RTreeIntersectionIteratorState) -> DiametralBoundingBox

Returns the current element in state.

get_tr_corner(r::BoundingBox) -> NTuple{2,Float64}

Returns the top-right corner of r.

get_twig_cache(tree::RTree) -> TwigCache

Returns the twig cache of tree.

has_children(node::AbstractNode) -> Bool

Returns true if node has children.

has_parent(node::AbstractNode) -> Bool

Returns true if node has a parent.

hspan(r::BoundingBox) -> Float64

Returns the horizontal span of r, i.e. length(r.x).

increment_num_elements!(tree::RTree)

Increments the number of elements in tree by 1.

is_full(node::AbstractNode, tree::RTree) -> Bool

Returns true if node is full, i.e. if num_children(node) ≥ get_size_limit(tree).

is_full(cache::NodeCache) -> Bool

Returns true if cache is full, i.e. if length(cache) ≥ get_size_limit(cache).

is_root(node::AbstractNode, tree::RTree) -> Bool

Returns true if node is the root of tree.

is_touching(r1::BoundingBox, r2::BoundingBox) -> Bool

Tests whether r1 and r2 are touching, i.e. if they share a common boundary. This only considers interior touching.

midpoint(r::BoundingBox) -> NTuple{2,Float64}

Returns the center of r.

midpoint(I::BoundingInterval) -> Float64

Returns the midpoint of I.

num_children(node::AbstractNode) -> Int

Returns the number of children of node.

num_elements(tree::RTree) -> Int

Returns the number of elements in tree.

pop_child!(node::AbstractNode)

Removes the last child of node via pop!.

set_bounding_box!(node::AbstractNode, bounding_box::BoundingBox)

Sets the bounding box of node to be bounding_box.

set_child!(parent_node::AbstractNode, child_node, i::Integer)

Sets the ith child of parent_node to be child_node.

set_level!(branch::Branch, level::Integer)

Sets the level of branch to be level.

set_parent!(child_node::AbstractNode, parent_node::AbstractNode)

Sets the parent of child_node to be parent_node.

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

Sets the root of tree to be node.

spawn_branch!(tree::RTree, bounding_box::BoundingBox, level) -> Branch

Returns a new branch node with bounding box bounding_box and level level from tree.

spawn_leaf!(tree::RTree, bounding_box::BoundingBox) -> Leaf{Branch}

Returns a new leaf node with bounding box bounding_box from tree.

spawn_node!(cache::NodeCache{Node}) where {Node} -> Node

Returns a node from cache. If cache is empty, returns a new node.

spawn_node!(tree::RTree, ::Type{N}, [bounding_box::BoundingBox], level) where {N} -> N

Returns a new node of type N with bounding box bounding_box and level level from tree. If bounding_box is not provided, it is replaced with InvalidBoundingBox.

split_edge!(tree::BoundaryRTree, i, j, r)

Splits the diametral bounding box associated with (i, j) into two new boxes associated with the diametral circles of (i, r) and (j, r).

vspan(r::BoundingBox) -> Float64

Returns the vertical span of r, i.e. length(r.y).

QueryResult

An enum type for representing the result of an intersection query, with instances:

• Contains: The bounding box contains the element.
• Intersects: The bounding box intersects the element.
• Outside: The bounding box is outside the element.

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.

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

Adds child to tree.

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.

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

Deletes child from tree.

delete_tree!(hierarchy::PolygonHierarchy, index)

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

expand_bounds!(hierarchy::PolygonHierarchy, perc=0.10) -> PolygonHierarchy

Expands the bounding boxes of hierarchy by a factor of perc in each direction.

find_tree(hierarchy::PolygonHierarchy, points, boundary_nodes, p) -> Union{Nothing,PolygonTree}

Finds a tree in hierarchy containing p.

Arguments

• hierarchy::PolygonHierarchy: The PolygonHierarchy to search.
• points: The point set.
• boundary_nodes: The boundary nodes.
• p: The point to test the trees of hierarchy against.

Output

• nothing if p is not inside any tree in hierarchy, and the PolygonTree containing p otherwise.

find_tree(hierarchy::PolygonHierarchy, points, boundary_nodes, tree::PolygonTree, p) -> PolygonTree

Finds a tree in hierarchy containing p that is a child of tree, assuming p is inside tree.

Arguments

• hierarchy::PolygonHierarchy: The PolygonHierarchy to search.
• points: The point set.
• boundary_nodes: The boundary nodes.
• tree::PolygonTree: The PolygonTree to search, assuming p is inside tree.
• p: The point to test the children of tree against.

Output

• tree if p is inside tree but none of its children, and a child containing p otherwise.

get_bounding_box(hierarchy::PolygonHierarchy, index) -> BoundingBox

Returns the bounding box of the indexth polygon in hierarchy.

get_bounding_boxes(hierarchy::PolygonHierarchy) -> Vector{BoundingBox}

Returns the bounding boxes of hierarchy.

get_children(tree::PolygonTree) -> Set{PolygonTree}

Returns the children of tree.

get_exterior_curve_indices(hierarchy::PolygonHierarchy) -> KeySet

Returns the indices of the exterior curves of hierarchy.

get_height(tree::PolygonTree) -> Int

Returns the height of tree.

get_index(tree::PolygonTree{I}) -> I

Returns the index of tree.

get_parent(tree::PolygonTree) -> Union{Nothing,PolygonTree}

Returns the parent of tree.

get_polygon_orientation(hierarchy::PolygonHierarchy, index) -> Bool

Returns the polygon orientation of the indexth polygon in hierarchy.

get_polygon_orientations(hierarchy::PolygonHierarchy) -> BitVector

Returns the polygon orientations of hierarchy.

get_reorder_cache(hierarchy::PolygonHierarchy) -> Vector{PolygonTree{I}}

Returns the reorder cache of hierarchy.

get_tree(hierarchy::PolygonHierarchy, index) -> PolygonTree{I}

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

get_trees(hierarchy::PolygonHierarchy) -> Dict{I,PolygonTree{I}}

Returns the trees of hierarchy, mapping the index of an exterior polygon to its PolygonTree.

has_children(tree::PolygonTree) -> Bool

Returns true if tree has children, and false otherwise.

has_parent(tree::PolygonTree) -> Bool

Returns true if tree has a parent, and false otherwise.

increase_depth!(tree::PolygonTree)

Increases the height of tree and all of its children by 1.

is_in_tree(hierarchy::PolygonHierarchy, points, boundary_nodes, tree::PolygonTree, p) -> Bool

Tests if the point p is inside tree.

Arguments

• hierarchy::PolygonHierarchy: The PolygonHierarchy containing tree.
• points: The point set.
• boundary_nodes: The boundary nodes.
• tree::PolygonTree: The PolygonTree to test p against.
• p: The point to test.

Output

• true if p is inside tree, and false otherwise.

has_children(tree::PolygonTree) -> Bool

Returns true if tree has children, and false otherwise.

reorder_hierarchy!(hierarchy::PolygonHierarchy, points, boundary_nodes, new_tree::PolygonTree)

Given a new_tree that is not contained inside any other polygon in hierarchy, adds it into hierarchy. The existing trees are checked to see if they are contained inside new_tree, and if so, they are added as children of new_tree and removed from hierarchy.

Arguments

• hierarchy::PolygonHierarchy: The PolygonHierarchy to add new_tree to.
• points: The point set.
• boundary_nodes: The boundary nodes.
• new_tree::PolygonTree: The PolygonTree to add to hierarchy.

reorder_subtree!(hierarchy::PolygonHierarchy, points, boundary_nodes, tree::PolygonTree, new_tree)

Given a new_tree contained inside tree, adds it into hierarchy. The children of tree are reordered if necessary, in case they are now contained inside new_tree.

Arguments

• hierarchy::PolygonHierarchy: The PolygonHierarchy to add new_tree to.
• points: The point set.
• boundary_nodes: The boundary nodes.
• tree::PolygonTree: The PolygonTree to add new_tree to.
• new_tree::PolygonTree: The PolygonTree to add to hierarchy and tree.

set_bounding_box!(hierarchy::PolygonHierarchy, index, bounding_box)

Sets the bounding box of the indexth polygon in hierarchy to bounding_box. If index is greater than the length of the bounding boxes vector, the vector is resized.

set_height!(tree::PolygonTree, height::Int)

Sets the height of tree to height.

set_orientation!(hierarchy::PolygonHierarchy, index, orientation)

Sets the polygon orientation of the indexth polygon in hierarchy to orientation. If index is greater than the length of the polygon orientations vector, the vector is resized.

set_parent!(tree::PolygonTree, parent::PolygonTree)

Sets the parent of tree to parent.

set_tree!(hierarchy::PolygonHierarchy, index, tree)

Sets the PolygonTree of the indexth polygon in hierarchy to tree, or adds it if it is not an existing key. The index must be associated with an exterior polygon.

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

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

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_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}()

get_adjacent(adj::Adjacent) -> Dict

Returns the adjacent map of adj.

Examples

julia> using DelaunayTriangulation

julia> d = Dict((1, 2) => 3, (2, 3) => 1, (3, 1) => 2);

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

julia> get_adjacent(adj)
Dict{Tuple{Int64, Int64}, Int64} with 3 entries:
  (1, 2) => 3
  (3, 1) => 2
  (2, 3) => 1

julia> get_adjacent(adj) == d
true

get_adjacent(adj::Adjacent{I, E}, uv::E) -> Vertex
get_adjacent(adj::Adjacent{I, E}, u, v) -> Vertex

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

Examples

julia> using DelaunayTriangulation

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

julia> get_adjacent(adj, 4, 5)
-1

julia> get_adjacent(adj, (3, 1))
2

julia> get_adjacent(adj, (1, 2))
3

julia> get_adjacent(adj, 17, 5)
0

julia> get_adjacent(adj, (1, 6))
0

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

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_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)])

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}}}()

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_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()

get_adjacent2vertex(adj2v::Adjacent2Vertex, w) -> Edges

Returns 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> get_adjacent2vertex(adj2v, 1)
Set{Tuple{Int64, Int64}} with 3 elements:
  (8, 9)
  (5, 7)
  (2, 3)

julia> get_adjacent2vertex(adj2v, 5)
Set{Tuple{Int64, Int64}} with 3 elements:
  (1, 2)
  (8, 3)
  (7, 9)

get_adjacent2vertex(adj2v::Adjacent2Vertex) -> Dict

Returns the adjacent2vertex map of adj2v.

Examples

julia> using DelaunayTriangulation

julia> e1 = Set(((1, 2), (5, 3), (7, 8)));

julia> e2 = Set(((2, 3), (13, 5), (-1, 7)));

julia> d = Dict(9 => e1, 6 => e2);

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

julia> get_adjacent2vertex(adj2v)
Dict{Int64, Set{Tuple{Int64, Int64}}} with 2 entries:
  6 => Set([(13, 5), (-1, 7), (2, 3)])
  9 => Set([(1, 2), (7, 8), (5, 3)])

julia> get_adjacent2vertex(adj2v) == d
true

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

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

Adds the edge (u, v) to G.

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

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

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_vertex!(G::Graph, u...)

Adds the vertices u... to G.

clear_empty_vertices!(G::Graph)

Deletes all empty vertices from G.

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

Deletes the edge (u, v) from G.

delete_ghost_vertices!(G::Graph)

Deletes all ghost vertices from G.

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

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

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_vertex!(G::Graph, u...)

Deletes the vertices u... from G.

get_edges(graph::Graph) -> Set{NTuple{2, Vertex}}

Returns the set of edges in graph.

get_neighbours(G::Graph, u) -> Set{Vertex}

Returns the set of neighbours of u in G.

get_neighbours(graph::Graph) -> Dict{Vertex, Set{Vertex}}

Returns the neighbours map of graph.

get_vertices(graph::Graph) -> Set{Vertex}

Returns the set of vertices in graph.

has_ghost_vertices(G::Graph) -> Bool

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

has_vertex(G::Graph, u) -> Bool

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

num_edges(G::Graph) -> Integer

Returns the number of edges in G. The edges (i, j) and (j, i) are counted as one edge.

num_neighbours(G::Graph, u) -> Integer

Returns the number of neighbours of u in G.

num_vertices(G::Graph) -> Integer

Returns the number of vertices in G.

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

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)

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.

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.

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.

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.

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

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.

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

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

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

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

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

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

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

Given a circle centered at c(t₁) with radius r, finds the first intersection of the circle with the curve after t₁ and less than t₂. It is assumed that such an intersection exists. The returned value is (t, q), where t is the parameter value of the intersection and q is the point of intersection.

get_closest_point(b::AbstractParametricCurve p) -> (Float64, NTuple{2,Float64})

Returns the t-value and the associated point q on the curve b that is nearest to p using a binary search. The search is done until the binary search interval is smaller than 1e-12. This function will only work if the curve b has a lookup table.

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

Returns a value of t such that the arc length along c from t₁ to t is equal to the arc length along c from t to t₂. Uses the bisection method to compute the t-value.

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

Returns a value of t such that the total variation of c from t₁ to t is equal to the total variation of c from t to t₂. Uses the bisection method to compute the t-value. Also returns the new total variation of the two pieces.

get_inverse(c::AbstractParametricCurve, p) -> Float64

Given a point p on c, returns the t-value such that c(t) ≈ p.

get_segment(c::CatmullRomSpline, t) -> (CatmullRomSplineSegment, Int)

Returns the CatmullRomSplineSegment of the CatmullRomSpline c that contains the point at t. Also returns the segment index.

has_lookup_table(c::AbstractParametricCurve) -> Bool

Returns true if c has a lookup table, and false otherwise.

horizontal_inflection_points(c::AbstractParametricCurve; steps=200, iters = 50, tol = 1e-5) -> Vector{Float64}

Returns points t such that x''(t) = 0 and 0 ≤ t ≤ 1, where x'' is the second derivative of the x-coordinate of c. This function uses Newton's method to find the roots of x''. Note that these are only technically inflection points if x'''(t) ≠ 0 at these points, but this is not checked.

Arguments

• c::AbstractParametricCurve: The curve to find the horizontal inflection points of.

Keyword Arguments

• steps=200: The number of t-values to use for seeding Newton's method. In particular, Newton's method is run for each initial value in LinRange(0, 1, steps).
• iters=50: The number of iterations to run Newton's method for.
• tol=1e-5: The tolerance to use for uniquetol. Also used for deciding whether a root is a valid root, i.e. if abs(x''(t)) > tol for a found root t, then t is not a valid root and is rejected.

Output

• t: All inflection points, given in sorted order.

horizontal_turning_points(c::AbstractParametricCurve; steps=200, iters = 50, tol = 1e-5) -> Vector{Float64}

Returns points t such that x'(t) = 0 and 0 ≤ t ≤ 1, where x' is the derivative of the x-coordinate of c. This function uses Newton's method to find the roots of x'.

Arguments

• c::AbstractParametricCurve: The curve to find the horizontal turning points of.

Keyword Arguments

• steps=200: The number of t-values to use for seeding Newton's method. In particular, Newton's method is run for each initial value in LinRange(0, 1, steps).
• iters=50: The number of iterations to run Newton's method for.
• tol=1e-5: The tolerance to use for uniquetol. Also used for deciding whether a root is a valid root, i.e. if abs(x'(t)) > tol for a found root t, then t is not a valid root and is rejected.

Output

• t: All turning points, given in sorted order.

inflection_points(c::AbstractParametricCurve; steps=200, iters = 50, tol = 1e-5) -> Vector{Float64}

Returns points t such that κ(t) = 0 and 0 ≤ t ≤ 1, where κ is the curvature of c. This function uses Newton's method to find the roots of κ.

Arguments

• c::AbstractParametricCurve: The curve to find the inflection points of.

Keyword Arguments

• steps=200: The number of t-values to use for seeding Newton's method. In particular, Newton's method is run for each initial value in LinRange(0, 1, steps).
• iters=50: The number of iterations to run Newton's method for.
• tol=1e-5: The tolerance to use for uniquetol. Also used for deciding whether a root is a valid root, i.e. if abs(κ(t)) > tol for a found root t, then t is not a valid root and is rejected.

is_curve_bounded(c::AbstractParametricCurve) -> Bool

Returns true if c is not a PiecewiseLinear curve. This is equivalent to !is_piecewise_linear(c).

is_interpolating(c::AbstractParametricCurve) -> Bool

Returns true if c goes through all its control points, and false otherwise.

is_piecewise_linear(c::AbstractParametricCurve) -> Bool

Returns true if c is PiecewiseLinear, and false otherwise.

marked_total_variation(b::AbstractParametricCurve, t₁, t₂)

Returns the total variation of the curve b over the interval [t₁, t₂] using the orientation markers of b.

orientation_markers(c::AbstractParametricCurve; steps=200, iters=50, tol=1e-5) -> Vector{Float64}

Finds all orientation markers of the AbstractParametricCurve c. These are points t where any of the following conditions hold (not necessarily simultaneously), letting c(t) = (x(t), y(t)):

• x'(t) = 0
• y'(t) = 0
• κ(t; x) = 0, where κ(t; x) is the curvature of the component function x(t)
• κ(t; y) = 0, where κ(t; y) is the curvature of the component function y(t)
• κ(t) = 0, where κ is the curvature of c(t)

Note that the third and fourth conditions give all the inflection points of the component functions, and similarly for the fifth condition.

See also horizontal_turning_points, vertical_turning_points, horizontal_inflection_points, vertical_inflection_points, and inflection_points.

Arguments

• c::AbstractParametricCurve: The AbstractParametricCurve.

Keyword Arguments

• steps=200: The number of equally spaced points to use for initialising Newton's method.
• iters=50: How many iterations to use for Newton's method.
• tol=1e-5: The tolerance used for determining if two t-values are the same.

Output

• markers::Vector{Float64}: The t-values of the orientation markers of b. The returned vector is sorted, and also includes the endpoints 0 and 1; any t-values outside of [0, 1] are discarded, and multiplicity of any t is not considered (so the t-values in the returned vector are unique). These values can be used to split the curve into monotone pieces, meaning the orientation is monotone. These markers also guarantee that, over any monotone piece, the orientation changes by an angle of at most π/2.

point_position_relative_to_curve(e::AbstractParametricCurve, p) -> Certificate

Returns the position of the point p relative to the curve c. This function returns a [Certificate]:

• Left: p is to the left of c.
• Right: p is to the right of c.
• On: p is on c.

point_position_relative_to_curve(L::LineSegment, p) -> Certificate

Returns the position of p relative to L, returning a Certificate:

• Left: p is to the left of L.
• Right: p is to the right of L.
• On: p is on L.

See also point_position_relative_to_line.

process_roots_and_residuals!(roots, residuals, tol) -> Vector{Float64}

Processes the roots and residuals of a root-finding algorithm. This function removes all NaN values from roots and residuals, sorts the roots in ascending order, and removes all roots with residuals greater than tol. The returned vector is the vector of roots with duplicates (i.e. roots that are within tol of each other) removed.

protect_against_bad_division!(roots, residuals, val, i) -> Bool

Protects against bad division in root-finding algorithms. This function checks if val is close to 0 or if roots[i] is outside of [0, 1]. If either of these conditions are true, then roots[i] and residuals[i] are set to NaN and true is returned. Otherwise, false is returned.

vertical_inflection_points(c::AbstractParametricCurve; steps=200, iters = 50, tol = 1e-5) -> Vector{Float64}

Returns points t such that y''(t) = 0 and 0 ≤ t ≤ 1, where y'' is the second derivative of the y-coordinate of c. This function uses Newton's method to find the roots of y''. Note that these are only technically inflection points if y'''(t) ≠ 0 at these points, but this is not checked.

Arguments

• c::AbstractParametricCurve: The curve to find the vertical inflection points of.

Keyword Arguments

• steps=200: The number of t-values to use for seeding Newton's method. In particular, Newton's method is run for each initial value in LinRange(0, 1, steps).
• iters=50: The number of iterations to run Newton's method for.
• tol=1e-5: The tolerance to use for uniquetol. Also used for deciding whether a root is a valid root, i.e. if abs(y''(t)) > tol for a found root t, then t is not a valid root and is rejected.

Output

• t: All inflection points, given in sorted order.

vertical_turning_points(c::AbstractParametricCurve; steps=200, iters = 50, tol = 1e-5) -> Vector{Float64}

Returns points t such that y'(t) = 0 and 0 ≤ t ≤ 1, where y' is the derivative of the y-coordinate of c. This function uses Newton's method to find the roots of y'.

Arguments

• c::AbstractParametricCurve: The curve to find the vertical turning points of.

Keyword Arguments

• steps=200: The number of t-values to use for seeding Newton's method. In particular, Newton's method is run for each initial value in LinRange(0, 1, steps).
• iters=50: The number of iterations to run Newton's method for.
• tol=1e-5: The tolerance to use for uniquetol. Also used for deciding whether a root is a valid root, i.e. if abs(y'(t)) > tol for a found root t, then t is not a valid root and is rejected.

Output

• t: All turning points, given in sorted order.

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.

add_point!(c::RepresentativeCoordinates, p)

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

compute_centroid!(c::RepresentativeCoordinates, points)

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

delete_point!(c::RepresentativeCoordinates, p)

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

getn(c::RepresentativeCoordinates) -> Integer

Returns the number of points represented by c.

getx(c::RepresentativeCoordinates) -> Number

Returns the x-coordinate of c.

gety(c::RepresentativeCoordinates) -> Number

Returns the y-coordinate of c.

reset!(c::RepresentativeCoordinates)

Resets the coordinates of c to zero.

update_centroid_after_addition!(tri::Triangulation, curve_index, p)

Updates the centroid of the curve_indexth curve in tri after the addition of the point p.

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.

getx(c::Cell) -> Number

Returns the x-coordinate of c.

gety(c::Cell) -> Number

Returns the y-coordinate of c.

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

isempty(queue::CellQueue) -> Bool

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

get_next_cell!(queue::CellQueue)

Returns the next cell in the queue.

insert_cell!(queue::CellQueue, cell::Cell)

Inserts a cell into the queue.

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)

get_points(convex_hull::ConvexHull) -> Points

Returns the underlying point set of convex_hull.

get_vertices(convex_hull::ConvexHull) -> Vector{Vertices}

Returns the vertices of convex_hull. These are given in counter-clockwise order, and are defined so that the first and last vertices and equal.

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; kwargs...) -> Triangulation

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

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.

edge_type(tri::Triangulation) -> DataType

Returns the type used for representing individual edges in tri.

edges_type(tri::Triangulation) -> DataType

Returns the type used for representing collections of edges in tri.

get_adjacent(tri::Triangulation) -> Adjacent

Returns the adjacency map of the triangulation. This is a map from each edge (u, v) to a vertex w such that (u, v, w) is a positively oriented triangle in tri.

See also Adjacent.

get_adjacent2vertex(tri::Triangulation) -> Adjacent2Vertex

Returns the Adjacent2Vertex map of the triangulation tri. This is a map from a vertex w to a set of all edges (u, v) such that (u, v, w) is a positively oriented triangle in tri.

get_all_segments(tri::Triangulation) -> Edges

Return all segments of the triangulation. This includes interior segments and boundary segments. Segments are edges that are forced to be in the triangulation.

get_boundary_curves(tri::Triangulation) -> NTuple{N, Function}

Returns the functions defining the boundaries of tri. If !is_curve_bounded(tri), then this returns an empty Tuple. Otherwise, this returns a Tuple of functions, one for each section of the boundary, where the ith element of the Tuple corresponds to the ith section of the boundary, which corresponds to the ghost vertex -i. For curves that are defined by boundary nodes rather than by a function, the function is PiecewiseLinear. For the other functions, these are all defined by t -> NTuple{2, Number}, where t ∈ [0, 1] and the NTuple{2, Number} is the coordinate on the curve at that t.

get_boundary_edge_map(tri::Triangulation) -> Dict

Returns the boundary edge map of the triangulation tri. This is a Dict that maps a boundary edge (u, v) to its position in get_boundary_nodes(tri). In particular, the returned value is a Tuple (position, index) so that boundary_nodes = get_boundary_nodes(tri, position) are the boundary nodes associated with the section that (u, v) resides on, and u = get_boundary_nodes(boundary_nodes, index) and v = get_boundary_nodes(boundary_nodes, index + 1).

See also construct_boundary_edge_map.

get_boundary_enricher(tri::Triangulation) -> BoundaryEnricher

Returns the BoundaryEnricher of tri. If the domain is not curve-bounded, this is nothing.

get_boundary_nodes(tri::Triangulation) -> BoundaryNodes

Return the boundary nodes of the triangulation. This is only for triangulations with a constrained boundary. If the triangulation has no constrained boundary, then the boundary is instead given by its convex hull and this function returns an empty vector. See get_convex_hull.

get_cache(tri::Triangulation) -> TriangulationCache

Returns the cache of tri. This is a TriangulationCache used as a cache for add_segment! which requires a separate Triangulation structure for use.

get_convex_hull(tri::Triangulation) -> ConvexHull

Returns the convex hull of the points in tri. This is given as a ConvexHull object, where the vertices are sorted counter-clockwise and defined so that the first and last vertices are equal.

get_exterior_curve_indices(tri::Triangulation) -> KeySet{Integer}

Returns the set of all curve indices that correspond to exterior curves of tri.

get_ghost_vertex_map(tri::Triangulation) -> Dict

Returns the ghost vertex map of the triangulation tri. This is a Dict that maps ghost vertices to their associated section in boundary_nodes. There are three cases; below, I is integer_type(tri):

• has_multiple_curves(tri)

Returns dict::Dict{I, NTuple{2, I}}, mapping ghost vertices i to Tuples (m, n) so that get_boundary_nodes(tri, 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(tri)

Returns dict::Dict{I, I}, mapping ghost vertices i to n so that get_boundary_nodes(tri, 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 get_boundary_nodes(tri), where A = typeof(get_boundary_nodes(tri)).

See also construct_ghost_vertex_map.

get_ghost_vertex_ranges(tri::Triangulation) -> Dict

Returns the ghost vertex ranges map of the triangulation tri. This is a Dict that maps ghost vertices i to the range of all other ghost vertices associated with the curve that i is associated with.

See also construct_ghost_vertex_ranges.

get_graph(tri::Triangulation) -> Graph

Returns the Graph of the triangulation tri. This is an undirected graph.

get_interior_segments(tri::Triangulation) -> Edges

Return the interior segments of the triangulation. These are segments that are forced to be in the triangulation - they are not the same as edges.

get_points(tri::Triangulation) -> Points

Return the points of the triangulation. Note that this may include points not yet in tri.

get_polygon_hierarchy(tri::Triangulation) -> PolygonHierarchy

Returns the PolygonHierarchy of the boundary of tri. This defines the hierarchy of the boundary curves, giving information about which curves are contained in which other curves.

get_representative_point_list(tri::Triangulation) -> Dict

Returns the Dict of RepresentativeCoordinates of tri, mapping curve indices i to the representative point for that curve. These representative points are how we interpret ghost triangles relative to that curve.

get_triangles(tri::Triangulation) -> Triangles

Return the triangles of the triangulation. These triangles are all given in counter-clockwise order, and may include ghost triangles.

get_weights(tri::Triangulation) -> Weights

Return the weights of the triangulation. These are the weights of the vertices of the triangulation.

integer_type(tri::Triangulation) -> DataType

Returns the type used for representing vertices in tri.

number_type(tri::Triangulation) -> DataType

Returns the type used for representing individual coordinates in tri.

triangle_type(tri::Triangulation) -> DataType

Returns the type used for representing individual triangles in tri.

triangle_type(tri::Triangulation) -> DataType

Returns the type used for representing collections of triangles in tri.

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.

empty!(cache::TriangulationCache)

Empties the cache by emptying the triangulation stored in it.

empty_unconstrained_triangulation!(tri::Triangulation)

Empties the triangulation tri by emptying its fields. Only works for unconstrained triangulaions.

get_fan_triangles(cache::TriangulationCache) -> Triangles

Returns the triangles in a fan stored in cache.

get_interior_segments_on_hull(cache::TriangulationCache) -> Set{Edge}

Returns the interior segments on the convex hull of the triangulation stored in cache.

get_marked_vertices(cache::TriangulationCache) -> Vector{Vertex}

Returns the marked vertices stored in cache.

get_surrounding_polygon(cache::TriangulationCache) -> Vector{Vertex}

Returns the polygon surrounding the triangulation stored in cache.

get_triangulation(cache::TriangulationCache) -> Triangulation

Returns the Triangulation stored in cache.

get_triangulation_2(cache::TriangulationCache) -> Triangulation

Returns the second Triangulation stored in cache.

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.

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.

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

Appends the members of new_complex onto the members of complex.

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

Pushes member onto the members of complex.

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

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

construct_curve_index_map!(enricher::BoundaryEnricher)

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

construct_parent_map!(enricher::BoundaryEnricher)

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

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.

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

Deletes the edge (i, j) in boundary_enricher.

each_boundary_edge(enricher::BoundaryEnricher) -> KeySet

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

eval_boundary_curve(enricher::BoundaryEnricher, curve_index, t) -> NTuple{2,Float64}

Returns the curve_indexth boundary curve at t.

get_apex(complex::SmallAngleComplex{I}) where {I} -> I

Returns the apex of complex.

get_boundary_curve(boundary_enricher::BoundaryEnricher, curve_index) -> AbstractParametricCurve

Returns the curve_indexth curve from the boundary curves in boundary_enricher.

get_boundary_curves(boundary_enricher::BoundaryEnricher{P,B,C}) -> C

Returns the boundary curves associated with boundary_enricher.

get_boundary_edge_map(boundary_enricher::BoundaryEnricher, i, j)

Returns the value from the key (i, j) in the boundary edge map of boundary_enricher. The returned value is a Tuple (position, index) so that boundary_nodes = get_boundary_nodes(get_boundary_nodes(boundary_enricher), position) are the boundary nodes associated with the section that (i, j) resides on, and i = get_boundary_nodes(boundary_nodes, index) and j = get_boundary_nodes(boundary_nodes, index + 1).

get_boundary_edge_map(boundary_enricher::BoundaryEnricher{P,B,C,I,BM}) -> BM

Returns the boundary edge map associated with boundary_enricher.

get_boundary_nodes(boundary_enricher::BoundaryEnricher{P,B}) -> B

Returns the boundary nodes associated with boundary_enricher.

get_circle_intersection(enricher::BoundaryEnricher, curve_index, t₁, t₂, r) -> (Float64, NTuple{2,Float64})

Finds the intersection of the curve_indexth curve with the circle centered at the curve evaluated at t₁ with radius r. The argument t₂ defines the end of the subcurve to consider. The returned tuple is (t, p) where t is the parameter value of the intersection and p is the point of intersection.

get_curve_index_map(boundary_enricher::BoundaryEnricher{P,B,C,I}) -> Dict{I,I}

Returns the curve index map associated with boundary_enricher.

get_equidistant_split(enricher::BoundaryEnricher, curve_index, t₁, t₂) -> Float64

Returns the equidistant split of the curve_indexth curve between t₁ and t₂.

get_equivariation_split(enricher::BoundaryEnricher, curve_index, t₁, t₂) -> Float64, Float64

Returns the equivariation split of the curve_indexth curve between t₁ and t₂. Also returns the total variation of the two pieces.

get_inverse(enricher::BoundaryEnricher, curve_index, q) -> Float64

Returns the inverse of the curve_indexth curve at q.

get_members(complex::SmallAngleComplex{I}) where {I} -> Vector{SmallAngleComplexMember{I}}

Returns the members of complex.

get_minimum_edge_length(complex::SmallAngleComplex, points) -> Float64

Returns the minimum edge length in complex with respect to points.

get_next_edge(member::SmallAngleComplexMember{I}) where {I} -> I

Returns the next edge of member.

get_parent(boundary_enricher::BoundaryEnricher{P,B,C,I}, i::I, j::I) -> I

Returns the parent of the edge (i, j) in boundary_enricher. If the edge is not in the parent map, then 0 is returned.

get_parent_curve(member::SmallAngleComplexMember{I}) where {I} -> I

Returns the parent curve of member.

get_parent_map(boundary_enricher::BoundaryEnricher{P,B,C,I}) -> Dict{NTuple{2,I},I}

Returns the parent map associated with boundary_enricher.

get_points(boundary_enricher::BoundaryEnricher{P}) -> P

Returns the point set associated with boundary_enricher.

get_polygon_hierarchy(boundary_enricher::BoundaryEnricher{P,B,C,I}) -> PolygonHierarchy{I}

Returns the polygon hierarchy associated with boundary_enricher.

get_queue(boundary_enricher::BoundaryEnricher{P,B,C,I}) -> Queue{I}

Returns the queue associated with boundary_enricher.

get_segments(boundary_enricher::BoundaryEnricher{P,B,C,I,BM,S}) -> S

Returns the segments associated with boundary_enricher.

get_small_angle_complexes(points, boundary_nodes, boundary_curves, segments=nothing; IntegerType=Int) -> Dict{IntegerType,Vector{SmallAngleComplex{IntegerType}}}

Returns a map from an apex vertex to a list of all curves that define a small angle complex associated with that apex vertex.

get_small_angle_complex(boundary_enricher::BoundaryEnricher, apex) -> Vector{SmallAngleComplex}

Returns the small angle complexes in boundary_enricher associated with apex.

get_small_angle_complexes(boundary_enricher::BoundaryEnricher{P,B,C,I}) -> Dict{I,Vector{SmallAngleComplex{I}}}

Returns the small angle complexes associated with boundary_enricher.

get_spatial_tree(boundary_enricher::BoundaryEnricher{P,B,C,I}) -> RTree

Returns the spatial tree associated with boundary_enricher.

has_segments(boundary_enricher::BoundaryEnricher -> Bool

Returns true if boundary_enricher has interior segments, and false otherwise.

is_piecewise_linear(enricher::BoundaryEnricher, curve_index) -> Bool

Returns true if the curve_indexth curve in enricher is piecewise linear, and false otherwise.

is_segment(enricher::BoundaryEnricher, i, j) -> Bool

Returns true if (i, j) or (j, i) is an interior segment of enricher, and false otherwise.

is_small_angle_complex_apex(boundary_enricher::BoundaryEnricher, apex) -> Bool

Returns true if apex is the apex of a small angle complex in boundary_enricher, and false otherwise.

is_small_angle_complex_member(enricher::BoundaryEnricher, i, j) -> Bool, I, IntegerType, IntegerType

Returns true if the edge (i, j) is a member of a small angle complex in enricher, and false otherwise.

Outputs

• flag: true if the edge is a member of a small angle complex, and false otherwise.
• apex: If the edge is a member of a small angle complex, then apex is the apex of the complex. Otherwise, apex is 0.
• complex_id: If the edge is a member of a small angle complex, then complex_id is the index of the complex in the list of complexes associated with apex. Otherwise, complex_id is 0.
• member_id: If the edge is a member of a small angle complex, then member_id is the index of the member in the list of members associated with complex_id. Otherwise, member_id is 0.

map_curve_index(boundary_enricher::BoundaryEnricher, curve_index) -> Integer

Returns the curve index in boundary_enricher associated with curve_index.

partition_members(complexes::Vector{SmallAngleComplex{I}}, points) where {I} -> Vector{SmallAngleComplex{I}}

Partitions the members of each complex in complexes into a new set of complexes. The complexes in complexes are assumed to be sorted in a counter-clockwise order around the apex of each complex. The partitioning is done so that the original set of members are now correctly split into their own complexes, since the original complexes might not have formed a properly contiguous set of small angles.

point_position_relative_to_curve(enricher::BoundaryEnricher, curve_index, p) -> Certificate

Returns a Certificate which is

• Left: If p is to the left of the curve_indexth curve.
• Right: If p is to the right of the curve_indexth curve.
• On: If p is on the curve_indexth curve.

polygonise(points, boundary_nodes, boundary_curves; n=4096)

Fills out a set of points for a curve-bounded domain for use with PolygonHierarchy.

Arguments

• points: The point set.
• boundary_nodes: The boundary nodes.
• boundary_curves: The boundary curves.

Keyword Arguments

• n=4096: The number of points to use for filling in each boundary curves.

Output

• new_points: The points defining the filled out boundaries.
• new_boundary_nodes: The boundary nodes associated with new_points.

reorient_edge(enricher::BoundaryEnricher, i, j) -> NTuple{2,Integer}

Given an edge (i, j), reorients it so that it is correctly oriented with the boundary. If (i, j) is instead an interior segment rather than a boundary edge, then (i, j) is returned.

replace_next_edge!(enricher::BoundaryEnricher, apex, complex_id, member_id, next_edge)

Replaces the next edge of the member_idth member of the complex_idth complex associated with apex with next_edge.

replace_next_edge!(complex::SmallAngleComplex, member_id, next_edge)

Replaces the next edge of the member_idth member of complex with next_edge.

See also replace_next_edge.

replace_next_edge(member::SmallAngleComplexMember{I}, next_edge) where {I} -> SmallAngleComplexMember{I}

Returns a new SmallAngleComplexMember with the same parent curve as member but with next_edge as the next edge.

set_parent!(boundary_enricher::BoundaryEnricher, i, j, k)

Sets the parent of the edge (i, j) in boundary_enricher to k.

sort_members!(complex::SmallAngleComplex, points)

Sorts the members of complex in a counter-clockwise order around the apex of complex.

split_boundary_edge!(enricher::BoundaryEnricher, i, j, r, update_boundary_nodes = Val(true))

Updates the fields of enricher after splitting a boundary edge (i, j) at the rth vertex. The update_boundary_nodes argument can be used to avoid inserting an additional boundary node when boundary_nodes was already updated somewhere else (e.g., we need this for mesh refinement which already updates the boundary_nodes which is aliased with the same field in the enricher).

split_edge!(enricher::BoundaryEnricher, i, j, r, update_boundary_nodes = Val(true), update_segments = Val(true), is_interior = is_segment(enricher, i, j))

Updates the fields of enricher after splitting an edge (i, j) at the rth vertex. The update_boundary_nodes argument can be used to avoid inserting an additional boundary node when boundary_nodes was already updated somewhere else (e.g., we need this for mesh refinement which already updates the boundary_nodes which is aliased with the same field in the enricher). The same point goes for update_segments which can be used to avoid inserting an additional segment when segments was already updated somewhere else. The is_interior argument can be used to specify whether the edge is an interior segment or a boundary edge.

See also split_boundary_edge! and split_interior_segment!.

split_interior_segment!(enricher::BoundaryEnricher, i, j, r, update_segments = Val(true))

Updates the fields of enricher after splitting an interior segment (i, j) at the rth vertex. The update_segments argument can be used to avoid inserting an additional segment when segments was already updated somewhere else (e.g., we need this for mesh refinement which already updates the interior_segments which is aliased with the segments field in the enricher).

update_parent_map!(boundary_enricher::BoundaryEnricher, i, j, k)

Replaces the edge (i, j) in boundary_enricher with the edges (i, k) and (k, j) in the parent map.

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.

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.

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_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(tri::Triangulation) -> Points

Returns an iterator over all points in tri.

each_point_index(tri::Triangulation) -> Indices

Returns an iterator over all point indices in tri.

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.

each_triangle(tri::Triangulation) -> Triangles

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

See also each_solid_triangle and each_ghost_triangle.

" each_vertex(tri::Triangulation) -> Set{Vertex}

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

See also each_solid_vertex and each_ghost_vertex.

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.

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

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

add_index!(history::PointLocationHistory, i)

Adds the index i to the collinear_point_indices field of history.

add_left_vertex!(history::PointLocationHistory, i)

Adds the vertex i to the left_vertices field of history.

add_right_vertex!(history::PointLocationHistory, j)

Adds the vertex j to the right_vertices field of history.

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

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

num_edges(history::PointLocationHistory) -> Integer

Returns the number of edges in history.collinear_segments.

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.

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

make_shortest_edge_first(p, q, r, idx) -> (NTuple{2, Number}, NTuple{2, Number}, NTuple{2, Number})

Given a triangle (p, q, r), rotate it (preserving orientation) so that the shortest edge is first. The argument idx gives the index of the shortest edge, where idx == 1 means (p, q), idx == 2 means (q, r), and idx == 3 means (r, p).

min_med_max(a, b, c) -> (Number, Number, Number)

Returns the arguments in sorted order.