Data Structures

Adjacent{IntegerType, EdgeType}

Struct for storing adjacency relationships for a triangulation.

Fields

• adjacent::Dict{EdgeType, IntegerType}

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

Constructors

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

Adjacent2Vertex{IntegerType, EdgesType}

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

Fields

• adjacent2vertex::Dict{IntegerType, EdgesType}

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

Constructors

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

Graph{IntegerType}

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

Fields

• vertices::Set{IntegerType}

The set of vertices in the underlying triangulation.

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

The set of edges in the underlying triangulation.

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

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

Constructors

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

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

Struct representing a triangulation, as constructed by triangulate.

Fields

• points::P

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

• triangles::T

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

• boundary_nodes::BN

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

• interior_segments::Es

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

• all_segments::Es

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

• weights::W

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

• adjacent::Adjacent{I,E}

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

• adjacent2vertex::Adjacent2Vertex{I,Es}

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

• graph::Graph{I}

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

• boundary_curves::BC

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

• boundary_edge_map::BEM

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

• ghost_vertex_map::GVM

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

• ghost_vertex_ranges::GVR

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

• convex_hull::ConvexHull{P,I}

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

• representative_point_list::BPL

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

• polygon_hierarchy::PolygonHierarchy{I}

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

• boundary_enricher::BE

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

• cache::C

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

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

Struct for representing a Voronoi tessellation.

See also voronoi.

Fields

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

ConvexHull{PointsType, IntegerType}

Struct for representing a convex hull. See also convex_hull.

Fields

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

Constructors

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

InsertionEventHistory{T,E}

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

Fields

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

Constructor

The default constructor is available, but we also provide

InsertionEventHistory(tri::Triangulation)

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