#  Copyright (c) 1997-2005
#  Ewgenij Gawrilow, Michael Joswig (Technische Universitaet Berlin, Germany)
#  http://www.math.tu-berlin.de/polymake,  mailto:polymake@math.tu-berlin.de
#
#  This program is free software; you can redistribute it and/or modify it
#  under the terms of the GNU General Public License as published by the
#  Free Software Foundation; either version 2, or (at your option) any
#  later version: http://www.gnu.org/licenses/gpl.txt.
#
#  This program is distributed in the hope that it will be useful,
#  but WITHOUT ANY WARRANTY; without even the implied warranty of
#  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
#  GNU General Public License for more details.
#-----------------------------------------------------------------------------
#  $Project: polymake $$Id: voronoi.rules 7592 2007-01-24 11:42:17Z gawrilow $

# For a finite set of @see 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 VoronoiDiagram becomes a derived class from @see RationalPolytope.

object VoronoiDiagram : RationalPolytope

# category: Voronoi diagrams
# Coordinates of the sites in case the polyhedron is Voronoi.
# Sites must be distinct.
#
property SITES
$type="matrix";

# The polyhedron defined by the set of @see SITES is the Voronoi polyhedron.  Beware of facet at infinity.
FACETS : SITES
  client("voronoi", $this , "FACETS", "SITES");

# category: Voronoi diagrams
# Number of @see SITES.
#
property N_SITES
$type="cardinal";


# category: Voronoi diagrams
# Unique names assigned to the @see SITES.  Works like @see VERTEX_LABELS.
#
property SITE_LABELS
$type="array<label>";


# category: Voronoi diagrams
# Since a Voronoi polyhedron is unbounded it must be artificially bounded for visualization purposes.
# Allowed is any set of hyperplanes which makes the projection onto the last d-1 coordinates bounded.
# By default, these are the vertical facets of a suitably scaled cube.
# Not very useful for other unbounded polyhedra not related to Voronoi diagrams.
#
property VORONOI_BOUNDING_BOX
$type="matrix";


# category: Voronoi diagrams
# Vertices of the Voronoi diagram of the @see SITES.
#
property VORONOI_VERTICES
$type="matrix";


# category: Voronoi diagrams
# Graph of the Voronoi diagram of the @see SITES.  The coordinates (homogeneous, before projection) are stored as node attributes.
# The graph is truncated according to the @see VORONOI_BOUNDING_BOX.  All vertices of the Voronoi diagram are visible (and represented in
# the VORONOI_GRAPH) for the default VORONOI_BOUNDING_BOX.
#
property VORONOI_GRAPH
$type="graph";
@upgrade=(v2.1.1, \&embrace_vector_as_node_attr);

