====== BigObject VoronoiPolyhedron<Scalar> ======
//from application [[..:polytope|polytope]]//\\
\\
 For a finite set of ''[[..:polytope:VoronoiPolyhedron#SITES |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 [[]].

  ? Type Parameters:
  :: ''Scalar'': numeric data type used for the coordinates, must be an ordered field. Default is ''[[..:common#Rational |Rational]]''.
  ? derived from:
  : ''[[..:polytope:Polytope |Polytope]]''
===== Properties =====

==== no category ====
{{anchor:crust_graph:}}
  ?  **''CRUST_GRAPH''**
  :: Graph of the crust as defined by Amenta, Bern, and Eppstein.
    ? Type:
    :''[[..:graph:Graph |Graph]]<[[..:common#Undirected |Undirected]]>''


----
{{anchor:delaunay_diagram:}}
  ?  **''DELAUNAY_DIAGRAM''**
  :: The Delaunay triangulation of the sites returned as a ''[[..:fan:PolyhedralComplex |PolyhedralComplex]]''.
    ? Type:
    :''[[..:fan:PolyhedralComplex |PolyhedralComplex]]<Scalar>''
    ? Example:
    :: To construct the Delaunay diagram of a given set of sites in the plane, do this:
    :: <code perl> > $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
</code>
    :: <code perl> > print $dd->MAXIMAL_POLYTOPES;
 {0 1 2}
 {0 2 3}
 {2 3 4}
 {1 2 4}
</code>


----
{{anchor:delaunay_graph:}}
  ?  **''DELAUNAY_GRAPH''**
  :: Graph of the Delaunay decomposition Del(''[[..:polytope:VoronoiPolyhedron#SITES |SITES]]'').
    ? Type:
    :''[[..:graph:Graph |Graph]]<[[..:common#Undirected |Undirected]]>''


----
{{anchor:delaunay_triangulation:}}
  ?  **''DELAUNAY_TRIANGULATION''**
  :: Delaunay triangulation of the [[..:polytope:VoronoiPolyhedron#SITES |sites]]. (Delaunay subdivision, non-simplices are triangulated.)
    ? Type:
    :''[[..:common#Array |Array]]<[[..:common#Set |Set]]<[[..:common#Int |Int]]%%>>%%''


----
{{anchor:iterated_delaunay_graph:}}
  ?  **''ITERATED_DELAUNAY_GRAPH''**
  :: Graph of the Del(''[[..:polytope:VoronoiPolyhedron#SITES |SITES]]'') + Vor(''[[..:polytope:VoronoiPolyhedron#SITES |SITES]]'').
    ? Type:
    :''[[..:graph:Graph |Graph]]<[[..:common#Undirected |Undirected]]>''


----
{{anchor:iterated_voronoi_graph:}}
  ?  **''ITERATED_VORONOI_GRAPH''**
  :: Graph of the joint Voronoi diagram of the ''[[..:polytope:VoronoiPolyhedron#SITES |SITES]]'' and the vertices of Vor(SITES).  The coordinates (homogeneous, before projection) are stored as node attributes.  The graph is truncated according to the ''[[..:graph:GeometricGraph#BOUNDING_BOX |BOUNDING_BOX]]''. For the default BOUNDING_BOX it may happen that some of the iterated Voronoi vertices are truncated. Create new objects of type ''[[..:polytope:VoronoiPolyhedron |VoronoiPolyhedron]]'' to produce proper iterated Voronoi diagrams.
    ? Type:
    :''[[..:graph:GeometricGraph |GeometricGraph]]<Scalar>''


----
{{anchor:nn_crust_graph:}}
  ?  **''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]]>''


----
{{anchor:nn_graph:}}
  ?  **''NN_GRAPH''**
  :: Graph of the nearest neighbors.  This is a subgraph of ''[[..:polytope:VoronoiPolyhedron#NN_CRUST_GRAPH |NN_CRUST_GRAPH]]''.
    ? Type:
    :''[[..:graph:Graph |Graph]]<[[..:common#Undirected |Undirected]]>''


----
{{anchor:n_sites:}}
  ?  **''N_SITES''**
  :: Number of ''[[..:polytope:VoronoiPolyhedron#SITES |SITES]]''
    ? Type:
    :''[[..:common#Int |Int]]''


----
{{anchor:sites:}}
  ?  **''SITES''**
  :: Homogeneous coordinates of the sites in case the polyhedron is Voronoi. Sites must be pairwise distinct.
    ? Type:
    :''[[..:common#Matrix |Matrix]]<Scalar,[[..:common#NonSymmetric |NonSymmetric]]>''


----
{{anchor:site_labels:}}
  ?  **''SITE_LABELS''**
  :: Unique names assigned to the ''[[..:polytope:VoronoiPolyhedron#SITES |SITES]]''.  Works like ''[[..:polytope:Polytope#VERTEX_LABELS |VERTEX_LABELS]]''.
    ? Type:
    :''[[..:common#Array |Array]]<[[..:common#String |String]]>''


----
{{anchor:voronoi_diagram:}}
  ?  **''VORONOI_DIAGRAM''**
  :: The Voronoi regions as polyhedral complex. Polyhedron indices correspond to site indices.
    ? Type:
    :''[[..:fan:PolyhedralComplex |PolyhedralComplex]]<Scalar>''
    ? Example:
    :: To construct the Voronoi diagram of a given set of sites in the plane, do this:
    :: <code perl> > $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
</code>
    :: <code perl> > print $vd->MAXIMAL_POLYTOPES;
 {0 1 2 3}
 {0 1 4 5}
 {2 3 6 7}
 {1 2 5 6}
 {0 3 4 7}
</code>


----
{{anchor:voronoi_graph:}}
  ?  **''VORONOI_GRAPH''**
  :: Graph of the Voronoi diagram of the ''[[..:polytope:VoronoiPolyhedron#SITES |SITES]]''.  The homogeneous coordinates after projection are stored as node attributes. The graph is truncated according to the [[..:graph:GeometricGraph#BOUNDING_BOX |BOUNDING_BOX]]. All vertices of the Voronoi diagram are visible (and represented in the ''[[..:polytope:VoronoiPolyhedron#VORONOI_GRAPH |VORONOI_GRAPH]]'') for the default BOUNDING_BOX.
    ? Type:
    :''[[..:graph:GeometricGraph |GeometricGraph]]<Scalar>''


----
{{anchor:voronoi_vertices:}}
  ?  **''VORONOI_VERTICES''**
  :: Vertices of the Voronoi diagram of the ''[[..:polytope:VoronoiPolyhedron#SITES |SITES]]''.
    ? Type:
    :''[[..:common#Matrix |Matrix]]<Scalar,[[..:common#NonSymmetric |NonSymmetric]]>''


----
===== Methods =====

==== Visualization ====
 These methods are for visualization.
----
{{anchor:visual_crust:}}
  ?  **''VISUAL_CRUST()''**
  :: Draw a Voronoi diagram, its [[/polytope/objects/VoronoiPolyhedron/properties/DELAUNAY_GRAPH||dual graph]] and the [[..:polytope:VoronoiPolyhedron#CRUST_GRAPH |crust]].  Use the interactive features of the viewer to select.
    ? Options:
    : option list ''[[..:graph#Visual_Graph_decorations |Visual::Graph::decorations]]''
    ? Returns:
    :''[[..:common:Visual_Container |Visual::Container]]''


----
{{anchor:visual_nn_crust:}}
  ?  **''VISUAL_NN_CRUST()''**
  :: Draw a Voronoi diagram, its dual graph and the [[..:polytope:VoronoiPolyhedron#NN_CRUST_GRAPH |nearest neighbor crust]].  Use the interactive features of the viewer to select.
    ? Options:
    : option list ''[[..:graph#Visual_Graph_decorations |Visual::Graph::decorations]]''
    ? Returns:
    :''[[..:common:Visual_Container |Visual::Container]]''


----
{{anchor:visual_voronoi:}}
  ?  **''VISUAL_VORONOI()''**
  :: Visualize the Voronoi diagram together with its sites.
    ? Options:
    : option list ''[[..:common#Visual_Polygons_decorations |Visual::Polygons::decorations]]''
    ? Returns:
    :''[[..:common:Visual_Container |Visual::Container]]''


----