# 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.

`DelaunayTriangulation.VoronoiTessellation`

— Type`VoronoiTessellation{Tr<:Triangulation,P,I,T,S,E}`

Struct for a Voronoi tessellation.

**Fields**

`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:

`DelaunayTriangulation.get_triangulation`

— Method`get_triangulation(vor::VoronoiTessellation)`

Returns the triangulation field from the Voronoi tessellation `vor`

.

`DelaunayTriangulation.get_generators`

— Method`get_generators(vor::VoronoiTessellation)`

Returns the generators field from the Voronoi tessellation `vor`

.

`DelaunayTriangulation.get_polygon_points`

— Method`get_polygon_points(vor::VoronoiTessellation)`

Returns the polygon_points field from the Voronoi tessellation `vor`

.

`DelaunayTriangulation.get_polygons`

— Method`get_polygons(vor::VoronoiTessellation)`

Returns the polygons field from the Voronoi tessellation `vor`

.

`DelaunayTriangulation.get_circumcenter_to_triangle`

— Method`get_circumcenter_to_triangle(vor::VoronoiTessellation)`

Returns the circumcenter*to*triangle field from the Voronoi tessellation `vor`

.

`DelaunayTriangulation.get_triangle_to_circumcenter`

— Method`get_triangle_to_circumcenter(vor::VoronoiTessellation)`

Returns the triangle*to*circumcenter field from the Voronoi tessellation `vor`

.

`DelaunayTriangulation.get_unbounded_polygons`

— Method`get_unbounded_polygons(vor::VoronoiTessellation)`

Returns the unbounded_polygons field from the Voronoi tessellation `vor`

.

`DelaunayTriangulation.get_cocircular_circumcenters`

— Method`get_cocircular_circumcenters(vor::VoronoiTessellation)`

Returns the cocircular_circumcenters field from the Voronoi tessellation `vor`

.

`DelaunayTriangulation.get_adjacent`

— Method`get_adjacent(vor::VoronoiTessellation)`

Returns the adjacent field from the Voronoi tessellation `vor`

.

`DelaunayTriangulation.get_boundary_polygons`

— Method`get_boundary_polygons(vor::VoronoiTessellation)`

Returns the boundary_polygons field from the Voronoi tessellation `vor`

.

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

`DelaunayTriangulation.edge_type`

— Method`edge_type(tri::Triangulation)`

Returns the type used for representing edges in `tri`

.

`edge_type(vor::VoronoiTessellation)`

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

.

`DelaunayTriangulation.number_type`

— Method`number_type(vor::VoronoiTessellation)`

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

.

`number_type(x)`

Given a container `x`

, returns the number type used for storing coordinates.

`DelaunayTriangulation.integer_type`

— Method`integer_type(vor::VoronoiTessellation)`

Returns the type of the integers used in the Voronoi tessellation `vor`

.

`DelaunayTriangulation.triangle_type`

— Method`triangle_type(tri::Triangulation)`

Returns the type used for representing triangles in `tri`

.

`triangle_type(vor::VoronoiTessellation)`

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

.

## Getters

`DelaunayTriangulation.get_generator`

— Method`get_generators(vor::VoronoiTessellation, i...)`

Gets the coordinates for the `i`

th generator(s) of `vor`

.

`DelaunayTriangulation.get_polygon_point`

— Method`get_polygon_points(vor::VoronoiTessellation, i...)`

Gets the coordinates for the `i`

th polygon vertex(vertices) of `vor`

.

`DelaunayTriangulation.get_polygon`

— Method`get_polygons(vor::VoronoiTessellation, i)`

Gets the vertices of the `i`

th polygon of `vor`

. The vertices are given in counter-clockwise order, and the first and last vertices are equal.

`DelaunayTriangulation.get_circumcenter_to_triangle`

— Method`get_circumcenter_to_triangle(vor::VoronoiTessellation, i)`

Gets the triangle that contains the `i`

th circumcenter of `vor`

.

`DelaunayTriangulation.get_triangle_to_circumcenter`

— Method`get_triangle_to_circumcenter(vor::VoronoiTessellation, T)`

Gets the index of the circumcenter of the triangle `T`

in `vor`

.

`DelaunayTriangulation.get_polygon_coordinates`

— Function`get_polygon_coordinates(vorn::VoronoiTessellation, i, bounding_box = nothing)`

Returns a vector for the coordinates of the `i`

th 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`

.

`DelaunayTriangulation.get_neighbouring_boundary_edges`