sub embrace_vector_as_node_attr {
   my $value=shift;
   foreach (@$value) {
      s/^\((?!<)(.*?)(?=\s+\{)/(<$1>/;
   }
   $value;
}


# category: Voronoi diagrams
# Graph of the Delaunay decomposition Del(SITES).
#
property DELAUNAY_GRAPH
$type="graph";


# category: Voronoi diagrams
# Graph of the Del(SITES) + Vor(SITES).
#
property ITERATED_DELAUNAY_GRAPH
$type="graph";


# category: Voronoi diagrams
# Graph of the crust as defined by Amenta, Bern, and Eppstein.
#
property CRUST_GRAPH
$type="graph";


# category: Voronoi diagrams
# Graph of the nearest neighbor crust, as defined by Dey and Kumar.
#
property NN_CRUST_GRAPH
$type="graph";


# category: Voronoi diagrams
# Graph of the nearest neighbors.  This is a subgraph of NN_CRIST_GRAPH.
#
property NN_GRAPH
$type="graph";


# category: Voronoi diagrams
# Graph of the joint Voronoi diagram of the @see SITES and the vertices of Vor(SITES).  The coordinates (homogeneous, before projection)
# are stored as node attributes.  The graph is truncated according to the @see VORONOI_BOUNDING_BOX.  For the default VORONOI_BOUNDING_BOX it may happen
# that some of the iterated Voronoi vertices are truncated.  Use the client voronoi to produce proper iterated Voronoi diagrams.
#
property ITERATED_VORONOI_GRAPH
$type="graph";
@upgrade=(v2.1.1, \&embrace_vector_as_node_attr);


N_SITES : SITES
WEIGHT 0.10
   $this->N_SITES=@{$this->SITES};

VORONOI_VERTICES : VERTICES
   $this->VORONOI_VERTICES=[ map { /^(.*\S)\s+\S+$/; "$1\n"; } (grep { /^1/ } @{$this->VERTICES}) ];

VORONOI_BOUNDING_BOX : SITES, VERTICES
   my @points=@{$this->SITES};
   @points=((map { s/$/ 0/; $_ } @points), @{$this->VERTICES});
   client("bounding_box", $this, \@points, "VORONOI_BOUNDING_BOX", "-voronoi");

VORONOI_GRAPH : VERTICES, GRAPH, VORONOI_BOUNDING_BOX
   client("clip_graph", $this, "VORONOI_GRAPH", "VERTICES", "GRAPH", "VORONOI_BOUNDING_BOX");

DELAUNAY_GRAPH : DUAL_GRAPH, N_SITES
# for this it is essential that the first few facets correspond to the sites
   my $site_set = [ "{".join(" ", 0..$this->N_SITES-1)."}\n" ];
   client("induced_subgraph", $this, "DUAL_GRAPH", $site_set, "DELAUNAY_GRAPH", "-nol");

NN_GRAPH, NN_CRUST_GRAPH : SITES, DELAUNAY_GRAPH
   client("nn_crust", $this, "NN_GRAPH", "NN_CRUST_GRAPH", "SITES", "DELAUNAY_GRAPH");

CRUST_GRAPH, ITERATED_DELAUNAY_GRAPH, ITERATED_VORONOI_GRAPH : SITES, VORONOI_VERTICES, VORONOI_GRAPH
   my @sites2 = (@{$this->SITES}, @{$this->VORONOI_VERTICES});
   my $crust_poly=new Apps::polytope::VoronoiDiagram(SITES => \@sites2);
   my $site_set = [ "{".join(" ", 0..$#{$this->SITES})."}\n" ];
   my @crust_graph;
   client("induced_subgraph", $crust_poly, "DELAUNAY_GRAPH", $site_set, \@crust_graph, "-nol");
   $this->CRUST_GRAPH=\@crust_graph;
   $this->ITERATED_DELAUNAY_GRAPH=$crust_poly->DELAUNAY_GRAPH;
   $this->ITERATED_VORONOI_GRAPH=$crust_poly->VORONOI_GRAPH;


# category: Visualization
# Draw a Voronoi diagram and its dual.  Use the interactive features of the viewer to select.
user_method VISUAL_VORONOI(%Visual::Graph::decorations) {
   my ($this, $decor)=@_;
   my $d=$this->AMBIENT_DIM-1;
   if ($d<2 || $d>3) {
      die "don't know how to visualize $d-d Voronoi diagram\n";
   }

   my @sites = $this->dehomogenize($this->SITES);
   my @voronoi_vertices_and_clip = map { /^\(<(.*\S)>\s*\{.*\}\)$/; "$1\n"; } @{$this->VORONOI_GRAPH};
   @voronoi_vertices_and_clip = $this->project_down(\@voronoi_vertices_and_clip); # does dehomogenization and conversion to float
   my @sites_and_vor=(@sites,@voronoi_vertices_and_clip);
# Delaunay graph
   my $dGraph=new Visual::Graph( Name => $this->name." delaunay graph",
				 Graph => $this->DELAUNAY_GRAPH,
				 NodeLabels => $this->lookup("SITE_LABELS"),
				 Coord => \@sites,
				 NodeColor => $Visual::Color::DelaunayVertex,
				 EdgeColor => $Visual::Color::DelaunayEdge,
				 EdgeStyle => $Visual::Style::DelaunayEdge,
				 $decor,
			       );
# Voronoi graph (without the vertices)
   my $vGraph=new Visual::Graph( Name => $this->name." voronoi graph",
				 Graph => $this->VORONOI_GRAPH,
				 Coord => \@voronoi_vertices_and_clip,
				 NodeStyle => "hidden",
				 EdgeStyle => $dGraph->EdgeStyle,
			       );
# Voronoi vertices
   my $vVertices=new Visual::PointSet( Name => $this->name." voronoi vertices",
				       Points => [ $this->dehomogenize($this->VORONOI_VERTICES) ],
			             );
   compose($dGraph, $vGraph, $vVertices);
}

# category: Visualization
# Draw a Voronoi diagram, its dual graph and the crust.  Use the interactive features of the viewer to select.
user_method VISUAL_CRUST() {
   my ($this)=@_;
   my $d=$this->AMBIENT_DIM-1;
   if ($d<2 || $d>3) {
      die "don't know how to visualize $d-d Voronoi diagram\n";
   }

   my @sites = $this->dehomogenize($this->SITES);
   my @voronoi_vertices_and_clip = map { /^\(<(.*\S)>\s*\{.*\}\)$/; "$1\n"; } @{$this->VORONOI_GRAPH};
   @voronoi_vertices_and_clip = $this->project_down(\@voronoi_vertices_and_clip); # does dehomogenization and conversion to float
   my @sites_and_vor=(@sites,@voronoi_vertices_and_clip);
# Delaunay graph
   my $dGraph=new Visual::Graph( Name => $this->name." delaunay graph",
				 Graph => $this->DELAUNAY_GRAPH,
				 NodeLabels => $this->lookup("SITE_LABELS"),
				 Coord => \@sites,
				 NodeColor => $Visual::Color::DelaunayVertex,
				 EdgeColor => $Visual::Color::DelaunayEdge,
				 EdgeStyle => $Visual::Style::DelaunayEdge,
				 $decor,
			       );
# Voronoi graph (without the vertices)
   my $vGraph=new Visual::Graph( Name => $this->name." voronoi graph",
				 Graph => $this->VORONOI_GRAPH,
				 Coord => \@voronoi_vertices_and_clip,
				 NodeStyle => "hidden",
				 EdgeStyle => $Visual::Style::VoronoiEdge,
			       );
# iterated Delaunay graph
   my $idGraph=new Visual::Graph( Name => $this->name." iterated delaunay graph",
				  Graph => $this->ITERATED_DELAUNAY_GRAPH,
				  Coord => \@sites_and_vor,
				  EdgeColor => $Visual::Color::IteratedDelaunayEdge,
				  NodeStyle => "hidden",
				  EdgeStyle => $Visual::Style::IteratedDelaunayEdge,
				);
# crust graph
   my $cGraph=new Visual::Graph( Name => $this->name." crust graph",
				 Graph => $this->CRUST_GRAPH,
				 NodeLabels => $this->lookup("SITE_LABELS"),
				 Coord => \@sites,
				 NodeColor => $Visual::Color::CrustVertex,
				 EdgeColor => $Visual::Color::CrustEdge,
				 EdgeStyle => $Visual::Style::CrustEdge,
			       );
# Voronoi vertices
   my $vVertices=new Visual::PointSet( Name => $this->name." voronoi vertices",
				       Points => [ $this->dehomogenize($this->VORONOI_VERTICES) ],
			             );
   compose($dGraph, $vGraph, $idGraph, $cGraph, $vVertices);
}


# category: Visualization
# Draw a Voronoi diagram, its dual graph and the nearest neighbor crust.  Use the interactive features of the viewer to select.
user_method VISUAL_NN_CRUST() {
   my ($this)=@_;
   my $d=$this->AMBIENT_DIM-1;
   if ($d<2 || $d>3) {
      die "don't know how to visualize $d-d Voronoi diagram\n";
   }

   my @sites = $this->dehomogenize($this->SITES);
# Delaunay graph
   my $dGraph=new Visual::Graph( Name => $this->name." delaunay graph",
				 Graph => $this->DELAUNAY_GRAPH,
				 NodeLabels => $this->lookup("SITE_LABELS"),
				 Coord => \@sites,
				 NodeStyle => "hidden",
				 EdgeColor => $Visual::Color::DelaunayEdge,
				 EdgeStyle => $Visual::Style::DelaunayEdge,
			       );
# nearest neighbor graph
   my $nGraph=new Visual::Graph( Name => $this->name." nearest neighbor graph",
				 Graph => $this->NN_GRAPH,
				 Coord => \@sites,
				 NodeStyle => "hidden",
				 EdgeStyle => $Visual::Style::NearestNeighbors,
			       );
# nearest neighbor crust graph
   my $cGraph=new Visual::Graph( Name => $this->name." nn-crust graph",
				 Graph => $this->NN_CRUST_GRAPH,
				 NodeLabels => $this->lookup("SITE_LABELS"),
				 Coord => \@sites,
				 NodeColor => $Visual::Color::CrustVertex,
				 EdgeColor => $Visual::Color::CrustEdge,
				 EdgeStyle => $Visual::Style::CrustEdge,
			       );
   compose($dGraph, $nGraph, $cGraph);
}


package Visual::Color;

# vertices of the Delaunay decomposition: white
custom $DelaunayVertex="255 255 255";

# edges of the Delaunay decomposition: shabby orange
custom $DelaunayEdge="255 192 128";

# vertices of the crust: white
custom $CrustVertex="255 255 255";

# edges of the crust: yellow
custom $CrustEdge="255 255 0";

# vertices of Vor(Vor(SITES)): grey
custom $IteratedVoronoiVertex="64 64 64";

# edges of Del(Vor(SITES)): shabby blue
custom $IteratedDelaunayEdge="100 100 255";


package Visual::Style;

# edge style of Vor(SITES)
custom $VoronoiEdge="thickness 1.5";

# edge style of Del(SITES)
custom $DelaunayEdge="thickness 1.5";

# edge style of Del(Vor(SITES))
custom $IteratedDelaunayEdge="thickness 1";

# edge style between nearest neighbors
custom $NearestNeighbors="thickness 1";

# edge style for crust edges
custom $CrustEdge="thickness 0.333";

# Local Variables:
# c-basic-offset:3
# mode: perl
# End: