Polyhedron partition¶
Polyhedron partitions
EXAMPLES:
A polyhedron partition:
sage: from slabbe import PolyhedronPartition
sage: h = 1/3
sage: p = Polyhedron([(0,h),(0,1),(h,1)])
sage: q = Polyhedron([(0,0), (0,h), (h,1), (h,0)])
sage: r = Polyhedron([(h,1), (1,1), (1,h), (h,0)])
sage: s = Polyhedron([(h,0), (1,0), (1,h)])
sage: P = PolyhedronPartition({0:p, 1:q, 2:r, 3:s})
sage: P.is_pairwise_disjoint()
True
sage: list(P)
[(0, A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 3 vertices),
(1, A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 4 vertices),
(2, A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 4 vertices),
(3, A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 3 vertices)]
sage: G = P.plot()
AUTHORS:
- Sébastien Labbé, November 2017, initial version of polyhedron partitions
-
class
slabbe.polyhedron_partition.
PolyhedronPartition
(atoms, base_ring=None)¶ Bases:
object
Return a partition into polyhedron.
Note: Many atoms may share the same key.
INPUT:
atoms
– list of polyhedron or dict of key -> polyhedron or list of (key, polyhedron)base_ring
– base ring (default:None
) of the vertices
EXAMPLES:
sage: from slabbe import PolyhedronPartition sage: h = 1/2 sage: p = Polyhedron([(0,h),(0,1),(h,1)]) sage: q = Polyhedron([(0,0), (0,h), (h,1), (1,1), (1,h), (h,0)]) sage: r = Polyhedron([(h,0), (1,0), (1,h)]) sage: P = PolyhedronPartition([p,q,r]) sage: P Polyhedron partition of 3 atoms with 3 letters
sage: P.is_pairwise_disjoint() True sage: P.volume() 1 sage: G = P.plot()
From a dict:
sage: PolyhedronPartition(dict(a=p,b=q,c=r)) Polyhedron partition of 3 atoms with 3 letters
From a list of (key, polyhedron):
sage: PolyhedronPartition([(9,p),(8,q),(9,r)]) Polyhedron partition of 3 atoms with 2 letters
-
alphabet
()¶ EXAMPLES:
sage: from slabbe import PolyhedronPartition sage: h = 1/2 sage: p = Polyhedron([(0,h),(0,1),(h,1)]) sage: q = Polyhedron([(0,0), (0,h), (h,1), (1,1), (1,h), (h,0)]) sage: r = Polyhedron([(h,0), (1,0), (1,h)]) sage: P = PolyhedronPartition([(3,p), (5,q), (9,r)]) sage: P.alphabet() {3, 5, 9} sage: P = PolyhedronPartition([(3,p), (5,q), (3,r)]) sage: P.alphabet() {3, 5}
-
alphabet_size
()¶ EXAMPLES:
sage: from slabbe import PolyhedronPartition sage: h = 1/2 sage: p = Polyhedron([(0,h),(0,1),(h,1)]) sage: q = Polyhedron([(0,0), (0,h), (h,1), (1,1), (1,h), (h,0)]) sage: r = Polyhedron([(h,0), (1,0), (1,h)]) sage: P = PolyhedronPartition([(3,p), (5,q), (9,r)]) sage: P.alphabet_size() 3 sage: P = PolyhedronPartition([(3,p), (5,q), (3,r)]) sage: P.alphabet_size() 2
-
ambient_space
()¶ EXAMPLES:
sage: from slabbe import PolyhedronPartition sage: h = 1/2 sage: p = Polyhedron([(0,h),(0,1),(h,1)]) sage: q = Polyhedron([(0,0), (0,h), (h,1), (1,1), (1,h), (h,0)]) sage: r = Polyhedron([(h,0), (1,0), (1,h)]) sage: P = PolyhedronPartition([p,q,r]) sage: P.ambient_space() Vector space of dimension 2 over Rational Field
-
apply_linear_map
(M)¶ INPUT:
M
– a matrix
EXAMPLES:
sage: from slabbe import PolyhedronPartition sage: h = 1/3 sage: p = Polyhedron([(0,h),(0,1),(h,1)]) sage: q = Polyhedron([(0,0), (0,h), (h,1), (h,0)]) sage: r = Polyhedron([(h,1), (1,1), (1,h), (h,0)]) sage: s = Polyhedron([(h,0), (1,0), (1,h)]) sage: P = PolyhedronPartition({0:p, 1:q, 2:r, 3:s})
Vertical symmetry:
sage: M = diagonal_matrix((-1,1)) sage: P = P.apply_linear_map(M) sage: P = P.translation((1,0)) sage: P Polyhedron partition of 4 atoms with 4 letters
-
atoms
()¶ EXAMPLES:
sage: from slabbe import PolyhedronPartition sage: h = 1/2 sage: p = Polyhedron([(0,h),(0,1),(h,1)]) sage: q = Polyhedron([(0,0), (0,h), (h,1), (1,1), (1,h), (h,0)]) sage: r = Polyhedron([(h,0), (1,0), (1,h)]) sage: P = PolyhedronPartition([p,q,r]) sage: P.atoms() [A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 3 vertices, A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 6 vertices, A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 3 vertices]
-
base_ring
()¶ EXAMPLES:
sage: from slabbe import PolyhedronPartition sage: h = 1/2 sage: p = Polyhedron([(0,h),(0,1),(h,1)]) sage: q = Polyhedron([(0,0), (0,h), (h,1), (1,1), (1,h), (h,0)]) sage: r = Polyhedron([(h,0), (1,0), (1,h)]) sage: P = PolyhedronPartition([p,q,r]) sage: P.base_ring() Rational Field
-
cached_atoms_set
()¶ EXAMPLES:
sage: from slabbe import PolyhedronPartition sage: h = 1/2 sage: p = Polyhedron([(0,h),(0,1),(h,1)]) sage: q = Polyhedron([(0,0), (0,h), (h,1), (1,1), (1,h), (h,0)]) sage: r = Polyhedron([(h,0), (1,0), (1,h)]) sage: P = PolyhedronPartition([p,q,r]) sage: P.cached_atoms_set() {A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 3 vertices, A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 3 vertices, A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 6 vertices}
-
code
(p)¶ Returns in which atom the polyhedron lives in.
INPUT:
p
– a polyhedron
OUTPUT:
integer (for the i-th atom)EXAMPLES:
sage: from slabbe import PolyhedronPartition sage: h = 1/3 sage: p = Polyhedron([(0,h),(0,1),(h,1)]) sage: q = Polyhedron([(0,0), (0,h), (h,1), (h,0)]) sage: r = Polyhedron([(h,1), (1,1), (1,h), (h,0)]) sage: s = Polyhedron([(h,0), (1,0), (1,h)]) sage: P = PolyhedronPartition({0:p, 1:q, 2:r, 3:s}) sage: P.code(p) 0 sage: P.code(q) 1 sage: t = Polyhedron([(0, 8/9), (0, 1), (1/9, 1)]) sage: P.code(t) 0
TESTS:
sage: t = Polyhedron([(0, 1/9), (0, 1), (1/9, 1)]) sage: P.code(t) Traceback (most recent call last): ... ValueError: polyhedron p whose vertices are (A vertex at (0, 1), A vertex at (0, 1/9), A vertex at (1/9, 1)) lies in no atom
-
domain
()¶ Return the domain of the partition.
OUTPUT:
a polyhedronEXAMPLES:
sage: from slabbe import PolyhedronPartition sage: h = 1/3 sage: p = Polyhedron([(0,0),(h,0),(h,1),(0,1)]) sage: q = Polyhedron([(1,0),(h,0),(h,1),(1,1)]) sage: P = PolyhedronPartition({0:p, 1:q}) sage: P.domain() A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 4 vertices sage: P.domain().vertices() (A vertex at (0, 0), A vertex at (0, 1), A vertex at (1, 0), A vertex at (1, 1))
-
edges
()¶ Return the edges of partition (one copy of each edge).
Note
If there are vertices of atoms on the interior of the edge of another atom, then, the overlapping edges will be repeated.
OUTPUT:
- set of sorted pair of immutable vectors
EXAMPLES:
sage: from slabbe import PolyhedronPartition sage: h = 1/2 sage: p = Polyhedron([(0,h),(0,1),(h,1)]) sage: q = Polyhedron([(0,0), (0,h), (h,1), (1,1), (1,h), (h,0)]) sage: r = Polyhedron([(h,0), (1,0), (1,h)]) sage: P = PolyhedronPartition([p,q,r]) sage: sorted(P.edges()) [((0, 0), (0, 1/2)), ((0, 0), (1/2, 0)), ((0, 1/2), (0, 1)), ((0, 1/2), (1/2, 1)), ((0, 1), (1/2, 1)), ((1/2, 0), (1, 0)), ((1/2, 0), (1, 1/2)), ((1/2, 1), (1, 1)), ((1, 0), (1, 1/2)), ((1, 1/2), (1, 1))]
Irrational partition:
sage: z = polygen(QQ, 'z') #z = QQ['z'].0 # same as sage: K = NumberField(z**2-z-1, 'phi', embedding=RR(1.6)) sage: phi = K.gen() sage: h = 1/phi^2 sage: p = Polyhedron([(0,h),(0,1),(h,1)]) sage: q = Polyhedron([(0,0), (0,h), (h,1), (h,0)]) sage: r = Polyhedron([(h,1), (1,1), (1,h), (h,0)]) sage: s = Polyhedron([(h,0), (1,0), (1,h)]) sage: P = PolyhedronPartition({0:p, 1:q, 2:r, 3:s}, base_ring=K) sage: sorted(P.edges()) [((0, 0), (0, -phi + 2)), ((0, 0), (-phi + 2, 0)), ((0, -phi + 2), (0, 1)), ((0, -phi + 2), (-phi + 2, 1)), ((0, 1), (-phi + 2, 1)), ((-phi + 2, 0), (-phi + 2, 1)), ((-phi + 2, 0), (1, 0)), ((-phi + 2, 0), (1, -phi + 2)), ((-phi + 2, 1), (1, 1)), ((1, 0), (1, -phi + 2)), ((1, -phi + 2), (1, 1))]
-
is_pairwise_disjoint
()¶ Return whether atoms of the partition are pairwise disjoint.
EXAMPLES:
sage: from slabbe import PolyhedronPartition sage: h = 1/2 sage: p = Polyhedron([(0,h),(0,1),(h,1)]) sage: q = Polyhedron([(0,0), (0,h), (h,1), (1,1), (1,h), (h,0)]) sage: r = Polyhedron([(h,0), (1,0), (1,h)]) sage: P = PolyhedronPartition([p,q,r]) sage: P.is_pairwise_disjoint() True
-
classmethod
jeandel_rao_tilings_partition
()¶ This construct the polygon partition associated to Jeandel-Rao tilings introduced in [Lab2019].
EXAMPLES:
sage: from slabbe import PolyhedronPartition sage: P0 = PolyhedronPartition.jeandel_rao_tilings_partition() sage: P0.is_pairwise_disjoint() True sage: P0.volume() 4*phi + 1
The volume is consistent with:
sage: z = polygen(QQ, 'z') sage: K = NumberField(z**2-z-1, 'phi', embedding=RR(1.6)) sage: phi = K.gen() sage: phi * (phi + 3) 4*phi + 1
REFERENCES:
[Lab2019] S. Labbé. A Markov partition for Jeandel-Rao aperiodic Wang tilings. March 2019. https://arxiv.org/abs/1903.06137
-
keys_permutation
(other)¶ Return a relabelling permutation of the keys for self to look like other.
Note
currently, the code works only if the coding of self and other is injective, i.e., no two polyhedron are coded by the same letter.
INPUT:
other
– a polyhedron partition (with injective coding)
OUTPUT:
dict, key -> keyEXAMPLES:
sage: from slabbe import PolyhedronPartition sage: h = 1/2 sage: p = Polyhedron([(0,h),(0,1),(h,1)]) sage: q = Polyhedron([(0,0), (0,h), (h,1), (1,1), (1,h), (h,0)]) sage: r = Polyhedron([(h,0), (1,0), (1,h)]) sage: P = PolyhedronPartition({4:p, 1:q, 2:r}) sage: Q = PolyhedronPartition({0:p, 5:q}) sage: d = P.keys_permutation(Q) sage: d {1: 5, 2: 1, 4: 0} sage: P.rename_keys(d) Polyhedron partition of 3 atoms with 3 letters
-
keys_permutation_lexicographic
()¶ Return a permutation relabelling of the keys for self in increasing order for the lexicographic order of the centers of the polyhedrons.
OUTPUT:
dict, key -> keyEXAMPLES:
sage: from slabbe import PolyhedronPartition sage: h = 1/2 sage: p = Polyhedron([(0,h),(0,1),(h,1)]) sage: q = Polyhedron([(0,0), (0,h), (h,1), (1,1), (1,h), (h,0)]) sage: r = Polyhedron([(h,0), (1,0), (1,h)]) sage: P = PolyhedronPartition({4:p, 1:q, 2:r}) sage: d = P.keys_permutation_lexicographic() sage: d {1: 1, 2: 2, 4: 0} sage: P.rename_keys(d) Polyhedron partition of 3 atoms with 3 letters
sage: Q = PolyhedronPartition({0:p, 5:q}) sage: Q.keys_permutation_lexicographic() {0: 0, 5: 1}
It works when the partition has two atoms coded by the same key:
sage: P = PolyhedronPartition([(0,p), (0,q), (3,r)]) sage: d = P.keys_permutation_lexicographic() sage: d {0: 0, 3: 1} sage: P.rename_keys(d).alphabet() {0, 1}
-
merge_atoms
(d)¶ Return the polyhedron partition obtained by merging atoms having the same image under the dictionnary.
INPUT:
d
– dict
OUTPUT:
a polyhedron partitionEXAMPLES:
sage: from slabbe import PolyhedronPartition sage: h = 1/2 sage: p = Polyhedron([(0,h),(0,1),(h,1)]) sage: q = Polyhedron([(0,0), (0,h), (h,1), (1,1), (1,h), (h,0)]) sage: r = Polyhedron([(h,0), (1,0), (1,h)]) sage: P = PolyhedronPartition({0:p, 1:q, 2:r}) sage: P.merge_atoms({0:4, 1:4, 2:5}) Polyhedron partition of 2 atoms with 2 letters sage: P.merge_atoms({0:4, 1:5, 2:4}) Polyhedron partition of 3 atoms with 2 letters
When pair of atoms are not convex, it needs to merge 3 or more atoms:
sage: h = 1/5 sage: p = Polyhedron([(0,0),(h,1-h),(0,1)]) sage: q = Polyhedron([(0,1), (h,1-h), (1,1)]) sage: r = Polyhedron([(0,0), (h,1-h), (1,1), (1,0)]) sage: P = PolyhedronPartition({0:p, 1:q, 2:r}) sage: P.merge_atoms({0:4, 1:4, 2:4}) Polyhedron partition of 1 atoms with 1 letters
-
plot
()¶ EXAMPLES:
sage: from slabbe import PolyhedronPartition sage: h = 1/2 sage: p = Polyhedron([(0,h),(0,1),(h,1)]) sage: q = Polyhedron([(0,0), (0,h), (h,1), (1,1), (1,h), (h,0)]) sage: r = Polyhedron([(h,0), (1,0), (1,h)]) sage: P = PolyhedronPartition([p,q,r]) sage: P.plot() Graphics object consisting of 21 graphics primitives
-
refine_by_hyperplane
(ieq)¶ Refine the partition with the two half spaces of each side of an hyperplane.
INPUT:
ieq
– list, an inequality. An entry equal to “[-1,7,3,4]” represents the inequality 7x_1+3x_2+4x_3>= 1.
EXAMPLES:
sage: from slabbe import PolyhedronPartition sage: h = 1/3 sage: p = Polyhedron([(0,h),(0,1),(h,1)]) sage: q = Polyhedron([(0,0), (0,h), (h,1), (h,0)]) sage: r = Polyhedron([(h,1), (1,1), (1,h), (h,0)]) sage: s = Polyhedron([(h,0), (1,0), (1,h)]) sage: P = PolyhedronPartition({0:p, 1:q, 2:r, 3:s}) sage: ieq = [-4, 5, 1] sage: P.refine_by_hyperplane(ieq) Polyhedron partition of 6 atoms with 6 letters
-
refinement
(other, key_fn=None)¶ Return the polyhedron partition obtained by the intersection of the atoms of self with the atoms of other.
Only atoms of positive volume are kept.
INPUT:
other
– a polyhedron partitionkey_fn
– function to apply on pairs of labels, or None
OUTPUT:
a polyhedron partitionEXAMPLES:
sage: from slabbe import PolyhedronPartition sage: h = 1/3 sage: p = Polyhedron([(0,h),(0,1),(h,1)]) sage: q = Polyhedron([(0,0), (0,h), (h,1), (h,0)]) sage: r = Polyhedron([(h,1), (1,1), (1,h), (h,0)]) sage: s = Polyhedron([(h,0), (1,0), (1,h)]) sage: P = PolyhedronPartition({0:p, 1:q, 2:r, 3:s}) sage: g = 1/5 sage: t1 = Polyhedron([(g,g), (g,1-g), (1-g,g) ]) sage: t2 = Polyhedron([(g,1-g), (1-g,g), (1-g,1-g)]) sage: Q = PolyhedronPartition([t1,t2]) sage: P.refinement(Q) Polyhedron partition of 8 atoms with 8 letters
-
rename_keys
(d)¶ Return a polyhedron partition whose keys are the images under a map.
INPUT:
d
– dict, function old key -> new key
EXAMPLES:
sage: from slabbe import PolyhedronPartition sage: h = 1/2 sage: p = Polyhedron([(0,h),(0,1),(h,1)]) sage: q = Polyhedron([(0,0), (0,h), (h,1), (1,1), (1,h), (h,0)]) sage: r = Polyhedron([(h,0), (1,0), (1,h)]) sage: P = PolyhedronPartition([p,q,r]) sage: Q = P.rename_keys({0:'b', 1:'a', 2:'z'}) sage: Q Polyhedron partition of 3 atoms with 3 letters sage: sorted(key for key,p in Q) ['a', 'b', 'z']
It does not have to be injective:
sage: Q = P.rename_keys({0:'b', 1:'a', 2:'b'}) sage: sorted(key for key,p in Q) ['a', 'b', 'b']
-
classmethod
self_similar_19_tiles_partition
()¶ This construct the polygon partition introduced in [Lab2019] associated to the self-similar 19 Wang tiles [Lab2018].
EXAMPLES:
sage: from slabbe import PolyhedronPartition sage: PU = PolyhedronPartition.self_similar_19_tiles_partition() sage: PU.is_pairwise_disjoint() True sage: PU.volume() 1
REFERENCES:
[Lab2018] S. Labbé. A self-similar aperiodic set of 19 Wang tiles. Geom. Dedicata, 2018. https://doi.org/10.1007/s10711-018-0384-8. [Lab2019] S. Labbé. A Markov partition for Jeandel-Rao aperiodic Wang tilings. March 2019. https://arxiv.org/abs/1903.06137
-
tikz
(fontsize='\\normalsize', scale=1, label_format='{}', extra_code='')¶ INPUT:
fontsize
– string (default:r'\normalsize'
scale
– number (default:1
)label_format
– string (default:r'{}'
) to be called withlabel_format.format(key)
extra_code
– string (default:''
)
EXAMPLES:
sage: from slabbe import PolyhedronPartition sage: h = 1/2 sage: p = Polyhedron([(0,h),(0,1),(h,1)]) sage: q = Polyhedron([(0,0), (0,h), (h,1), (1,1), (1,h), (h,0)]) sage: r = Polyhedron([(h,0), (1,0), (1,h)]) sage: P = PolyhedronPartition([p,q,r]) sage: _ = P.tikz().pdf(view=False)
Irrational partition:
sage: z = polygen(QQ, 'z') #z = QQ['z'].0 # same as sage: K = NumberField(z**2-z-1, 'phi', embedding=RR(1.6)) sage: phi = K.gen() sage: h = 1/phi^2 sage: p = Polyhedron([(0,h),(0,1),(h,1)]) sage: q = Polyhedron([(0,0), (0,h), (h,1), (h,0)]) sage: r = Polyhedron([(h,1), (1,1), (1,h), (h,0)]) sage: s = Polyhedron([(h,0), (1,0), (1,h)]) sage: P = PolyhedronPartition({0:p, 1:q, 2:r, 3:s}, base_ring=K) sage: _ = P.tikz().pdf(view=False)
Testing the options:
sage: _ = P.tikz(fontsize=r'\scriptsize').pdf(view=False) sage: _ = P.tikz(scale=2).pdf(view=False) sage: _ = P.tikz(label_format=r'$a_{{{}}}$').pdf(view=False)
-
translation
(displacement)¶ Return the translated partition of polyhedron.
INPUT:
displacement
– a displacement vector or a list/tuple of coordinates that determines a displacement vector.
OUTPUT:
The translated partition.
EXAMPLES:
sage: from slabbe import PolyhedronPartition sage: h = 1/2 sage: p = Polyhedron([(0,h),(0,1),(h,1)]) sage: q = Polyhedron([(0,0), (0,h), (h,1), (1,1), (1,h), (h,0)]) sage: r = Polyhedron([(h,0), (1,0), (1,h)]) sage: P = PolyhedronPartition([p,q,r]) sage: P.translation((1,1)) Polyhedron partition of 3 atoms with 3 letters
-
volume
()¶ EXAMPLES:
sage: from slabbe import PolyhedronPartition sage: h = 1/2 sage: p = Polyhedron([(0,h),(0,1),(h,1)]) sage: q = Polyhedron([(0,0), (0,h), (h,1), (1,1), (1,h), (h,0)]) sage: r = Polyhedron([(h,0), (1,0), (1,h)]) sage: P = PolyhedronPartition([p,q,r]) sage: P.volume() 1
TESTS:
sage: PolyhedronPartition([], base_ring=ZZ).volume() 0
-
volume_dict
(normalize=False)¶ INPUT
normalize
– boolean (default:False
), whether to normalize the sum of the whole volume to 1
EXAMPLES:
sage: from slabbe import PolyhedronPartition sage: h = 1/2 sage: p = Polyhedron([(0,h),(0,1),(h,1)]) sage: q = Polyhedron([(0,0), (0,h), (h,1), (1,1), (1,h), (h,0)]) sage: r = Polyhedron([(h,0), (1,0), (1,h)]) sage: P = PolyhedronPartition([p,q,r]) sage: P.volume_dict() {0: 1/8, 1: 3/4, 2: 1/8} sage: (2*P).volume_dict() {0: 1/2, 1: 3, 2: 1/2}
-
slabbe.polyhedron_partition.
find_unused_key
(d, sequence)¶ Return the first key in sequence which is not in d.
EXAMPLES:
sage: from slabbe.polyhedron_partition import find_unused_key sage: d = {3:32, 0:21, 1:4, 5:5} sage: find_unused_key(d, NN) 2 sage: d[2] = 1234 sage: find_unused_key(d, NN) 4 sage: d[4] = 1234 sage: find_unused_key(d, NN) 6
-
slabbe.polyhedron_partition.
is_union_convex
(t)¶ Return whether the union of the polyhedrons is convex.
INPUT:
t
– list of polyhedron
EXAMPLES:
sage: from slabbe.polyhedron_partition import is_union_convex sage: h = 1/2 sage: p = Polyhedron([(0,h),(0,1),(h,1)]) sage: q = Polyhedron([(0,0), (0,h), (h,1), (1,1), (1,h), (h,0)]) sage: r = Polyhedron([(h,0), (1,0), (1,h)]) sage: is_union_convex((p,q,r)) True sage: is_union_convex((p,q)) True sage: is_union_convex((p,r)) False
Here we need to consider the three at the same time to get a convex union:
sage: h = 1/5 sage: p = Polyhedron([(0,0),(h,1-h),(0,1)]) sage: q = Polyhedron([(0,1), (h,1-h), (1,1)]) sage: r = Polyhedron([(0,0), (h,1-h), (1,1), (1,0)]) sage: is_union_convex((p,q)) False sage: is_union_convex((p,r)) False sage: is_union_convex((q,r)) False sage: is_union_convex((p,q,r)) True