Data Structures
Here we list the internal data structures used throughout the package, along with functions related to working with the respective data structures.
MaxPriorityQueue
The MaxPriorityQueue
is our implementation of a maximum priority queue; see, for example, the wikipedia page. The MaxPriorityQueue
works similarly to the priority queue in DataStructures.jl. This struct is used for determining which triangles and edges to prioritise during mesh refinement, as well as which cells to prioritise during the quadtree construction for the pole of inaccessibility.
DelaunayTriangulation.MaxPriorityQueue
— TypeMaxPriorityQueue{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.
Base.first
— Methodfirst(queue::MaxPriorityQueue) -> Pair{K, V}
Returns the element with the highest priority in a queue
, without removing it from queue
.
Base.getindex
— Methodgetindex(queue::MaxPriorityQueue, key)
queue[key]
Returns the priority of the element with key key
in a queue
.
Base.haskey
— Methodhaskey(queue::MaxPriorityQueue, key) -> Bool
Returns true
if the queue
has an element with key key
.
Base.isempty
— Methodisempty(queue::MaxPriorityQueue) -> Bool
Returns true
if the queue
is empty.
Base.length
— MethodBase.length(queue::MaxPriorityQueue) -> Int
Returns the number of elements in queue
.
Base.popfirst!
— Methodpopfirst!(queue::MaxPriorityQueue{K, V}) where {K, V} -> Pair{K, V}
Removes and returns the element with the highest priority from the queue
.
Base.push!
— Methodpush!(queue::MaxPriorityQueue, pair)
Adds the key-value pair pair
to the queue
.
Base.setindex!
— Methodsetindex!(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.
DelaunayTriangulation.fix_down!
— Methodfix_down!(queue::MaxPriorityQueue, k)
Fixes the queue
after decreasing the value of one of its elements by percolating downwards.
DelaunayTriangulation.fix_up!
— Methodfix_up!(queue::MaxPriorityQueue, k)
Fixes the queue
after increasing the value of one of its elements by percolating upwards.
DelaunayTriangulation.has_children
— Methodhas_children(queue::MaxPriorityQueue, k) -> Bool
Returns true
if the element at index k
has children in the queue
.
DelaunayTriangulation.hchildren
— Methodhchildren(k) -> Tuple{Int, Int}
Returns the indices of the children of the element at index k
in a heap.
DelaunayTriangulation.hleft
— Methodhleft(k) -> Int
Returns the index of the left child of the element at index k
in a heap.
DelaunayTriangulation.hparent
— Methodhparent(k) -> Int
Returns the index of the parent of the element at index k
in a heap.
DelaunayTriangulation.hright
— Methodhright(k) -> Int
Returns the index of the right child of the element at index k
in a heap.
DelaunayTriangulation.is_root
— Methodis_root(k) -> Bool
Returns true
if the element at index k
is the root of a heap.
DelaunayTriangulation.swap!
— Methodswap!(queue::MaxPriorityQueue, i, j)
Swaps the elements at indices i
and j
in queue
.
Queue
The Queue
is our implementation of a basic FIFO queue; see, for example, the wikipedia page. The implementation of a Queue
in this package is very simple - it is just a vector. A block-based approach could also be implemented in the future, it just hasn't. The idea here is to avoid a dependency on DataStructures.jl. The Queue
is used in a variety of places, such as during boundary enrichment in enrich_boundary!
to determine which edges to process next.
DelaunayTriangulation.Queue
— TypeQueue{T}
Struct for a first-in first-out queue.
Under the hood, Queue
simply uses a Vector
. This may not be as optimised compared to other implementations, e.g. DataStructure.jl's block-based approach with a Dequeue
.
Base.eltype
— Methodeltype(queue::Queue{T}) -> Type{T}
Returns the type of elements stored in q
.
Base.isempty
— Methodisempty(queue::Queue) -> Bool
Returns true
if the queue
is empty, false
otherwise.
Base.length
— Methodlength(queue::Queue) -> Int
Returns the number of elements in the queue
.
Base.popfirst!
— Methodpopfirst!(queue::Queue)
Removes the element from the front of the queue
and returns it.
Base.push!
— Methodpush!(queue::Queue, item)
Adds item
to the end of the queue
.
DelaunayTriangulation.enqueue_all!
— Methodenqueue_all!(queue::Queue, data)
Adds all data
to the end of the queue
.
BalancedBST
The BalancedBST
is our implementation of a balanced binary search tree; see, for example, these notes. The BalancedBST
is not currently used anywhere. Originally, it was intended for use with the Bentley-Ottman algorithm, but the complete algorithm is yet to be implemented; this algorithm was to be implemented to allow for users to provide intersecting segments that, through the algorithm, could be automatically split for the user. The BalancedBST
implementation is fully functional for this purpose, the work in getting the actual algorithm up and going just has to be done.
DelaunayTriangulation.BalancedBST
— Typemutable 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.
Nodes with duplicate keys are not supported. If a duplicate key is inserted, the tree will not be modified.
DelaunayTriangulation.BalancedBSTNode
— Typemutable 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
.
Base.delete!
— Methoddelete!(tree::BalancedBST{K}, key::K) -> BalancedBST{K}
Deletes the node in tree
with key key
if it exists. Returns tree
.
Base.findfirst
— Methodfindfirst(tree::BalancedBST{K}, key::K) -> Union{Nothing,BalancedBSTNode{K}}
Returns the node in tree
with key key
. If no such node exists, returns nothing
.
Base.haskey
— Methodhaskey(tree::BalancedBST{K}, key::K) -> Bool
Returns true
if tree
has a node with key key
, false
otherwise.
Base.push!
— Methodpush!(tree::BalancedBST{K}, key::K)
Inserts key
into tree
if it is not already present.
DelaunayTriangulation._minimum
— Method_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
.
DelaunayTriangulation.compute_balance
— Methodcompute_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.
DelaunayTriangulation.compute_count
— Methodcompute_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
.
DelaunayTriangulation.compute_height
— Methodcompute_height(node::Union{Nothing,BalancedBSTNode{K}}) -> Int8
Computes the height of the subtree rooted at node
.
DelaunayTriangulation.delete_node!
— Methoddelete_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.
DelaunayTriangulation.get_count
— Methodget_count(node::Union{Nothing, BalancedBSTNode}) -> Int32
Returns the count of node
. If the node
is nothing
, returns 0
.
DelaunayTriangulation.get_count
— Methodget_count(tree::BalancedBST{K}) -> Int32
DelaunayTriangulation.get_height
— Methodget_height(node::Union{Nothing, BalancedBSTNode}) -> Int8
Returns the height of node
. If the node
is nothing
, returns 0
.
DelaunayTriangulation.get_key
— Methodget_key(node::BalancedBSTNode{K}) -> K
Returns the key associated with node
.
DelaunayTriangulation.get_left
— Methodget_left(node::BalancedBSTNode) -> Union{Nothing, BalancedBSTNode}
Returns the left child of node
. If the node
is nothing
, returns nothing
.
DelaunayTriangulation.get_parent
— Methodget_parent(node::BalancedBSTNode) -> Union{Nothing, BalancedBSTNode}
Returns the parent of node
. If the node
is nothing
, returns nothing
.
DelaunayTriangulation.get_right
— Methodget_right(node::BalancedBSTNode) -> Union{Nothing, BalancedBSTNode}
Returns the right child of node
. If the node
is nothing
, returns nothing
.
DelaunayTriangulation.get_root
— Methodget_root(tree::BalancedBST{K}) -> Union{Nothing,BalancedBSTNode{K}}
Returns the root of tree
. If tree
is empty, returns nothing
.
DelaunayTriangulation.has_left
— Methodhas_left(node::BalancedBSTNode) -> Bool
Returns true
if node
has a left child, false
otherwise.
DelaunayTriangulation.has_parent
— Methodhas_parent(node::BalancedBSTNode) -> Bool
Returns true
if node
has a parent, false
otherwise.
DelaunayTriangulation.has_right
— Methodhas_right(node::BalancedBSTNode) -> Bool
Returns true
if node
has a right child, false
otherwise.
DelaunayTriangulation.has_root
— Methodhas_root(tree::BalancedBST{K}) -> Bool
Returns true
if tree
has a root, false
otherwise.
DelaunayTriangulation.inorder
— Methodinorder(tree::BalancedBST{K}) -> Vector{K}
Returns the inorder traversal of tree
.
DelaunayTriangulation.insert_node!
— Methodinsert_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.
DelaunayTriangulation.rotate_left!
— Methodrotate_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.
DelaunayTriangulation.rotate_right!
— Methodrotate_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.
DelaunayTriangulation.set_count!
— Methodset_count!(tree::BalancedBST{K}, count::Int32)
Sets the count of tree
to count
.
DelaunayTriangulation.set_count!
— Methodset_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
.
DelaunayTriangulation.set_height!
— Methodset_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
.
DelaunayTriangulation.set_key!
— Methodset_key!(node::BalancedBSTNode{K}, key::K)
Sets the key associated with node
to key
.
DelaunayTriangulation.set_left!
— Methodset_left!(node::BalancedBSTNode, left::Union{Nothing, BalancedBSTNode})
Sets the left child of node
to left
.
DelaunayTriangulation.set_parent!
— Methodset_parent!(node::BalancedBSTNode, parent::Union{Nothing, BalancedBSTNode})
Sets the parent of node
to parent
.
DelaunayTriangulation.set_right!
— Methodset_right!(node::BalancedBSTNode, right::Union{Nothing, BalancedBSTNode})
Sets the right child of node
to right
.
DelaunayTriangulation.set_root!
— Methodset_root!(tree::BalancedBST{K}, root::Union{Nothing,BalancedBSTNode{K}})
Sets the root of tree
to root
.
RTree
The RTree
is our implementation of a simple RTree
data structure, following heavily the original code in SpatialIndexing.jl. This tree is needed for triangulating curve-bounded domains. In particular, since the enrichment phase of triangulating a curve-bounded domain has no triangulation data structure that can be used for finding intersections between an edge's diametral circle and another vertex, the RTree
is used to find these intersections.
DelaunayTriangulation.RTree
— Typemutable 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 indetached_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 theTuple
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.
DelaunayTriangulation.InvalidBoundingBox
— ConstantInvalidBoundingBox
A constant for representing an invalid rectangle, i.e. a rectangle with NaN
endpoints.
DelaunayTriangulation.InvalidBoundingInterval
— ConstantInvalidBoundingInterval
A constant for representing an invalid intervaBoundingInterval
, i.e. an interval with NaN
endpoints.
DelaunayTriangulation.AbstractBoundingShape
— Typeabstract type AbstractBoundingShape
Abstract type for representing a bounding box.
DelaunayTriangulation.AbstractNode
— Typeabstract type AbstractNode end
Abstract type for representing a node in an R-tree.
DelaunayTriangulation.BoundaryRTree
— TypeBoundaryRTree{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)
DelaunayTriangulation.BoundingBox
— TypeBoundingBox <: 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])
DelaunayTriangulation.BoundingInterval
— TypeBoundingInterval <: AbstractBoundingShape
Type for representing a bounding interval [a, b]
.
Fields
a::Float64
: The left endpoint.b::Float64
: The right endpoint.
DelaunayTriangulation.Branch
— Typemutable 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)
DelaunayTriangulation.BranchCache
— TypeBranchCache
Type for representing a cache of branch nodes.
DelaunayTriangulation.DiametralBoundingBox
— TypeDiametralBoundingBox
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.
DelaunayTriangulation.Leaf
— Typemutable struct Leaf <: AbstractNode
Type for representing a leaf node in an R-tree.
Technically, this type should be referred to by Leaf{Branch}
. Due to a lack of support for mutually recursive types or forward declarations, we have a parametric type in this struct's definition since Branch is not yet defined. In particular, Leaf
is not a concrete type, whereas Leaf{Branch}
is.
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[])
DelaunayTriangulation.LeafCache
— TypeLeafCache
Type for representing a cache of leaf nodes.
DelaunayTriangulation.NodeCache
— TypeNodeCache{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)
DelaunayTriangulation.RTreeIntersectionCache
— TypeRTreeIntersectionCache
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
: ABitVector
cache for keeping track of which indices innode_indices
need to be tested for intersections.
DelaunayTriangulation.RTreeIntersectionIterator
— TypeRTreeIntersectionIterator
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.
DelaunayTriangulation.RTreeIntersectionIteratorState
— TypeRTreeIntersectionIteratorState
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
: ABitVector
cache for keeping track of which indices innode_indices
need to be tested for intersections.
DelaunayTriangulation.TwigCache
— TypeTwigCache
Type for representing a cache of twig nodes, i.e. branch nodes at level 2.
Base.:∩
— Methodintersect(r1::BoundingBox, r2::BoundingBox) -> BoundingBox
r1::BoundingBox ∩ r2::BoundingBox -> BoundingBox
Returns the intersection of r1
and r2
. If the intersection is empty, returns InvalidBoundingBox
.
Base.:∩
— Methodintersect(I::BoundingInterval, J::BoundingInterval) -> BoundingInterval
I::BoundingInterval ∩ J::BoundingInterval -> BoundingInterval
Returns the intersection of I
and J
. If the intersection is empty, returns InvalidBoundingInterval
.
Base.:∪
— Methodunion(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
.
Base.:∪
— Methodunion(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
.
Base.delete!
— Methoddelete!(tree::BoundaryRTree, i, j)
Deletes the bounding box of the diametral circle of the edge between i
and j
in tree
.
Base.in
— Methodin(r1::BoundingBox, r2::BoundingBox) -> Bool
r1::BoundingBox ∈ r2::BoundingBox -> Bool
Tests whether r1
is in r2
.
Base.in
— Methodin(I::BoundingInterval, J::BoundingInterval) -> Bool
I::BoundingInterval ∈ J::BoundingInterval -> Bool
Tests whether the interval I
is in the interval J
.
Base.in
— Methodin(a::Float64, I::BoundingInterval) -> Bool
a::Float64 ∈ I::BoundingInterval -> Bool
Tests whether a
is in I
.
Base.in
— Methodin(p::NTuple{2,<:Number}, r::BoundingBox) -> Bool
p::NTuple{2,<:Number} ∈ r::BoundingBox -> Bool
Tests whether p
is in r
.
Base.insert!
— Methodinsert!(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.
Base.isempty
— Methodisempty(r::BoundingBox) -> Bool
Returns true
if r
is empty, i.e. if r.x
or r.y
is empty.
Base.isempty
— Methodisempty(I::BoundingInterval) -> Bool
Returns true
if I
is empty, i.e. if I.a
or I.b
is NaN
or if length(I) < 0
.
Base.isempty
— Methodisempty(cache::NodeCache) -> Bool
Returns true
if cache
is empty.
Base.length
— Methodlength(I::BoundingInterval) -> Float64
Returns the length of the interval I
.
Base.length
— Methodlength(cache::NodeCache) -> Int
Returns the number of nodes in cache
.
Base.pop!
— Methodpop!(cache::NodeCache) -> Node
Removes and returns the last node in cache
.
Base.push!
— Methodpush!(cache::NodeCache, node)
Base.setindex!
— Methodsetindex!(branch::Branch, child, i::Integer)
branch[i] = child
Sets the i
th child of branch
to be child
, also updating the parent of child
to be branch
.
DelaunayTriangulation.add_child!
— Methodadd_child!(node::AbstractNode, child)
Adds child
to node
, i.e. appends child
to the children of node
via push!
.
DelaunayTriangulation.bounding_box
— Methodbounding_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
.
DelaunayTriangulation.bounding_box
— Methodbounding_box(points) -> BoundingBox
Gets the bounding box for a set of points.
DelaunayTriangulation.bounding_box
— Methodbounding_box(tree::BoundaryRTree, i, j) -> DiametralBoundingBox
Returns the bounding box of the diametral circle of the edge between i
and j
in tree
.
DelaunayTriangulation.bounding_box
— Methodbounding_box(p::NTuple, q::NTuple, r::NTuple) -> BoundingBox
Returns the bounding box of the points p
, q
and r
.
DelaunayTriangulation.bounding_box
— Methodbounding_box(center, radius) -> BoundingBox
Returns the bounding box of the circle (center, radius)
.
DelaunayTriangulation.cache_node!
— Functioncache_node!(tree::RTree, node::AbstractNode)
Caches node
in into tree
's node caches.
DelaunayTriangulation.cache_node!
— Methodcache_node!(cache::NodeCache, node)
Caches node
in cache
if cache
is not full. Otherwise, does nothing.
DelaunayTriangulation.decrement_num_elements!
— Methoddecrement_num_elements!(tree::RTree)
Decrements the number of elements in tree
by 1.
DelaunayTriangulation.diametral_circle
— Methoddiametral_circle(p, q) -> (NTuple{2,Float64}, Float64)
Returns the circle with diameter pq
.
DelaunayTriangulation.expand
— Functionexpand(box::BoundingBox, perc=0.10) -> BoundingBox
Expands the bounding box box
by a factor perc
in each direction.
DelaunayTriangulation.find_position_in_parent
— Methodfind_position_in_parent(node::AbstractNode) -> Int
Returns the position of node
in its parent's children. If node
has no parent, returns 0
.
DelaunayTriangulation.get_area
— Methodget_area(r::BoundingBox) -> Float64
Returns the area of r
, i.e. hspan(r) * vspan(r)
.
DelaunayTriangulation.get_bl_corner
— Methodget_bl_corner(r::BoundingBox) -> NTuple{2,Float64}
Returns the bottom-left corner of r
.
DelaunayTriangulation.get_bounding_box
— Methodget_bounding_box(node::AbstractNode) -> BoundingBox
Returns the bounding box of node
.
DelaunayTriangulation.get_bounding_box
— Methodget_bounding_box(id_bounding_box::DiametralBoundingBox) -> BoundingBox
Returns the bounding box of id_bounding_box
.
DelaunayTriangulation.get_bounding_box
— Methodget_bounding_box(tree::RTree) -> BoundingBox
Returns the bounding box of tree
.
DelaunayTriangulation.get_branch_cache
— Methodget_branch_cache(tree::RTree) -> BranchCache
Returns the branch cache of tree
.
DelaunayTriangulation.get_child
— Methodget_child(node::AbstractNode, i::Integer) -> AbstractNode
Returns the i
th child of node
.
DelaunayTriangulation.get_child_type
— Methodget_child_type(node::AbstractNode) -> Union{Type{Leaf}, Type{Branch}}
Returns the type of the children of node
.
DelaunayTriangulation.get_children
— Methodget_children(node::AbstractNode) -> Vector
Returns the children of node
.
DelaunayTriangulation.get_detached_cache
— Methodget_detached_cache(tree::RTree) -> Vector{Union{Branch,Leaf{Branch}}}
Returns the detached cache of tree
.
DelaunayTriangulation.get_edge
— Methodget_edge(id_bounding_box::DiametralBoundingBox) -> NTuple{2,Int}
Returns the generator edge of id_bounding_box
.
DelaunayTriangulation.get_fill_factor
— Methodget_fill_factor(tree::RTree) -> Float64
Returns the fill factor of tree
.
DelaunayTriangulation.get_free_cache
— Methodget_free_cache(tree::RTree) -> BitVector
Returns the free cache of tree
.
DelaunayTriangulation.get_height
— Methodget_height(tree::RTree) -> Int
Returns the height of tree
.
DelaunayTriangulation.get_intersection_cache
— Methodget_intersection_cache(tree::RTree) -> NTuple{2,RTreeIntersectionCache}
Returns the intersection cache of tree
.
DelaunayTriangulation.get_intersections
— Methodget_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.
DelaunayTriangulation.get_intersections
— Methodget_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.
DelaunayTriangulation.get_intersections
— Methodget_intersections(tree::BoundaryRTree, i; cache_id=1) -> RTreeIntersectionIterator
Returns an RTreeIntersectionIterator
over the elements in tree
that intersect with the i
th vertex. cache_id
must be 1
or 2
, and determines what cache to use for the intersection query.
DelaunayTriangulation.get_intersections
— Methodget_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.
DelaunayTriangulation.get_leaf_cache
— Methodget_leaf_cache(tree::RTree) -> LeafCache
Returns the leaf cache of tree
.
DelaunayTriangulation.get_level
— Functionget_level(node::AbstractNode) -> Int
Returns the level of node
. If node
is a leaf, returns 1
.
DelaunayTriangulation.get_min_nodes
— Methodget_min_nodes(tree::RTree) -> Int
Returns the minimum number of nodes that a node in tree
can have.
DelaunayTriangulation.get_need_tests
— Methodget_need_tests(cache::RTreeIntersectionCache) -> BitVector
Returns the need_tests
cache of tree
.
DelaunayTriangulation.get_node_indices
— Methodget_node_indices(cache::RTreeIntersectionCache) -> Vector{Int}
Returns the node indices of cache
.
DelaunayTriangulation.get_parent
— Methodget_parent(node::AbstractNode) -> Union{Branch, Nothing}
Returns the parent of node
.
DelaunayTriangulation.get_root
— Methodget_root(tree::RTree) -> Union{Branch,Leaf{Branch}}
Returns the root of tree
.
DelaunayTriangulation.get_size_limit
— Methodget_size_limit(cache::NodeCache) -> Int
Returns the size limit of cache
.
DelaunayTriangulation.get_size_limit
— Methodget_size_limit(tree::RTree) -> Int
Returns the size limit of tree
.
DelaunayTriangulation.get_state
— Methodget_state(state::RTreeIntersectionIteratorState) -> DiametralBoundingBox
Returns the current element in state
.
DelaunayTriangulation.get_tr_corner
— Methodget_tr_corner(r::BoundingBox) -> NTuple{2,Float64}
Returns the top-right corner of r
.
DelaunayTriangulation.get_twig_cache
— Methodget_twig_cache(tree::RTree) -> TwigCache
Returns the twig cache of tree
.
DelaunayTriangulation.has_children
— Methodhas_children(node::AbstractNode) -> Bool
Returns true
if node
has children.
DelaunayTriangulation.has_parent
— Methodhas_parent(node::AbstractNode) -> Bool
Returns true
if node
has a parent.
DelaunayTriangulation.hspan
— Methodhspan(r::BoundingBox) -> Float64
Returns the horizontal span of r
, i.e. length(r.x)
.
DelaunayTriangulation.increment_num_elements!
— Methodincrement_num_elements!(tree::RTree)
Increments the number of elements in tree
by 1.
DelaunayTriangulation.is_full
— Methodis_full(node::AbstractNode, tree::RTree) -> Bool
Returns true
if node
is full, i.e. if num_children(node) ≥ get_size_limit(tree)
.
DelaunayTriangulation.is_full
— Methodis_full(cache::NodeCache) -> Bool
Returns true
if cache
is full, i.e. if length(cache) ≥ get_size_limit(cache)
.
DelaunayTriangulation.is_root
— Methodis_root(node::AbstractNode, tree::RTree) -> Bool
Returns true
if node
is the root of tree
.
DelaunayTriangulation.is_touching
— Methodis_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.
DelaunayTriangulation.midpoint
— Methodmidpoint(r::BoundingBox) -> NTuple{2,Float64}
Returns the center of r
.
DelaunayTriangulation.midpoint
— Methodmidpoint(I::BoundingInterval) -> Float64
Returns the midpoint of I
.
DelaunayTriangulation.num_children
— Methodnum_children(node::AbstractNode) -> Int
Returns the number of children of node
.
DelaunayTriangulation.num_elements
— Methodnum_elements(tree::RTree) -> Int
Returns the number of elements in tree
.
DelaunayTriangulation.pop_child!
— Methodpop_child!(node::AbstractNode)
Removes the last child of node
via pop!
.
DelaunayTriangulation.set_bounding_box!
— Methodset_bounding_box!(node::AbstractNode, bounding_box::BoundingBox)
Sets the bounding box of node
to be bounding_box
.
DelaunayTriangulation.set_child!
— Methodset_child!(parent_node::AbstractNode, child_node, i::Integer)
Sets the i
th child of parent_node
to be child_node
.
DelaunayTriangulation.set_level!
— Methodset_level!(branch::Branch, level::Integer)
Sets the level of branch
to be level
.
DelaunayTriangulation.set_parent!
— Methodset_parent!(child_node::AbstractNode, parent_node::AbstractNode)
Sets the parent of child_node
to be parent_node
.
DelaunayTriangulation.set_root!
— Methodset_root!(tree::RTree, node::AbstractNode)
Sets the root of tree
to be node
.
DelaunayTriangulation.spawn_branch!
— Methodspawn_branch!(tree::RTree, bounding_box::BoundingBox, level) -> Branch
Returns a new branch node with bounding box bounding_box
and level level
from tree
.
DelaunayTriangulation.spawn_leaf!
— Methodspawn_leaf!(tree::RTree, bounding_box::BoundingBox) -> Leaf{Branch}
Returns a new leaf node with bounding box bounding_box
from tree
.
DelaunayTriangulation.spawn_node!
— Methodspawn_node!(cache::NodeCache{Node}) where {Node} -> Node
Returns a node from cache
. If cache
is empty, returns a new node.
DelaunayTriangulation.spawn_node!
— Methodspawn_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
.
DelaunayTriangulation.split_edge!
— Methodsplit_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)
.
DelaunayTriangulation.vspan
— Methodvspan(r::BoundingBox) -> Float64
Returns the vertical span of r
, i.e. length(r.y)
.
DelaunayTriangulation.QueryResult
— ModuleQueryResult
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
The PolygonHierarchy
is a data structure used for representing hierarchical information about a set of polygons, such as the piecewise linear approximation of a curve-bounded domain's boundary. This structure is implemented as a collection of directed trees, where the disjoint trees each represent the disjoint parts of a domain, and the root of each tree contains the boundary curves of all the boundaries that are inside this tree.
DelaunayTriangulation.PolygonHierarchy
— TypePolygonHierarchy{I}
Struct used to define a polygon hierarchy. The hierarchy is represented as a forest of PolygonTree
s.
The polygons must not intersect any other polygon's boundaries.
Fields
polygon_orientations::BitVector
: ABitVector
of lengthn
wheren
is the number of polygons in the hierarchy. Thei
th entry istrue
if thei
th polygon is positively oriented, andfalse
otherwise.bounding_boxes::Vector{BoundingBox}
: AVector
ofBoundingBox
s of lengthn
wheren
is the number of polygons in the hierarchy. Thei
th entry is theBoundingBox
of thei
th polygon.trees::Dict{I,PolygonTree{I}}
: ADict
mapping the index of a polygon to itsPolygonTree
. The keys oftrees
are the roots of each individual tree, i.e. the outer-most polygons.reorder_cache::Vector{PolygonTree{I}}
: AVector
used for caching trees to be deleted inreorder_subtree!
.
Note that the vector definitions for polygon_orientations
and bounding_boxes
are treating the curves with the assumption that they are enumerated in the order 1, 2, 3, ....
Constructor
PolygonHierarchy{I}() where {I}
Constructs a PolygonHierarchy
with no polygons.
DelaunayTriangulation.PolygonTree
— Typemutable struct PolygonTree{I}
A tree structure used to define a polygon hierarchy.
Fields
parent::Union{Nothing,PolygonTree{I}}
: The parent of the tree. Ifnothing
, 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 thatindex
is inside of. The root has height0
.
Constructor
PolygonTree{I}(parent::Union{Nothing,PolygonTree{I}}, index, height) where {I}
Constructs a PolygonTree
with parent
, index
, and height
, and no children.
DelaunayTriangulation.add_child!
— Methodadd_child!(tree::PolygonTree, child::PolygonTree)
Adds child
to tree
.
DelaunayTriangulation.construct_polygon_hierarchy
— Methodconstruct_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 fromconvert_boundary_curves!
.boundary_curves
: The boundary curves. These should be the output fromconvert_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 inpolygonise
.
DelaunayTriangulation.construct_polygon_hierarchy
— Methodconstruct_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.
DelaunayTriangulation.construct_polygon_hierarchy
— Methodconstruct_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.
DelaunayTriangulation.delete_child!
— Methoddelete_child!(tree::PolygonTree, child::PolygonTree)
Deletes child
from tree
.
DelaunayTriangulation.delete_tree!
— Methoddelete_tree!(hierarchy::PolygonHierarchy, index)
Deletes the PolygonTree
of the index
th polygon in hierarchy
. The index
must be associated with an exterior polygon.
DelaunayTriangulation.expand_bounds!
— Functionexpand_bounds!(hierarchy::PolygonHierarchy, perc=0.10) -> PolygonHierarchy
Expands the bounding boxes of hierarchy
by a factor of perc
in each direction.
DelaunayTriangulation.find_tree
— Methodfind_tree(hierarchy::PolygonHierarchy, points, boundary_nodes, p) -> Union{Nothing,PolygonTree}
Finds a tree in hierarchy
containing p
.
Arguments
hierarchy::PolygonHierarchy
: ThePolygonHierarchy
to search.points
: The point set.boundary_nodes
: The boundary nodes.p
: The point to test the trees ofhierarchy
against.
Output
nothing
ifp
is not inside any tree inhierarchy
, and thePolygonTree
containingp
otherwise.
DelaunayTriangulation.find_tree
— Methodfind_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
: ThePolygonHierarchy
to search.points
: The point set.boundary_nodes
: The boundary nodes.tree::PolygonTree
: ThePolygonTree
to search, assumingp
is insidetree
.p
: The point to test the children oftree
against.
Output
tree
ifp
is insidetree
but none of its children, and a child containingp
otherwise.
DelaunayTriangulation.get_bounding_box
— Methodget_bounding_box(hierarchy::PolygonHierarchy, index) -> BoundingBox
Returns the bounding box of the index
th polygon in hierarchy
.
DelaunayTriangulation.get_bounding_boxes
— Methodget_bounding_boxes(hierarchy::PolygonHierarchy) -> Vector{BoundingBox}
Returns the bounding boxes of hierarchy
.
DelaunayTriangulation.get_children
— Methodget_children(tree::PolygonTree) -> Set{PolygonTree}
Returns the children of tree
.
DelaunayTriangulation.get_exterior_curve_indices
— Methodget_exterior_curve_indices(hierarchy::PolygonHierarchy) -> KeySet
Returns the indices of the exterior curves of hierarchy
.
DelaunayTriangulation.get_height
— Methodget_height(tree::PolygonTree) -> Int
Returns the height of tree
.
DelaunayTriangulation.get_index
— Methodget_index(tree::PolygonTree{I}) -> I
Returns the index of tree
.
DelaunayTriangulation.get_parent
— Methodget_parent(tree::PolygonTree) -> Union{Nothing,PolygonTree}
Returns the parent of tree
.
DelaunayTriangulation.get_polygon_orientation
— Methodget_polygon_orientation(hierarchy::PolygonHierarchy, index) -> Bool
Returns the polygon orientation of the index
th polygon in hierarchy
.
DelaunayTriangulation.get_polygon_orientations
— Methodget_polygon_orientations(hierarchy::PolygonHierarchy) -> BitVector
Returns the polygon orientations of hierarchy
.
DelaunayTriangulation.get_positive_curve_indices
— Methodget_positive_curve_indices(hierarchy::PolygonHierarchy) -> Generator
Returns the indices of the positively oriented curves of hierarchy
as a generator, i.e. as a lazy result.
DelaunayTriangulation.get_reorder_cache
— Methodget_reorder_cache(hierarchy::PolygonHierarchy) -> Vector{PolygonTree{I}}
Returns the reorder cache of hierarchy
.
DelaunayTriangulation.get_tree
— Methodget_tree(hierarchy::PolygonHierarchy, index) -> PolygonTree{I}
Returns the PolygonTree
of the index
th polygon in hierarchy
. The index
must be associated with an exterior polygon.
DelaunayTriangulation.get_trees
— Methodget_trees(hierarchy::PolygonHierarchy) -> Dict{I,PolygonTree{I}}
Returns the trees of hierarchy
, mapping the index of an exterior polygon to its PolygonTree
.
DelaunayTriangulation.has_children
— Methodhas_children(tree::PolygonTree) -> Bool
Returns true
if tree
has children, and false
otherwise.
DelaunayTriangulation.has_parent
— Methodhas_parent(tree::PolygonTree) -> Bool
Returns true
if tree
has a parent, and false
otherwise.
DelaunayTriangulation.increase_depth!
— Methodincrease_depth!(tree::PolygonTree)
Increases the height of tree
and all of its children by 1
.
DelaunayTriangulation.is_in_tree
— Methodis_in_tree(hierarchy::PolygonHierarchy, points, boundary_nodes, tree::PolygonTree, p) -> Bool
Tests if the point p
is inside tree
.
Arguments
hierarchy::PolygonHierarchy
: ThePolygonHierarchy
containingtree
.points
: The point set.boundary_nodes
: The boundary nodes.tree::PolygonTree
: ThePolygonTree
to testp
against.p
: The point to test.
Output
true
ifp
is insidetree
, andfalse
otherwise.
DelaunayTriangulation.num_children
— Methodhas_children(tree::PolygonTree) -> Bool
Returns true
if tree
has children, and false
otherwise.
DelaunayTriangulation.reorder_hierarchy!
— Methodreorder_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
: ThePolygonHierarchy
to addnew_tree
to.points
: The point set.boundary_nodes
: The boundary nodes.new_tree::PolygonTree
: ThePolygonTree
to add tohierarchy
.
DelaunayTriangulation.reorder_subtree!
— Methodreorder_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
: ThePolygonHierarchy
to addnew_tree
to.points
: The point set.boundary_nodes
: The boundary nodes.tree::PolygonTree
: ThePolygonTree
to addnew_tree
to.new_tree::PolygonTree
: ThePolygonTree
to add tohierarchy
andtree
.
DelaunayTriangulation.set_bounding_box!
— Methodset_bounding_box!(hierarchy::PolygonHierarchy, index, bounding_box)
Sets the bounding box of the index
th polygon in hierarchy
to bounding_box
. If index
is greater than the length of the bounding boxes vector, the vector is resized.
DelaunayTriangulation.set_height!
— Methodset_height!(tree::PolygonTree, height::Int)
Sets the height of tree
to height
.
DelaunayTriangulation.set_orientation!
— Methodset_orientation!(hierarchy::PolygonHierarchy, index, orientation)
Sets the polygon orientation of the index
th polygon in hierarchy
to orientation
. If index
is greater than the length of the polygon orientations vector, the vector is resized.
DelaunayTriangulation.set_parent!
— Methodset_parent!(tree::PolygonTree, parent::PolygonTree)
Sets the parent of tree
to parent
.
DelaunayTriangulation.set_tree!
— Methodset_tree!(hierarchy::PolygonHierarchy, index, tree)
Sets the PolygonTree
of the index
th 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
The Adjacent
data structure is used for mapping edges to vertices (for triangulations) or polygons (for tessellations). The Adjacent
structure itself is in the public API, as is get_adjacent
.
DelaunayTriangulation.Adjacent
— TypeAdjacent{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})
DelaunayTriangulation.add_adjacent!
— Methodadd_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
DelaunayTriangulation.add_triangle!
— Methodadd_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
DelaunayTriangulation.delete_adjacent!
— Methoddelete_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
DelaunayTriangulation.delete_triangle!
— Methoddelete_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}()
DelaunayTriangulation.get_adjacent
— Methodget_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
DelaunayTriangulation.get_adjacent
— Methodget_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
The Adjacent2Vertex
data structure is used for mapping vertices to edges for triangulations. The Adjacent2Vertex
structure itself is in the public API, as is get_adjacent2vertex
.
DelaunayTriangulation.Adjacent2Vertex
— TypeAdjacent2Vertex{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})
DelaunayTriangulation.add_adjacent2vertex!
— Methodadd_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)])
DelaunayTriangulation.add_triangle!
— Methodadd_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)])
DelaunayTriangulation.clear_empty_keys!
— Methodclear_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}}}()
DelaunayTriangulation.delete_adjacent2vertex!
— Methoddelete_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)])
DelaunayTriangulation.delete_adjacent2vertex!
— Methoddelete_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}}}()
DelaunayTriangulation.delete_triangle!
— Methoddelete_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()
DelaunayTriangulation.get_adjacent2vertex
— Methodget_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)
DelaunayTriangulation.get_adjacent2vertex
— Methodget_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
The Graph
data structure is used for storing connectivity information about vertices in a triangulation. The Graph
structure itself is in the public API, as is get_graph
and get_neighbours
.
DelaunayTriangulation.Graph
— TypeGraph{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}})
DelaunayTriangulation._delete!
— Method_delete!(G::Graph, u, v)
Deletes the neighbour v
from u
in G
. If the neighbours of u
are empty once v
is deleted, then u
is also deleted from the vertex set.
Even though the graph is undirected, this function only deletes v
from the neighbours of u
. If you want to delete u
from the neighbours of v
, you should call delete_neighbour!(G, v, u)
.
DelaunayTriangulation.add_edge!
— Methodadd_edge!(G::Graph, u, v)
Adds the edge (u, v)
to G
.
DelaunayTriangulation.add_neighbour!
— Methodadd_neighbour!(G::Graph, u, v...)
Adds the neighbours v...
to u
in G
.
DelaunayTriangulation.add_triangle!
— Methodadd_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
.
DelaunayTriangulation.add_vertex!
— Methodadd_vertex!(G::Graph, u...)
Adds the vertices u...
to G
.
DelaunayTriangulation.clear_empty_vertices!
— Methodclear_empty_vertices!(G::Graph)
Deletes all empty vertices from G
.
DelaunayTriangulation.delete_edge!
— Methoddelete_edge!(G::Graph, u, v)
Deletes the edge (u, v)
from G
.
DelaunayTriangulation.delete_ghost_vertices_from_graph!
— Methoddelete_ghost_vertices!(G::Graph)
Deletes all ghost vertices from G
.
DelaunayTriangulation.delete_neighbour!
— Methoddelete_neighbour!(G::Graph, u, v...)
Deletes the neighbours v...
from u
in G
.
DelaunayTriangulation.delete_triangle!
— Methoddelete_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
.
DelaunayTriangulation.delete_vertex!
— Methoddelete_vertex!(G::Graph, u...)
Deletes the vertices u...
from G
.
DelaunayTriangulation.get_edges
— Methodget_edges(graph::Graph) -> Set{NTuple{2, Vertex}}
Returns the set of edges in graph
.
DelaunayTriangulation.get_neighbours
— Methodget_neighbours(G::Graph, u) -> Set{Vertex}
Returns the set of neighbours of u
in G
.
DelaunayTriangulation.get_neighbours
— Methodget_neighbours(graph::Graph) -> Dict{Vertex, Set{Vertex}}
Returns the neighbours
map of graph
.
DelaunayTriangulation.get_vertices
— Methodget_vertices(graph::Graph) -> Set{Vertex}
Returns the set of vertices in graph
.
DelaunayTriangulation.has_ghost_vertices
— Methodhas_ghost_vertices(G::Graph) -> Bool
Returns true
if G
has ghost vertices, and false
otherwise.
DelaunayTriangulation.has_vertex
— Methodhas_vertex(G::Graph, u) -> Bool
Returns true
if u
is a vertex in G
, and false
otherwise.
DelaunayTriangulation.num_edges
— Methodnum_edges(G::Graph) -> Integer
Returns the number of edges in G
. The edges (i, j)
and (j, i)
are counted as one edge.
DelaunayTriangulation.num_neighbours
— Methodnum_neighbours(G::Graph, u) -> Integer
Returns the number of neighbours of u
in G
.
DelaunayTriangulation.num_vertices
— Methodnum_vertices(G::Graph) -> Integer
Returns the number of vertices in G
.
Curves
There are many data structures used to define the curves we provide in this package, all subtyping the AbstractParametricCurve
type. This type, and its subtypes, are all in the public API with the exception of PiecewiseLinear
.
DelaunayTriangulation.AbstractParametricCurve
— Typeabstract 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 definedtotal_variation
).- The struct must be callable so that
c(t)
, wherec
an instance of the struct, returns the associated value of the curve att
. - If the struct does not implement
point_position_relative_to_curve
, then the struct must implementget_closest_point
. Alternatively, rather than implementingget_closest_point
, the struct should have alookup_table
field as aVector{NTuple{2,Float64}}
, which returns values on the curve at a set of points, wherelookup_table[i]
is the value of the curve att = (i - 1) / (length(lookup_table) - 1)
.
Functions that are defined for all AbstractParametricCurve
subtypes are:
The curves in this package evaluate the total variation not by evaluating the integral itself, but by taking care of the changes in orientation in the curve to efficiently compute it. This is done by using the orientation markers of the curves, obtained using orientation_markers
, that stored in the field orientation_markers
of these curves. The function marked_total_variation
is then used to evaluate it. You may like to consider using these functions for any curve you wish to implement yourself, using e.g. the BezierCurve
struct's implementation as a reference.
DelaunayTriangulation.LineSegment
— TypeLineSegment <: 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)
DelaunayTriangulation.CircularArc
— TypeCircularArc <: 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 byend_angle - start_angle
, whereend_angle
is the angle atlast
, 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 forpoint_position_relative_to_curve
.
The angles start_angle
and end_angle
should be setup such that start_angle > end_angle
implies a positively oriented arc, and start_angle < end_angle
implies a negatively oriented arc. Moreover, they must be in [0°, 2π°)
.
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.
DelaunayTriangulation.EllipticalArc
— TypeEllipticalArc <: 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 fromcenter
, 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 byend_angle - start_angle
, whereend_angle
is the angle atlast
, 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.
DelaunayTriangulation.BezierCurve
— TypeBezierCurve <: 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
.
This curve is only tested on loop-free curves (and closed curves that otherwise have no self-intersections). It is not guaranteed to work on curves with loops, especially for finding the nearest point on the curve to a given point.
Remember that Bezier curves are not interpolation curves. They only go through the first and last control points, but not the intermediate ones. If you want an interpolation curve, use 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. Thei
th entry of the lookup table corresponds to thet
-valuei / (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 always0
and1
, respectively. Seeorientation_markers
.
The cache is not thread-safe, and so you should not evaluate this curve in parallel.
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
.
DelaunayTriangulation.BSpline
— TypeBSpline <: 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.
This curve is only tested on loop-free curves (and closed curves that otherwise have no self-intersections). It is not guaranteed to work on curves with loops, especially for finding the nearest point on the curve to a given point.
Remember that B-spline curves are not interpolation curves. They only go through the first and last control points, but not the intermediate ones. For an interpolating spline, see CatmullRomSpline
.
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. Thei
th entry of the lookup table corresponds to thet
-valuei / (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 always0
and1
, respectively. Seeorientation_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
.
DelaunayTriangulation.CatmullRomSpline
— TypeCatmullRomSpline <: 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.
This curve is only tested on loop-free curves (and closed curves that otherwise have no self-intersections). It is not guaranteed to work on curves with loops, especially for finding the nearest point on the curve to a given point.
Typically, Catmull-Rom splines are defined on segments of four control points, and drawn between the two interior control points. This creates an issue in that the first and last control points will not be joined to the spline. To overcome this, we extend the spline to the left and right during the evaluation of a spline, using the fields left
and right
defined below. The rules used for extending these points come from CatmullRom.jl, which extrapolates based on a Thiele-like cubic polynomial.
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. Thei
th entry of this vector corresponds to thet
-value associated with thei
th control point. With an alpha parameterα
, these values are given byknots[i+1] = knots[i] + dist(control_points[i], control_points[i+1])^α
, whereknots[1] = 0
, and the vector is the normalised by dividing byknots[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. Thei
th entry of the lookup table corresponds to thet
-valuei / (length(lookup_table) - 1)
.alpha::Float64
: The alpha parameter of the Catmull-Rom spline. This controls the type of the parametrisation, wherealpha = 0
corresponds to uniform parametrisation,alpha = 1/2
corresponds to centripetal parametrisation, andalpha = 1
corresponds to chordal parametrisation. Must be in[0, 1]
. For reasons similar to what we describe fortension
below, we only supportalpha = 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, withtension = 0
being the least tight, andtension = 1
leading to straight lines between the control points. Must be in[0, 1]
. You can not currently set this to anything except0.0
due to numerical issues with boundary refinement. (For example, equivariation splits are not possible iftension=1
since the curve is piecewise linear in that case, and fortension
very close to1
, 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 always0
and1
, respectively. Seeorientation_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
.
DelaunayTriangulation.twice_differentiate
— Functiontwice_differentiate(c::AbstractParametricCurve, t) -> NTuple{2, Float64}
Evaluates the second derivative of c
at t
.
DelaunayTriangulation.total_variation
— Functiontotal_variation(c::AbstractParametricCurve) -> Float64
total_variation(c::AbstractParametricCurve, t₁, t₂) -> Float64
Returns the total variation of a curve c
, or the subcurve over [t₁, t₂]
with 0 ≤ t₁ ≤ t₂ ≤ 1
, defined as the integral of the absolute curvature over this interval. (This is also known as the total absolute curvature.)
DelaunayTriangulation.thrice_differentiate
— Functionthrice_differentiate(c::AbstractParametricCurve, t) -> NTuple{2, Float64}
Evaluates the third derivative of c
at t
.
DelaunayTriangulation.differentiate
— Functiondifferentiate(c::AbstractParametricCurve, t) -> NTuple{2, Float64}
Evaluates the derivative of c
at t
.
DelaunayTriangulation.arc_length
— Functionarc_length(c::AbstractParametricCurve) -> Float64
arc_length(c::AbstractParametricCurve, t₁, t₂) -> Float64
Returns the arc length of the [AbstractParametricCurve
] c
. The second method returns the arc length in the interval [t₁, t₂]
, where 0 ≤ t₁ ≤ t₂ ≤ 1
.
Base.reverse
— Methodreverse(curve::AbstractParametricCurve) -> AbstractParametricCurve
Returns an AbstractParametricCurve
that reverses the orientation of curve
. In particular, c(t) = c̄(1-t)
for all t
in [0, 1]
, where c
is the original curve and c̄
is the reversed curve.
DelaunayTriangulation._get_interval_for_get_circle_intersection
— Method_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₁)
.
DelaunayTriangulation.angle_between
— Methodangle_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.
DelaunayTriangulation.convert_lookup_idx
— Methodconvert_lookup_idx(b::AbstractParametricCurve, i) -> Float64
Converts the index i
of the lookup table of the curve b
to the corresponding t
-value.
DelaunayTriangulation.curvature
— Methodcurvature(c::AbstractParametricCurve, t) -> Float64
Returns the curvature of the [AbstractParametricCurve
] c
at t
.
DelaunayTriangulation.get_circle_intersection
— Methodget_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.
DelaunayTriangulation.get_closest_point
— Methodget_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.
This function is only tested on loop-free curves. It is not guaranteed to work on curves with loops. Moreover, for this function to be accurate, you want the lookup table in b
to be sufficiently dense.
DelaunayTriangulation.get_equidistant_split
— Methodget_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.
DelaunayTriangulation.get_equivariation_split
— Methodget_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.
DelaunayTriangulation.get_inverse
— Methodget_inverse(c::AbstractParametricCurve, p) -> Float64
Given a point p
on c
, returns the t
-value such that c(t) ≈ p
.
DelaunayTriangulation.has_lookup_table
— Methodhas_lookup_table(c::AbstractParametricCurve) -> Bool
Returns true
if c
has a lookup table, and false
otherwise.
DelaunayTriangulation.horizontal_inflection_points
— Methodhorizontal_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.
For curves of very high degree, such as Bezier curves with steps
control points or greater, this function might fail to return all inflection points.
Arguments
c::AbstractParametricCurve
: The curve to find the horizontal inflection points of.
Keyword Arguments
steps=200
: The number oft
-values to use for seeding Newton's method. In particular, Newton's method is run for each initial value inLinRange(0, 1, steps)
.iters=50
: The number of iterations to run Newton's method for.tol=1e-5
: The tolerance to use foruniquetol
. Also used for deciding whether a root is a valid root, i.e. ifabs(x''(t)) > tol
for a found roott
, thent
is not a valid root and is rejected.
Output
t
: All inflection points, given in sorted order.
DelaunayTriangulation.horizontal_turning_points
— Methodhorizontal_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'
.
For curves of very high degree, such as Bezier curves with steps
control points or greater, this function might fail to return all turning points.
Arguments
c::AbstractParametricCurve
: The curve to find the horizontal turning points of.
Keyword Arguments
steps=200
: The number oft
-values to use for seeding Newton's method. In particular, Newton's method is run for each initial value inLinRange(0, 1, steps)
.iters=50
: The number of iterations to run Newton's method for.tol=1e-5
: The tolerance to use foruniquetol
. Also used for deciding whether a root is a valid root, i.e. ifabs(x'(t)) > tol
for a found roott
, thent
is not a valid root and is rejected.
Output
t
: All turning points, given in sorted order.
DelaunayTriangulation.inflection_points
— Methodinflection_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 κ
.
For curves of very high degree, such as Bezier curves with steps
control points or greater, this function might fail to return all inflection points.
Arguments
c::AbstractParametricCurve
: The curve to find the inflection points of.
Keyword Arguments
steps=200
: The number oft
-values to use for seeding Newton's method. In particular, Newton's method is run for each initial value inLinRange(0, 1, steps)
.iters=50
: The number of iterations to run Newton's method for.tol=1e-5
: The tolerance to use foruniquetol
. Also used for deciding whether a root is a valid root, i.e. ifabs(κ(t)) > tol
for a found roott
, thent
is not a valid root and is rejected.
DelaunayTriangulation.is_curve_bounded
— Methodis_curve_bounded(c::AbstractParametricCurve) -> Bool
Returns true
if c
is not a PiecewiseLinear
curve. This is equivalent to !is_piecewise_linear(c)
.
DelaunayTriangulation.is_interpolating
— Methodis_interpolating(c::AbstractParametricCurve) -> Bool
Returns true
if c
goes through all its control points, and false
otherwise.
DelaunayTriangulation.is_linear
— Methodis_linear(c::AbstractParametricCurve) -> Bool
Returns true
if c
is LineSegment
, and false
otherwise.
DelaunayTriangulation.is_piecewise_linear
— Methodis_piecewise_linear(c::AbstractParametricCurve) -> Bool
Returns true
if c
is PiecewiseLinear
, and false
otherwise.
DelaunayTriangulation.marked_total_variation
— Methodmarked_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
.
DelaunayTriangulation.orientation_markers
— Methodorientation_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 functionx(t)
κ(t; y) = 0
, whereκ(t; y)
is the curvature of the component functiony(t)
κ(t) = 0
, whereκ
is the curvature ofc(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
.
For curves of very high degree, such as Bezier curves with steps
control points or greater, this function might fail to return all inflection points.
Arguments
c::AbstractParametricCurve
: TheAbstractParametricCurve
.
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 twot
-values are the same.
Output
markers::Vector{Float64}
: Thet
-values of the orientation markers ofb
. The returned vector is sorted, and also includes the endpoints0
and1
; anyt
-values outside of[0, 1]
are discarded, and multiplicity of anyt
is not considered (so thet
-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
.
DelaunayTriangulation.point_position_relative_to_curve
— Methodpoint_position_relative_to_curve([kernel::AbstractPredicateKernel=AdaptiveKernel(),] 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 ofc
.Right
:p
is to the right ofc
.On
:p
is onc
.
The kernel
argument determines how this result is computed, and should be one of ExactKernel
, FastKernel
, and AdaptiveKernel
(the default). See the documentation for more information about these choices.
DelaunayTriangulation.process_roots_and_residuals!
— Methodprocess_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.
DelaunayTriangulation.protect_against_bad_division!
— Methodprotect_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.
DelaunayTriangulation.vertical_inflection_points
— Methodvertical_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.
For curves of very high degree, such as Bezier curves with steps
control points or greater, this function might fail to return all inflection points.
Arguments
c::AbstractParametricCurve
: The curve to find the vertical inflection points of.
Keyword Arguments
steps=200
: The number oft
-values to use for seeding Newton's method. In particular, Newton's method is run for each initial value inLinRange(0, 1, steps)
.iters=50
: The number of iterations to run Newton's method for.tol=1e-5
: The tolerance to use foruniquetol
. Also used for deciding whether a root is a valid root, i.e. ifabs(y''(t)) > tol
for a found roott
, thent
is not a valid root and is rejected.
Output
t
: All inflection points, given in sorted order.
DelaunayTriangulation.vertical_turning_points
— Methodvertical_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'
.
For curves of very high degree, such as Bezier curves with steps
control points or greater, this function might fail to return all turning points.
Arguments
c::AbstractParametricCurve
: The curve to find the vertical turning points of.
Keyword Arguments
steps=200
: The number oft
-values to use for seeding Newton's method. In particular, Newton's method is run for each initial value inLinRange(0, 1, steps)
.iters=50
: The number of iterations to run Newton's method for.tol=1e-5
: The tolerance to use foruniquetol
. Also used for deciding whether a root is a valid root, i.e. ifabs(y'(t)) > tol
for a found roott
, thent
is not a valid root and is rejected.
Output
t
: All turning points, given in sorted order.
DelaunayTriangulation.CatmullRomSplineSegment
— TypeCatmullRomSplineSegment <: 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 ont³
.b::NTuple{2,Float64}
: The coefficient ont²
.c::NTuple{2,Float64}
: The coefficient ont
.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]
.
DelaunayTriangulation.get_segment
— Methodget_segment(c::CatmullRomSpline, t) -> (CatmullRomSplineSegment, Int)
Returns the CatmullRomSplineSegment
of the CatmullRomSpline
c
that contains the point at t
. Also returns the segment index.
DelaunayTriangulation.angle_between
— Methodangle_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.
DelaunayTriangulation.point_position_relative_to_curve
— Methodpoint_position_relative_to_curve([kernel::AbstractPredicateKernel=AdaptiveKernel(),] L::LineSegment, p) -> Certificate
Returns the position of p
relative to L
, returning a Certificate
:
Left
:p
is to the left ofL
.Right
:p
is to the right ofL
.On
:p
is onL
.
See also point_position_relative_to_line
.
The kernel
argument determines how this result is computed, and should be one of ExactKernel
, FastKernel
, and AdaptiveKernel
(the default). See the documentation for more information about these choices.
DelaunayTriangulation.PiecewiseLinear
— TypePiecewiseLinear <: 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.
This struct does have fields, namely points
and boundary_nodes
(and boundarynodes should be a contiguous section). These are only used so that we can use this struct in [`anglebetween](@ref) easily. In particular, we need to allow for evaluating this curve at
t=0and at
t=1, and similarly for differentiating the curve at
t=0and at
t=1. For this, we have defined, letting
Lbe a
PiecewiseLinearcurve,
L(0)to return the first point on the curve, and the last point otherwise (meaning
L(h)is constant for
h > 0`), and similarly for differentiation. Do NOT rely on the implementation of these methods.
RepresentativeCoordinates
We use a RepresentativeCoordinates
struct for storing the representative coordinates used for interpreting ghost vertices.
DelaunayTriangulation.RepresentativeCoordinates
— TypeRepresentativeCoordinates{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.
DelaunayTriangulation.add_point!
— Methodadd_point!(c::RepresentativeCoordinates, p)
Treating c
as an arithmetic average, updates the coordinates of c
to include p
.
DelaunayTriangulation.compute_centroid!
— Methodcompute_centroid!(c::RepresentativeCoordinates, points)
Computes the centroid of points
and stores the result in c
.
DelaunayTriangulation.delete_point!
— Methoddelete_point!(c::RepresentativeCoordinates, p)
Treating c
as an arithmetic average, updates the coordinates of c
to exclude p
.
DelaunayTriangulation.getn
— Methodgetn(c::RepresentativeCoordinates) -> Integer
Returns the number of points represented by c
.
DelaunayTriangulation.getx
— Methodgetx(c::RepresentativeCoordinates) -> Number
Returns the x-coordinate of c
.
DelaunayTriangulation.gety
— Methodgety(c::RepresentativeCoordinates) -> Number
Returns the y-coordinate of c
.
DelaunayTriangulation.reset!
— Methodreset!(c::RepresentativeCoordinates)
Resets the coordinates of c
to zero.
DelaunayTriangulation.update_centroid_after_addition!
— Functionupdate_centroid_after_addition!(tri::Triangulation, curve_index, p)
Updates the centroid of the curve_index
th curve in tri
after the addition of the point p
.
Cell
We use a Cell
struct for representing an individual square in a quadtree during the computation of the pole of inaccessibility.
DelaunayTriangulation.Cell
— TypeCell{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
.
DelaunayTriangulation.getx
— Methodgetx(c::Cell) -> Number
Returns the x-coordinate of c
.
DelaunayTriangulation.gety
— Methodgety(c::Cell) -> Number
Returns the y-coordinate of c
.
CellQueue
We use a CellQueue
struct for storing the Cell
s in a quadtree during the computation of the pole of inaccessibility.
DelaunayTriangulation.CellQueue
— TypeCellQueue{T}
A struct representing the priority queue of Cell
s, 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}
.
Base.isempty
— Methodisempty(queue::CellQueue) -> Bool
Returns true
if the queue
is empty, and false
otherwise.
DelaunayTriangulation.get_next_cell!
— Methodget_next_cell!(queue::CellQueue)
Returns the next cell in the queue.
DelaunayTriangulation.insert_cell!
— Methodinsert_cell!(queue::CellQueue, cell::Cell)
Inserts a cell
into the queue
.
ConvexHull
We use a ConvexHull
struct to represent a convex hull. This struct is in the public API.
DelaunayTriangulation.ConvexHull
— TypeConvexHull{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 thatvertices[begin] == vertices[end]
.
Constructors
ConvexHull(points, vertices)
convex_hull(points; predicates=AdaptiveKernel(), IntegerType=Int)
DelaunayTriangulation.get_points
— Methodget_points(convex_hull::ConvexHull) -> Points
Returns the underlying point set of convex_hull
.
DelaunayTriangulation.get_vertices
— Methodget_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
We use a Triangulation
struct to represent a triangulation. This struct is in the public API.
DelaunayTriangulation.Triangulation
— TypeTriangulation{P,T,BN,W,I,E,Es,BC,BCT,BEM,GVM,GVR,BPL,C,BE}
Struct representing a triangulation, as constructed by triangulate
.
Accessing the fields themselves using e.g. tri.field
is not recommended and is not intended to be in the public API. You should be using the accessor functions, e.g. instead of tri.points
do get_points(tri)
. Similarly, for the iterators, e.g. tri.triangles
, each_triangle(tri)
is recommended instead.
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 with 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 i
th vertex. The weights should have the same type as the coordinates in points
.
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 i
th element of the Tuple
is associated with the ghost vertex -i
, i.e. the i
th section as indicated by ghost_vertex_map
. If the i
th 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!
.
DelaunayTriangulation.build_triangulation_from_data!
— Functionbuild_triangulation_from_data!(tri::Triangulation, triangles, boundary_nodes, delete_ghosts, predicates::AbstractPredicateKernel=AdaptiveKernel())
Given an empty triangulation
, tri
, adds all the triangles
and boundary_nodes
into it. Use delete_ghosts=true
if you want to have all ghost triangles deleted afterwards.
The kernel
argument determines how predicates are computed, and should be one of ExactKernel
, FastKernel
, and AdaptiveKernel
(the default). See the documentation for more information about these choices.
DelaunayTriangulation.edge_type
— Methodedge_type(tri::Triangulation) -> DataType
Returns the type used for representing individual edges in tri
.
DelaunayTriangulation.edges_type
— Methodedges_type(tri::Triangulation) -> DataType
Returns the type used for representing collections of edges in tri
.
DelaunayTriangulation.get_adjacent
— Methodget_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
.
DelaunayTriangulation.get_adjacent2vertex
— Methodget_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
.
DelaunayTriangulation.get_all_segments
— Methodget_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.
DelaunayTriangulation.get_boundary_curves
— Methodget_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 i
th element of the Tuple
corresponds to the i
th 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
.
DelaunayTriangulation.get_boundary_edge_map
— Methodget_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
.
DelaunayTriangulation.get_boundary_enricher
— Methodget_boundary_enricher(tri::Triangulation) -> BoundaryEnricher
Returns the BoundaryEnricher
of tri
. If the domain is not curve-bounded, this is nothing
.
DelaunayTriangulation.get_boundary_nodes
— Methodget_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
.
DelaunayTriangulation.get_cache
— Methodget_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.
DelaunayTriangulation.get_convex_hull
— Methodget_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.
DelaunayTriangulation.get_exterior_curve_indices
— Methodget_exterior_curve_indices(tri::Triangulation) -> KeySet{Integer}
Returns the set of all curve indices that correspond to exterior curves of tri
.
DelaunayTriangulation.get_ghost_vertex_map
— Methodget_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 Tuple
s (m, n)
so that get_boundary_nodes(tri, m, n)
are the boundary nodes associated with i
, i.e. the n
th section of the m
th 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 n
th 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
.
DelaunayTriangulation.get_ghost_vertex_ranges
— Methodget_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
.
DelaunayTriangulation.get_graph
— Methodget_graph(tri::Triangulation) -> Graph
Returns the Graph
of the triangulation tri
. This is an undirected graph.
DelaunayTriangulation.get_incircle_cache
— Methodget_incircle_cache(tri::Triangulation) -> Tuple
Returns the incircle cache stored in tri
.
DelaunayTriangulation.get_insphere_cache
— Methodget_insphere_cache(tri::Triangulation) -> Tuple
Returns the insphere cache stored in tri
.
DelaunayTriangulation.get_interior_segments
— Methodget_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.
DelaunayTriangulation.get_orient3_cache
— Methodget_orient3_cache(tri::Triangulation) -> Tuple
Returns the orient3 cache stored in tri
.
DelaunayTriangulation.get_points
— Methodget_points(tri::Triangulation) -> Points
Return the points of the triangulation. Note that this may include points not yet in tri
.
DelaunayTriangulation.get_polygon_hierarchy
— Methodget_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.
DelaunayTriangulation.get_positive_curve_indices
— Methodget_positive_curve_indices(tri::Triangulation) -> Generator
Returns the indices of the positively oriented curves of hierarchy
as a generator, i.e. as a lazy result.
DelaunayTriangulation.get_representative_point_list
— Methodget_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.
DelaunayTriangulation.get_triangles
— Methodget_triangles(tri::Triangulation) -> Triangles
Return the triangles of the triangulation. These triangles are all given in counter-clockwise order, and may include ghost triangles.
DelaunayTriangulation.get_weights
— Methodget_weights(tri::Triangulation) -> Weights
Return the weights of the triangulation. These are the weights of the vertices of the triangulation.
DelaunayTriangulation.integer_type
— Methodinteger_type(tri::Triangulation) -> DataType
Returns the type used for representing vertices in tri
.
DelaunayTriangulation.number_type
— Methodnumber_type(tri::Triangulation) -> DataType
Returns the type used for representing individual coordinates in tri
.
DelaunayTriangulation.triangle_type
— Methodtriangle_type(tri::Triangulation) -> DataType
Returns the type used for representing individual triangles in tri
.
DelaunayTriangulation.triangles_type
— Methodtriangle_type(tri::Triangulation) -> DataType
Returns the type used for representing collections of triangles in tri
.
TriangulationCache
The TriangulationCache
is what we store in the cache
field of a triangulation.
DelaunayTriangulation.TriangulationCache
— TypeTriangulationCache{T,M,I,S,IC,OC,IS}
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 theweights
. 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 oftri
. This is needed forlock_convex_hull!
in case the convex hull also contains interior segments.surrounding_polygon::S
: The polygon surrounding the triangulation. This is needed fordelete_point!
.fan_triangles::F
: Triangles in a fan. This is needed for sorting fans for constrained triangulations.incircle_cache::IC
: Cache for incircle tests.orient3_cache::OC
: Cache for orient3 tests.insphere_cache::IS
: Cache for insphere tests.
The triangulation cache itself does not have a cache. Instead, it stores a TriangulationCache(nothing)
.
The points
of the cache's triangulation
will be aliased to the points
of the parent triangulation.
Base.empty!
— Methodempty!(cache::TriangulationCache)
Empties the cache by emptying the triangulation stored in it.
DelaunayTriangulation.empty_unconstrained_triangulation!
— Methodempty_unconstrained_triangulation!(tri::Triangulation)
Empties the triangulation tri
by emptying its fields. Only works for unconstrained triangulaions.
DelaunayTriangulation.get_fan_triangles
— Methodget_fan_triangles(cache::TriangulationCache) -> Triangles
Returns the triangles in a fan stored in cache
.
DelaunayTriangulation.get_incircle_cache
— Methodget_incircle_cache(cache::TriangulationCache) -> Tuple
Returns the incircle cache stored in cache
.
DelaunayTriangulation.get_insphere_cache
— Methodget_insphere_cache(cache::TriangulationCache) -> Tuple
Returns the insphere cache stored in cache
.
DelaunayTriangulation.get_interior_segments_on_hull
— Methodget_interior_segments_on_hull(cache::TriangulationCache) -> Set{Edge}
Returns the interior segments on the convex hull of the triangulation stored in cache
.
DelaunayTriangulation.get_marked_vertices
— Methodget_marked_vertices(cache::TriangulationCache) -> Vector{Vertex}
Returns the marked vertices stored in cache
.
DelaunayTriangulation.get_orient3_cache
— Methodget_orient3_cache(cache::TriangulationCache) -> Tuple
Returns the orient3 cache stored in cache
.
DelaunayTriangulation.get_surrounding_polygon
— Methodget_surrounding_polygon(cache::TriangulationCache) -> Vector{Vertex}
Returns the polygon surrounding the triangulation stored in cache
.
DelaunayTriangulation.get_triangulation
— Methodget_triangulation(cache::TriangulationCache) -> Triangulation
Returns the Triangulation
stored in cache
.
DelaunayTriangulation.get_triangulation_2
— Methodget_triangulation_2(cache::TriangulationCache) -> Triangulation
Returns the second Triangulation
stored in cache
.
BoundaryEnricher
We use a BoundaryEnricher
struct for storing information using during the enrichment phase of the triangulation of a curve-bounded domain.
DelaunayTriangulation.BoundaryEnricher
— TypeBoundaryEnricher{P,B,C,I,BM,S,E}
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 aTuple
, to the index of the parent curve inboundary_curves
.curve_index_map::Dict{I,I}
: A map from a curve index to the index of the curve inboundary_curves
.boundary_edge_map::B
: A map from a boundary node to the index of the curve inboundary_curves
that it belongs to. Seeconstruct_boundary_edge_map
.spatial_tree::BoundaryRTree{P}
: TheBoundaryRTree
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.
DelaunayTriangulation.SmallAngleComplex
— TypeSmallAngleComplex{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.
DelaunayTriangulation.SmallAngleComplexMember
— TypeSmallAngleComplexMember{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 is0
, 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.
Base.append!
— Methodappend!(complex::SmallAngleComplex, new_complex::SmallAngleComplex)
Appends the members of new_complex
onto the members of complex
.
Base.push!
— Methodpush!(complex::SmallAngleComplex, member::SmallAngleComplexMember)
Pushes member
onto the members of complex
.
DelaunayTriangulation.angle_between
— Methodangle_between(enricher::BoundaryEnricher, curve_index1, curve_index2) -> Float64
Evaluates angle_between
on the curves with indices curve_index1
and curve_index2
in enricher
.
DelaunayTriangulation.construct_curve_index_map!
— Methodconstruct_curve_index_map!(enricher::BoundaryEnricher)
Constructs the curve index map for enricher
, modifying the curve index map field in-place.
DelaunayTriangulation.construct_parent_map!
— Methodconstruct_parent_map!(enricher::BoundaryEnricher)
Constructs the parent map for enricher
, modifying the parent map field in-place.
DelaunayTriangulation.construct_segment_map
— Methodconstruct_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.
DelaunayTriangulation.construct_tree!
— Methodconstruct_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.
DelaunayTriangulation.delete_edge!
— Methoddelete_edge!(boundary_enricher::BoundaryEnricher, i, j)
Deletes the edge (i, j)
in boundary_enricher
.
DelaunayTriangulation.each_boundary_edge
— Methodeach_boundary_edge(enricher::BoundaryEnricher) -> KeySet
Returns the set of keys in the parent map of enricher
, i.e. each boundary edge in enricher
.
DelaunayTriangulation.eval_boundary_curve
— Methodeval_boundary_curve(enricher::BoundaryEnricher, curve_index, t) -> NTuple{2,Float64}
Returns the curve_index
th boundary curve at t
.
DelaunayTriangulation.get_apex
— Methodget_apex(complex::SmallAngleComplex{I}) where {I} -> I
Returns the apex of complex
.
DelaunayTriangulation.get_boundary_curve
— Methodget_boundary_curve(boundary_enricher::BoundaryEnricher, curve_index) -> AbstractParametricCurve
Returns the curve_index
th curve from the boundary curves in boundary_enricher
.
DelaunayTriangulation.get_boundary_curves
— Methodget_boundary_curves(boundary_enricher::BoundaryEnricher{P,B,C}) -> C
Returns the boundary curves associated with boundary_enricher
.
DelaunayTriangulation.get_boundary_edge_map
— Methodget_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)
.
DelaunayTriangulation.get_boundary_edge_map
— Methodget_boundary_edge_map(boundary_enricher::BoundaryEnricher{P,B,C,I,BM}) -> BM
Returns the boundary edge map associated with boundary_enricher
.
DelaunayTriangulation.get_boundary_nodes
— Methodget_boundary_nodes(boundary_enricher::BoundaryEnricher{P,B}) -> B
Returns the boundary nodes associated with boundary_enricher
.
DelaunayTriangulation.get_circle_intersection
— Methodget_circle_intersection(enricher::BoundaryEnricher, curve_index, t₁, t₂, r) -> (Float64, NTuple{2,Float64})
Finds the intersection of the curve_index
th 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.
DelaunayTriangulation.get_curve_index_map
— Methodget_curve_index_map(boundary_enricher::BoundaryEnricher{P,B,C,I}) -> Dict{I,I}
Returns the curve index map associated with boundary_enricher
.
DelaunayTriangulation.get_equidistant_split
— Methodget_equidistant_split(enricher::BoundaryEnricher, curve_index, t₁, t₂) -> Float64
Returns the equidistant split of the curve_index
th curve between t₁
and t₂
.
DelaunayTriangulation.get_equivariation_split
— Methodget_equivariation_split(enricher::BoundaryEnricher, curve_index, t₁, t₂) -> Float64, Float64
Returns the equivariation split of the curve_index
th curve between t₁
and t₂
. Also returns the total variation of the two pieces.
DelaunayTriangulation.get_inverse
— Methodget_inverse(enricher::BoundaryEnricher, curve_index, q) -> Float64
Returns the inverse of the curve_index
th curve at q
.
DelaunayTriangulation.get_members
— Methodget_members(complex::SmallAngleComplex{I}) where {I} -> Vector{SmallAngleComplexMember{I}}
Returns the members of complex
.
DelaunayTriangulation.get_minimum_edge_length
— Methodget_minimum_edge_length(complex::SmallAngleComplex, points) -> Float64
Returns the minimum edge length in complex
with respect to points
.
DelaunayTriangulation.get_next_edge
— Methodget_next_edge(member::SmallAngleComplexMember{I}) where {I} -> I
Returns the next edge of member
.
DelaunayTriangulation.get_parent
— Methodget_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.
DelaunayTriangulation.get_parent_curve
— Methodget_parent_curve(member::SmallAngleComplexMember{I}) where {I} -> I
Returns the parent curve of member
.
DelaunayTriangulation.get_parent_map
— Methodget_parent_map(boundary_enricher::BoundaryEnricher{P,B,C,I}) -> Dict{NTuple{2,I},I}
Returns the parent map associated with boundary_enricher
.
DelaunayTriangulation.get_points
— Methodget_points(boundary_enricher::BoundaryEnricher{P}) -> P
Returns the point set associated with boundary_enricher
.
DelaunayTriangulation.get_polygon_hierarchy
— Methodget_polygon_hierarchy(boundary_enricher::BoundaryEnricher{P,B,C,I}) -> PolygonHierarchy{I}
Returns the polygon hierarchy associated with boundary_enricher
.
DelaunayTriangulation.get_queue
— Methodget_queue(boundary_enricher::BoundaryEnricher{P,B,C,I}) -> Queue{I}
Returns the queue associated with boundary_enricher
.
DelaunayTriangulation.get_segments
— Methodget_segments(boundary_enricher::BoundaryEnricher{P,B,C,I,BM,S}) -> S
Returns the segments associated with boundary_enricher
.
DelaunayTriangulation.get_small_angle_complexes
— Functionget_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.
DelaunayTriangulation.get_small_angle_complexes
— Methodget_small_angle_complex(boundary_enricher::BoundaryEnricher, apex) -> Vector{SmallAngleComplex}
Returns the small angle complexes in boundary_enricher
associated with apex
.
DelaunayTriangulation.get_small_angle_complexes
— Methodget_small_angle_complexes(boundary_enricher::BoundaryEnricher{P,B,C,I}) -> Dict{I,Vector{SmallAngleComplex{I}}}
Returns the small angle complexes associated with boundary_enricher
.
DelaunayTriangulation.get_spatial_tree
— Methodget_spatial_tree(boundary_enricher::BoundaryEnricher{P,B,C,I}) -> RTree
Returns the spatial tree associated with boundary_enricher
.
DelaunayTriangulation.has_segments
— Methodhas_segments(boundary_enricher::BoundaryEnricher -> Bool
Returns true
if boundary_enricher
has interior segments, and false
otherwise.
DelaunayTriangulation.is_linear
— Methodis_linear(enricher::BoundaryEnricher, curve_index) -> Bool
Returns true
if the curve_index
th curve in enricher
is a LineSegment
, and false
otherwise.
DelaunayTriangulation.is_piecewise_linear
— Methodis_piecewise_linear(enricher::BoundaryEnricher, curve_index) -> Bool
Returns true
if the curve_index
th curve in enricher
is piecewise linear, and false
otherwise.
DelaunayTriangulation.is_segment
— Methodis_segment(enricher::BoundaryEnricher, i, j) -> Bool
Returns true
if (i, j)
or (j, i)
is an interior segment of enricher
, and false
otherwise.
DelaunayTriangulation.is_small_angle_complex_apex
— Methodis_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.
DelaunayTriangulation.is_small_angle_complex_member
— Methodis_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, andfalse
otherwise.apex
: If the edge is a member of a small angle complex, thenapex
is the apex of the complex. Otherwise,apex
is0
.complex_id
: If the edge is a member of a small angle complex, thencomplex_id
is the index of the complex in the list of complexes associated withapex
. Otherwise,complex_id
is0
.member_id
: If the edge is a member of a small angle complex, thenmember_id
is the index of the member in the list of members associated withcomplex_id
. Otherwise,member_id
is0
.
DelaunayTriangulation.map_curve_index
— Methodmap_curve_index(boundary_enricher::BoundaryEnricher, curve_index) -> Integer
Returns the curve index in boundary_enricher
associated with curve_index
.
DelaunayTriangulation.partition_members
— Methodpartition_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.
DelaunayTriangulation.point_position_relative_to_curve
— Methodpoint_position_relative_to_curve([kernel::AbstractPredicateKernel=AdaptiveKernel(),] enricher::BoundaryEnricher, curve_index, p) -> Certificate
Returns a Certificate
which is
Left
: Ifp
is to the left of thecurve_index
th curve.Right
: Ifp
is to the right of thecurve_index
th curve.On
: Ifp
is on thecurve_index
th curve.
The kernel
argument determines how this result is computed, and should be one of ExactKernel
, FastKernel
, and AdaptiveKernel
(the default). See the documentation for more information about these choices.
DelaunayTriangulation.polygonise
— Methodpolygonise(points, boundary_nodes, boundary_curves; n=4096)
Fills out a set of points for a curve-bounded domain for use with PolygonHierarchy
.
If the boundary curves are complicated so that they take a lot of points in order to be accurately resolved, then you should increase n
.
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 withnew_points
.
If the boundary is not curve bounded, then new_points
and new_boundary_nodes
remain aliased with the input points
and boundary_nodes
.
DelaunayTriangulation.reorient_edge
— Methodreorient_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.
DelaunayTriangulation.replace_next_edge!
— Methodreplace_next_edge!(enricher::BoundaryEnricher, apex, complex_id, member_id, next_edge)
Replaces the next edge of the member_id
th member of the complex_id
th complex associated with apex
with next_edge
.
DelaunayTriangulation.replace_next_edge!
— Methodreplace_next_edge!(complex::SmallAngleComplex, member_id, next_edge)
Replaces the next edge of the member_id
th member of complex
with next_edge
.
See also replace_next_edge
.
DelaunayTriangulation.replace_next_edge
— Methodreplace_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.
DelaunayTriangulation.set_parent!
— Methodset_parent!(boundary_enricher::BoundaryEnricher, i, j, k)
Sets the parent of the edge (i, j)
in boundary_enricher
to k
.
DelaunayTriangulation.sort_members!
— Methodsort_members!(complex::SmallAngleComplex, points)
Sorts the members of complex
in a counter-clockwise order around the apex of complex
.
DelaunayTriangulation.split_boundary_edge!
— Functionsplit_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 r
th 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). Note that not updating the boundary nodes also implies that the boundary_edge_map
will not be updated.
DelaunayTriangulation.split_edge!
— Functionsplit_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 r
th 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!
.
DelaunayTriangulation.split_interior_segment!
— Functionsplit_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 r
th 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).
DelaunayTriangulation.update_parent_map!
— Methodupdate_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.
AbstractEach(Vertex/Edge/Triangle) Iterators
We use a variety of iterators for iterating over the vertices, edges, and triangles of a triangulation.
DelaunayTriangulation.AbstractEachEdge
— TypeAbstractEachEdge{E}
An abstract type for an iterator over edges in a triangulation.
DelaunayTriangulation.AbstractEachTriangle
— TypeAbstractEachTriangle{T}
An abstract type for an iterator over triangles in a triangulation.
DelaunayTriangulation.AbstractEachVertex
— TypeAbstractEachVertex{V}
An abstract type for an iterator over vertices in a triangulation.
DelaunayTriangulation.EachGhostEdge
— TypeEachGhostEdge{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.
DelaunayTriangulation.EachGhostTriangle
— TypeEachGhostTriangle{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.
DelaunayTriangulation.EachGhostVertex
— TypeEachGhostVertex{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.
DelaunayTriangulation.EachSolidEdge
— TypeEachSolidEdge{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.
DelaunayTriangulation.EachSolidTriangle
— TypeEachSolidTriangle{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.
DelaunayTriangulation.EachSolidVertex
— TypeEachSolidVertex{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.
DelaunayTriangulation.each_edge
— Methodeach_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
.
DelaunayTriangulation.each_ghost_edge
— Methodeach_ghost_edge(tri::Triangulation) -> Edges
Returns an iterator over all ghost edges in tri
.
See also each_edge
and each_solid_edge
.
DelaunayTriangulation.each_ghost_triangle
— Methodeach_ghost_triangle(tri::Triangulation) -> Triangles
Returns an iterator over all ghost triangles in tri
.
See also each_triangle
and each_solid_triangle
.
DelaunayTriangulation.each_ghost_vertex
— Methodeach_ghost_vertex(tri::Triangulation) -> Set{Vertex}
Returns an iterator over all ghost vertices in tri
.
See also each_vertex
and each_solid_vertex
.
DelaunayTriangulation.each_point
— Methodeach_point(tri::Triangulation) -> Points
Returns an iterator over all points in tri
.
If tri
has vertices that are not yet present in the triangulation, e.g. if you have deleted vertices or have some submerged vertices in a weighted triangulation, then the corresponding points will still be present in this iterator. It is recommended that you instead consider each_vertex
, each_solid_vertex
, or each_ghost_vertex
together with get_point
to get the coordinates.
DelaunayTriangulation.each_point_index
— Methodeach_point_index(tri::Triangulation) -> Indices
Returns an iterator over all point indices in tri
.
If tri
has vertices that are not yet present in the triangulation, e.g. if you have deleted vertices or have some submerged vertices in a weighted triangulation, then the corresponding point indices will still be present in this iterator. It is recommended that you instead consider each_vertex
, each_solid_vertex
, or each_ghost_vertex
.
DelaunayTriangulation.each_solid_edge
— Methodeach_solid_edge(tri::Triangulation) -> Edges
Returns an iterator over all solid edges in tri
.
See also each_edge
and each_ghost_edge
.
DelaunayTriangulation.each_solid_triangle
— Methodeach_solid_triangle(tri::Triangulation) -> Triangles
Returns an iterator over all solid triangles in tri
.
See also each_triangle
and each_ghost_triangle
.
DelaunayTriangulation.each_solid_vertex
— Methodeach_solid_vertex(tri::Triangulation) -> Set{Vertex}
Returns an iterator over all solid vertices in tri
.
See also each_vertex
and each_ghost_vertex
.
DelaunayTriangulation.each_triangle
— Methodeach_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
.
DelaunayTriangulation.each_vertex
— Methodeach_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
We provide a means for storing the history of triangles encountered during point location, using a PointLocationHistory
struct. The main motivation for this struct is for constrained triangulations.
DelaunayTriangulation.PointLocationHistory
— TypePointLocationHistory{T,E,I}
History from using find_triangle
.
Fields
triangles::Vector{T}
: The visited triangles.collinear_segments::Vector{E}
: Segments collinear with the original linepq
using to jump.collinear_point_indices::Vector{I}
: This field contains indices to segments incollinear_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 ofpq
.right_verices::Vector{I}
: Vertices from the visited triangles to the right ofpq
.
DelaunayTriangulation.add_edge!
— Methodadd_edge!(history::PointLocationHistory{T,E}, i, j)
Adds the edge (i, j)
to the collinear_segments
field of history
.
DelaunayTriangulation.add_index!
— Methodadd_index!(history::PointLocationHistory, i)
Adds the index i
to the collinear_point_indices
field of history
.
DelaunayTriangulation.add_left_vertex!
— Methodadd_left_vertex!(history::PointLocationHistory, i)
Adds the vertex i
to the left_vertices
field of history
.
DelaunayTriangulation.add_right_vertex!
— Methodadd_right_vertex!(history::PointLocationHistory, j)
Adds the vertex j
to the right_vertices
field of history
.
DelaunayTriangulation.add_triangle!
— Methodadd_triangle!(history::PointLocationHistory, i, j, k)
Adds the triangle (i, j, k)
to the triangles
field of history
.
DelaunayTriangulation.num_edges
— Methodnum_edges(history::PointLocationHistory) -> Integer
Returns the number of edges in history.collinear_segments
.
IndividualTriangleStatistics
We provide an IndividualTriangleStatistics
struct for storing statistics about individual triangles in a triangulation. This struct is in the public API, as listed in the API.
DelaunayTriangulation.IndividualTriangleStatistics
— TypeIndividualTriangleStatistics{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
DelaunayTriangulation.distance_to_offcenter
— Methoddistance_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 β
.
DelaunayTriangulation.make_shortest_edge_first
— Methodmake_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)
.
DelaunayTriangulation.min_med_max
— Methodmin_med_max(a, b, c) -> (Number, Number, Number)
Returns the arguments in sorted order.
DelaunayTriangulation.select_shortest_edge_for_offcenter
— Methodselect_shortest_edge_for_offcenter(p, q, r, c, ℓ²) -> (NTuple{2, Number}, NTuple{2, Number}, NTuple{2, Number})
Given a triangle (p, q, r)
with more than one edge attaining the shortest length, selects the appropriate shortest edge for triangle_offcenter
.
Arguments
p
: The first vertex of the triangle.q
: The second vertex of the triangle.r
: The third vertex of the triangle.c
: The circumcenter of the triangle.ℓ²
: The squared shortest edge length.
The arguments should be so that (p, q, r)
is positively oriented and ℓ² = |p - q|²
is the squared shortest edge length.
Outputs
u
: The first vertex of the rotated triangle.v
: The second vertex of the rotated triangle.w
: The third vertex of the rotated triangle.
These outputs (u, v, w)
are a permutation of (p, q, r)
(maintaining positive orientation) such that |m - c₁|
is maximised over all other shortest edges, where m = (u + v)/2
. If there is no unique maximiser, then the output is the permutation that is lexicographically smallest (i.e., sorted by x and then by y).
DelaunayTriangulation.squared_triangle_lengths
— Methodsquared_triangle_lengths(p, q, r) -> (Number, Number, Number)
Computes the squared lengths of the edges of the triangle with coordinates p
, q
, r
. The squared lengths are returned in sorted order.
DelaunayTriangulation.squared_triangle_lengths_and_smallest_index
— Methodsquared_triangle_lengths_and_smallest_index(p, q, r) -> (Number, Number, Number, Integer)
Computes the squared lengths of the edges of the triangle with coordinates p
, q
, r
. The squared lengths are returned in sorted order, and the index of the shortest edge is returned as well. Here, the index refers to which edge in the order (p, q)
, (q, r)
, (q, p)
.
DelaunayTriangulation.triangle_angles
— Methodtriangle_angles(p, q, r) -> (Number, Number, Number)
Computes the angles of a triangle with vertices p
, q
, and r
. The formula for, say, the angle at p
is given by
\[\theta_1 = \arctan\left(\dfrac{2A}{\left(p - q\right)\cdot\left(p - r\right)}\right),\]
where A
is the area of the triangle. The angles are returned in sorted order.
DelaunayTriangulation.triangle_area
— Methodtriangle_area(p, q, r) -> Number
Returns the signed area of a triangle (p, q, r)
. The area is positive if (p, q, r)
is positively oriented.
DelaunayTriangulation.triangle_area
— Methodtriangle_area(ℓ₁²::Number, ℓ₂²::Number, ℓ₃²::Number) -> Number
Compute the area of a triangle given the squares of its edge lengths. The edges should be sorted so that ℓ₁² ≤ ℓ₂² ≤ ℓ₃²
. If there are precision issues that cause the area to be negative, then the area is set to zero.
DelaunayTriangulation.triangle_aspect_ratio
— Methodtriangle_aspect_ratio(p, q, r) -> Number
Computes the aspect ratio of the triangle with coordinates (p, q, r)
.
DelaunayTriangulation.triangle_aspect_ratio
— Methodtriangle_aspect_ratio(inradius::Number, circumradius::Number) -> Number
Computes the aspect ratio of a triangle with inradius inradius
and circumradius circumradius
. The aspect ratio is given by
\[\tau = \dfrac{r_i}{r},\]
where $r_i$ is the inradius and $r$ is the circumradius.
DelaunayTriangulation.triangle_centroid
— Methodtriangle_centroid(p, q, r) -> (Number, Number)
Computes the centroid of a triangle with vertices p
, q
, and r
, given by
\[c = \dfrac{p + q + r}{3}.\]
DelaunayTriangulation.triangle_circumcenter
— Functiontriangle_circumcenter(p, q, r, A=triangle_area(p, q, r)) -> (Number, Number)
Computes the circumcenter of the triangle with coordinates (p, q, r)
. The circumcenter is given by
\[c_x = r_x + \dfrac{d_{11}d_{22} - d_{12}d_{21}}{4A}, \quad c_y = r_y + \dfrac{e_{11}e_{22} - e_{12}e_{21}}{4A},\]
where $d_{11} = \|p - r\|_2^2$, $d_{12} = p_y - r_y$, $d_{21} = \|q - r\|_2^2$, $d_{22} = q_y - r_y$, $e_{11} = p_x - r_x$ $e_{12} = d_{11}$, $e_{21} = q_x - r_x$, and $e_{22} = d_{21}$.
DelaunayTriangulation.triangle_circumcenter
— Methodtriangle_circumcenter(tri::Triangulation, T) -> (Number, Number)
Computes the circumcenter of the triangle T
in the triangulation tri
.
DelaunayTriangulation.triangle_circumradius
— Methodtriangle_circumradius(A, ℓmin², ℓmed², ℓmax²) -> Number
Computes the circumradius of a triangle with area A
and squared edge lengths ℓmin² ≤ ℓmed² ≤ ℓmax²
. The circumradius is given by
\[r = \dfrac{\ell_{\min}\ell_{\text{med}}\ell_{\max}}{4A}.\]
DelaunayTriangulation.triangle_circumradius
— Methodtriangle_circumradius(p, q, r) -> Number
Computes the circumradius of the triangle with coordinates (p, q, r)
.
DelaunayTriangulation.triangle_edge_midpoints
— Methodtriangle_edge_midpoints(p, q, r) -> (Number, Number), (Number, Number), (Number, Number)
Computes the midpoints of the edges of the triangle with coordinates (p, q, r)
.
DelaunayTriangulation.triangle_inradius
— Methodtriangle_inradius(p, q, r) -> Number
Computes the inradius of the triangle with coordinates (p, q, r)
.
DelaunayTriangulation.triangle_inradius
— Methodtriangle_inradius(A, perimeter) -> Number
Computes the inradius of a triangle with area A
and perimeter perimeter
. The inradius is given by
\[r_i = \dfrac{2A}{P},\]
where $P$ is the perimeter
.
DelaunayTriangulation.triangle_lengths
— Methodtriangle_lengths(p, q, r) -> (Number, Number, Number)
Computes the lengths of the edges of the triangle with coordinates p
, q
, r
. The lengths are returned in sorted order.
DelaunayTriangulation.triangle_offcenter
— Functiontriangle_offcenter(p, q, r, c₁=triangle_circumcenter(p, q, r), β=1.0) -> (Number, Number)
Computes the off-center of the triangle (p, q, r)
.
Arguments
p
,q
,r
: The coordinates of the triangle, given in counter-clockwise order.c₁=triangle_circumcenter(p, q, r)
: The circumcenter of the triangle.β=1.0
: The radius-edge ratio cutoff.
Output
cx
: The x-coordinate of the off-center.cy
: The y-coordinate of the off-center.
In the original paper, the off-center is defined to instead be the circumcenter if it the triangle pqc₁
has radius-edge ratio less than β
. Here, we just let the off-center be the point c
so that pqc
has radius-edge ratio of exactly β
.
DelaunayTriangulation.triangle_orthocenter
— Methodtriangle_orthocenter(tri::Triangulation, T) -> NTuple{2, Number}
Finds the triangle orthocenter of T
. In particular, the point (ox, oy)
equidistant from each of the points of T
with respect to the power distance.
DelaunayTriangulation.triangle_orthoradius_squared
— Methodtriangle_orthoradius_squared(p, q, r, a, b, c) -> Number
Computes the squared orthoradius of the triangle (p, q, r)
with weights a
, b
, and c
. Note that this number may be negative.
DelaunayTriangulation.triangle_perimeter
— Methodtriangle_perimeter(p, q, r) -> Number
Computes the perimeter of the triangle with coordinates (p, q, r)
.
DelaunayTriangulation.triangle_perimeter
— Methodtriangle_perimeter(ℓmin::Number, ℓmed::Number, ℓmax::Number) -> Number
Computes the perimeter of a triangle with edge lengths ℓmin ≤ ℓmed ≤ ℓmax
. The perimeter is given by
\[P = \ell_{\min} + \ell_{\text{med}} + \ell_{\max}.\]
DelaunayTriangulation.triangle_radius_edge_ratio
— Methodtriangle_radius_edge_ratio(p, q, r) -> Number
Computes the radius-edge ratio of the triangle with coordinates (p, q, r)
.
DelaunayTriangulation.triangle_radius_edge_ratio
— Methodtriangle_radius_edge_ratio(circumradius::Number, ℓmin::Number) -> Number
Computes the radius-edge ratio of a triangle with circumradius circumradius
and minimum edge length ℓmin
, given by
\[\rho = \dfrac{r}{\ell_{\min}},\]
where $r$ is the circumradius and $\ell_{\min}$ is the shortest edge length.
DelaunayTriangulation.triangle_sink
— Functiontriangle_sink(tri::Triangulation, T; predicates::AbstractPredicateKernel=AdaptiveKernel()) -> (Number, Number)
Computes the sink of the triangle T
in tri
. See this paper for more information. Use the predicates
argument to control how predicates are computed.
Extended help
Sinks were introduced in this paper. For a given triangle T
, the sink of T
is defined as follows:
- If
c
, the circumcenter ofT
, is in the interior ofT
, then the sink ofT
isT
. - If
T
is a boundary triangle, then the sink ofT
isT
. - If neither 1 or 2, then the sink is defined as the sink of the triangle
V
, whereV
is the triangle adjoining the edge ofT
which intersects the linemc
, wherem
is the centroid ofT
.
In cases where the triangulation has holes, this definition can lead to loops. In such a case, we just pick one of the triangles in the loop as the sink triangle.
TriangulationStatistics
We also provide a function for computing statistics about a triangulation, using the TriangulationStatistics
struct. This struct is in the public API, as listed in the API.
DelaunayTriangulation.TriangulationStatistics
— TypeTriangulationStatistics{T,V,I}
A struct containing statistics about a triangulation.
Fields
num_vertices::I
: The number of vertices in the triangulation.num_solid_vertices::I
: The number of solid vertices in the triangulation.num_ghost_vertices::I
: The number of ghost vertices in the triangulation.num_edges::I
: The number of edges in the triangulation.num_solid_edges::I
: The number of solid edges in the triangulation.num_ghost_edges::I
: The number of ghost edges in the triangulation.num_triangles::I
: The number of triangles in the triangulation.num_solid_triangles::I
: The number of solid triangles in the triangulation.num_ghost_triangles::I
: The number of ghost triangles in the triangulation.num_boundary_segments::I
: The number of boundary segments in the triangulation.num_interior_segments::I
: The number of interior segments in the triangulation.num_segments::I
: The number of segments in the triangulation.num_convex_hull_vertices::I
: The number of vertices on the convex hull of the triangulation.smallest_angle::V
: The smallest angle in the triangulation.largest_angle::V
: The largest angle in the triangulation.smallest_area::V
: The smallest area of a triangle in the triangulation.largest_area::V
: The largest area of a triangle in the triangulation.smallest_radius_edge_ratio::V
: The smallest radius-edge ratio of a triangle in the triangulation.largest_radius_edge_ratio::V
: The largest radius-edge ratio of a triangle in the triangulation.area::V
: The total area of the triangulation.individual_statistics::Dict{T,IndividualTriangleStatistics{V}}
: A map from triangles in the triangulation to their individual statistics. SeeIndividualTriangleStatistics
.
Constructors
To construct these statistics, use statistics
, which you call as statistics(tri::Triangulation)
.
DelaunayTriangulation.get_all_stat
— Methodget_all_stat(stats::TriangulationStatistics, stat::Symbol) -> Vector
Returns a vector of the statistic stat
for each triangle in stats
.
DelaunayTriangulation.get_angles
— Methodget_angles(stats::TriangulationStatistics, T)
Returns the angles field from the individual triangle statistics for the triangle T
in the TriangulationStatistics
stats
.
DelaunayTriangulation.get_area
— Methodget_area(stats::TriangulationStatistics, T)
Returns the area field from the individual triangle statistics for the triangle T
in the TriangulationStatistics
stats
.
DelaunayTriangulation.get_area
— Methodget_area(stats::TriangulationStatistics)
Returns the area field from the TriangulationStatistics
stats
.
DelaunayTriangulation.get_aspect_ratio
— Methodget_aspect_ratio(stats::TriangulationStatistics, T)
Returns the aspect_ratio field from the individual triangle statistics for the triangle T
in the TriangulationStatistics
stats
.
DelaunayTriangulation.get_centroid
— Methodget_centroid(stats::TriangulationStatistics, T)
Returns the centroid field from the individual triangle statistics for the triangle T
in the TriangulationStatistics
stats
.
DelaunayTriangulation.get_circumcenter
— Methodget_circumcenter(stats::TriangulationStatistics, T)
Returns the circumcenter field from the individual triangle statistics for the triangle T
in the TriangulationStatistics
stats
.
DelaunayTriangulation.get_circumradius
— Methodget_circumradius(stats::TriangulationStatistics, T)
Returns the circumradius field from the individual triangle statistics for the triangle T
in the TriangulationStatistics
stats
.
DelaunayTriangulation.get_edge_midpoints
— Methodget_edge_midpoints(stats::TriangulationStatistics, T)
Returns the edge_midpoints field from the individual triangle statistics for the triangle T
in the TriangulationStatistics
stats
.
DelaunayTriangulation.get_individual_statistics
— Methodget_individual_statistics(stats::TriangulationStatistics)
Returns the individual_statistics field from the TriangulationStatistics
stats
.
DelaunayTriangulation.get_inradius
— Methodget_inradius(stats::TriangulationStatistics, T)
Returns the inradius field from the individual triangle statistics for the triangle T
in the TriangulationStatistics
stats
.
DelaunayTriangulation.get_largest_angle
— Methodget_largest_angle(stats::TriangulationStatistics)
Returns the largest_angle field from the TriangulationStatistics
stats
.
DelaunayTriangulation.get_largest_area
— Methodget_largest_area(stats::TriangulationStatistics)
Returns the largest_area field from the TriangulationStatistics
stats
.
DelaunayTriangulation.get_largest_radius_edge_ratio
— Methodget_largest_radius_edge_ratio(stats::TriangulationStatistics)
Returns the largestradiusedge_ratio field from the TriangulationStatistics
stats
.
DelaunayTriangulation.get_lengths
— Methodget_lengths(stats::TriangulationStatistics, T)
Returns the lengths field from the individual triangle statistics for the triangle T
in the TriangulationStatistics
stats
.
DelaunayTriangulation.get_maximum_angle
— Methodget_maximum_angle(stats::TriangulationStatistics, T) -> Float64
Returns the maximum angle of T
from stats
.
DelaunayTriangulation.get_median_angle
— Methodget_median_angle(stats::TriangulationStatistics, T) -> Float64
Returns the median angle of T
from stats
.
DelaunayTriangulation.get_minimum_angle
— Methodget_minimum_angle(stats::TriangulationStatistics, T) -> Float64
Returns the minimum angle of T
from stats
.
DelaunayTriangulation.get_offcenter
— Methodget_offcenter(stats::TriangulationStatistics, T)
Returns the offcenter field from the individual triangle statistics for the triangle T
in the TriangulationStatistics
stats
.
DelaunayTriangulation.get_perimeter
— Methodget_perimeter(stats::TriangulationStatistics, T)
Returns the perimeter field from the individual triangle statistics for the triangle T
in the TriangulationStatistics
stats
.
DelaunayTriangulation.get_radius_edge_ratio
— Methodget_radius_edge_ratio(stats::TriangulationStatistics, T)
Returns the radiusedgeratio field from the individual triangle statistics for the triangle T
in the TriangulationStatistics
stats
.
DelaunayTriangulation.get_sink
— Methodget_sink(stats::TriangulationStatistics, T)
Returns the sink field from the individual triangle statistics for the triangle T
in the TriangulationStatistics
stats
.
DelaunayTriangulation.get_smallest_angle
— Methodget_smallest_angle(stats::TriangulationStatistics)
Returns the smallest_angle field from the TriangulationStatistics
stats
.
DelaunayTriangulation.get_smallest_area
— Methodget_smallest_area(stats::TriangulationStatistics)
Returns the smallest_area field from the TriangulationStatistics
stats
.
DelaunayTriangulation.get_smallest_radius_edge_ratio
— Methodget_smallest_radius_edge_ratio(stats::TriangulationStatistics)
Returns the smallestradiusedge_ratio field from the TriangulationStatistics
stats
.
DelaunayTriangulation.num_boundary_segments
— Methodnum_boundary_segments(stats::TriangulationStatistics)
Returns the numboundarysegments field from the TriangulationStatistics` stats
.
DelaunayTriangulation.num_convex_hull_vertices
— Methodnum_convex_hull_vertices(stats::TriangulationStatistics)
Returns the numconvexhull_vertices field from the TriangulationStatistics` stats
.
DelaunayTriangulation.num_edges
— Methodnum_edges(stats::TriangulationStatistics)
Returns the num_edges field from the TriangulationStatistics` stats
.
DelaunayTriangulation.num_ghost_edges
— Methodnum_ghost_edges(stats::TriangulationStatistics)
Returns the numghostedges field from the TriangulationStatistics` stats
.
DelaunayTriangulation.num_ghost_triangles
— Methodnum_ghost_triangles(stats::TriangulationStatistics)
Returns the numghosttriangles field from the TriangulationStatistics` stats
.
DelaunayTriangulation.num_ghost_vertices
— Methodnum_ghost_vertices(stats::TriangulationStatistics)
Returns the numghostvertices field from the TriangulationStatistics` stats
.
DelaunayTriangulation.num_interior_segments
— Methodnum_interior_segments(stats::TriangulationStatistics)
Returns the numinteriorsegments field from the TriangulationStatistics` stats
.
DelaunayTriangulation.num_segments
— Methodnum_segments(stats::TriangulationStatistics)
Returns the num_segments field from the TriangulationStatistics` stats
.
DelaunayTriangulation.num_solid_edges
— Methodnum_solid_edges(stats::TriangulationStatistics)
Returns the numsolidedges field from the TriangulationStatistics` stats
.
DelaunayTriangulation.num_solid_triangles
— Methodnum_solid_triangles(stats::TriangulationStatistics)
Returns the numsolidtriangles field from the TriangulationStatistics` stats
.
DelaunayTriangulation.num_solid_vertices
— Methodnum_solid_vertices(stats::TriangulationStatistics)
Returns the numsolidvertices field from the TriangulationStatistics` stats
.
DelaunayTriangulation.num_triangles
— Methodnum_triangles(stats::TriangulationStatistics)
Returns the num_triangles field from the TriangulationStatistics` stats
.
DelaunayTriangulation.num_vertices
— Methodnum_vertices(stats::TriangulationStatistics)
Returns the num_vertices field from the TriangulationStatistics` stats
.
DelaunayTriangulation.statistics
— Methodstatistics(tri::Triangulation) -> TriangulationStatistics
Returns a TriangulationStatistics
object containing statistics about the triangulation tri
.
InsertionEventHistory
For mesh refinement we need a way to identify what happens to a triangulation after a point is added, in case we need to reverse the insertion. For this, we use InsertionEventHistory
internally.
DelaunayTriangulation.InsertionEventHistory
— TypeInsertionEventHistory{T,E}
A data structure for storing the changes to the triangulation during the insertion of a point.
Fields
added_triangles::Set{T}
: The triangles that were added.deleted_triangles::Set{T}
: The triangles that were deleted.added_segments::Set{E}
: The interior segments that were added.deleted_segments::Set{E}
: The interior segments that were deleted.added_boundary_segments::Set{E}
: The boundary segments that were added.deleted_boundary_segments::Set{E}
: The boundary segments that were deleted.
Constructor
The default constructor is available, but we also provide
InsertionEventHistory(tri::Triangulation)
which will initialise this struct with empty, appropriately sizehint!
ed, sets.
Base.empty!
— Methodempty!(events::InsertionEventHistory)
Empties events
by emptying all of its fields.
DelaunayTriangulation.add_edge!
— Methodadd_edge!(events::InsertionEventHistory, e)
Add the edge e
to the added_segments
of events
.
DelaunayTriangulation.add_triangle!
— Methodadd_triangle!(events::InsertionEventHistory, T)
Add the triangle T
to the added_triangles
of events
.
DelaunayTriangulation.delete_edge!
— Methoddelete_edge!(events::InsertionEventHistory, e)
Add the edge e
to the deleted_segments
of events
.
DelaunayTriangulation.delete_triangle!
— Methoddelete_triangle!(events::InsertionEventHistory, T)
Add the triangle T
to the deleted_triangles
of events
.
DelaunayTriangulation.each_added_boundary_segment
— Methodeach_added_boundary_segment(events::InsertionEventHistory) -> Iterator
Returns an iterator over the boundary segments that were added to the triangulation during the insertion of a point.
DelaunayTriangulation.each_added_segment
— Methodeach_deleted_triangle(events::InsertionEventHistory) -> Iterator
Returns an iterator over the triangles that were deleted from the triangulation during the insertion of a point.
DelaunayTriangulation.each_added_triangle
— Methodeach_added_triangle(events::InsertionEventHistory) -> Iterator
Returns an iterator over the triangles that were added to the triangulation during the insertion of a point.
DelaunayTriangulation.has_segment_changes
— Methodhas_triangle_changes(events::InsertionEventHistory) -> Bool
Returns true
if there are any changes to the segments in events
, and false
otherwise.
DelaunayTriangulation.split_boundary_edge!
— Methodsplit_boundary_edge!(events::InsertionEventHistory, u, v, new_point)
Add the edge (u, v)
to the deleted_boundary_segments
of events
and add the edges (u, new_point)
and (new_point, v)
to the added_boundary_segments
of events
.
DelaunayTriangulation.triangle_type
— Methodtriangle_type(::InsertionEventHistory{T}) where {T} = T
Returns the type of the triangles in events
, T
.
DelaunayTriangulation.undo_boundary_segment_changes!
— Methodundo_boundary_segment_changes!(tri::Triangulation, events::InsertionEventHistory)
Undoes any changes to the boundary segments in tri
that were made after an insertion event, as recorded in events
, assuming the inserted vertex is num_points(tri)
.
DelaunayTriangulation.undo_insertion!
— Functionundo_insertion!(tri::Triangulation, events::InsertionEventHistory, pop=Val(true))
Undoes the insertion of the most recent vertex into tri
, assuming that its insertion history has been recorded into events
and the vertex is num_points(tri)
.
If you do not want to delete the latest vertex from the triangulation, set pop
to Val(false)
.
DelaunayTriangulation.undo_segment_changes!
— Methodundo_segment_changes!(tri::Triangulation, events::InsertionEventHistory)
Undoes any changes to the segments in tri
that were made after an insertion event, as recorded in events
.
RefinementConstraints
For mesh refinement, internally we store the user-provided constraints inside their own struct RefinementConstraints
.
DelaunayTriangulation.RefinementConstraints
— TypeRefinementConstraints{F}
A struct for storing constraints for mesh refinement.
Fields
min_angle=0.0
: The minimum angle of a triangle.max_angle=180.0
: The maximum angle of a triangle.min_area=0.0
: The minimum area of a triangle.max_area=Inf
: The maximum area of a triangle.max_radius_edge_ratio=csd(min_angle) / 2
: The maximum radius-edge ratio of a triangle. This is computed frommin_angle
- you cannot provide a value for it yourself.max_points=typemax(Int)
: The maximum number of vertices allowed in the triangulation. Note that this refers tonum_solid_vertices
, not the amount returned bynum_points
.seiditous_angle=20.0
: The inter-segment angle used to define seditious edges in degrees. Should not be substantially smaller than 20.0° or any greater than 60.0°.custom_constraint::F=(tri, triangle) -> false
: A custom constraint function. This should take aTriangulation
and atriangle
as arguments, and returntrue
if thetriangle
violates the constraints andfalse
otherwise.
DelaunayTriangulation.has_max_angle_constraint
— Methodhas_max_angle_constraint(constraints::RefinementConstraints) -> Bool
Return true
if constraints
has a maximum angle constraint, false
otherwise.
DelaunayTriangulation.violates_custom_constraint
— Methodviolates_custom_constraint(constraints::RefinementConstraints{F}, tri::Triangulation, T) where {F} -> Bool
Return true
if T
violates the custom constraint in constraints
, false
otherwise.
RefinementQueue
The mesh refinement algorithm we use requires a method for prioritising which segments and triangles need to be split. Using a MaxPriorityQueue
, so that large segments and large triangles are prioritised, we use a RefinementQueue
internally to determine this ordering.
DelaunayTriangulation.RefinementQueue
— TypeRefinementQueue{T,E,F}
Struct defining a pair of priority queues for encroached segments and poor-quality triangles.
Fields
segments::MaxPriorityQueue{E,F}
: A priority queue of encroached segments, where the priorities are the squared edge lengths.triangles::MaxPriorityQueue{T,F}
: A priority queue of poor-quality triangles, where the priorities are the radius-edge ratios.
Constructor
The default constructor is available, but we also provide
RefinementQueue(tri::Triangulation)
which will initialise this struct with empty queues with the appropriate types.
Base.getindex
— Methodgetindex(queue::RefinementQueue{T,E,F}, triangle::T) -> F
queue[triangle] -> F
Return the radius-edge ratio of triangle
in queue
.
Base.haskey
— Methodhaskey(queue::RefinementQueue{T,E,F}, segment::E) -> Bool
Return true
if queue
has segment
or its reverse, and false
otherwise.
Base.haskey
— Methodhaskey(queue::RefinementQueue{T,E,F}, triangle::T) -> Bool
Return true
if queue
has triangle
or any of its counter-clockwise rotations, and false
otherwise.
Base.isempty
— Methodisempty(queue::RefinementQueue) -> Bool
Return true
if queue
has no segments or triangles, false
otherwise.
Base.setindex!
— MethodBassetindex!(queue::RefinementQueue{T,E,F}, ρ::F, triangle::T) where {T,E,F}
queue[triangle] = ρ
Add a triangle
to queue
whose radius-edge ratio is ρ
. If the triangle
is already in the queue
, its priority is updated to ρ
.
Base.setindex!
— Methodsetindex!(queue::RefinementQueue{T,E,F}, ℓ²::F, segment::E) where {T,E,F}
queue[segment] = ℓ²
Add a segment
to queue
whose squared length is ℓ²
. If the segment
is already in the queue
, its priority is updated to ℓ
.
DelaunayTriangulation.has_segments
— Methodhas_segments(queue::RefinementQueue) -> Bool
Return true
if queue
has any segments, false
otherwise.
DelaunayTriangulation.has_triangles
— Methodhas_triangles(queue::RefinementQueue) -> Bool
Return true
if queue
has any triangles, false
otherwise.
DelaunayTriangulation.popfirst_segment!
— Methodpopfirst_segment!(queue::RefinementQueue) -> Edge
Dequeue the next segment from queue
, returning the segment and its squared length.
DelaunayTriangulation.popfirst_triangle!
— Methodpopfirst_triangle!(queue::RefinementQueue) -> (Triangle, Number)
Dequeue the next triangle from queue
, returning the triangle and its radius-edge ratio.
RefinementArguments
There are many arguments that need to be passed around during mesh refinement. To simplify this, we use a RefinementArguments
struct internally.
DelaunayTriangulation.RefinementArguments
— TypeRefinementArguments{Q,C,H,I,E,T,R,P<:AbstractPredicateKernel}
A struct for storing arguments for mesh refinement.
Fields
queue::Q
: TheRefinementQueue
.constraints::C
: TheRefinementConstraints
.events::H
: TheInsertionEventHistory
.min_steiner_vertex::I
: The minimum vertex of a Steiner point. All vertices greater than or equal to this can be considered as Steiner vertices.segment_list::Set{E}
: The set of segments in the triangulation before refinement.segment_vertices::Set{I}
: Set of vertices that are vertices of segments insegment_list
.midpoint_split_list::Set{I}
: Set of vertices that are centre-splits of encroached edges.offcenter_split_list::Set{I}
: Set of vertices that are off-centre splits of encroached edges.use_circumcenter::Bool
: Whether to use circumcenters for Steiner points, or the more general approach of Erten and Üngör (2009).use_lens::Bool
: Whether to use diametral lens (true
) or diametral circles (false
) for the defining encroachment.steiner_scale::T
: The factor by which to scale the Steiner points closer to the triangle's shortest edge.locked_convex_hull::Bool
: Whether the convex hull of the triangulation had to be locked for refinement.had_ghosts::Bool
: Whether the triangulation initially had ghost triangles or not.rng::R
: The random number generator.concavity_protection::Bool
: Whether to use concavity protection or not forfind_triangle
. Most likely not needed, but may help in pathological cases.predicates::P<:AbstractPredicateKernel
: Method to use for computing predicates. Can be one ofFastKernel
,ExactKernel
, andAdaptiveKernel
. See the documentation for a further discussion of these methods.
Constructors
In addition to the default constructor, we provide
RefinementArguments(tri::Triangulation; kwargs...)
for constructing this struct. This constructor will lock the convex hull and add ghost triangles to tri
if needed (refine!
will undo these changes once the refinement is finished))
DelaunayTriangulation.RefinementArguments
— MethodRefinementArguments(tri::Triangulation; kwargs...) -> RefinementArguments
Initialises the RefinementArguments
for the given Triangulation
, tri
. The kwargs...
match those from refine!
.
If tri
has no ghost triangles, it will be mutated so that it has them. Similarly, if the triangulation has no constrained boundary, then the convex hull will be locked so that it is treated as a constrained boundary. These changes will be undone in refine!
once the refinement is finished.
DelaunayTriangulation.is_free
— Methodis_free(args::RefinementArguments, u) -> Bool
Returns true
if u
is a free vertex, and false
otherwise. A free vertex is a Steiner vertex (meaning a non-input vertex) that is not part of a segment or subsegment.
DelaunayTriangulation.is_midpoint_split
— Methodis_midpoint_split(args::RefinementArguments, u) -> Bool
Returns true
if u
is a midpoint of an encroached segment, and false
otherwise.
DelaunayTriangulation.is_offcenter_split
— Methodis_offcenter_split(args::RefinementArguments, u) -> Bool
Returns true
if u
is an off-centre split of an encroached segment, and false
otherwise.
DelaunayTriangulation.is_segment_vertex
— Methodis_segment_vertex(args::RefinementArguments, u) -> Bool
Returns true
if u
is a vertex of a segment, and false
otherwise. Note that this excludes vertices of subsegments.
DelaunayTriangulation.is_subsegment
— Methodis_subsegment(args::RefinementArguments, u, v) -> Bool
Returns true
if the edge (u, v)
is a subsegment, and false
otherwise.
DelaunayTriangulation.keep_iterating
— Methodkeep_iterating(tri::Triangulation, args::RefinementArguments) -> Bool
Returns true
if the refinement should continue, and false
otherwise. The check is based on whether the RefinementQueue
is empty or not, and whether the number of points in the triangulation is less than or equal to the maximum number of points allowed by the RefinementConstraints
.
DelaunayTriangulation.keep_splitting
— Methodkeep_splitting(tri::Triangulation, args::RefinementArguments) -> Bool
Returns true
if more encroached segments need to be split, and false
otherwise. The check is based on whether the segment queue in the RefinementQueue
of args
is empty or not, and whether the number of points in the triangulation is less than or equal to the maximum number of points allowed by the RefinementConstraints
in args
.
VoronoiTessellation
We use a VoronoiTessellation
struct to represent a Voronoi tessellation. This struct is in the public API.
DelaunayTriangulation.VoronoiTessellation
— TypeVoronoiTessellation{Tr<:Triangulation,P,I,T,S,E}
Struct for representing a Voronoi tessellation.
See also voronoi
.
Accessing the fields themselves using e.g. vorn.field
is not recommended and is not intended to be in the public API. You should be using the accessor functions, e.g. instead of vorn.adjacent
do get_adjacent(vorn)
. Similarly, for the iterators, e.g. vorn.generators
, each_generators(vorn)
is recommended instead.
In the case that the underlying triangulation is weighted, then this struct represents the power diagram, and instead of circumcenters the points are orthocenters computed with triangle_orthocenter
.
Fields
triangulation::Tr
: The underlying triangulation. The tessellation is dual to this triangulation, although if the underlying triangulation is constrained then this is no longer the case (but it is still used).generators::Dict{I,P}
: ADict
that maps vertices of generators to coordinates. These are simply the points present in the triangulation. ADict
is needed in case the triangulation is missing some points.polygon_points::Vector{P}
: The points defining the coordinates of the polygons. The points are not guaranteed to be unique if a circumcenter appears on the boundary or you are considering a clipped tessellation. (See alsoget_polygon_coordinates
.)polygons::Dict{I,Vector{I}}
: ADict
mapping polygon indices (which is the same as a generator vertex) to the vertices of a polygon. The polygons are given in counter-clockwise order and the first and last vertices are equal.circumcenter_to_triangle::Dict{I,T}
: ADict
mapping a circumcenter index to the triangle that contains it. The triangles are sorted such that the minimum vertex is last.triangle_to_circumcenter::Dict{T,I}
: ADict
mapping a triangle to its circumcenter index. The triangles are sorted such that the minimum vertex is last.unbounded_polygons::Set{I}
: ASet
of indices of the unbounded polygons.cocircular_circumcenters::S
: ASet
of indices of circumcenters that come from triangles that are cocircular with another triangle's vertices, and adjoin said triangles.adjacent::Adjacent{I,E}
: The adjacent map. This maps an oriented edge to the polygon that it belongs to.boundary_polygons::Set{I}
: ASet
of indices of the polygons that are on the boundary of the tessellation. Only relevant for clipped tessellations, otherwise seeunbounded_polygons
.
DelaunayTriangulation.add_adjacent!
— Methodadd_adjacent!(vor::VoronoiTessellation, ij, k)
add_adjacent!(vor::VoronoiTessellation, i, j, k)
Adds the adjacency relationship (i, j) ⟹ k
between the oriented edge (i, j)
and polygon index k
to the Voronoi tessellation vor
.
DelaunayTriangulation.add_boundary_polygon!
— Methodadd_boundary_polygon!(vor::VoronoiTessellation, i)
Adds the index i
to the set of boundary polygons of vor
.
DelaunayTriangulation.add_polygon!
— Methodadd_polygon!(vor::VoronoiTessellation, B, i)
Adds, or replaces, the polygon associated with the index i
with B
. B
should be a counter-clockwise sequence of vertices, with B[begin] == B[end]
.
DelaunayTriangulation.add_polygon_adjacent!
— Methodadd_polygon_adjacent!(vorn::VoronoiTessellation, polygon)
Adds the adjacent polygons of the boundary edges of the polygon polygon
to the adjacency list.
DelaunayTriangulation.add_unbounded_polygon!
— Methodadd_unbounded_polygon!(vor::VoronoiTessellation, i)
Adds the index i
to the set of unbounded polygons of vor
.
DelaunayTriangulation.convert_to_edge_adjoining_ghost_vertex
— Methodconvert_to_edge_adjoining_ghost_vertex(vorn::VoronoiTessellation, e) -> Edge
Returns the edge e
if it is not a boundary edge, and the edge reverse(e)
if it is a boundary edge.
See also is_boundary_edge
.
DelaunayTriangulation.delete_adjacent!
— Methoddelete_adjacent!(vor::VoronoiTessellation, ij)
delete_adjacent!(vor::VoronoiTessellation, i, j)
Deletes the edge (i, j)
from the adjacency map of vor
.
DelaunayTriangulation.delete_polygon_adjacent!
— Methoddelete_polygon!(vor::VoronoiTessellation, polygon)
Deletes the adjacent polygons of the boundary edges of the polygon polygon
from the adjacency list.
DelaunayTriangulation.delete_unbounded_polygon!
— Methoddelete_unbounded_polygon!(vor::VoronoiTessellation, i)
Deletes the index i
from the set of unbounded polygons of vor
.
DelaunayTriangulation.each_generator
— Methodeach_boundary_polygon(vorn::VoronoiTessellation) -> KeySet
Returns an iterator over the boundary polygon indices of vorn
.
DelaunayTriangulation.each_polygon
— Methodeach_polygon(vor::VoronoiTessellation) -> ValueIterator
Returns an iterator over each set of polygon vertices of vor
.
DelaunayTriangulation.each_polygon_index
— Methodeach_polygon_index(vor::VoronoiTessellation) -> KeySet
Returns an iterator over the polygon indices of vor
.
DelaunayTriangulation.each_polygon_vertex
— Methodeach_polygon_vertex(vor::VoronoiTessellation) -> UnitRange
Returns an iterator over each polygon point index of vor
.
DelaunayTriangulation.each_unbounded_polygon
— Methodeach_polygon(vor::VoronoiTessellation) -> Set
Returns an iterator over the polygon indices of vor
.
DelaunayTriangulation.edge_type
— Methodedge_type(vorn::VoronoiTessellation) -> DataType
Type used for representing individual edges in the Voronoi tessellation.
DelaunayTriangulation.get_adjacent
— Methodget_adjacent(vor::VoronoiTessellation, ij) -> Index
get_adjacent(vor::VoronoiTessellation, i, j) -> Index
Gets the polygon index associated with the oriented edge ij
in the Voronoi tessellation vor
.
DelaunayTriangulation.get_adjacent
— Methodget_adjacent(vorn::VoronoiTessellation) -> Adjacent{Index,Edge}
Gets the adjacency information of the Voronoi tessellation vorn
as an Adjacent
object. This object maps oriented edges to the polygons that they belong to.
DelaunayTriangulation.get_area
— Methodget_area(vor::VoronoiTessellation, i) -> Number
Gets the area of the i
th Voronoi polygon.
DelaunayTriangulation.get_boundary_polygons
— Methodget_boundary_polygons(vorn::VoronoiTessellation) -> Set{Index}
Gets the boundary polygons of the Voronoi tessellation vorn
as a Set
of polygon indices.
DelaunayTriangulation.get_centroid
— Methodget_centroid(vor::VoronoiTessellation, i) -> NTuple{2, Number}
Gets the centroid of the i
th Voronoi polygon, given as a Tuple
of the form (x, y)
.
DelaunayTriangulation.get_circumcenter_to_triangle
— Methodget_circumcenter_to_triangle(vor::VoronoiTessellation, i) -> Triangle
Gets the triangle associated with the i
th circumcenter. The triangle is sorted so that the minimum vertex is last.
DelaunayTriangulation.get_circumcenter_to_triangle
— Methodget_circumcenter_to_triangle(vorn::VoronoiTessellation) -> Dict{Index,Triangle}
Gets the circumcenters of the Voronoi tessellation vorn
as a Dict
, mapping circumcenter indices to their corresponding triangles. The triangles are sorted so that the minimum vertex is last.
DelaunayTriangulation.get_cocircular_circumcenters
— Methodget_cocircular_circumcenters(vorn::VoronoiTessellation) -> Set
Gets the cocircular circumcenters of the Voronoi tessellation vorn
as a Set
of circumcenter indices. These are circumcenters that come from triangles that are cocircular with another adjoining triangle.
DelaunayTriangulation.get_generator
— Methodget_generator(vor::VoronoiTessellation, i) -> NTuple{2, Number}
get_generator(vor::VoronoiTessellation, i...) -> NTuple{length(i), NTuple{2, Number}}
Gets the coordinates for the generators i...
, returned as Tuple
s of the form (x, y)
for each generator.
DelaunayTriangulation.get_generators
— Methodget_generators(vorn::VoronoiTessellation) -> Dict{Vertex,Point}
Gets the generators of the Voronoi tessellation vorn
as a Dict
, mapping vertices to their coordinates. These coordinates are given as Tuple
s of the form (x, y)
.
DelaunayTriangulation.get_neighbouring_boundary_edges
— Methodget_neighbouring_boundary_edges(vorn::VoronoiTessellation, e) -> (Edge, Edge)
Given a boundary edge e
, returns the edges left and right of e
.
DelaunayTriangulation.get_polygon
— Methodget_polygon(vor::VoronoiTessellation, i) -> Vector{Vertex}
Gets the vector of vertices corresponding to the i
th polygon, given in counter-clockwise order and with the first and last vertices equal. To obtain the coordinates, see get_polygon_point
.
DelaunayTriangulation.get_polygon_point
— Methodget_polygon_point(vor::VoronoiTessellation, i) -> NTuple{2, Number}
get_polygon_point(vor::VoronoiTessellation, i...) -> NTuple{length(i), NTuple{2, Number}}
Gets the coordinates corresponding to the vertices i...
of the polygons, returned as Tuple
s of the form (x, y)
for each vertex.
DelaunayTriangulation.get_polygon_points
— Methodget_polygon_points(vorn::VoronoiTessellation) -> Vector{Point}
Gets the polygon points of the Voronoi tessellation vorn
. These are the vertices of the Voronoi polygons, and are given as Tuple
s of the form (x, y)
.
DelaunayTriangulation.get_polygons
— Methodget_polygons(vorn::VoronoiTessellation) -> Dict{Index,Vector{Vertex}}
Gets the polygons of the Voronoi tessellation vorn
as a Dict
, mapping polygon indices to their vertices, where the vertices refer to points in get_polygon_points(vorn)
. The vertices are given in counter-clockwise order and the first and last vertices are equal.
DelaunayTriangulation.get_surrounding_polygon
— Methodget_surrounding_polygon(vor::VoronoiTessellation, i) -> Vector{Vertex}
Gets the polygon surrounding the generator with index i
in vor
.
You shouldn't need to use this, see get_polygon
instead.
DelaunayTriangulation.get_triangle_to_circumcenter
— Methodget_triangle_to_circumcenter(vor::VoronoiTessellation, T) -> Index
Gets the circumcenter index associated with the triangle T
. The triangle should be sorted so that the minimum vertex is last.
DelaunayTriangulation.get_triangle_to_circumcenter
— Methodget_triangle_to_circumcenter(vorn::VoronoiTessellation) -> Dict{Triangle,Index}
Gets the triangles of the Voronoi tessellation vorn
as a Dict
, mapping triangle indices to their corresponding circumcenters. The circumcenters are given as their vertices, referring to points in get_polygon_points(vorn)
.
DelaunayTriangulation.get_triangulation
— Methodget_triangulation(vorn::VoronoiTessellation) -> Triangulation
Gets the underlying triangulation of the Voronoi tessellation vorn
.
DelaunayTriangulation.get_unbounded_polygons
— Methodget_unbounded_polygons(vorn::VoronoiTessellation) -> Set{Index}
Gets the unbounded polygons of the Voronoi tessellation vorn
as a Set
of polygon indices.
DelaunayTriangulation.has_polygon
— Methodhas_polygon(vor::VoronoiTessellation, i) -> Bool
Returns true
if the Voronoi tessellation vor
has a polygon with index i
.
DelaunayTriangulation.integer_type
— Methodinteger_type(vorn::VoronoiTessellation) -> DataType
Type used for representing indices in the Voronoi tessellation.
DelaunayTriangulation.is_weighted
— Methodis_weighted(vorn::VoronoiTessellation) -> Bool
Returns true
if the Voronoi tessellation vorn
is weighted, and false
otherwise.
DelaunayTriangulation.num_generators
— Methodnum_generators(vor::VoronoiTessellation) -> Integer
Returns the number of generators in the Voronoi tessellation vor
.
DelaunayTriangulation.num_polygon_vertices
— Methodnum_polygon_vertices(vor::VoronoiTessellation) -> Integer
Returns the number of polygon vertices in the Voronoi tessellation vor
. This might include duplicate vertices if get_polygon_points(vor)
has duplicates.
DelaunayTriangulation.num_polygons
— Methodnum_polygons(vor::VoronoiTessellation) -> Integer
Returns the number of polygons in the Voronoi tessellation vor
.
DelaunayTriangulation.number_type
— Methodnumber_type(vorn::VoronoiTessellation) -> DataType
Type used for representing individual coordinates in the Voronoi tessellation.
DelaunayTriangulation.polygon_bounds
— Functionpolygon_bounds(vorn::VoronoiTessellation, unbounded_extension_factor=0.0; include_polygon_vertices=true) -> (Number, Number, Number, Number)
Gets the bounding box for the Voronoi tessellation vorn
.
Arguments
vorn::VoronoiTessellation
: The Voronoi tessellation.unbounded_extension_factor=0.0
: The factor by which to extend the bounding box for unbounded polygons.
Keyword Arguments
include_polygon_vertices=true
: Iftrue
, then the bounding box will also include the polygon vertices. Otherwise, only the generators are included.
Output
xmin
: Given byxmin′ - unbounded_extension_factor * (xmin′ - xmin′)
, wherexmin′
is the original minimumx
-coordinate of the computed bounding box and similarly forxmax′
.xmax
: Given byxmax′ + unbounded_extension_factor * (xmax′ - xmax′)
, wherexmax′
is the original maximumx
-coordinate of the computed bounding box and similarly forxmin′
.ymin
: Given byymin′ - unbounded_extension_factor * (ymin′ - ymin′)
, whereymin′
is the original minimumy
-coordinate of the computed bounding box and similarly forymax′
.ymax
: Given byymax′ + unbounded_extension_factor * (ymax′ - ymax′)
, whereymax′
is the original maximumy
-coordinate of the computed bounding box and similarly forymin′
.
DelaunayTriangulation.polygon_features
— Methodpolygon_features(vor::VoronoiTessellation, i) -> (Number, NTuple{2, Number})
Gets the area and centroid of the polygon with index i
in vor
.
DelaunayTriangulation.push_polygon_point!
— Methodpush_polygon_point!(vor::VoronoiTessellation, p)
push_polygon_point!(vor::VoronoiTessellation, x, y)
Adds the point p = (x, y)
into the vector of polygon points of vor
.
DelaunayTriangulation.triangle_type
— Methodtriangle_type(vorn::VoronoiTessellation) -> DataType
Type used for representing individual triangles in the Voronoi tessellation.
Polygon
We sometimes find it useful to use a specific Polygon
struct for representing polygons.
DelaunayTriangulation.Polygon
— TypePolygon{T,V,P} <: AbstractVector{T}
A struct for representing a polygon. The vertices
are to be a counter-clockwise list of integers, where the integers themselves refer to points in points
.
Fields
vertices::V
: A list of integers that refer to points inpoints
. The last vertex shokuld not be the same as the first.points::P
: A list of points.
In the case where vertices[begin] ≠ vertices[end]
, the vertices
field is exactly the same as the input vertices
. Where vertices[begin] = vertices[end]
, the vertices
field is a view of vertices
that excludes the last element.
ShuffledPolygonLinkedList
For computing constrained Delaunay triangulations, we use a ShuffledPolygonLinkedList
struct to store the polygons involved.
DelaunayTriangulation.ShuffledPolygonLinkedList
— TypeShuffledPolygonLinkedList{I,T}
Data structure for representing a polygon as a doubly-linked list. In the descriptions below, π
is used to denote the shuffled_indices
vector.
Fields
next::Vector{I}
: Thenext
vertices, so thatnext[π[i]]
is the vertex afterS[π[i]]
.prev::Vector{I}
: Theprev
vertices, so thatprev[π[i]]
is the vertex beforeS[π[i]]
.shuffled_indices::Vector{I}
: The shuffled indices of the vertices, so thatS[π[i]]
is thei
th vertex.k::I
: The number of vertices in the polygon.S::T
: The vertices of the polygon. This should not be a circular vector, i.e.S[begin] ≠ S[end]
, and must use one-based indexing. Additionally, the vertices must be provided in counter-clockwise order - this is NOT checked.
Constructor
To construct this, use
ShuffledPolygonLinkedList(S::Vector; rng::Random.AbstractRNG=Random.default_rng())
The argument rng
is used for shuffling the shuffled_indices
vector.
DelaunayTriangulation.delete_vertex!
— Methoddelete_vertex!(list::ShuffledPolygonLinkedList, i)
Deletes the vertex S[πᵢ]
from the linked list
, where πᵢ = list.shuffled_indices[i]
. This deletion is done symbolically rather than by mutating the vectors in list
. In particular, we perform
next[prev[πᵢ]] = next[πᵢ]
prev[next[πᵢ]] = prev[πᵢ]
which is the same as removing S[πᵢ]
from the linked list
.
DelaunayTriangulation.get_triplet
— Methodget_triplet(list::ShuffledPolygonLinkedList, i) -> (Vertex, Vertex, Vertex)
Returns (u, v, w) = (S[πᵢ], S[next[πᵢ]], S[prev[πᵢ]])
, where πᵢ = list.shuffled_indices[i]
and S = list.S
.
DelaunayTriangulation.reset!
— Methodreset!(list::ShuffledPolygonLinkedList; rng::Random.AbstractRNG=Random.default_rng())
Resets the linked list
, so that list.next[i] = mod1(i+1, list.k)
and list.prev[i] = mod1(i-1, list.k)
, and also reshuffles the list.shuffled_indices
vector.
DelaunayTriangulation.swap_permutation!
— Methodswap_permutation!(list::ShuffledPolygonLinkedList, i, j)
Reorders the permutation list.shuffled_indices
of the linked list
, swapping πᵢ
and πⱼ
where πₖ = list.shuffled_indices[k]
.
Points (Primitive Interface)
Here are functions that are used for defining and working with points in the package.
DelaunayTriangulation.set_point!
— Functionset_point!(points, i, x, y)
set_point!(points, i, p) = set_point!(points, i, getx(p), gety(p))
Sets the point at index i
in points
to (x, y)
.
Examples
julia> using DelaunayTriangulation
julia> points = [(1.0, 3.0), (5.0, 17.0)]
2-element Vector{Tuple{Float64, Float64}}:
(1.0, 3.0)
(5.0, 17.0)
julia> DelaunayTriangulation.set_point!(points, 1, 0.0, 0.0)
(0.0, 0.0)
julia> points
2-element Vector{Tuple{Float64, Float64}}:
(0.0, 0.0)
(5.0, 17.0)
julia> points = [1.0 2.0 3.0; 4.0 5.0 6.0]
2×3 Matrix{Float64}:
1.0 2.0 3.0
4.0 5.0 6.0
julia> DelaunayTriangulation.set_point!(points, 2, (17.3, 0.0))
2-element view(::Matrix{Float64}, :, 2) with eltype Float64:
17.3
0.0
julia> points
2×3 Matrix{Float64}:
1.0 17.3 3.0
4.0 0.0 6.0
DelaunayTriangulation.push_point!
— Functionpush_point!(points, x, y)
push_point!(points, p) = push_point!(points, getx(p), gety(p))
Pushes the point p = (x, y)
into points
.
Examples
julia> using DelaunayTriangulation
julia> points = [(1.0, 3.0), (5.0, 1.0)]
2-element Vector{Tuple{Float64, Float64}}:
(1.0, 3.0)
(5.0, 1.0)
julia> DelaunayTriangulation.push_point!(points, 2.3, 5.3)
3-element Vector{Tuple{Float64, Float64}}:
(1.0, 3.0)
(5.0, 1.0)
(2.3, 5.3)
julia> DelaunayTriangulation.push_point!(points, (17.3, 5.0))
4-element Vector{Tuple{Float64, Float64}}:
(1.0, 3.0)
(5.0, 1.0)
(2.3, 5.3)
(17.3, 5.0)
DelaunayTriangulation.pop_point!
— Functionpop_point!(points)
Pops the last point from points
.
Examples
julia> using DelaunayTriangulation
julia> points = [(1.0, 2.0), (1.3, 5.3)]
2-element Vector{Tuple{Float64, Float64}}:
(1.0, 2.0)
(1.3, 5.3)
julia> DelaunayTriangulation.pop_point!(points) # returns the popped vector
(1.3, 5.3)
julia> points
1-element Vector{Tuple{Float64, Float64}}:
(1.0, 2.0)
DelaunayTriangulation.num_points
— Functionnum_points(points) -> Integer
Returns the number of points in points
.
Examples
julia> using DelaunayTriangulation
julia> points = [(1.0, 1.0), (2.3, 1.5), (0.0, -5.0)];
julia> DelaunayTriangulation.num_points(points)
3
julia> points = [1.0 5.5 10.0 -5.0; 5.0 2.0 0.0 0.0];
julia> DelaunayTriangulation.num_points(points)
4
DelaunayTriangulation.getpoint
— Functiongetpoint(points, vertex) -> NTuple{2, Number}
Get the point associated with vertex
in points
, returned as a Tuple
of the coordinates. If vertex
is not an integer, then vertex
is returned so that points and vertices can be easily mixed.
Examples
julia> using DelaunayTriangulation
julia> points = [(0.3, 0.7), (1.3, 5.0), (5.0, 17.0)];
julia> DelaunayTriangulation.getpoint(points, 2)
(1.3, 5.0)
julia> points = [0.3 1.3 5.0; 0.7 5.0 17.0];
julia> DelaunayTriangulation.getpoint(points, 2)
(1.3, 5.0)
julia> DelaunayTriangulation.getpoint(points, (17.3, 33.0))
(17.3, 33.0)
DelaunayTriangulation.get_point
— Functionget_point(points, vertices...) -> NTuple{length(vertices), NTuple{2, Number}}
Get the points associated with vertices
in points
.
Examples
julia> using DelaunayTriangulation
julia> points = [(1.0, 2.0), (3.0, 5.5), (1.7, 10.3), (-5.0, 0.0)];
julia> get_point(points, 1)
(1.0, 2.0)
julia> get_point(points, 1, 2, 3, 4)
((1.0, 2.0), (3.0, 5.5), (1.7, 10.3), (-5.0, 0.0))
julia> points = [1.0 3.0 1.7 -5.0; 2.0 5.5 10.3 0.0];
julia> get_point(points, 1)
(1.0, 2.0)
julia> get_point(points, 1, 2, 3, 4)
((1.0, 2.0), (3.0, 5.5), (1.7, 10.3), (-5.0, 0.0))
julia> typeof(ans)
NTuple{4, Tuple{Float64, Float64}}
DelaunayTriangulation.each_point_index
— Functioneach_point_index(points) -> Iterator
Returns an iterator over each point index in points
.
Examples
julia> using DelaunayTriangulation
julia> points = [(1.0, 2.0), (-5.0, 2.0), (2.3, 2.3)];
julia> DelaunayTriangulation.each_point_index(points)
Base.OneTo(3)
julia> points = [1.0 -5.0 2.3; 2.0 2.0 2.3];
julia> DelaunayTriangulation.each_point_index(points)
Base.OneTo(3)
DelaunayTriangulation.each_point
— Functioneach_point(points) -> Iterator
Returns an iterator over each point in points
.
Examples
julia> using DelaunayTriangulation
julia> points = [(1.0, 2.0), (5.0, 13.0)];
julia> DelaunayTriangulation.each_point(points)
2-element Vector{Tuple{Float64, Float64}}:
(1.0, 2.0)
(5.0, 13.0)
julia> points = [1.0 5.0 17.7; 5.5 17.7 0.0];
julia> DelaunayTriangulation.each_point(points)
3-element ColumnSlices{Matrix{Float64}, Tuple{Base.OneTo{Int64}}, SubArray{Float64, 1, Matrix{Float64}, Tuple{Base.Slice{Base.OneTo{Int64}}, Int64}, true}}:
[1.0, 5.5]
[5.0, 17.7]
[17.7, 0.0]
DelaunayTriangulation._getx
— Method_getx(p) -> Float64
Get the x-coordinate of p
as a Float64
.
Examples
julia> using DelaunayTriangulation
julia> p = (0.37, 0.7);
julia> DelaunayTriangulation._getx(p)
0.37
julia> p = (0.37f0, 0.7f0);
julia> DelaunayTriangulation._getx(p)
0.3700000047683716
DelaunayTriangulation._getxy
— Method_getxy(p) -> NTuple{2, Float64}
Get the coordinates of p
as a Tuple
of Float64
s.
Examples
julia> using DelaunayTriangulation
julia> p = [0.3, 0.5];
julia> DelaunayTriangulation._getxy(p)
(0.3, 0.5)
julia> p = [0.3f0, 0.5f0];
julia> DelaunayTriangulation._getxy(p)
(0.30000001192092896, 0.5)
DelaunayTriangulation._getxyz
— Method_getxyz(p) -> NTuple{3, Float64}
Given a three-dimemsional p
, returns its coordinates as a Tuple
of Float64
s.
DelaunayTriangulation._gety
— Method_gety(p) -> Float64
Get the y-coordinate of p
as a Float64
.
Examples
julia> using DelaunayTriangulation
julia> p = (0.5, 0.5);
julia> DelaunayTriangulation._gety(p)
0.5
julia> p = (0.5f0, 0.5f0);
julia> DelaunayTriangulation._gety(p)
0.5
DelaunayTriangulation._getz
— Method_getz(p) -> Float64
Get the z-coordinate of p
as a Float64.
DelaunayTriangulation.find_duplicate_points
— Methodfind_duplicate_points(points) -> Dict{Point, Vector{Int}}
Returns a Dict
of points
that maps each duplicate point to a Vector
of the indices of the duplicate points.
DelaunayTriangulation.find_point_index
— Methodfind_point_index(points, x, y) -> Integer
find_point_index(points, p) -> Integer
Returns an index of a point in points
that is equal to p = (x, y)
. If no such point exists, then 0
is returned.
DelaunayTriangulation.getx
— Methodgetx(p) -> Number
Get the x-coordinate of p
.
Examples
julia> using DelaunayTriangulation
julia> p = (0.3, 0.7);
julia> getx(p)
0.3
DelaunayTriangulation.getxy
— Methodgetxy(p) -> NTuple{2, Number}
Get the coordinates of p
as a Tuple
.
Examples
julia> using DelaunayTriangulation
julia> p = [0.9, 23.8];
julia> getxy(p)
(0.9, 23.8)
DelaunayTriangulation.getxyz
— Methodgetxyz(p) -> NTuple{3, Number}
Given a three-dimensional p
, returns its coordinates as a Tuple
.
DelaunayTriangulation.gety
— Methodgety(p) -> Number
Get the y-coordinate of p
.
Examples
julia> using DelaunayTriangulation
julia> p = (0.9, 1.3);
julia> gety(p)
1.3
DelaunayTriangulation.getz
— Methodgetz(p) -> Number
Get the z-coordinate of p
.
DelaunayTriangulation.is_planar
— Methodis_planar(points) -> Bool
Returns true
if all points in points
are two-dimensional. The default definition is simply all(is_point2, each_point(points))
.
DelaunayTriangulation.is_point2
— Methodis_point2(p) -> Bool
Tests if p
represents a point in the plane. By default, this returns the result of
eltype(p) <: Number && length(p) == 2
DelaunayTriangulation.is_point3
— Methodis_point3(p) -> Bool
Tests if p
represents a point in space. By default, this returns the result of
eltype(p) <: Number && length(p) == 3
DelaunayTriangulation.lexicographic_order
— Methodlexicographic_order(points) -> Vector{Int}
Returns a set of indices that give the lexicographic ordering of points
, meaning the indices so that the points are sorted first by x
and then by y
.
Examples
julia> using DelaunayTriangulation
julia> points = [(1.0, 5.0), (0.0, 17.0), (0.0, 13.0), (5.0, 17.3), (3.0, 1.0), (5.0, -2.0)]
6-element Vector{Tuple{Float64, Float64}}:
(1.0, 5.0)
(0.0, 17.0)
(0.0, 13.0)
(5.0, 17.3)
(3.0, 1.0)
(5.0, -2.0)
julia> DelaunayTriangulation.lexicographic_order(points)
6-element Vector{Int64}:
3
2
1
5
6
4
julia> hcat(points, points[ans])
6×2 Matrix{Tuple{Float64, Float64}}:
(1.0, 5.0) (0.0, 13.0)
(0.0, 17.0) (0.0, 17.0)
(0.0, 13.0) (1.0, 5.0)
(5.0, 17.3) (3.0, 1.0)
(3.0, 1.0) (5.0, -2.0)
(5.0, -2.0) (5.0, 17.3)
DelaunayTriangulation.mean_points
— Functionmean_points(points[, vertices = each_point_index(points)]) -> NTuple{2, Number}
Returns the mean of the points in points
indexed by vertices
, given as a Tuple
of the form (mean_x, mean_y)
.
Examples
julia> using DelaunayTriangulation
julia> points = [(1.0, 2.0), (2.3, 5.0), (17.3, 5.3)]
3-element Vector{Tuple{Float64, Float64}}:
(1.0, 2.0)
(2.3, 5.0)
(17.3, 5.3)
julia> DelaunayTriangulation.mean_points(points)
(6.866666666666667, 4.1000000000000005)
julia> (1.0 + 2.3 + 17.3)/3, (2.0 + 5.0 + 5.3)/3
(6.866666666666667, 4.1000000000000005)
julia> points = [1.0 2.3 17.3; 2.0 5.0 5.3]
2×3 Matrix{Float64}:
1.0 2.3 17.3
2.0 5.0 5.3
julia> DelaunayTriangulation.mean_points(points)
(6.866666666666667, 4.1000000000000005)
julia> DelaunayTriangulation.mean_points(points, (1, 3))
(9.15, 3.65)
julia> (1.0 + 17.3)/2, (2.0 + 5.3)/2
(9.15, 3.65)
DelaunayTriangulation.points_are_unique
— Methodpoints_are_unique(points) -> Bool
Returns true
if all points in points
are unique.
Examples
julia> using DelaunayTriangulation
julia> points = [1.0 2.0 3.0 4.0 5.0; 0.0 5.5 2.0 1.3 17.0]
2×5 Matrix{Float64}:
1.0 2.0 3.0 4.0 5.0
0.0 5.5 2.0 1.3 17.0
julia> DelaunayTriangulation.points_are_unique(points)
true
julia> points[:, 4] .= points[:, 1];
julia> DelaunayTriangulation.points_are_unique(points)
false
Edges (Primitive Interface)
Here are functions that are used for defining and working with edges in the package.
DelaunayTriangulation.random_edge
— Functionrandom_edge([rng], E) -> E
Get a random edge from E
.
Examples
julia> using DelaunayTriangulation, StableRNGs
julia> E = Set(((1,2),(10,15),(23,20)))
Set{Tuple{Int64, Int64}} with 3 elements:
(1, 2)
(23, 20)
(10, 15)
julia> rng = StableRNG(123);
julia> DelaunayTriangulation.random_edge(rng, E)
(10, 15)
julia> DelaunayTriangulation.random_edge(rng, E)
(10, 15)
julia> DelaunayTriangulation.random_edge(rng, E)
(23, 20)
julia> DelaunayTriangulation.random_edge(E)
(1, 2)
DelaunayTriangulation.each_edge
— Functioneach_edge(E) -> Iterator
Get an iterator over the edges in E
.
Examples
julia> using DelaunayTriangulation
julia> E = Set(((1,2),(1,3),(2,-1)))
Set{Tuple{Int64, Int64}} with 3 elements:
(1, 2)
(1, 3)
(2, -1)
julia> each_edge(E)
Set{Tuple{Int64, Int64}} with 3 elements:
(1, 2)
(1, 3)
(2, -1)
DelaunayTriangulation.contains_edge
— Functioncontains_edge(i, j, E) -> Bool
contains_edge(e, E) -> Bool
Check if E
contains the edge e = (i, j)
.
Examples
julia> using DelaunayTriangulation
julia> E = Set(((1,3),(17,3),(1,-1)))
Set{Tuple{Int64, Int64}} with 3 elements:
(1, -1)
(17, 3)
(1, 3)
julia> DelaunayTriangulation.contains_edge((1, 2), E)
false
julia> DelaunayTriangulation.contains_edge((17, 3), E)
true
julia> DelaunayTriangulation.contains_edge(3, 17, E) # order
false
julia> E = [[1,2],[5,13],[-1,1]]
3-element Vector{Vector{Int64}}:
[1, 2]
[5, 13]
[-1, 1]
julia> DelaunayTriangulation.contains_edge(1, 2, E)
true
DelaunayTriangulation.construct_edge
— Functionconstruct_edge(::Type{E}, i, j) where {E} -> E
Construct an edge of type E
from vertices i
and j
.
Examples
julia> using DelaunayTriangulation
julia> DelaunayTriangulation.construct_edge(NTuple{2,Int}, 2, 5)
(2, 5)
julia> DelaunayTriangulation.construct_edge(Vector{Int32}, 5, 15)
2-element Vector{Int32}:
5
15
DelaunayTriangulation.add_edge!
— Methodadd_edge!(E, e...)
Add the edges e...
to E
.
Examples
julia> using DelaunayTriangulation
julia> E = Set(((1,5),(17,10),(5,3)))
Set{Tuple{Int64, Int64}} with 3 elements:
(5, 3)
(17, 10)
(1, 5)
julia> DelaunayTriangulation.add_edge!(E, (3, 2))
julia> E
Set{Tuple{Int64, Int64}} with 4 elements:
(3, 2)
(5, 3)
(17, 10)
(1, 5)
julia> DelaunayTriangulation.add_edge!(E, (1, -3), (5, 10), (1, -1))
julia> E
Set{Tuple{Int64, Int64}} with 7 elements:
(3, 2)
(5, 10)
(1, -3)
(1, -1)
(5, 3)
(17, 10)
(1, 5)
DelaunayTriangulation.add_to_edges!
— Methodadd_to_edges!(E, e)
Add the edge e
to E
.
Examples
julia> using DelaunayTriangulation
julia> E = Set(((1, 2),(3,5)))
Set{Tuple{Int64, Int64}} with 2 elements:
(1, 2)
(3, 5)
julia> DelaunayTriangulation.add_to_edges!(E, (1, 5))
Set{Tuple{Int64, Int64}} with 3 elements:
(1, 2)
(3, 5)
(1, 5)
DelaunayTriangulation.compare_unoriented_edge_collections
— Methodcompareunorientededge_collections(E, F) -> Bool
Tests if the edge collections E
and F
are equal, ignoring edge orientation.
DelaunayTriangulation.compare_unoriented_edges
— Methodcompare_unoriented_edges(u, v) -> Bool
Compare the unoriented edges u
and v
, i.e. compare the vertices of u
and v
in any order.
Examples
julia> using DelaunayTriangulation
julia> u = (1, 3);
julia> v = (5, 3);
julia> DelaunayTriangulation.compare_unoriented_edges(u, v)
false
julia> v = (1, 3);
julia> DelaunayTriangulation.compare_unoriented_edges(u, v)
true
julia> v = (3, 1);
julia> DelaunayTriangulation.compare_unoriented_edges(u, v)
true
DelaunayTriangulation.contains_unoriented_edge
— Methodcontains_unoriented_edge(e, E) -> Bool
Check if E
contains the unoriented edge e
, i.e. check if E
contains the edge e
or reverse_edge(e)
.
DelaunayTriangulation.delete_edge!
— Methoddelete_edge!(E, e...)
Delete the edges e...
from E
.
Examples
julia> using DelaunayTriangulation
julia> E = Set(([1,2],[10,15],[1,-1],[13,23],[1,5]))
Set{Vector{Int64}} with 5 elements:
[10, 15]
[1, 5]
[1, 2]
[1, -1]
[13, 23]
julia> DelaunayTriangulation.delete_edge!(E, [10,15])
julia> E
Set{Vector{Int64}} with 4 elements:
[1, 5]
[1, 2]
[1, -1]
[13, 23]
julia> DelaunayTriangulation.delete_edge!(E, [1,5], [1, -1])
julia> E
Set{Vector{Int64}} with 2 elements:
[1, 2]
[13, 23]
DelaunayTriangulation.delete_from_edges!
— Methoddelete_from_edges!(E, e)
Delete the edge e
from E
.
Examples
julia> using DelaunayTriangulation
julia> E = Set(([1,2],[5,15],[17,10],[5,-1]))
Set{Vector{Int64}} with 4 elements:
[17, 10]
[5, 15]
[5, -1]
[1, 2]
julia> DelaunayTriangulation.delete_from_edges!(E, [5, 15])
Set{Vector{Int64}} with 3 elements:
[17, 10]
[5, -1]
[1, 2]
DelaunayTriangulation.delete_unoriented_edge!
— Methoddelete_unoriented_edge!(E, e)
Delete the unoriented edge e
from E
, i.e. delete both the edge e
and reverse_edge(e)
.
DelaunayTriangulation.edge_type
— Methodedge_type(E) -> DataType
Get the type of edges in E
.
Examples
julia> using DelaunayTriangulation
julia> e = Set(((1,2),(2,3),(17,5)))
Set{Tuple{Int64, Int64}} with 3 elements:
(1, 2)
(17, 5)
(2, 3)
julia> DelaunayTriangulation.edge_type(e)
Tuple{Int64, Int64}
julia> e = [[1,2],[3,4],[17,3]]
3-element Vector{Vector{Int64}}:
[1, 2]
[3, 4]
[17, 3]
julia> DelaunayTriangulation.edge_type(e)
Vector{Int64} (alias for Array{Int64, 1})
DelaunayTriangulation.edge_vertices
— Methodedge_vertices(e) -> NTuple{2, Vertex}
Get the vertices of e
Examples
julia> using DelaunayTriangulation
julia> e = (1, 5);
julia> edge_vertices(e)
(1, 5)
julia> e = [23, 50];
julia> edge_vertices(e)
(23, 50)
DelaunayTriangulation.edges_are_disjoint
— Methodedges_are_disjoint(e, e′) -> Bool
Returns true
if e
and e′
have any shared vertex, and false
otherwise.
DelaunayTriangulation.initial
— Methodinitial(e) -> Vertex
Get the initial vertex of e
.
Examples
julia> using DelaunayTriangulation
julia> e = (1, 3);
julia> DelaunayTriangulation.initial(e)
1
julia> e = [2, 5];
julia> DelaunayTriangulation.initial(e)
2
DelaunayTriangulation.num_edges
— Methodnum_edges(E) -> Integer
Get the number of edges in E
.
Examples
julia> using DelaunayTriangulation
julia> e = [(1, 2), (3, 4), (1, 5)];
julia> num_edges(e)
3
DelaunayTriangulation.reverse_edge
— Methodreverse_edge(e) -> Edge
Get the edge with the vertices of e
in reverse order.
Examples
julia> using DelaunayTriangulation
julia> e = (17, 3);
julia> DelaunayTriangulation.reverse_edge(e)
(3, 17)
julia> e = [1, 2];
julia> DelaunayTriangulation.reverse_edge(e)
2-element Vector{Int64}:
2
1
DelaunayTriangulation.terminal
— Methodterminal(e) -> Vertex
Get the terminal vertex of e
.
Examples
julia> using DelaunayTriangulation
julia> e = (1, 7);
julia> DelaunayTriangulation.terminal(e)
7
julia> e = [2, 13];
julia> DelaunayTriangulation.terminal(e)
13
Triangles (Primitive Interface)
Here are functions that are used for defining and working with triangles in the package.
DelaunayTriangulation.triangle_edges
— Functiontriangle_edges(T) -> NTuple{3, Edge}
triangle_edges(i, j, k) -> NTuple{3, Edge}
Get the edges of T = (i, j, k)
as a Tuple
, in particular
((i, j), (j, k), (k, i)).
Examples
julia> using DelaunayTriangulation
julia> T = (1, 2, 3);
julia> DelaunayTriangulation.triangle_edges(T)
((1, 2), (2, 3), (3, 1))
julia> DelaunayTriangulation.triangle_edges(1, 2, 3)
((1, 2), (2, 3), (3, 1))
DelaunayTriangulation.sort_triangle
— Functionsort_triangle(T) -> Triangle
sort_triangle(i, j, k) -> Triangle
Sort the triangle T = (i, j, k)
so that its last vertex is the smallest, respecting the orientation of T
.
Examples
julia> using DelaunayTriangulation
julia> DelaunayTriangulation.sort_triangle((1, 5, 3))
(5, 3, 1)
julia> DelaunayTriangulation.sort_triangle((1, -1, 2))
(2, 1, -1)
julia> DelaunayTriangulation.sort_triangle((3, 2, 1))
(3, 2, 1)
DelaunayTriangulation.each_triangle
— Functioneach_triangle(T) -> Iterator
Return an iterator over the triangles in T
.
Examples
julia> using DelaunayTriangulation
julia> T = Set(((1, 2, 3), (-1, 5, 10), (17, 13, 18)));
julia> each_triangle(T)
Set{Tuple{Int64, Int64, Int64}} with 3 elements:
(-1, 5, 10)
(1, 2, 3)
(17, 13, 18)
julia> T = [[1, 2, 3], [10, 15, 18], [1, 5, 6]];
julia> each_triangle(T)
3-element Vector{Vector{Int64}}:
[1, 2, 3]
[10, 15, 18]
[1, 5, 6]
DelaunayTriangulation.delete_triangle!
— Functiondelete_triangle!(V, T...)
delete_triangle!(V, i, j, k)
Delete the triangles T...
from the collection of triangles V
.
Examples
julia> using DelaunayTriangulation
julia> V = Set(((1, 2, 3), (4, 5, 6), (7, 8, 9), (10, 11, 12), (13, 14, 15)))
Set{Tuple{Int64, Int64, Int64}} with 5 elements:
(7, 8, 9)
(10, 11, 12)
(4, 5, 6)
(13, 14, 15)
(1, 2, 3)
julia> delete_triangle!(V, (6, 4, 5))
Set{Tuple{Int64, Int64, Int64}} with 4 elements:
(7, 8, 9)
(10, 11, 12)
(13, 14, 15)
(1, 2, 3)
julia> delete_triangle!(V, (10, 11, 12), (1, 2, 3))
Set{Tuple{Int64, Int64, Int64}} with 2 elements:
(7, 8, 9)
(13, 14, 15)
julia> delete_triangle!(V, 8, 9, 7)
Set{Tuple{Int64, Int64, Int64}} with 1 element:
(13, 14, 15)
DelaunayTriangulation.contains_triangle
— Functioncontains_triangle(T, V) -> (Triangle, Bool)
Check if the collection of triangles V
contains the triangle T
up to rotation. The Triangle
returned is the triangle in V
that is equal to T
up to rotation, or T
if no such triangle exists. The Bool
is true
if V
contains T
, and false
otherwise.
Examples
julia> using DelaunayTriangulation
julia> V = Set(((1, 2, 3), (4, 5, 6), (7, 8, 9)))
Set{Tuple{Int64, Int64, Int64}} with 3 elements:
(7, 8, 9)
(4, 5, 6)
(1, 2, 3)
julia> DelaunayTriangulation.contains_triangle((1, 2, 3), V)
((1, 2, 3), true)
julia> DelaunayTriangulation.contains_triangle((2, 3, 1), V)
((1, 2, 3), true)
julia> DelaunayTriangulation.contains_triangle((10, 18, 9), V)
((10, 18, 9), false)
julia> DelaunayTriangulation.contains_triangle(9, 7, 8, V)
((7, 8, 9), true)
DelaunayTriangulation.construct_triangle
— Functionconstruct_triangle(::Type{T}, i, j, k) where {T} -> Triangle
Construct a triangle of type T
from vertices i
, j
, and k
.
Examples
julia> using DelaunayTriangulation
julia> DelaunayTriangulation.construct_triangle(NTuple{3,Int}, 1, 2, 3)
(1, 2, 3)
julia> DelaunayTriangulation.construct_triangle(Vector{Int32}, 1, 2, 3)
3-element Vector{Int32}:
1
2
3
DelaunayTriangulation.add_triangle!
— Functionadd_triangle!(T, V...)
add_triangle!(T, i, j, k)
Add the triangles V...
or V = (i, j, k)
to the collection of triangles T
.
Examples
julia> using DelaunayTriangulation
julia> T = Set(((1, 2, 3), (4, 5, 6)))
Set{Tuple{Int64, Int64, Int64}} with 2 elements:
(4, 5, 6)
(1, 2, 3)
julia> add_triangle!(T, (7, 8, 9));
julia> add_triangle!(T, (10, 11, 12), (13, 14, 15));
julia> add_triangle!(T, 16, 17, 18);
julia> T
Set{Tuple{Int64, Int64, Int64}} with 6 elements:
(7, 8, 9)
(10, 11, 12)
(4, 5, 6)
(13, 14, 15)
(16, 17, 18)
(1, 2, 3)
DelaunayTriangulation.add_to_triangles!
— Methodadd_to_triangles!(T, V)
Add the triangle V
to the collection of triangles T
.
Examples
julia> using DelaunayTriangulation
julia> T = Set(((1, 2, 3), (17, 8, 9)));
julia> DelaunayTriangulation.add_to_triangles!(T, (1, 5, 12))
Set{Tuple{Int64, Int64, Int64}} with 3 elements:
(1, 5, 12)
(1, 2, 3)
(17, 8, 9)
julia> DelaunayTriangulation.add_to_triangles!(T, (-1, 3, 6))
Set{Tuple{Int64, Int64, Int64}} with 4 elements:
(1, 5, 12)
(1, 2, 3)
(17, 8, 9)
(-1, 3, 6)
DelaunayTriangulation.compare_triangle_collections
— Methodcompare_triangle_collections(T, V) -> Bool
Compare the collections of triangles T
and V
by comparing their triangles according to compare_triangles
.
Examples
julia> using DelaunayTriangulation
julia> T = Set(((1, 2, 3), (4, 5, 6), (7, 8, 9)));
julia> V = [[2, 3, 1], [4, 5, 6], [9, 7, 8]];
julia> DelaunayTriangulation.compare_triangle_collections(T, V)
true
julia> V[1] = [17, 19, 20];
julia> DelaunayTriangulation.compare_triangle_collections(T, V)
false
julia> V = [[1, 2, 3], [8, 9, 7]];
julia> DelaunayTriangulation.compare_triangle_collections(T, V)
false
DelaunayTriangulation.compare_triangles
— Methodcompare_triangles(T, V) -> Bool
Compare the triangles T
and V
by comparing their vertices up to rotation.
Examples
julia> using DelaunayTriangulation
julia> T1 = (1, 5, 10);
julia> T2 = (17, 23, 20);
julia> DelaunayTriangulation.compare_triangles(T1, T2)
false
julia> T2 = (5, 10, 1);
julia> DelaunayTriangulation.compare_triangles(T1, T2)
true
julia> T2 = (10, 1, 5);
julia> DelaunayTriangulation.compare_triangles(T1, T2)
true
julia> T2 = (10, 5, 1);
julia> DelaunayTriangulation.compare_triangles(T1, T2)
false
DelaunayTriangulation.construct_positively_oriented_triangle
— Methodconstruct_positively_oriented_triangle(::Type{V}, i, j, k, points) where {V} -> V
Construct a triangle of type V
from vertices i
, j
, and k
such that the triangle is positively oriented, using points
for the coordinates.
Examples
julia> using DelaunayTriangulation
julia> points = [(0.0, 0.0), (0.0, 1.0), (1.0, 0.0)];
julia> DelaunayTriangulation.construct_positively_oriented_triangle(NTuple{3, Int}, 1, 2, 3, points)
(2, 1, 3)
julia> DelaunayTriangulation.construct_positively_oriented_triangle(NTuple{3, Int}, 2, 3, 1, points)
(3, 2, 1)
julia> DelaunayTriangulation.construct_positively_oriented_triangle(NTuple{3, Int}, 2, 1, 3, points)
(2, 1, 3)
julia> DelaunayTriangulation.construct_positively_oriented_triangle(NTuple{3, Int}, 3, 2, 1, points)
(3, 2, 1)
julia> points = [(1.0, 1.0), (2.5, 2.3), (17.5, 23.0), (50.3, 0.0), (-1.0, 2.0), (0.0, 0.0), (5.0, 13.33)];
julia> DelaunayTriangulation.construct_positively_oriented_triangle(Vector{Int}, 5, 3, 2, points)
3-element Vector{Int64}:
3
5
2
julia> DelaunayTriangulation.construct_positively_oriented_triangle(Vector{Int}, 7, 1, 2, points)
3-element Vector{Int64}:
7
1
2
julia> DelaunayTriangulation.construct_positively_oriented_triangle(Vector{Int}, 7, 2, 1, points)
3-element Vector{Int64}:
2
7
1
julia> DelaunayTriangulation.construct_positively_oriented_triangle(Vector{Int}, 5, 4, 3, points)
3-element Vector{Int64}:
5
4
3
DelaunayTriangulation.delete_from_triangles!
— Methoddelete_from_triangles!(T, V)
Delete the triangle V
from the collection of triangles T
. Only deletes V
if V
is in T
up to rotation.
Examples
julia> using DelaunayTriangulation
julia> V = Set(((1, 2, 3), (4, 5, 6), (7, 8, 9)))
Set{Tuple{Int64, Int64, Int64}} with 3 elements:
(7, 8, 9)
(4, 5, 6)
(1, 2, 3)
julia> DelaunayTriangulation.delete_from_triangles!(V, (4, 5, 6))
Set{Tuple{Int64, Int64, Int64}} with 2 elements:
(7, 8, 9)
(1, 2, 3)
julia> DelaunayTriangulation.delete_from_triangles!(V, (9, 7, 8))
Set{Tuple{Int64, Int64, Int64}} with 1 element:
(1, 2, 3)
DelaunayTriangulation.geti
— Methodgeti(T) -> Vertex
Get the first vertex of T
.
Examples
julia> using DelaunayTriangulation
julia> DelaunayTriangulation.geti((1, 2, 3))
1
julia> DelaunayTriangulation.geti([2, 5, 1])
2
DelaunayTriangulation.getj
— Methodgetj(T) -> Vertex
Get the second vertex of T
.
Examples
julia> using DelaunayTriangulation
julia> DelaunayTriangulation.getj((5, 6, 13))
6
julia> DelaunayTriangulation.getj([10, 19, 21])
19
DelaunayTriangulation.getk
— Methodgetk(T) -> Vertex
Get the third vertex of T
.
Examples
julia> using DelaunayTriangulation
julia> DelaunayTriangulation.getk((1,2,3))
3
julia> DelaunayTriangulation.getk([1,2,3])
3
DelaunayTriangulation.num_triangles
— Methodnum_triangles(T) -> Integer
Get the number of triangles in T
.
Examples
julia> using DelaunayTriangulation
julia> T1, T2, T3 = (1, 5, 10), (17, 23, 10), (-1, 10, 5);
julia> T = Set((T1, T2, T3));
julia> num_triangles(T)
3
DelaunayTriangulation.rotate_triangle
— Methodrotate_triangle(T, rotation) -> Triangle
Rotate the vertices of T
by rotation
. In particular, if T = (i, j, k)
:
rotation = 0
:(i, j, k)
rotation = 1
:(j, k, i)
rotation = 2
:(k, i, j)
- Otherwise, return
rotate_triangle(T, rotation % 3)
.
Examples
julia> using DelaunayTriangulation
julia> T = (1, 2, 3)
(1, 2, 3)
julia> DelaunayTriangulation.rotate_triangle(T, 0)
(1, 2, 3)
julia> DelaunayTriangulation.rotate_triangle(T, 1)
(2, 3, 1)
julia> DelaunayTriangulation.rotate_triangle(T, 2)
(3, 1, 2)
julia> DelaunayTriangulation.rotate_triangle(T, 3)
(1, 2, 3)
DelaunayTriangulation.sort_triangles
— Methodsort_triangles(T) -> Triangle
Sort the triangles in T
so that the first vertex of each triangle is the largest, respecting the orientation of the triangles. See sort_triangle
.
Examples
julia> using DelaunayTriangulation
julia> T = Set(((1, 3, 2), (5, 2, 3), (10, 1, 13), (-1, 10, 12), (10, 1, 17), (5, 8, 2)))
Set{Tuple{Int64, Int64, Int64}} with 6 elements:
(5, 8, 2)
(10, 1, 13)
(10, 1, 17)
(5, 2, 3)
(1, 3, 2)
(-1, 10, 12)
julia> DelaunayTriangulation.sort_triangles(T)
Set{Tuple{Int64, Int64, Int64}} with 6 elements:
(13, 10, 1)
(3, 5, 2)
(10, 12, -1)
(5, 8, 2)
(17, 10, 1)
(3, 2, 1)
DelaunayTriangulation.triangle_type
— Methodtriangle_type(::Type{T}) -> DataType
Get the triangle type of T
.
Examples
julia> using DelaunayTriangulation
julia> DelaunayTriangulation.triangle_type(Set{NTuple{3,Int64}})
Tuple{Int64, Int64, Int64}
julia> DelaunayTriangulation.triangle_type(Vector{NTuple{3,Int32}})
Tuple{Int32, Int32, Int32}
julia> DelaunayTriangulation.triangle_type(Vector{Vector{Int64}})
Vector{Int64} (alias for Array{Int64, 1})
DelaunayTriangulation.triangle_vertices
— Methodtriangle_vertices(T) -> NTuple{3, Vertex}
Returns the vertices of T
as a Tuple
.
Examples
julia> using DelaunayTriangulation
julia> triangle_vertices((1, 5, 17))
(1, 5, 17)
julia> triangle_vertices([5, 18, 23]) # -> tuple
(5, 18, 23)
Boundary Nodes (Primitive Interface)
Here are functions that are used for defining and working with boundary nodes in the package.
DelaunayTriangulation.has_multiple_sections
— Functionhas_multiple_sections(boundary_nodes) -> Bool
Check if boundary_nodes
has multiple sections.
Examples
julia> using DelaunayTriangulation
julia> DelaunayTriangulation.has_multiple_sections([1, 2, 3, 1])
false
julia> DelaunayTriangulation.has_multiple_sections([[1, 2, 3], [3, 4, 1]])
true
julia> DelaunayTriangulation.has_multiple_sections([[[1, 2, 3], [3, 4, 1]], [[5, 6, 7, 8, 5]]])
true
DelaunayTriangulation.has_multiple_curves
— Functionhas_multiple_curves(boundary_nodes) -> Bool
Check if boundary_nodes
has multiple curves.
Examples
julia> using DelaunayTriangulation
julia> DelaunayTriangulation.has_multiple_curves([1, 2, 3, 1])
false
julia> DelaunayTriangulation.has_multiple_curves([[1, 2, 3], [3, 4, 1]])
false
julia> DelaunayTriangulation.has_multiple_curves([[[1, 2, 3], [3, 4, 1]], [[5, 6, 7, 8, 5]]])
true
DelaunayTriangulation.get_section_index
— Functionget_section_index(dict, ghost_vertex) -> Int
get_section_index(ghost_vertex) -> Int
Given a Dict
from construct_ghost_vertex_map
and a ghost_vertex
, returns the index of the section corresponding to that ghost vertex. The second method maps ghost_vertex
to itself if it is an Integer
, 1
if it is a Vector
, and ghost_vertex[2]
if it is a Tuple
.
Examples
julia> using DelaunayTriangulation
julia> DelaunayTriangulation.get_section_index((2, 3)) # 3rd section of the 2nd curve
3
julia> DelaunayTriangulation.get_section_index(4)
4
julia> DelaunayTriangulation.get_section_index([1, 2, 3, 4, 5, 1])
1
julia> gv_map = DelaunayTriangulation.construct_ghost_vertex_map([[[1, 5, 17, 18, 1]], [[23, 29, 31, 33], [33, 107, 101], [101, 99, 85, 23]]])
Dict{Int64, Tuple{Int64, Int64}} with 4 entries:
-1 => (1, 1)
-3 => (2, 2)
-2 => (2, 1)
-4 => (2, 3)
julia> DelaunayTriangulation.get_section_index(gv_map, -1)
1
julia> DelaunayTriangulation.get_section_index(gv_map, -2)
1
julia> DelaunayTriangulation.get_section_index(gv_map, -3)
2
julia> DelaunayTriangulation.get_section_index(gv_map, -4)
3
DelaunayTriangulation.get_curve_index
— Functionget_curve_index(dict, ghost_vertex) -> Int
get_curve_index(ghost_vertex) -> Int
Given a Dict
from construct_ghost_vertex_map
and a ghost_vertex
, returns the index of the curve corresponding to that ghost vertex. The second method maps ghost_vertex
to 1
if it is an Integer
or a Vector
, and ghost_vertex[1]
if it is a Tuple
.
Examples
julia> using DelaunayTriangulation
julia> DelaunayTriangulation.get_curve_index(-1)
1
julia> DelaunayTriangulation.get_curve_index((5, 3))
5
julia> gv_map = DelaunayTriangulation.construct_ghost_vertex_map([[[1, 5, 17, 18, 1]], [[23, 29, 31, 33], [33, 107, 101], [101, 99, 85, 23]]])
Dict{Int64, Tuple{Int64, Int64}} with 4 entries:
-1 => (1, 1)
-3 => (2, 2)
-2 => (2, 1)
-4 => (2, 3)
julia> DelaunayTriangulation.get_curve_index(gv_map, -1)
1
julia> DelaunayTriangulation.get_curve_index(gv_map, -2)
2
julia> DelaunayTriangulation.get_curve_index(gv_map, -3)
2
julia> DelaunayTriangulation.get_curve_index(gv_map, -4)
2
DelaunayTriangulation.get_boundary_nodes
— Functionget_boundary_nodes(boundary_nodes, mnℓ...)
Given a collection of boundary_nodes
, returns the specified component of the collection. There are several forms for the methods:
get_boundary_nodes(boundary_nodes, m)
: Ifboundary_nodes
has multiple curves, this returns them
th curve. Ifboundary_nodes
has multiple sections, this returns them
th section. Otherwise, this returns them
th boundary node.get_boundary_nodes(boundary_nodes, m, n)
: Ifboundary_nodes
has multiple curves, this returns then
th section of them
th curve. Otherwise, ifboundary_nodes
has multiple sections, this returns then
th boundary node of them
th section.get_boundary_nodes(boundary_nodes, (m, n))
: This is equivalent toget_boundary_nodes(boundary_nodes, m, n)
.get_boundary_nodes(boundary_nodes::A, ::A)
: This just returnsboundary_nodes
.
Examples
julia> using DelaunayTriangulation
julia> get_boundary_nodes([[[1, 2, 3, 4], [4, 5, 1]], [[6, 7, 8, 9], [9, 10, 6]]], 2)
2-element Vector{Vector{Int64}}:
[6, 7, 8, 9]
[9, 10, 6]
julia> get_boundary_nodes([[1, 2, 3, 4], [4, 5, 1]], 1)
4-element Vector{Int64}:
1
2
3
4
julia> get_boundary_nodes([1, 2, 3, 4, 5, 6, 1], 4)
4
julia> get_boundary_nodes([[[1, 2, 3, 4], [4, 5, 1]], [[6, 7, 8, 9], [9, 10, 6]]], 1, 2)
3-element Vector{Int64}:
4
5
1
julia> get_boundary_nodes([[1, 2, 3, 4], [4, 5, 6, 1]], 2, 3)
6
julia> get_boundary_nodes([1, 2, 3, 4, 5, 1], [1, 2, 3, 4, 5, 1])
6-element Vector{Int64}:
1
2
3
4
5
1
DelaunayTriangulation.construct_boundary_edge_map
— Methodconstruct_boundary_edge_map(boundary_nodes::A, IntegerType::Type{I}=number_type(boundary_nodes), EdgeType::Type{E}=NTuple{2,IntegerType}) where {A,I,E} -> Dict
Constructs a map that takes boundary edges in boundary_nodes
to a Tuple
giving the edge's position in boundary_nodes
. In particular, if dict = construct_boundary_edge_map(boundary_nodes)
, then dict[e] = (pos, ℓ)
so that bn = get_boundary_nodes(boundary_nodes, pos)
gives the boundary nodes associated with the section that e
lives on, and get_boundary_nodes(bn, ℓ)
is the first vertex of e
.
Examples
julia> using DelaunayTriangulation
julia> DelaunayTriangulation.construct_boundary_edge_map([17, 18, 15, 4, 3, 17])
Dict{Tuple{Int64, Int64}, Tuple{Vector{Int64}, Int64}} with 5 entries:
(18, 15) => ([17, 18, 15, 4, 3, 17], 2)
(3, 17) => ([17, 18, 15, 4, 3, 17], 5)
(17, 18) => ([17, 18, 15, 4, 3, 17], 1)
(4, 3) => ([17, 18, 15, 4, 3, 17], 4)
(15, 4) => ([17, 18, 15, 4, 3, 17], 3)
julia> DelaunayTriangulation.construct_boundary_edge_map([[5, 17, 3, 9], [9, 18, 13, 1], [1, 93, 57, 5]])
Dict{Tuple{Int64, Int64}, Tuple{Int64, Int64}} with 9 entries:
(18, 13) => (2, 2)
(17, 3) => (1, 2)
(9, 18) => (2, 1)
(13, 1) => (2, 3)
(3, 9) => (1, 3)
(93, 57) => (3, 2)
(5, 17) => (1, 1)
(57, 5) => (3, 3)
(1, 93) => (3, 1)
julia> DelaunayTriangulation.construct_boundary_edge_map([[[2, 5, 10], [10, 11, 2]], [[27, 28, 29, 30], [30, 31, 85, 91], [91, 92, 27]]])
Dict{Tuple{Int64, Int64}, Tuple{Tuple{Int64, Int64}, Int64}} with 12 entries:
(92, 27) => ((2, 3), 2)
(2, 5) => ((1, 1), 1)
(11, 2) => ((1, 2), 2)
(10, 11) => ((1, 2), 1)
(30, 31) => ((2, 2), 1)
(91, 92) => ((2, 3), 1)
(29, 30) => ((2, 1), 3)
(31, 85) => ((2, 2), 2)
(27, 28) => ((2, 1), 1)
(5, 10) => ((1, 1), 2)
(28, 29) => ((2, 1), 2)
(85, 91) => ((2, 2), 3)
DelaunayTriangulation.construct_ghost_vertex_map
— Methodconstruct_ghost_vertex_map(boundary_nodes::A, IntegerType::Type{I}=number_type(boundary_nodes)) where {A,I} -> Dict
Given a set of boundary_nodes
, returns a Dict
that maps ghost vertices to their associated section in boundary_nodes
. There are three cases:
has_multiple_curves(boundary_nodes)
Returns dict::Dict{I, NTuple{2, I}}
, mapping ghost vertices i
to Tuple
s (m, n)
so that get_boundary_nodes(boundary_nodes, m, n)
are the boundary nodes associated with i
, i.e. the n
th section of the m
th curve is associated with the ghost vertex i
.
has_multiple_sections(boundary_nodes)
Returns dict::Dict{I, I}
, mapping ghost vertices i
to n
so that get_boundary_nodes(boundary_nodes, n)
are the boundary nodes associated with i
, i.e. the n
th section of the boundary is associated with the ghost vertex i
.
otherwise
Returns dict::Dict{I, A}
, mapping the ghost vertex i
to boundary_nodes
.
Examples
julia> using DelaunayTriangulation
julia> gv_map = DelaunayTriangulation.construct_ghost_vertex_map([1, 2, 3, 4, 5, 1])
Dict{Int64, Vector{Int64}} with 1 entry:
-1 => [1, 2, 3, 4, 5, 1]
julia> gv_map = DelaunayTriangulation.construct_ghost_vertex_map([[17, 29, 23, 5, 2, 1], [1, 50, 51, 52], [52, 1]])
Dict{Int64, Int64} with 3 entries:
-1 => 1
-3 => 3
-2 => 2
julia> gv_map = DelaunayTriangulation.construct_ghost_vertex_map([[[1, 5, 17, 18, 1]], [[23, 29, 31, 33], [33, 107, 101], [101, 99, 85, 23]]])
Dict{Int64, Tuple{Int64, Int64}} with 4 entries:
-1 => (1, 1)
-3 => (2, 2)
-2 => (2, 1)
-4 => (2, 3)
Extended help
This map can be useful for iterating over all boundary nodes. For example, you can iterate over all sections of a boundary using:
gv_map = construct_ghost_vertex_map(boundary_nodes)
for (ghost_vertex, section) in gv_map
nodes = get_boundary_nodes(boundary_nodes, section)
# do something with nodes
end
This works for any form of boundary_nodes
.
DelaunayTriangulation.construct_ghost_vertex_ranges
— Methodconstruct_ghost_vertex_ranges(boundary_nodes::A, IntegerType::Type{I}=number_type(boundary_nodes)) where {A,I} -> Dict
Given a set of boundary_nodes
, returns a Dict
that maps ghost vertices to the range of all ghost vertices that the corresponding boundary curve could correspond to.
Examples
julia> using DelaunayTriangulation
julia> boundary_nodes = [
[
[1, 2, 3, 4], [4, 5, 6, 1]
],
[
[18, 19, 20, 25, 26, 30]
],
[
[50, 51, 52, 53, 54, 55], [55, 56, 57, 58], [58, 101, 103, 105, 107, 120], [120, 121, 122, 50]
]
]
3-element Vector{Vector{Vector{Int64}}}:
[[1, 2, 3, 4], [4, 5, 6, 1]]
[[18, 19, 20, 25, 26, 30]]
[[50, 51, 52, 53, 54, 55], [55, 56, 57, 58], [58, 101, 103, 105, 107, 120], [120, 121, 122, 50]]
julia> DelaunayTriangulation.construct_ghost_vertex_ranges(boundary_nodes)
Dict{Int64, UnitRange{Int64}} with 7 entries:
-5 => -7:-4
-1 => -2:-1
-7 => -7:-4
-3 => -3:-3
-2 => -2:-1
-4 => -7:-4
-6 => -7:-4
DelaunayTriangulation.delete_boundary_node!
— Methoddelete_boundary_node!(boundary_nodes, pos)
Deletes the boundary node at the position pos
from boundary_nodes
. Here, pos[1]
is such that get_boundary_nodes(boundary_nodes, pos[1])
is the section that the node will be deleted from, and pos[2]
gives the position of the array to delete from. In particular,
delete_boundary_node!(boundary_nodes, pos)
is the same as
deleteat!(get_boundary_nodes(boundary_nodes, pos[1]), pos[2])
Examples
julia> using DelaunayTriangulation
julia> boundary_nodes = [71, 25, 33, 44, 55, 10];
julia> DelaunayTriangulation.delete_boundary_node!(boundary_nodes, (boundary_nodes, 4))
5-element Vector{Int64}:
71
25
33
55
10
julia> boundary_nodes = [[7, 13, 9, 25], [25, 26, 29, 7]];
julia> DelaunayTriangulation.delete_boundary_node!(boundary_nodes, (2, 3))
2-element Vector{Vector{Int64}}:
[7, 13, 9, 25]
[25, 26, 7]
julia> boundary_nodes = [[[17, 23, 18, 25], [25, 26, 81, 91], [91, 101, 17]], [[1, 5, 9, 13], [13, 15, 1]]];
julia> DelaunayTriangulation.delete_boundary_node!(boundary_nodes, ((2, 2), 2))
2-element Vector{Vector{Vector{Int64}}}:
[[17, 23, 18, 25], [25, 26, 81, 91], [91, 101, 17]]
[[1, 5, 9, 13], [13, 1]]
DelaunayTriangulation.each_boundary_node
— Methodeach_boundary_node(boundary_nodes) -> Iterator
Returns an iterator that goves over each node in boundary_nodes
. It is assumed that boundary_nodes
represents a single section or a single contiguous boundary; if you do want to loop over every boundary nodes for a boundary with multiple sections, you should to see the result from construct_ghost_vertex_map
.
Examples
julia> using DelaunayTriangulation
julia> DelaunayTriangulation.each_boundary_node([7, 8, 19, 2, 17])
5-element Vector{Int64}:
7
8
19
2
17
julia> DelaunayTriangulation.each_boundary_node([7, 8, 19, 2, 17, 7])
6-element Vector{Int64}:
7
8
19
2
17
7
DelaunayTriangulation.get_skeleton
— Methodget_skeleton(boundary_nodes, IntegerType) -> empty(boundary_nodes)
Given a set of boundary nodes, returns the empty skeleton of the boundary nodes. This is essentially empty
applied to boundary_nodes
, but with vertices of type IntegerType
. This is mainly needed for convert_boundary_curves!
. You will need to implement a new method for this if you want your custom boundary node interface to be supported for curve-bounded domains.
DelaunayTriangulation.insert_boundary_node!
— Methodinsert_boundary_node!(boundary_nodes, pos, node)
Inserts a boundary node node
into boundary_nodes
at the position pos
. Here, pos[1]
is such that get_boundary_nodes(boundary_nodes, pos[1])
is the section that the node will be inserted onto, and pos[2]
gives the position of the array to insert node
into. In particular,
insert_boundary_node!(boundary_nodes, pos, node)
is the same as
insert!(get_boundary_nodes(boundary_nodes, pos[1]), pos[2], node)
Examples
julia> using DelaunayTriangulation
julia> boundary_nodes = [1, 2, 3, 4, 5, 1];
julia> DelaunayTriangulation.insert_boundary_node!(boundary_nodes, (boundary_nodes, 4), 23)
7-element Vector{Int64}:
1
2
3
23
4
5
1
julia> boundary_nodes = [[7, 13, 9, 25], [25, 26, 29, 7]];
julia> DelaunayTriangulation.insert_boundary_node!(boundary_nodes, (2, 1), 57)
2-element Vector{Vector{Int64}}:
[7, 13, 9, 25]
[57, 25, 26, 29, 7]
julia> boundary_nodes = [[[17, 23, 18, 25], [25, 26, 81, 91], [91, 101, 17]], [[1, 5, 9, 13], [13, 15, 1]]];
julia> DelaunayTriangulation.insert_boundary_node!(boundary_nodes, ((1, 3), 3), 1001)
2-element Vector{Vector{Vector{Int64}}}:
[[17, 23, 18, 25], [25, 26, 81, 91], [91, 101, 1001, 17]]
[[1, 5, 9, 13], [13, 15, 1]]
DelaunayTriangulation.num_boundary_edges
— Methodnum_boundary_edges(boundary_nodes) -> Integer
Get the number of boundary edges in boundary_nodes
, assuming that boundary_nodes
defines a boundary with only one curve and a single section.
DelaunayTriangulation.num_curves
— Methodnum_curves(boundary_nodes) -> Integer
Get the number of curves in boundary_nodes
.
Examples
julia> using DelaunayTriangulation
julia> DelaunayTriangulation.num_curves([1, 2, 3, 1])
1
julia> DelaunayTriangulation.num_curves([[1, 2, 3], [3, 4, 1]])
1
julia> DelaunayTriangulation.num_curves([[[1, 2, 3], [3, 4, 1]], [[5, 6, 7, 8, 5]]])
2
DelaunayTriangulation.num_sections
— Methodnum_sections(boundary_nodes) -> Integer
Assuming boundary_nodes
has only one curve, get the number of sections in boundary_nodes
.
Examples
julia> using DelaunayTriangulation
julia> DelaunayTriangulation.num_sections([1, 2, 3, 4, 5, 1])
1
julia> DelaunayTriangulation.num_sections([[1, 2, 3, 4], [4, 5, 1]])
2
julia> DelaunayTriangulation.num_sections([[1, 2, 3], [3, 4, 5, 6, 7, 8], [8, 9], [9, 1]])
4