GitHub

Predicates

Certificates

DelaunayTriangulation.Certificate — Module
Certificate

This is an Enum that defines certificates returned from predicates. The instances, and associated certifiers, are:

  • Inside: is_inside
  • Degenerate: is_degenerate
  • Outside: is_outside
  • On: is_on
  • Left: is_left
  • Right: is_right
  • PositivelyOriented: is_positively_oriented
  • NegativelyOriented: is_negatively_oriented
  • Collinear: is_collinear
  • None: is_none or has_no_intersections
  • Single: is_single or has_one_intersection
  • Multiple: is_multiple or has_multiple_intersections
  • Touching: is_touching
  • Legal: is_legal
  • Illegal: is_illegal
  • Closer: is_closer
  • Further: is_further
  • Equidistant: is_equidistant
  • Obtuse: is_obtuse
  • Acute: is_acute
  • SuccessfulInsertion: is_successful_insertion
  • FailedInsertion: is_failed_insertion
  • PrecisionFailure: is_precision_failure
  • EncroachmentFailure: is_encroachment_failure
  • Above: is_above
  • Below: is_below
  • Visible: is_visible
  • Invisible: is_invisible
source
DelaunayTriangulation.is_positively_oriented — Function
is_positively_oriented(tri::Triangulation, curve_index) -> Bool

Tests if the curve_indexth curve in tri is positively oriented, returning true if so and false otherwise.

source
is_positively_oriented(cert::Certificate) -> Bool

Returns true if cert is PositivelyOriented, and false otherwise.

source
DelaunayTriangulation.is_touching — Function
is_touching(r1::BoundingBox, r2::BoundingBox) -> Bool

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

source
is_touching(cert::Certificate) -> Bool

Returns true if cert is Touching, and false otherwise.

source

Predicates

DelaunayTriangulation.triangle_orientation — Function
triangle_orientation(tri::Triangulation, i, j, k) -> Certificate 
triangle_orientation(tri::Triangulation, T) -> Certificate
triangle_orientation(p, q, r) -> Certificate

Computes the orientation of the triangle T = (i, j, k) with correspondig coordinates (p, q, r). The returned value is a Certificate, which is one of:

  • PositivelyOriented: The triangle is positively oriented.
  • Degenerate: The triangle is degenerate, meaning the coordinates are collinear.
  • NegativelyOriented: The triangle is negatively oriented.
source
DelaunayTriangulation.point_position_relative_to_circle — Function
point_position_relative_to_circle(a, b, c, p) -> Certificate

Given a circle through the coordinates (a, b, c), assumed to be positively oriented, computes the position of p relative to the circle. Returns a Certificate, which is one of:

  • Inside: p is inside the circle.
  • On: p is on the circle.
  • Outside: p is outside the triangle.
source
DelaunayTriangulation.point_position_relative_to_line — Function
point_position_relative_to_line(a, b, p) -> Certificate
point_position_relative_to_line(tri::Triangulation, i, j, u) -> Certificate

Tests the position of p (or the vertex u of tri) relative to the edge (a, b) (or the edge with vertices (i, j) of tri), returning a Certificate which is one of:

  • Left: p is to the left of the line.
  • Collinear: p is on the line.
  • Right: p is to the right of the line.
source
DelaunayTriangulation.point_closest_to_line — Function
point_closest_to_line(a, b, p, q) -> Certificate
point_closest_to_line(tri::Triangulation, i, j, u, v) -> Certificate

Given a line ℓ through (a, b) (or through the vertices (i, j)), tests if p (or the vertex u) is closer to ℓ than q (or the vertex v), assuming that p and q are to the left of ℓ, returning a Certificate which is one of:

  • Closer: p is closer to ℓ.
  • Further: q is closer to ℓ.
  • Equidistant: p and q are the same distance from ℓ.
source
DelaunayTriangulation.point_position_on_line_segment — Function
point_position_on_line_segment(a, b, p) -> Certificate
point_position_on_line_segment(tri::Triangulation, i, j, u) -> Certificate

Given a point p (or vertex u) and the line segment (a, b) (or edge (i, j)), assuming p to be collinear with a and b, computes the position of p relative to the line segment. The returned value is a Certificate which is one of:

  • On: p is on the line segment, meaning between a and b.
  • Degenerate: Either p == a or p == b, i.e. p is one of the endpoints.
  • Left: p is off and to the left of the line segment.
  • Right: p is off and to the right of the line segment.
source
DelaunayTriangulation.line_segment_intersection_type — Function
line_segment_intersection_type(p, q, a, b) -> Certificate 
line_segment_intersection_type(tri::Triangulation, u, v, i, j) -> Certificate

Given the coordinates (p, q) (or vertices (u, v)) and (a, b) (or vertices (i, j)) defining two line segments, tests the number of intersections between the two segments. The returned value is a Certificate, which is one of:

  • None: The line segments do not meet at any points.
  • Multiple: The closed line segments [p, q] and [a, b] meet in one or several points.
  • Single: The open line segments (p, q) and (a, b) meet in a single point.
  • Touching: One of the endpoints is on [a, b], but there are no other intersections.
source
DelaunayTriangulation.point_position_relative_to_triangle — Function
point_position_relative_to_triangle(a, b, c, p) -> Certificate
point_position_relative_to_triangle(tri::Triangulation, i, j, k, u) -> Certificate
point_position_relative_to_triangle(tri::Triangulation, T, u) -> Certificate

Given a positively oriented triangle with coordinates (a, b, c) (or triangle T = (i, j, k) of tri), computes the position of p (or vertex u) relative to the triangle. The returned value is a Certificate, which is one of:

  • Outside: p is outside of the triangle.
  • On: p is on one of the edges.
  • Inside: p is inside the triangle.
Ghost triangles

If T is a ghost triangle, then it is not checked if the point is on any of the ghost edges,

source
DelaunayTriangulation.point_position_relative_to_oriented_outer_halfplane — Function
point_position_relative_to_oriented_outer_halfplane(a, b, p) -> Certificate

Given an edge with coordinates (a, b) and a point p, tests the position of p relative to the oriented outer halfplane defined by (a, b). The returned value is a Certificate, which is one of:

  • Outside: p is outside of the oriented outer halfplane, meaning to the right of the line (a, b) or collinear with a and b but not on the line segment (a, b).
  • On: p is on the line segment [a, b].
  • Inside: p is inside of the oriented outer halfplane, meaning to the left of the line (a, b).

Extended help

The oriented outer halfplane is the union of the open halfplane defined by the region to the left of the oriented line (a, b), and the open line segment (a, b).

source
DelaunayTriangulation.is_legal — Function
is_legal(tri::Triangulation, i, j) -> Certificate 
is_legal(p, q, r, s) -> Certificate

Tests if the edge (p, q) (or the edge (i, j) of tri) is legal, where the edge (p, q) is incident to two triangles (p, q, r) and (q, p, s). In partiuclar, tests that s is not inside the triangle through (p, q, r). The returned value is a Certificate, which is one of:

  • Legal: The edge (p, q) is legal.
  • Illegal: The edge (p, q) is illegal.

If the edge (i, j) is a segment of tri or is a ghost edge, then the edge is always legal.

source
DelaunayTriangulation.triangle_line_segment_intersection — Function
triangle_line_segment_intersection(p, q, r, a, b) -> Certificate 
triangle_line_segment_intersection(tri::Triangulation, i, j, k, u, v) -> Certificate

Classifies the intersection of the line segment (a, b) (or the edge (u, v) of tri) with the triangle (p, q, r) (or the triangle (i, j, k) of tri). The returned value is a Certificate, which is one of:

  • Inside: (a, b) is entirely inside (p, q, r).
  • Single: (a, b) has one endpoint inside (p, q, r), and the other is outside.
  • Outside: (a, b) is entirely outside (p, q, r).
  • Touching: (a, b) is on (p, q, r)'s boundary, but not in its interior.
  • Multiple: (a, b) passes entirely through (p, q, r). This includes the case where a point is on the boundary of (p, q, r).
source
DelaunayTriangulation.find_edge — Function
find_edge(tri::Triangulation, T, ℓ) -> Edge

Given a triangle T = (i, j, k) of tri and a vertex ℓ of tri, returns the edge of T that contains ℓ. If no such edge exists, the edge (k, i) is returned.

