Voronoi Tessellations
DelaunayTriangulation.voronoi
— Functionvoronoi(tri::Triangulation; clip=false, smooth=false, kwargs...) -> VoronoiTessellation
Computes the Voronoi tessellation dual to a triangulation. If the triangulation is weighted, this computes the power diagram.
Arguments
tri
: The triangulation.
Keyword Arguments
clip=false
: Iftrue
, then the Voronoi tessellation is clipped to the convex hull of the triangulation. Otherwise, the Voronoi tessellation is unbounded.clip_polygon=nothing
: Ifclip=true
, then this is the polygon to clip the Voronoi tessellation to. Ifnothing
, the convex hull of the triangulation is used. The polygon should be defined as aTuple
of the form(points, boundary_nodes)
where theboundary_nodes
are vertices mapping to coordinates inpoints
, adhering to the usual conventions for defining boundaries.
The clipping polygon must be convex. If it is not, unexpected results may occur.
smooth=false
: Iftrue
, then the Voronoi tessellation is smoothed into a centroidal tessellation. Otherwise, the Voronoi tessellation is not smoothed. Must haveclip=true
ifsmooth=true
.predicates::AbstractPredicateKernel=AdaptiveKernel()
: Method to use for computing predicates. Can be one ofFastKernel
,ExactKernel
, andAdaptiveKernel
. See the documentation for a further discussion of these methods.kwargs...
: Additional keyword arguments passed tocentroidal_smooth
ifsmooth=true
.
Output
vorn
: TheVoronoiTessellation
.
DelaunayTriangulation.centroidal_smooth
— Functioncentroidal_smooth(vorn::VoronoiTessellation; maxiters=1000, tol=default_displacement_tolerance(vorn), rng=Random.default_rng(), predicates::AbstractPredicateKernel=AdaptiveKernel(), kwargs...) -> VoronoiTessellation
Smooths vorn
into a centroidal tessellation so that the new tessellation is of a set of generators whose associated Voronoi polygon is that polygon's centroid.
Arguments
vorn
: TheVoronoiTessellation
.
Keyword Arguments
maxiters=1000
: The maximum number of iterations.clip_polygon=nothing
: Ifclip=true
, then this is the polygon to clip the Voronoi tessellation to. Ifnothing
, the convex hull of the triangulation is used. The polygon should be defined as aTuple
of the form(points, boundary_nodes)
where theboundary_nodes
are vertices mapping to coordinates inpoints
, adhering to the usual conventions for defining boundaries. Must be a convex polygon.tol=default_displacement_tolerance(vorn)
: The displacement tolerance. Seedefault_displacement_tolerance
for the default.rng=Random.default_rng()
: The random number generator.predicates::AbstractPredicateKernel=AdaptiveKernel()
: Method to use for computing predicates. Can be one ofFastKernel
,ExactKernel
, andAdaptiveKernel
. See the documentation for a further discussion of these methods.kwargs...
: Extra keyword arguments passed toretriangulate
.
Outputs
vorn
: The updatedVoronoiTessellation
. This is not done in-place.
Extended help
The algorithm is simple. We iteratively smooth the generators, moving them to the centroid of their associated Voronoi polygon for the current tessellation, continuing until the maximum distance moved of any generator is less than tol
. Boundary generators are not moved.
DelaunayTriangulation.get_triangulation
— Functionget_triangulation(cache::TriangulationCache) -> Triangulation
Returns the Triangulation
stored in cache
.
get_triangulation(vorn::VoronoiTessellation) -> Triangulation
Gets the underlying triangulation of the Voronoi tessellation vorn
.
DelaunayTriangulation.get_generators
— Functionget_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_polygon_points
— Functionget_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
— Functionget_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_circumcenter_to_triangle
— Functionget_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.
get_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_triangle_to_circumcenter
— Functionget_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)
.
get_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_unbounded_polygons
— Functionget_unbounded_polygons(vorn::VoronoiTessellation) -> Set{Index}
Gets the unbounded polygons of the Voronoi tessellation vorn
as a Set
of polygon indices.
DelaunayTriangulation.get_cocircular_circumcenters
— Functionget_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_boundary_polygons
— Functionget_boundary_polygons(vorn::VoronoiTessellation) -> Set{Index}
Gets the boundary polygons of the Voronoi tessellation vorn
as a Set
of polygon indices.
DelaunayTriangulation.get_generator
— Functionget_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_polygon_point
— Functionget_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
— Functionget_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.num_polygons
— Functionnum_polygons(vor::VoronoiTessellation) -> Integer
Returns the number of polygons in the Voronoi tessellation vor
.
DelaunayTriangulation.num_polygon_vertices
— Functionnum_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_generators
— Functionnum_generators(vor::VoronoiTessellation) -> Integer
Returns the number of generators in the Voronoi tessellation vor
.
DelaunayTriangulation.get_centroid
— Functionget_centroid(stats::TriangulationStatistics, T)
Returns the centroid field from the individual triangle statistics for the triangle T
in the TriangulationStatistics
stats
.
get_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.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′
.
polygon_bounds(points, boundary_nodes, check_all_curves=Val(false)) -> (Number, Number, Number, Number)
Computes the bounding box of the polygon defined by (points, boundary_nodes)
. The boundary_nodes
must match the specification in the documentation and in check_args
. If check_all_curves
is true
, then the bounding box of the union of all curves of the polygon
is computed instead of just the first curve.
DelaunayTriangulation.get_polygon_coordinates
— Functionget_polygon_coordinates(vorn::VoronoiTessellation, i, bounding_box=nothing; predicates::AbstractPredicateKernel=AdaptiveKernel()) -> Vector{NTuple{2,Number}}
Returns the coordinates of the polygon with index i
in vorn
. If bounding_box
is provided, then the polygon is clipped to the bounding box. If the polygon is unbounded, then bounding_box
must be provided.
See also get_unbounded_polygon_coordinates
and get_bounded_polygon_coordinates
.
Arguments
vorn
: TheVoronoiTessellation
.i
: The index of the polygon.bounding_box=nothing
: The bounding box to clip the polygon to. Ifnothing
, then the polygon is not clipped. If the polygon is unbounded, thenbounding_box
must be provided.
Keyword Arguments
predicates::AbstractPredicateKernel=AdaptiveKernel()
: Method to use for computing predicates. Can be one ofFastKernel
,ExactKernel
, andAdaptiveKernel
. See the documentation for a further discussion of these methods.
Outputs
coords
: The coordinates of the polygon. This is a circular vector.
DelaunayTriangulation.polygon_features
— Functionpolygon_features(vor::VoronoiTessellation, i) -> (Number, NTuple{2, Number})
Gets the area and centroid of the polygon with index i
in vor
.
polygon_features(points, boundary_nodes) -> (Number, NTuple{2, Number})
Computes the signed area and centroid of the polygon defined by (points, boundary_nodes)
. The boundary_nodes
must match the specification in the documentation and in check_args
.
DelaunayTriangulation.toggle_inf_warn!
— Functiontoggle_inf_warn!()
Toggle the warning for infinite circumcenters in the Voronoi tessellation. By default, this warning is enabled.