1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
|
# Copyright (c) 1997-2021
# Ewgenij Gawrilow, Michael Joswig, and the polymake team
# Technische Universität Berlin, Germany
# https://polymake.org
#
# 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.
#-------------------------------------------------------------------------------
object polytope::VoronoiPolyhedron {
# The Voronoi regions as polyhedral complex. Polyhedron indices correspond
# to site indices.
# @example [prefer cdd] 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}
property VORONOI_DIAGRAM : PolyhedralComplex<Scalar>;
rule VORONOI_DIAGRAM : VERTICES_IN_FACETS, VERTICES, FAR_FACE{
my $ff = $this->FAR_FACE;
my $vif = $this->VERTICES_IN_FACETS;
my $n = $vif->rows;
#find index of far face
my $fi = 0;
for(;$fi < $n; $fi++){
if($vif->[$fi] == $ff){
last;
}
}
$this->VORONOI_DIAGRAM = new PolyhedralComplex<Scalar>(
POINTS => $this->VERTICES->minor(All, range(0, $this->VERTICES->cols-2)),
INPUT_POLYTOPES => $vif ->minor(sequence(0,$n)-sequence($fi,1), All));
}
# The Delaunay triangulation of the sites returned as a [[PolyhedralComplex]].
# @example [prefer cdd] 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}
property DELAUNAY_DIAGRAM : PolyhedralComplex<Scalar>;
rule DELAUNAY_DIAGRAM : VERTICES_IN_FACETS, SITES, FAR_FACE{
my $ff = $this->FAR_FACE;
my $vif = $this->VERTICES_IN_FACETS;
my $n = $vif->rows;
#find index of far face
my $fi = 0;
for(;$fi < $n; $fi++){
if($vif->[$fi] == $ff){
last;
}
}
# facets of voronoi diagram become vertices of delaunay and vice versa. hence the transpose.
$vif = transpose($vif->minor(sequence(0,$n)-sequence($fi,1), All));
$this->DELAUNAY_DIAGRAM = new PolyhedralComplex<Scalar>(POINTS=>$this->SITES, INPUT_POLYTOPES=>$vif);
}
}
|