source
DelaunayTriangulation.point_position_relative_to_circumcircle — Function
point_position_relative_to_circumcircle(tri::Triangulation, i, j, k, ℓ) -> Certificate
point_position_relative_to_circumcircle(tri::Triangulation, T, ℓ) -> Certificate

Tests the position of the vertex ℓ of tri relative to the circumcircle of the triangle T = (i, j, k). The returned value is a Certificate, which is one of:

  • Outside: ℓ is outside of the circumcircle of T.
  • On: ℓ is on the circumcircle of T.
  • Inside: ℓ is inside the circumcircle of T.
Ghost triangles

The circumcircle of a ghost triangle is defined as the oriented outer halfplane of the solid edge of the triangle. See point_position_relative_to_oriented_outer_halfplane.

Weighted triangulations

If tri is a weighted triangulation, then an orientation test is instead applied, testing the orientation of the lifted companions of each point to determine if ℓ is above or below the witness plane relative to (i, j, k). For ghost triangles, the same rule applies, although if the vertex is on the solid edge of the ghost triangle then, in addition to checking point_position_relative_to_oriented_outer_halfplane, we must check if the new vertex is not submerged by the adjoining solid triangle.

source
DelaunayTriangulation.point_position_relative_to_witness_plane — Function
point_position_relative_to_witness_plane(tri::Triangulation, i, j, k, ℓ) -> Certificate

Given a positively oriented triangle T = (i, j, k) of tri and a vertex ℓ of tri, returns the position of ℓ relative to the witness plane of T. The returned value is a Certificate, which is one of:

  • Above: ℓ is above the witness plane of T.
  • On: ℓ is on the witness plane of T.
  • Below: ℓ is below the witness plane of T.

Extended help

The witness plane of a triangle is defined as the plane through the triangle (i⁺, j⁺, k⁺) where, for example, pᵢ⁺ = (x, y, x^2 + y^2 - wᵢ) is the lifted companion of i and (x, y) are the coordinates of the ith vertex. Moreover, by the orientation of ℓ relative to this witness plane we are referring to ℓ⁺'s position, not the plane point ℓ.

source
DelaunayTriangulation.opposite_angle — Function
opposite_angle(p, q, r) -> Certificate

Tests the angle opposite to the edge (p, q) in the triangle (p, q, r), meaning ∠prq. The returned value is a Certificate, which is one of:

  • Obtuse: The angle opposite to (p, q) is obtuse.
  • Right: The angle opposite to (p, q) is a right angle.
  • Acute: The angle opposite to (p, q) is acute.
Angle between two vectors

This function computes (p - r) ⋅ (q - r). If you want the angle between vectors a = pq and b = pr, then you should use opposite_angle(r, q, p) = (r - p) ⋅ (q - p).

source
DelaunayTriangulation.point_position_relative_to_diametral_circle — Function
point_position_relative_to_diametral_circle(p, q, r) -> Certificate

Given an edge (p, q) and a point r, returns the position of r relative to the diametral circle of (p, q). The returned value is a Certificate, which is one of:

  • Inside: r is inside the diametral circle.
  • On: r is on the diametral circle.
  • Outside: r is outside the diametral circle.

Extended help

The check is done by noting that a point is in the diametral circle if, and only if, the angle at r is obtuse.

source
DelaunayTriangulation.point_position_relative_to_diametral_lens — Function
point_position_relative_to_diametral_lens(p, q, r, lens_angle=30.0) -> Certificate

Given an edge (p, q) and a point r, returns the position of r relative to the diametral lens of (p, q) with lens angle lens_angle (in degrees). The returned value is a Certificate, which is one of:

  • Inside: r is inside the diametral lens.
  • On: r is on the diametral lens.
  • Outside: r is outside the diametral lens.
Warning

This function assumes that the lens angle is at most 45°.

Extended help

The diametral lens is slightly similar to a diametral circle. Let us first define the standard definition of a diametral lens, where lens_angle = 30°, and then we define its generalisation. The standard definition was introduced by Shewchuk in 2002 in this paper, and the generalisation was originally described in Section 3.4 of Shewchuk's 1997 PhD thesis here (as was the standard definition, of course).

Standard definition: Let the segment be s ≔ (p, q) and let ℓ be the perpendicular bisector of s. Define two circles C⁺ and C⁻ whose centers lie left and right of s, respectively, both the same distance away from the midpoint m = (p + q)/2. By placing each disk a distance |s|/(2√3) away from m and extending the disks so that they both touch p and q, meaning they each have radius |s|/√3, we obtain disks that touch p and q as well as the center of the other disk. The intersection of the two disks defines the diametral lens. The lens angle associated with this lens is 30°, as we could draw lines between p and q and the poles of the disks to form isosceles triangles on each side, giving angles of 30° at p and q.

Generalised definition: The generalisation of the above definition aims to generalise the lens angle to some angle θ. In particular, let us draw a line from p towards some point u which is left of s and on the perpendicular bisector, where the line is at an angle θ. This defines a triplet of points (p, q, u) from which we can define a circle, and similarly for a point v right of s. The intersection of these two circles is the diametral lens with angle θ. We can also figure out how far u is along the perpendicular bisector, i.e. how far away it is from (p + q)/2, using basic trigonometry. Let m = (p + q)/2, and consider the triangle △pmu. The side lengths of this triangle are |pm| = |s|/2, |mu| ≔ b, and |up| ≔ c. Let us first compute c. We have cos(θ) = |pm|/|up| = |s|/(2c), and so c = |s|/(2cos(θ)). So, sin(θ) = |mu|/|up| = b/c, which gives b = csin(θ) = |s|sin(θ)/(2cos(θ)) = |s|tan(θ)/2. So, u is a distance |s|tan(θ)/2 from the midpoint. Notice that in the case θ = 30°, tan(θ) = √3/3, giving b = |s|√3/6 = |s|/(2√3), which is the same as the standard definition.

To test if a point r is inside the diametral lens with lens angle θ°, we simply have to check the angle at that point, i.e. the angle at r in the triangle pqr. If this angle is greater than 180° - 2θ°, then r is inside of the lens. This result comes from Shewchuk (2002). Note that this is the same as a diametral circle in the case θ° = 45°.

source
DelaunayTriangulation.is_boundary_edge — Function
is_boundary_edge(tri::Triangulation, ij) -> Bool
is_boundary_edge(tri::Triangulation, i, j) -> Bool

Tests if the edge (i, j) is a boundary edge of tri, meaning (j, i) adjoins a ghost vertex.

source
DelaunayTriangulation.is_boundary_triangle — Function
is_boundary_triangle(tri::Triangulation, T) -> Bool
is_boundary_triangle(tri::Triangulation, i, j, k) -> Bool

Returns true if the triangle T = (i, j, k) of tri has an edge on the boundary, and false otherwise.

source
DelaunayTriangulation.is_boundary_node — Function
is_boundary_node(tri::Triangulation, i) -> (Bool, Vertex)

Tests if the vertex i is a boundary node of tri.

Arguments

Outputs

  • flag: true if i is a boundary node, and false otherwise.
  • g: Either the ghost vertex corresponding with the section that i lives on if flag is true, or 0 otherwise.
source
DelaunayTriangulation.contains_segment — Function
contains_segment(tri::Triangulation, ij) -> Bool 
contains_segment(tri::Triangulation, i, j) -> Bool

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

source
DelaunayTriangulation.contains_triangle — Function
contains_triangle(T, V) -> (Triangle, Bool)

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

Examples

julia> using DelaunayTriangulation

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

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

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

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

julia> DelaunayTriangulation.contains_triangle(9, 7, 8, V)
((7, 8, 9), true)
source
DelaunayTriangulation.unoriented_edge_exists — Function
unoriented_edge_exists(tri::Triangulation, ij) -> Bool 
unoriented_edge_exists(tri::Triangulation, i, j) -> Bool

Tests if the unoriented edge (i, j) is in tri, returning true if so and false otherwise.

source
DelaunayTriangulation.has_multiple_curves — Function
has_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
source
DelaunayTriangulation.has_multiple_sections — Function
has_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
source
DelaunayTriangulation.is_weighted — Function
is_weighted(weights) -> Bool

Returns true if weights represents a set of weights that are not all zero, and false otherwise. Note that even for vectors like zeros(n), this will return true; by default, false is returned only for weights = ZeroWeight().

source
is_weighted(tri::Triangulation) -> Bool

Returns true if tri is weighted, and false otherwise.

source