Predicates
Certificates
DelaunayTriangulation.Certificate
— ModuleCertificate
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
orhas_no_intersections
Single
:is_single
orhas_one_intersection
Multiple
:is_multiple
orhas_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
DelaunayTriangulation.is_inside
— Functionis_inside(cert::Certificate) -> Bool
Returns true
if cert
is Inside
, and false
otherwise.
DelaunayTriangulation.is_degenerate
— Functionis_degenerate(cert::Certificate) -> Bool
Returns true
if cert
is Degenerate
, and false
otherwise.
DelaunayTriangulation.is_outside
— Functionis_outside(cert::Certificate) -> Bool
Returns true
if cert
is Outside
, and false
otherwise.
DelaunayTriangulation.is_on
— Functionis_on(cert::Certificate) -> Bool
Returns true
if cert
is On
, and false
otherwise.
DelaunayTriangulation.is_left
— Functionis_left(cert::Certificate) -> Bool
Returns true
if cert
is Left
, and false
otherwise.
DelaunayTriangulation.is_right
— Functionis_right(cert::Certificate) -> Bool
Returns true
if cert
is Right
, and false
otherwise.
DelaunayTriangulation.is_positively_oriented
— Functionis_positively_oriented(tri::Triangulation, curve_index) -> Bool
Tests if the curve_index
th curve in tri
is positively oriented, returning true
if so and false
otherwise.
is_positively_oriented(cert::Certificate) -> Bool
Returns true
if cert
is PositivelyOriented
, and false
otherwise.
DelaunayTriangulation.is_negatively_oriented
— Functionis_negatively_oriented(cert::Certificate) -> Bool
Returns true
if cert
is NegativelyOriented
, and false
otherwise.
DelaunayTriangulation.is_collinear
— Functionis_collinear(cert::Certificate) -> Bool
Returns true
if cert
is Collinear
, and false
otherwise.
DelaunayTriangulation.is_none
— Functionis_none(cert::Certificate) -> Bool
Returns true
if cert
is None
, and false
otherwise.
DelaunayTriangulation.has_no_intersections
— Functionhas_no_intersections(cert::Certificate) -> Bool
Returns true
if cert
is None
, and false
otherwise. Synonymous with is_none
.
DelaunayTriangulation.is_single
— Functionis_single(cert::Certificate) -> Bool
Returns true
if cert
is Single
, and false
otherwise.
DelaunayTriangulation.has_one_intersection
— Functionhas_one_intersection(cert::Certificate) -> Bool
Returns true
if cert
is Single
, and false
otherwise. Synonymous with is_single
.
DelaunayTriangulation.is_multiple
— Functionis_multiple(cert::Certificate) -> Bool
Returns true
if cert
is Multiple
, and false
otherwise.
DelaunayTriangulation.has_multiple_intersections
— Functionhas_multiple_intersections(cert::Certificate) -> Bool
Returns true
if cert
is Multiple
, and false
otherwise. Synonymous with is_multiple
.
DelaunayTriangulation.is_touching
— Functionis_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.
is_touching(cert::Certificate) -> Bool
Returns true
if cert
is Touching
, and false
otherwise.
DelaunayTriangulation.is_illegal
— Functionis_illegal(cert::Certificate) -> Bool
Returns true
if cert
is Illegal
, and false
otherwise.
DelaunayTriangulation.is_closer
— Functionis_closer(cert::Certificate) -> Bool
Returns true
if cert
is Closer
, and false
otherwise.
DelaunayTriangulation.is_further
— Functionis_further(cert::Certificate) -> Bool
Returns true
if cert
is Further
, and false
otherwise.
DelaunayTriangulation.is_equidistant
— Functionis_equidistant(cert::Certificate) -> Bool
Returns true
if cert
is Equidistant
, and false
otherwise.
DelaunayTriangulation.is_obtuse
— Functionis_obtuse(cert::Certificate) -> Bool
Returns true
if cert
is Obtuse
, and false
otherwise.
DelaunayTriangulation.is_acute
— Functionis_acute(cert::Certificate) -> Bool
Returns true
if cert
is Acute
, and false
otherwise.
DelaunayTriangulation.is_above
— Functionis_above(cert::Certificate) -> Bool
Returns true
if cert
is Above
, and false
otherwise.
DelaunayTriangulation.is_below
— Functionis_below(cert::Certificate) -> Bool
Returns true
if cert
is Below
, and false
otherwise.
Predicates
DelaunayTriangulation.AbstractPredicateKernel
— Typeabstract type AbstractPredicateKernel
Abstract type for defining a method for computing predicates. The subtypes are:
FastKernel
: Uses the determinant definitions of the predicates, with no adaptivity or exact arithmetic.ExactKernel
: Uses ExactPredicates.jl.AdaptiveKernel
: Uses AdaptivePredicates.jl.
Please see the documentation for more information on the differences between these predicate types.
DelaunayTriangulation.FastKernel
— TypeFastKernel()
Pass this to predicates to declare that determinant definitions of predicates should be used, avoiding adaptivity and exact arithmetic.
See also ExactKernel
and AdaptiveKernel
.
DelaunayTriangulation.ExactKernel
— TypeExactKernel()
Pass this to predicates to use ExactPredicates.jl for computing predicates.
See also FastKernel
and AdaptiveKernel
.
DelaunayTriangulation.AdaptiveKernel
— TypeAdaptiveKernel()
Pass this to predicates to use AdaptivePredicates.jl for computing predicates.
See also FastKernel
and ExactKernel
.
DelaunayTriangulation.orient_predicate
— Functionorient_predicate([kernel::AbstractPredicateKernel,] p, q, r) -> Integer
Returns
1
:(p, q, r)
is positively oriented.0
:(p, q, r)
is collinear / degenerate.-1
:(p, q, r)
is negatively oriented.
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.
orient_predicate([kernel::AbstractPredicateKernel,] p, q, r; cache = nothing) -> Integer
Returns
1
:(p, q, r, s)
is positively oriented.0
:(p, q, r, s)
is collinear / degenerate.-1
:(p, q, r, s)
is negatively oriented.
Here, a positively oriented tetrahedron (p, q, r, s)
takes the form
z.
.
,/
s
,/|'\
,/ | '\
,/ '. '\
,/ | '\
,/ | '\
p-----------'.--------q --> x
'\. | ,/
'\. | ,/
'\. '. ,/
'\. |/
'r
'\.
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.
The optional cache
keyword argument can be used for preallocating memory for intermediate results, passing the argument from AdaptivePredicates.orient3adapt_cache(T)
, where T
is the number type of the input points. If nothing
is passed, no cache is used. This is only needed if an AdaptiveKernel()
is used.
DelaunayTriangulation.incircle_predicate
— Functionincircle_predicate([kernel::AbstractPredicateKernel,] a, b, c, p; cache = nothing) -> Integer
Assuming that (a, b, c)
is a positively oriented triangle, returns
1
: Ifp
is inside the circle defined by(a, b, c)
.0
: Ifp
is on the circle defined by(a, b, c)
.-1
: Ifp
is outside the circle defined by(a, b, c)
.
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.
The optional cache
keyword argument can be used for preallocating memory for intermediate results, passing the argument from AdaptivePredicates.incircleadapt_cache(T)
, where T
is the number type of the input points. If nothing
is passed, no cache is used. This is only needed if an AdaptiveKernel()
is used.
DelaunayTriangulation.parallelorder_predicate
— Functionparallelorder_predicate([kernel::AbstractPredicateKernel,] a, b, p, q) -> Integer
Returns
1
:q
is closer to the line(a, b)
thanp
.0
:p
andq
are equidistant from the line(a, b)
.-1
:p
is closer to the line(a, b)
thanq
.
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.angle_is_acute_predicate
— Functionangle_is_acute([kernel::AbstractPredicateKernel,] p, q, r)
Tests if the angle opposite (p, q)
in the triangle (p, q, r)
, meaning ∠prq
, is acute, returning:
1
:∠prq
is acute.0
:∠prq
is a right angle.-1
:∠prq
is obtuse.
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.sameside_predicate
— Functionsameside_predicate(a, b, p) -> Integer
Assuming all of a, b, p
are collinear, returns
1
:a
andb
are on the same side ofp
on the line.0
:a == p
orb == p
.-1
:a
andb
are on different sides ofp
on the line.
The difference in the argument order to ExactPredicates.jl is to match the convention that the main point being tested is the last argument.
DelaunayTriangulation.meet_predicate
— Functionmeet_predicate([kernel::AbstractPredicateKernel], p, q, a, b) -> Integer
Returns
1
: The open line segments(p, q)
and(a, b)
meet in a single point.0
: The closed line segments[p, q]
and[a, b]
meet in one or several points.-1
: Otherwise.
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.triangle_orientation
— Functiontriangle_orientation([kernel::AbstractPredicateKernel=AdaptiveKernel(),] tri::Triangulation, i, j, k) -> Certificate
triangle_orientation([kernel::AbstractPredicateKernel=AdaptiveKernel(),] tri::Triangulation, T) -> Certificate
triangle_orientation([kernel::AbstractPredicateKernel=AdaptiveKernel(),] 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.
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.point_position_relative_to_circle
— Functionpoint_position_relative_to_circle([kernel::AbstractPredicateKernel=AdaptiveKernel(),] a, b, c, p; cache = nothing) -> 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.
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.
The cache
keyword argument is passed to [incircle_predicate
] and should be one of
nothing
: No cache is used.AdaptivePredicates.incircleadapt_cache(T)
, whereT
is the number type used (Float64
orFloat32
).
The cache is only needed if an AdaptiveKernel()
is used.
DelaunayTriangulation.point_position_relative_to_line
— Functionpoint_position_relative_to_line([kernel::AbstractPredicateKernel=AdaptiveKernel(),] a, b, p) -> Certificate
point_position_relative_to_line([kernel::AbstractPredicateKernel=AdaptiveKernel(),] 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.
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.point_closest_to_line
— Functionpoint_closest_to_line([kernel::AbstractPredicateKernel=AdaptiveKernel(),] a, b, p, q) -> Certificate
point_closest_to_line([kernel::AbstractPredicateKernel=AdaptiveKernel(),] 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
andq
are the same distance fromℓ
.
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.point_position_on_line_segment
— Functionpoint_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 betweena
andb
.Degenerate
: Eitherp == a
orp == 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.
DelaunayTriangulation.line_segment_intersection_type
— Functionline_segment_intersection_type([kernel::AbstractPredicateKernel=AdaptiveKernel(),] p, q, a, b) -> Certificate
line_segment_intersection_type([kernel::AbstractPredicateKernel=AdaptiveKernel(),] 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.
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.point_position_relative_to_triangle
— Functionpoint_position_relative_to_triangle([kernel::AbstractPredicateKernel=AdaptiveKernel(),] a, b, c, p) -> Certificate
point_position_relative_to_triangle([kernel::AbstractPredicateKernel=AdaptiveKernel(),] tri::Triangulation, i, j, k, u) -> Certificate
point_position_relative_to_triangle([kernel::AbstractPredicateKernel=AdaptiveKernel(),] 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.
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.
If T
is a ghost triangle, then it is not checked if the point is on any of the ghost edges,
DelaunayTriangulation.point_position_relative_to_oriented_outer_halfplane
— Functionpoint_position_relative_to_oriented_outer_halfplane([kernel::AbstractPredicateKernel=AdaptiveKernel(),] 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 witha
andb
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)
.
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.
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)
.
DelaunayTriangulation.is_legal
— Functionis_legal([kernel::AbstractPredicateKernel=AdaptiveKernel(),] tri::Triangulation, i, j; cache = nothing) -> Certificate
is_legal([kernel::AbstractPredicateKernel=AdaptiveKernel(),] p, q, r, s[, cache = nothing]) -> 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.
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.
The cache
keyword argument is passed to [point_position_relative_to_circumcircle
] and should be one of
nothing
: No cache is used.AdaptivePredicates.incircleadapt_cache(T)
, whereT
is the number type used (Float64
orFloat32
).
The cache is only needed if an AdaptiveKernel()
is used.
DelaunayTriangulation.triangle_line_segment_intersection
— Functiontriangle_line_segment_intersection([kernel::AbstractPredicateKernel=AdaptiveKernel(),] p, q, r, a, b) -> Certificate
triangle_line_segment_intersection([kernel::AbstractPredicateKernel=AdaptiveKernel(),] 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)
.
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.find_edge
— Functionfind_edge([kernel::AbstractPredicateKernel=AdaptiveKernel(),] 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. You can control the method for computing predicates using the kernel
argument.
DelaunayTriangulation.point_position_relative_to_circumcircle
— Functionpoint_position_relative_to_circumcircle([kernel::AbstractPredicateKernel=AdaptiveKernel(),] tri::Triangulation, i, j, k, ℓ; cache = nothing) -> Certificate
point_position_relative_to_circumcircle([kernel::AbstractPredicateKernel=AdaptiveKernel(),] tri::Triangulation, T, ℓ; cache = nothing) -> 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 ofT
.On
:ℓ
is on the circumcircle ofT
.Inside
:ℓ
is inside the circumcircle ofT
.
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.
The cache
keyword argument is useful when an AdaptiveKernel()
is used. Depending on whether the triangulation is weighted or not, the cache should be of the following:
nothing
: No cache is used.AdaptivePredicates.incircleadapt_cache(T)
, whereT
is the number type used (Float64
orFloat32
). This is used for unweighted triangulations.AdaptivePredicates.orient3adapt_cache(T)
, whereT
is the number type used (Float64
orFloat32
). This is used for weighted triangulations.
In case the wrong cache type is used, it is replaced with nothing
.
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
.
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.
DelaunayTriangulation.point_position_relative_to_witness_plane
— Functionpoint_position_relative_to_witness_plane([kernel::AbstractPredicateKernel=AdaptiveKernel(),] tri::Triangulation, i, j, k, ℓ; cache = nothing) -> 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 ofT
.On
:ℓ
is on the witness plane ofT
.Below
:ℓ
is below the witness plane ofT
.
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.
The cache
keyword argument is useful when an AdaptiveKernel()
is used, and should be one of:
nothing
: No cache is used.AdaptivePredicates.orient3adapt_cache(T)
, whereT
is the number type used (Float64
orFloat32
).
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 i
th vertex. Moreover, by the orientation of ℓ
relative to this witness plane we are referring to ℓ⁺
's position, not the plane point ℓ
.
DelaunayTriangulation.opposite_angle
— Functionopposite_angle([kernel::AbstractPredicateKernel=AdaptiveKernel(),] 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.
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.
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)
.
DelaunayTriangulation.point_position_relative_to_diametral_circle
— Functionpoint_position_relative_to_diametral_circle([kernel::AbstractPredicateKernel=AdaptiveKernel(),] 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.
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.
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.
DelaunayTriangulation.point_position_relative_to_diametral_lens
— Functionpoint_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.
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°
.
DelaunayTriangulation.is_ghost_vertex
— Functionis_ghost_vertex(i) -> Bool
Tests if i
is a ghost vertex, meaning i ≤ -1
.
DelaunayTriangulation.is_boundary_edge
— Functionis_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.
DelaunayTriangulation.is_boundary_triangle
— Functionis_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.
DelaunayTriangulation.is_ghost_edge
— Functionis_ghost_edge(ij) -> Bool
is_ghost_edge(i, j) -> Bool
Tests if the edge (i, j)
is a ghost edge, meaning i
or j
is a ghost vertex.
DelaunayTriangulation.is_ghost_triangle
— Functionis_ghost_triangle(T) -> Bool
is_ghost_triangle(i, j, k) -> Bool
Tests if T = (i, j, k)
is a ghost triangle, meaning i
, j
or k
is a ghost vertex.
DelaunayTriangulation.is_boundary_node
— Functionis_boundary_node(tri::Triangulation, i) -> (Bool, Vertex)
Tests if the vertex i
is a boundary node of tri
.
Arguments
tri::Triangulation
: TheTriangulation
.i
: The vertex to test.
Outputs
flag
:true
ifi
is a boundary node, andfalse
otherwise.g
: Either the ghost vertex corresponding with the section thati
lives on ifflag
is true, or 0 otherwise.
DelaunayTriangulation.contains_segment
— Functioncontains_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.
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.edge_exists
— Functionedge_exists(tri::Triangulation, ij) -> Bool
edge_exists(tri::Triangulation, i, j) -> Bool
Tests if the edge (i, j)
is in tri
, returning true
if so and false
otherwise.
See also unoriented_edge_exists
.
DelaunayTriangulation.unoriented_edge_exists
— Functionunoriented_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.
DelaunayTriangulation.has_ghost_triangles
— Functionhas_ghost_triangles(tri::Triangulation) -> Bool
Returns true
if tri
has ghost triangles, and false
otherwise.
DelaunayTriangulation.is_constrained
— Functionis_constrained(tri::Triangulation) -> Bool
Returns true
if tri
has constrained edges (segments), and false
otherwise.
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.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_boundary_nodes
— Functionhas_boundary_nodes(tri::Triangulation) -> Bool
Returns true
if tri
has boundary nodes, and false
otherwise.
DelaunayTriangulation.is_weighted
— Functionis_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()
.
is_weighted(tri::Triangulation) -> Bool
Returns true
if tri
is weighted, and false
otherwise.
is_weighted(vorn::VoronoiTessellation) -> Bool
Returns true
if the Voronoi tessellation vorn
is weighted, and false
otherwise.
DelaunayTriangulation.is_negativelyoriented
— Functionis_negativelyoriented(cert::Certificate) -> Bool
Returns true
if cert
is NegativelyOriented
, and false
otherwise.
DelaunayTriangulation.is_positivelyoriented
— Functionis_positivelyoriented(cert::Certificate) -> Bool
Returns true
if cert
is PositivelyOriented
, and false
otherwise.