This module provides high-level functionality to generate, manage and refine meshes based on constrained Delaunay triangulations.

addconstraint!(mesh::Mesh, vertices::Vector{Int})

Adds a constraint, given as a list of existing vertices, into the DelaunayMeshes.

Remarks

• Constraints are closed polygons. A constraint edge from the last vertex to the first vertex is automatically inserted to ensure closure.

• All faces interior of the constrained region are marked as "exterior" to the DelaunayMeshes. A face is interior to the constrained region if it is located to the right of the given constraint polygon (i.e. the constraint vertices circle the interior region counter-clockwise).

• Constraint edges must not intersect. For performance reasons, this is not checked.

• Any vertex of the triangulation can intersect either zero or two constraint edges.

getvoronoivertices(mesh::Mesh)

Computes the Voronoi vertices of the given DelaunayMeshes.

Remarks

• The results are cached but need to be re-computed whenever a new vertex or a new constraint is pushed into the DelaunayMeshes.

Maximal ratio of circumcircle radius and length of shortest edge before a triangle is considered bad.

Implementation of the QuadEdge-Datastructure. [Guibas85]_

.. [Guibas85] Leonidas Guibas and Jorge Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams, ACM Transactions on Graphics, 4(2), 1985, 75-123.

DelaunayTesselation()

Creates an initial triangulation consisting of a maximal triangle and the corresponding faces.

Remarks

• The inner face coordinates are the centroid of the triangle.

• The outer face coordinates are located at $(∞, ∞)$.

Defines a mesh. A mesh consists of a bounding box providing bounds to the vertex coordinates, constraints consisting of closed polygons and the corresponding Delaunay tesselation.

Represents a triangle. It can be constructed from three vertices or a starting edge. It finds the edges enclosing the triangle and its inner face.

convert(::Type{DiffEqPDEBase.SimpleFEMMesh}, mesh::Mesh)

Converts the given mesh to a format that can be used by the FEM-solvers.

push!(mesh::Mesh, points::Array{Float64, 2})

Inserts a number of vertices into the mesh.

Remarks

• If the mesh was initialized without a bounding box, it is determined by the first set of vertices that are pushed into the triangualation. All consecutive push operations cannot insert vertices that exceed the bounding box limits

• New faces that are created by a push operation are marked as interior by default, i.e. it is forbidden to push vertices into an exterior region.

base(ei::Int)

Computes base index of index ei.

check_triangle(mesh::Mesh, tri::Triangle)

Checks if the triangle satisfies the quality measure $r/ar{pq} le eta$, with $r$ the radius of the circumcircle and $ar{pq}$ the length of its shortest edge.

Returns

• true, if the triangle satisfies the quality measure.

checkconvexityquadriliteral(sd::DelaunayTesselation, vertices::Vector{Int})

Checks if the given quadriliteral is strictly convex.

Remarks

• The end points of the quadriliteral must be given in CCW order

compute_circumcenter_radius(mesh::Mesh, p::VertexIndex, r::VertexIndex, q::VertexIndex)

Computes the position and radius of the triangle circumcenter.

Returns

• cx, cy, rs with $c_x$, $c_y$ the position and $r_s$ the radius square of the circum center.

compute_offcenter(mesh:Mesh, p::VertexIndex, q::VertexIndex, r::VertexIndex)

Computes position of offcenter[1] for given triangle $p - q - r$.

Remarks

• $p - q$ must be the shortest edge of the triangle, i.e. the smallest angle is located at $r$.

References

[1] Alper Üngör (2009). Off-centers: A new type of Steiner points for computing size-optimal quality-guaranteed Delaunay triangulations, Computational Geometry, 42 (2)

computescaleandshiftfromboundingbox(boundingBox::Vector{Float64})

Computes the scale and horizontal/vertical shift from a given bounding box. This establishes an aspect-ratio-conserving transformation from the given bounding box into a square that fits comfortably into the outer bounding triangle of the DelaunayMeshes. The square (blue) fills ten per cent of the maximally inscribed square (dashed).

Specifically, if $(c_x, c_y)$ denote the center of the bounding box and $Delta = max((x_mathrm{max} - x_mathrm{min}), (x_mathrm{max} - x_mathrm{min}))$ is the maximum extent of the bounding box, then the coordinate transformation to the new primed coordinates is given by $(x', y') = 0.1 (x - c_x, y - c_y)/Delta + (c_x', c_y')$, where $(c_x', c_y') = (1.5, 1.25)$ denotes the center of the inscribed square.

connect!{T}(sd::SubDivision, ai::Int, bi::Int, newFace::T)

Connects the end vertex of edge ai to the start vertex bi.

Remarks

• This operation adds another face to the subdivision. The new face will be to the right of the new edge and will be correctly assigned to all adjacent edges.

dest(sd::SubDivision, ei::Int)

Gets the index of the destination vertex of edge index ei.

dprev(sd::SubDivision, ei::Int)

Gets the next edge ending at the destination of ei in clockwise direction.

endpoints!(sd::SubDivision, ei::Int, vio::Int, vid::Int, lfi::Int, rfi::Int)

Assigns the start(end) point vio(vid) and the left(right) faces lfi(rfi) to given edge ei.

Remarks

• The start(end) points of the symmetric and symmetric dual edges are assigned correctly.

findintersectingedges(sd::DelaunayTesselation, v1::Int, v2::Int, eg::Int)

Finds all edges of the given tesselation that intersect with a virtual edge from v1 to v2.

" get_shortest_edge(mesh::Mesh, ai::VertexIndex, bi::VertexIndex, ci::VertexIndex)

Given a triangle with CCW-ordered vertices ai - bi - ci, it computes the edge length and returns a sorted tuple p - q - r such that the triangle $p - q - r$ has its shortest edge between p and q.

getadjacentquadriliteral(sd::DelaunayTesselation, ei::Int)

Gets vertices of quadriliteral formed by the two triangles adjacent to given edge in ccw order.

getalltriangles(sd::SubDivision)

Returns all triangles as edge lists.

Remarks

• The boundary edges are included.

getfacesinsideregion(mesh::Mesh, ei::Int)

Finds all faces that are located inside the same region as the face identified by org(ei).

Remarks

• The algorithm performs a breadth-first search over all adjacent triangles while omitting triangles that requires crossing a boundary.

incircle(sd::DelaunayTesselation, v1::Int, v2::Int, v3::Int, v4::Int)

Tests if the vertex v4 is strictly inside the circumcircle of the triangle v1-v2-v3.

insertconstraint!(sd::DelaunayTesselation, v1::Int, v2::Int)

Inserts constraint going from v1 to v2.

Remarks

• The constrained region is assumed to be on the right of the directed edge.

insertpoint!(sd::DelaunayTesselation, x::Point, ei::Int)

Inserts a given point into an existing DelaunayMeshes.

Remarks

• The algorithm identifies the triangle in the existing triangulation that contains the vertex to be inserted, taking <paramref name ="ei"/> as start point for the search. It then connects the newly-inserted point to all vertices of the enclosing triangle.

• If an existing vertex is already located at the point coordinates an error is thrown.

#Returns

• new edge, last edge of target triangle (lnext(lastEdge) = newEdge)

invrot(ei::Int)

Inverse operation of rot(ei).

lface(sd::SubDivision, ei::Int)

Returns the index to face left of given edge ei.

lnext(sd::SubDivision, ei::Int)

Gets the next edge around the left face of ei and starting at destination of ei.

locatevertex(sd::DelaunayTesselation, x::Point, ei::Int)

Locates point x in existing subdivision by traversing the triangulation starting at edge ei.

Remarks

• The point coordinates must be exactly inside the enclosing triangle.

• The algorithm used here [Brown]_ is more stable than the original version

.. [Brown] Brown, Faigle: A robust efficient algorithm for point location in triangulations