— Function`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.

## Nums

`DelaunayTriangulation.num_polygons`

— Function`num_polygons(vor::VoronoiTessellation)`

Gets the number of polygons in `vor`

.

`DelaunayTriangulation.num_polygon_vertices`

— Function`num_polygon_vertices(vor::VoronoiTessellation)`

Gets the number of vertices in all the polygons in `vor`

.

`DelaunayTriangulation.num_generators`

— Function`num_generators(vor::VoronoiTessellation)`

Gets the number of generators in `vor`

.

## Adders

`DelaunayTriangulation.add_polygon!`

— Function`add_polygon!(vor::VoronoiTessellation, B, i)`

Adds the polygon `B`

to `vor`

at index `i`

.

`DelaunayTriangulation.push_polygon_point!`

— Function```
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 in`

vor`.

`DelaunayTriangulation.add_unbounded_polygon!`

— Function`add_unbounded_polygon!(vor::VoronoiTessellation, i)`

Adds the index `i`

to the list of unbounded polygons in `vor`

.

`DelaunayTriangulation.delete_unbounded_polygon!`

— Function`delete_unbounded_polygon!(vor::VoronoiTessellation, i)`

Deletes the index `i`

from the list of unbounded polygons in `vor`

.

`DelaunayTriangulation.add_boundary_polygon!`

— Function`add_boundary_polygon!(vorn::VoronoiTessellation, i)`

Adds the index `i`

to the list of boundary polygons in `vorn`

.

## Iterators

`DelaunayTriangulation.each_generator`

— Function`each_generator(vor::VoronoiTessellation)`

Gets an iterator over the indices of the generators in `vor`

.

`DelaunayTriangulation.each_polygon_vertex`

— Function`each_polygon_vertex(vor::VoronoiTessellation)`

Gets an iterator over the indices of the polygon points in `vor`

.

`DelaunayTriangulation.each_unbounded_polygon`

— Function`each_unbounded_polygon(vor::VoronoiTessellation)`

Gets an iterator over the indices of the unbounded polygons in `vor`

.

`DelaunayTriangulation.each_polygon`

— Function`each_polygon(vor::VoronoiTessellation)`

Gets an iterator over the polygons in `vor`

, giving their vertices.

`DelaunayTriangulation.each_polygon_index`

— Function`each_polygon_index(vor::VoronoiTessellation)`

Gets an iterator over the indices of the polygons in `vor`

.

## Adjacent

`DelaunayTriangulation.get_adjacent`

— Method```
get_adjacent(vor::VoronoiTessellation, e)
get_adjacent(vor::VoronoiTessellation, i, j)
```

Gets the adjacent polygon to the edge `e`

or the edge `(i, j)`

.

`DelaunayTriangulation.add_adjacent!`

— Method```
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`

.

`DelaunayTriangulation.delete_adjacent!`

— Method```
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`

.

`DelaunayTriangulation.delete_polygon_adjacent!`

— Function`delete_polygon_adjacent!(vorn::VoronoiTessellation, polygon)`

Deletes the adjacent polygons of the boundary edges of the polygon `polygon`

from the adjacency list.

`DelaunayTriangulation.add_polygon_adjacent!`

— Function`add_polygon_adjacent!(vorn::VoronoiTessellation, polygon)`

Adds the adjacent polygons of the boundary edges of the polygon `polygon`

to the adjacency list.

## Features

`DelaunayTriangulation.polygon_features`

— Method`polygon_features(vor::VoronoiTessellation, i)`

Gets the area and centroid of the polygon with index `i`

in `vor`

.

`DelaunayTriangulation.get_area`

— Function`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`

.

`DelaunayTriangulation.get_centroid`

— Function`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`

.

`DelaunayTriangulation.polygon_bounds`

— Method`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 for `jump_and_march(::VoronoiTessellation, ::Any)`

. Check Documenter's build log for details.

## Utilities

`DelaunayTriangulation.get_surrounding_polygon`

— Method`get_surrounding_polygon(vor::VoronoiTessellation, i)`

Gets the polygon surrounding the generator with index `i`

in `vor`

. You shouldn't need to use this, see `get_polygon`

instead.

`DelaunayTriangulation.convert_to_boundary_edge`

— Method`convert_to_boundary_edge(vorn::VoronoiTessellation, e)`

Converts the edge `e`

in the triangulation of `vorn`

to a boundary edge so that `get_adjacent(vorn, e)`

is a boundary index.