BigObject VoronoiPolyhedron<Scalar>

from application polytope

For a finite set of SITES S the Voronoi region of each site is the set of points closest (with respect to Euclidean distance) to the given site. All Voronoi regions (and their faces) form a polyhedral complex which is a vertical projection of the boundary complex of an unbounded polyhedron P(S). This way VoronoiPolyhedron becomes a derived class from polytope.

Type Parameters:: Scalar: numeric data type used for the coordinates, must be an ordered field. Default is Rational.
derived from:: Polytope

Properties

no category

CRUST_GRAPH

Graph of the crust as defined by Amenta, Bern, and Eppstein.

Type:: Graph<Undirected>

DELAUNAY_DIAGRAM

The Delaunay triangulation of the sites returned as a PolyhedralComplex.

Type:

PolyhedralComplex<Scalar>

Example:

To construct the Delaunay diagram of a given set of sites in the plane, do this:

 > $dd = new polytope::VoronoiPolyhedron(SITES=>[[1,0,0],[1,1,0],[1,-1,0],[1,0,1],[1,0,-1]])->DELAUNAY_DIAGRAM;
 > print rows_numbered($dd->VERTICES);
 0:1 1 0
 1:1 0 -1
 2:1 0 0
 3:1 0 1
 4:1 -1 0

 > print $dd->MAXIMAL_POLYTOPES;
 {0 1 2}
 {0 2 3}
 {2 3 4}
 {1 2 4}

DELAUNAY_GRAPH

Graph of the Delaunay decomposition Del(SITES).

Type:: Graph<Undirected>

DELAUNAY_TRIANGULATION

Delaunay triangulation of the sites. (Delaunay subdivision, non-simplices are triangulated.)

Type:: Array<Set<Int>>

ITERATED_DELAUNAY_GRAPH

Graph of the Del(SITES) + Vor(SITES).

Type:: Graph<Undirected>

ITERATED_VORONOI_GRAPH

Graph of the joint Voronoi diagram of the SITES and the vertices of Vor(SITES). The coordinates (homogeneous, before projection) are stored as node attributes. The graph is truncated according to the BOUNDING_BOX. For the default BOUNDING_BOX it may happen that some of the iterated Voronoi vertices are truncated. Create new objects of type VoronoiPolyhedron to produce proper iterated Voronoi diagrams.

Type:: GeometricGraph<Scalar>

NN_CRUST_GRAPH: Graph of the nearest neighbor crust, as defined in:

> T. K. Dey and P. Kumar: A simple provable algorithm for curve reconstruction.

> Proc. 10th. Annu. ACM-SIAM Sympos. Discrete Alg., 1999, 893-894.
.. Polygonal reconstruction of a smooth planar curve from a finite set of samples. Sampling rate of <= 1/3 suffices.
  ? Type:
  :''[[..:graph:Graph |Graph]]<[[..:common#Undirected |Undirected]]>''

NN_GRAPH

Graph of the nearest neighbors. This is a subgraph of NN_CRUST_GRAPH.

Type:: Graph<Undirected>

N_SITES

Number of SITES

Type:: Int

SITES

Homogeneous coordinates of the sites in case the polyhedron is Voronoi. Sites must be pairwise distinct.

Type:: Matrix<Scalar,NonSymmetric>

SITE_LABELS

Unique names assigned to the SITES. Works like VERTEX_LABELS.

Type:: Array<String>

VORONOI_DIAGRAM

The Voronoi regions as polyhedral complex. Polyhedron indices correspond to site indices.

Type:

PolyhedralComplex<Scalar>

Example:

To construct the Voronoi diagram of a given set of sites in the plane, do this:

 > $vd = new polytope::VoronoiPolyhedron(SITES=>[[1,0,0],[1,1,0],[1,-1,0],[1,0,1],[1,0,-1]])->VORONOI_DIAGRAM;
 > print rows_numbered($vd->VERTICES);
 0:1 1/2 -1/2
 1:1 1/2 1/2
 2:1 -1/2 1/2
 3:1 -1/2 -1/2
 4:0 1 -1
 5:0 1 1
 6:0 -1 1
 7:0 -1 -1

 > print $vd->MAXIMAL_POLYTOPES;
 {0 1 2 3}
 {0 1 4 5}
 {2 3 6 7}
 {1 2 5 6}
 {0 3 4 7}

VORONOI_GRAPH

Graph of the Voronoi diagram of the SITES. The homogeneous coordinates after projection are stored as node attributes. The graph is truncated according to the BOUNDING_BOX. All vertices of the Voronoi diagram are visible (and represented in the VORONOI_GRAPH) for the default BOUNDING_BOX.