lprev(sd::SubDivision, ei::Int)

Gets the previous edge around the left face of ei and ending at source of ei.

makeedge!(sd::SubDivision)

Creates an empty edge and adds it to given SubDivision.

#returns

• Number of newly-added edge.

onext(sd::SubDivision, ei::Int)

Gets the next edge starting at the origin of ei in counter-clockwise direction.

oprev(sd::SubDivision, ei::Int)

Gets the next edge starting at the origin of ei in clockwise direction.

org(sd::SubDivision, ei::Int)

Gets the index of the origin vertex of edge index ei.

pointsintersect(p1::Point, q1::Point, p2::Point, q2::Point)

Checks if line segments given by their end points intersect.

Remarks

• Taken from geeksforgeeks.org/check-if-two-given-line-segments-intersect

function refine_triangle(mesh::Mesh, tri::Triangle)

Refines the triangle located to the left of edge ei by adding a new vertex at the offcenter or the midpoint of encroached edges.

Remarks

• If a new vertex at the off-center of the triangle does not encroach any segments it is inserted at the off-center.

• Otherwise, a new vertex is inserted at the midpoint of each edge that the off-center would encroach on. try

refine_valid_triangles!(mesh::

Gets the first triangle that does not satisfy the quality measure or null.

removedeletededges!(sd::SubDivision)

Removes all edges that were marked as deleted in DelaunayMeshes.

removeintersectingedges!(
  sd::DelaunayTesselation, v1::Int, v2::Int, intersecting::Vector{Int})

Removes all intersecting edges by iteratively swapping diagonals of enclosing quadriliterals.

Remarks

• For details see Sloan: A fast algorithm for generating constrained Delaunay triangulations.

• Returns the index of the constraint edge

restoredelaunay!(sd::DelaunayTesselation, ei::Int, si::Int, xi::Int)

Restores Delaunay constraint for edge structure by swapping edges of adjacent triangles.

Remarks

• It examines all triangles to check if the new vertex xi is inside its circumcircle.

• The algorithm cycles through all adjacent edges starting at startEdge and stopping at stopEdge.

• If an edge is swapped, its neighbours are examined as well.

lface(sd::SubDivision, ei::Int)

Returns the index to face left of given edge ei.

rightof(sd::DelaunayTesselation, vi::Int, ei::Int)
rightof(sd::DelaunayTesselation, x::Point, ei::Int)

Computes the location of vertex vi relative to line defined by ei.

Remarks

• Internally, the computation is forwarded to GeometricalPredicates.orientation.

Returns

• True, if vi is located to the right of the edge

rot(ei::Int)

Computes the index of the dual edge to index ei.

Remarks

• The dual edge is obtained by rotating ei counter-clockwise by 90 degrees.

• The start(end) points of the dual edge can be interpreted as representing the right(left) face.

splice!(sd::SubDivision, ai::Int, bi::Int)

Combines or splices two given edge rings ai and bi.

Remarks

• If the origins of ai and bi are identical, it cuts the two edge rings

• If the origins differ, it joins the two edge rings

• After the operation, the new edge rings satisfy the identities onext(ai) = onext(bi) and onext(bi) = onext(ai) and the corresponding identities for the dual rings.

• The origins of the edges are neither evaluated nor are theyaffected by this operation and need to be updated manually.

swap!(sd::DelaunayTesselation, ei::Int)

Swaps edge ei such that the new edge connects the apexes of the triangles adjacent to the old edge.

Remarks

• Specifially, if a = oprev(ei) and b = oprev(sym(ei)) before the swap, then the edge ei will connect dest(a) with dest(b) after the swap.

sym(ei::Int)

Computes index of symmetric index ei.

vertex_encroaches_segment(mesh::Mesh, ei::Int, vertex::Point)

Checks if a potential vertex encroaches the segment denoted by ei.

Remarks

• If edge ei is not a segment, i.e. not marked as a boundary, it always returns false