Voronoi Tessellation

The data structure for a Voronoi tessellation is reasonably simple. The data structure here is probably not as exhaustive as it could be, but it is sufficient.


Struct for a Voronoi tessellation.


  • triangulation::Tr

The underlying triangulation, dual to the tessellation (unless there are constraints, in which case the tessellation is no longer dual, but it's still used).

  • generators::Dict{I, P}

The generators for each polygon. These are simply the points present in the triangulation. The keys are the vertices, while the values are the coordinates; we need to use a Dict in case the triangulation is missing points.

  • polygon_points::Vector{P}

The points defining the vertices of the polygons. The points are not guaranteed to be unique if a circumcenter appears on the boundary and you are considering a clipped tessellation.

See also get_polygon_coordinates.

  • polygons::Dict{I, Vector{I}}

A Dict mapping a polygon index (same as a generator index) to the vertices of the polygon. The polygons are given in counter-clockwise order, and their 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 index 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 index is last.

  • unbounded_polygons::Set{I}

A Set of the indices of the unbounded polygons.

  • cocircular_circumcenters::S

A Set of the indices of the circumcenters that come from triangles that are cocircular with another triangle's vertices, and adjoin said triangles.

  • adjacent::Adjacent{I, E}

An Adjacent struct that stores the adjacency information for the polygons, mapping an oriented edge to the polygon to which it belongs.

  • boundary_polygons::Set{I}

A Set of the indices of the polygons that are on the boundary of the tessellation. Only relevant for clipped tessellations, otherwise see unbounded_polygons.

Each field has its own accessor:

There are several useful methods available for working with this data structure. We list some of these below; for functions that actually construct the tessellation, see the dedicated tessellation section in the sidebar.

Type queries


Returns the type used for representing edges in tri.


Returns the type of the edges in the Voronoi tessellation vor.


Returns the type of the numbers used in the Voronoi tessellation vor.


Given a container x, returns the number type used for storing coordinates.


Returns the type used for representing triangles in tri.


Returns the type of the triangles used in the triangulation underlying the Voronoi tessellation vor.


get_polygons(vor::VoronoiTessellation, i)

Gets the vertices of the ith polygon of vor. The vertices are given in counter-clockwise order, and the first and last vertices are equal.

get_polygon_coordinates(vorn::VoronoiTessellation, i, bounding_box = nothing)

Returns a vector for the coordinates of the ith polygon in vorn. If bounding_box is provided, the polygon will be clipped to the bounding box, assuming that it takes the form (xmin, xmax, ymin, ymax). Some specific cases:

  • If the polygon is unbounded but bounding_box is nothing, then an error will be thrown.
  • If the polygon is bounded and bounding_box is nothing, then the polygon coordinates will be returned as if without any clipping.
  • If the polygon is outside of the bounding box entirely, then an empty vector will be returned.

If you do need to consider clipping your polygon to an arbitrary polygon, see the polygon_clip function; this function (get_polygon_coordinates) uses polygon_clip for rectangular clipping when bounding_box is considered.

See also polygon_bounds for a good default for bounding_box.

get_neighbouring_boundary_edges(vor::VoronoiTessellation, e)

Gets the boundary edges that are adjacent to the boundary edge e in vor.

get_neighbouring_boundary_edges(tri::Triangulation, e)

Given an edge e on the boundary, returns the edges to the left and to the right of e, oriented so that get_adjacent(tri, v) is a boundary index, where v are the edges returned.



push_polygon_point!(vor::VoronoiTessellation, p)
push_polygon_point!(vor::VoronoiTessellation, x, y)

Pushes the point p = (x, y)to the list of polygon points invor`.



get_adjacent(vor::VoronoiTessellation, e)
get_adjacent(vor::VoronoiTessellation, i, j)

Gets the adjacent polygon to the edge e or the edge (i, j).

add_adjacent!(vor::VoronoiTessellation, e, i)
add_adjacent!(vor::VoronoiTessellation, i, j, k)

Adds the adjacent polygon i to the edge e or the edge (i, j) to the polygon k.

delete_adjacent!(vor::VoronoiTessellation, e, i)
delete_adjacent!(vor::VoronoiTessellation, i, j, k)

Deletes the adjacent polygon i from the edge e or the edge (i, j) from the polygon k.


get_area(stats::TriangulationStatistics, T)

Returns the area field from the individual triangle statistics for the triangle T in the triangulation statistics stats.

get_area(vor::VoronoiTessellation, i)

Gets the area of the polygon with index i in vor.

get_centroid(stats::TriangulationStatistics, T)

Returns the centroid field from the individual triangle statistics for the triangle T in the triangulation statistics stats.

get_centroid(vor::VoronoiTessellation, i)

Gets the centroid of the polygon with index i in vor.

polygon_bounds(vorn::VoronoiTessellation, unbounded_extension_factor=0.0; include_polygon_vertices=true)

Gets the bounding box of the polygons in vorn. If unbounded_extension_factor is positive, the bounding box is extended by this factor in each direction, proportional to the width of each axis.

If include_polygon_vertices=true, then the bounds both the generators and the polygons. Otherwise, only the generators will be considered.

polygon_bounds(pts, boundary_nodes, check_all_curves = Val(false))

Given a polygon represented by the points pts with boundary_nodes defining the polygon connections, returns a bounding box of the polygon. The bounding box is returned in the order (xmin, xmax, ymin, ymax). If your polygon is not a multiple polygon, check_all_curves = Val(false) is sufficient, otherwise you might want to use Val(true).

Missing docstring.

Missing docstring for jump_and_march(::VoronoiTessellation, ::Any). Check Documenter's build log for details.