# ********************************************************************
# This file is part of sage-flatsurf.
#
# Copyright (C) 2017-2020 W. Patrick Hooper
# 2017-2020 Vincent Delecroix
# 2023 Julian Rüth
#
# sage-flatsurf 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 of the License, or
# (at your option) any later version.
#
# sage-flatsurf 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.
#
# You should have received a copy of the GNU General Public License
# along with sage-flatsurf. If not, see <https://www.gnu.org/licenses/>.
# ********************************************************************
from sage.rings.integer_ring import ZZ
from sage.rings.rational_field import QQ
from sage.rings.number_field.number_field import NumberField
from sage.rings.qqbar import AA, number_field_elements_from_algebraics
from sage.structure.sage_object import SageObject
from sage.matrix.constructor import matrix
from sage.modules.free_module_element import vector
from sage.geometry.polyhedron.constructor import Polyhedron
from sage.functions.other import sqrt
from flatsurf.geometry.straight_line_trajectory import (
StraightLineTrajectory,
SegmentInPolygon,
)
from flatsurf.geometry.tangent_bundle import SimilaritySurfaceTangentVector
[docs]class ConeSurfaceToPolyhedronMap(SageObject):
r"""
A map sending objects defined on a ConeSurface built from a polyhedron to the polyhedron. Currently, this
works to send a trajectory to a list of points.
This class should not be called directly. You get an object of this type from polyhedron_to_cone_surface.
"""
def __init__(self, cone_surface, polyhedron, mapping_data):
self._s = cone_surface
self._p = polyhedron
self._md = mapping_data
def __call__(self, o):
r"""
This method is used to convert from an object on the cone surface to an object on the polyhedron.
Currently works with
- StraightLineTrajectory -- returns the corresponding list of points on the polyhedron
- SegmentInPolygon -- returns the corresponding pair of points on the polyhedron
- SimilaritySurfaceTangentVector -- returns a pair of points corresponding to the image point and image of the tangent vector.
"""
if isinstance(o, StraightLineTrajectory):
points = []
it = iter(o.segments())
s = next(it)
label = s.polygon_label()
points.append(self._md[label][0] + self._md[label][1] * s.start().point())
points.append(self._md[label][0] + self._md[label][1] * s.end().point())
for s in it:
label = s.polygon_label()
points.append(self._md[label][0] + self._md[label][1] * s.end().point())
return points
if isinstance(o, SegmentInPolygon):
# Return the pair of images of the endpoints.
label = o.polygon_label()
return (
self._md[label][0] + self._md[label][1] * o.start().point(),
self._md[label][0] + self._md[label][1] * o.end().point(),
)
if isinstance(o, SimilaritySurfaceTangentVector):
# Map to a pair of vectors conisting of the image of the basepoint and the image of the vector.
label = o.polygon_label()
point = o.point()
vector = o.vector()
return (
self._md[label][0] + self._md[label][1] * point,
self._md[label][1] * vector,
)
raise ValueError("Failed to recognize type of passed object")
def __eq__(self, other):
r"""
Return whether this map is indistinguishable from ``other``.
EXAMPLES::
sage: from flatsurf.geometry.polyhedra import Polyhedron, polyhedron_to_cone_surface
sage: vertices=[]
sage: for i in range(3):
....: temp=vector([1 if k==i else 0 for k in range(3)])
....: for j in range(-1,3,2):
....: vertices.append(j*temp)
sage: octahedron=Polyhedron(vertices=vertices)
sage: surface, surface_to_octahedron = polyhedron_to_cone_surface(octahedron,scaling_factor=AA(1/sqrt(2))) # long time (.5s)
sage: surface_to_octahedron == surface_to_octahedron # long time (see above)
True
"""
if not isinstance(other, ConeSurfaceToPolyhedronMap):
return False
return self._s == other._s and self._p == other._p and self._md == other._md
def __ne__(self, other):
r"""
Return whether this map is distinguishable from ``other``.
EXAMPLES::
sage: from flatsurf.geometry.polyhedra import Polyhedron, polyhedron_to_cone_surface
sage: vertices=[]
sage: for i in range(3):
....: temp=vector([1 if k==i else 0 for k in range(3)])
....: for j in range(-1,3,2):
....: vertices.append(j*temp)
sage: octahedron=Polyhedron(vertices=vertices)
sage: surface, surface_to_octahedron = polyhedron_to_cone_surface(octahedron,scaling_factor=AA(1/sqrt(2))) # long time (.3s)
sage: surface_to_octahedron != surface_to_octahedron # long time (see above)
False
"""
return not (self == other)
[docs]def polyhedron_to_cone_surface(polyhedron, use_AA=False, scaling_factor=ZZ(1)):
r"""
Construct the Euclidean Cone Surface associated to the surface of a polyhedron and a map
from the cone surface to the polyhedron.
INPUT:
- ``polyhedron`` -- A 3-dimensional polyhedron, which should be defined over something that coerces into AA
- ``use_AA`` -- If True, the surface returned will be defined over AA. If false, the algorithm will find the smallest NumberField and write the field there.
- ``scaling_factor`` -- The surface returned will have a metric scaled by multiplication by this factor (compared with the original polyhendron). This can be used to produce a surface defined over a smaller NumberField.
OUTPUT:
A pair consisting of a ConeSurface and a ConeSurfaceToPolyhedronMap.
EXAMPLES::
sage: from flatsurf.geometry.polyhedra import Polyhedron, polyhedron_to_cone_surface
sage: vertices=[]
sage: for i in range(3):
....: temp=vector([1 if k==i else 0 for k in range(3)])
....: for j in range(-1,3,2):
....: vertices.append(j*temp)
sage: octahedron=Polyhedron(vertices=vertices)
sage: surface,surface_to_octahedron = \
....: polyhedron_to_cone_surface(octahedron,scaling_factor=AA(1/sqrt(2)))
sage: TestSuite(surface).run()
sage: TestSuite(surface_to_octahedron).run() # long time (.4s)
sage: len(surface.polygons())
8
sage: surface.base_ring()
Number Field in a with defining polynomial y^2 - 3 with a = 1.732050807568878?
sage: sqrt3=surface.base_ring().gen()
sage: tangent_bundle=surface.tangent_bundle()
sage: v=tangent_bundle(0,(0,0),(sqrt3,2))
sage: traj=v.straight_line_trajectory()
sage: traj.flow(10)
sage: traj.is_saddle_connection()
True
sage: traj.combinatorial_length()
8
sage: path3d = surface_to_octahedron(traj)
sage: len(path3d)
9
sage: # We will show that the length of the path is sqrt(42):
sage: total_length = 0
sage: for i in range(8):
....: start = path3d[i]
....: end = path3d[i+1]
....: total_length += (vector(end)-vector(start)).norm()
sage: ZZ(total_length**2)
42
"""
if polyhedron.dim() != 3:
raise ValueError
c = polyhedron.center()
vertices = polyhedron.vertices()
vertex_order = {}
for i, v in enumerate(vertices):
vertex_order[v] = i
faces = polyhedron.faces(2)
face_order = {}
face_edges = []
face_vertices = []
face_map_data = []
for i, f in enumerate(faces):
face_order[f] = i
edges = f.as_polyhedron().faces(1)
face_edges_temp = set()
for edge in edges:
edge_temp = set()
for vertex in edge.vertices():
v = vertex.vector()
v.set_immutable()
edge_temp.add(v)
face_edges_temp.add(frozenset(edge_temp))
last_edge = next(iter(face_edges_temp))
v = next(iter(last_edge))
face_vertices_temp = [v]
for j in range(len(face_edges_temp) - 1):
for edge in face_edges_temp:
if v in edge and edge != last_edge:
# bingo
last_edge = edge
for vv in edge:
if vv != v:
v = vv
face_vertices_temp.append(vv)
break
break
v0 = face_vertices_temp[0]
v1 = face_vertices_temp[1]
v2 = face_vertices_temp[2]
n = (v1 - v0).cross_product(v2 - v0)
if (v0 - c).dot_product(n) < 0:
n = -n
face_vertices_temp.reverse()
v0 = face_vertices_temp[0]
v1 = face_vertices_temp[1]
v2 = face_vertices_temp[2]
face_vertices.append(face_vertices_temp)
n = n / AA(n.norm())
w = v1 - v0
w = w / AA(w.norm())
m = 1 / scaling_factor * matrix(AA, [w, n.cross_product(w), n]).transpose()
mi = ~m
mi_submatrix = mi.submatrix(0, 0, 2, 3)
face_map_data.append(
(
v0, # translation to bring origin in plane to v0
m.submatrix(0, 0, 3, 2),
-mi_submatrix * v0,
mi_submatrix,
)
)
it = iter(face_vertices_temp)
v_last = next(it)
face_edge_dict = {}
j = 0
for v in it:
edge = frozenset([v_last, v])
face_edge_dict[edge] = j
j += 1
v_last = v
v = next(iter(face_vertices_temp))
edge = frozenset([v_last, v])
face_edge_dict[edge] = j
face_edges.append(face_edge_dict)
gluings = {}
for p1, face_edge_dict1 in enumerate(face_edges):
for edge, e1 in face_edge_dict1.items():
found = False
for p2, face_edge_dict2 in enumerate(face_edges):
if p1 != p2 and edge in face_edge_dict2:
e2 = face_edge_dict2[edge]
gluings[(p1, e1)] = (p2, e2)
found = True
break
if not found:
print(p1)
print(e1)
print(edge)
raise RuntimeError("Failed to find glued edge")
polygon_vertices_AA = []
for p, vs in enumerate(face_vertices):
trans = face_map_data[p][2]
m = face_map_data[p][3]
polygon_vertices_AA.append([trans + m * v for v in vs])
from flatsurf import MutableOrientedSimilaritySurface
if use_AA is True:
from flatsurf import Polygon
S = MutableOrientedSimilaritySurface(AA)
for vs in polygon_vertices_AA:
S.add_polygon(Polygon(vertices=vs, base_ring=AA))
for x, y in gluings.items():
S.glue(x, y)
S.set_immutable()
return S, ConeSurfaceToPolyhedronMap(S, polyhedron, face_map_data)
else:
elts = []
for vs in polygon_vertices_AA:
for v in vs:
elts.append(v[0])
elts.append(v[1])
# Find the best number field:
field, elts2, hom = number_field_elements_from_algebraics(elts, minimal=True)
if field == QQ:
# Defined over the rationals!
polygon_vertices_field2 = []
j = 0
for vs in polygon_vertices_AA:
vs2 = []
for v in vs:
vs2.append(vector(field, [elts2[j], elts2[j + 1]]))
j = j + 2
polygon_vertices_field2.append(vs2)
S = MutableOrientedSimilaritySurface(field)
from flatsurf import Polygon
for vs in polygon_vertices_field2:
S.add_polygon(Polygon(vertices=vs, base_ring=field))
for x, y in gluings.items():
S.glue(x, y)
S.set_immutable()
return S, ConeSurfaceToPolyhedronMap(S, polyhedron, face_map_data)
else:
# Unfortunately field doesn't come with an real embedding (which is given by hom!)
# So, we make a copy of the field, and add the embedding.
field2 = NumberField(
field.polynomial(), name="a", embedding=hom(field.gen())
)
# The following converts from field to field2:
hom2 = field.hom(im_gens=[field2.gen()])
polygon_vertices_field2 = []
j = 0
for vs in polygon_vertices_AA:
vs2 = []
for v in vs:
vs2.append(vector(field2, [hom2(elts2[j]), hom2(elts2[j + 1])]))
j = j + 2
polygon_vertices_field2.append(vs2)
S = MutableOrientedSimilaritySurface(field2)
from flatsurf import Polygon
for vs in polygon_vertices_field2:
S.add_polygon(Polygon(vertices=vs, base_ring=field2))
for x, y in gluings.items():
S.glue(x, y)
S.set_immutable()
return S, ConeSurfaceToPolyhedronMap(S, polyhedron, face_map_data)
[docs]def platonic_tetrahedron():
r"""Produce a triple consisting of a polyhedral version of the platonic tetrahedron,
the associated cone surface, and a ConeSurfaceToPolyhedronMap from the surface
to the polyhedron.
EXAMPLES::
sage: from flatsurf.geometry.polyhedra import platonic_tetrahedron
sage: polyhedron,surface,surface_to_polyhedron = platonic_tetrahedron()
sage: TestSuite(surface).run()
"""
vertices = []
for x in range(-1, 3, 2):
for y in range(-1, 3, 2):
vertices.append(vector(QQ, (x, y, x * y)))
p = Polyhedron(vertices=vertices)
s, m = polyhedron_to_cone_surface(p, scaling_factor=AA(1 / sqrt(2)))
return p, s, m
[docs]def platonic_cube():
r"""Produce a triple consisting of a polyhedral version of the platonic cube,
the associated cone surface, and a ConeSurfaceToPolyhedronMap from the surface
to the polyhedron.
EXAMPLES::
sage: from flatsurf.geometry.polyhedra import platonic_cube
sage: polyhedron,surface,surface_to_polyhedron = platonic_cube()
sage: TestSuite(surface).run()
"""
vertices = []
for x in range(-1, 3, 2):
for y in range(-1, 3, 2):
for z in range(-1, 3, 2):
vertices.append(vector(QQ, (x, y, z)))
p = Polyhedron(vertices=vertices)
s, m = polyhedron_to_cone_surface(p, scaling_factor=QQ(1) / 2)
return p, s, m
[docs]def platonic_octahedron():
r"""Produce a triple consisting of a polyhedral version of the platonic octahedron,
the associated cone surface, and a ConeSurfaceToPolyhedronMap from the surface
to the polyhedron.
EXAMPLES::
sage: from flatsurf.geometry.polyhedra import platonic_octahedron
sage: polyhedron,surface,surface_to_polyhedron = platonic_octahedron() # long time (.3s)
sage: TestSuite(surface).run() # long time (see above)
"""
vertices = []
for i in range(3):
temp = vector(QQ, [1 if k == i else 0 for k in range(3)])
for j in range(-1, 3, 2):
vertices.append(j * temp)
octahedron = Polyhedron(vertices=vertices)
surface, surface_to_octahedron = polyhedron_to_cone_surface(
octahedron, scaling_factor=AA(sqrt(2))
)
return octahedron, surface, surface_to_octahedron
[docs]def platonic_dodecahedron():
r"""Produce a triple consisting of a polyhedral version of the platonic dodecahedron,
the associated cone surface, and a ConeSurfaceToPolyhedronMap from the surface
to the polyhedron.
EXAMPLES::
sage: from flatsurf.geometry.polyhedra import platonic_dodecahedron
sage: polyhedron, surface, surface_to_polyhedron = platonic_dodecahedron() # long time (1s)
sage: TestSuite(surface).run() # long time (.8s)
"""
vertices = []
phi = AA(1 + sqrt(5)) / 2
F = NumberField(phi.minpoly(), "phi", embedding=phi)
phi = F.gen()
for x in range(-1, 3, 2):
for y in range(-1, 3, 2):
for z in range(-1, 3, 2):
vertices.append(vector(F, (x, y, z)))
for x in range(-1, 3, 2):
for y in range(-1, 3, 2):
vertices.append(vector(F, (0, x * phi, y / phi)))
vertices.append(vector(F, (y / phi, 0, x * phi)))
vertices.append(vector(F, (x * phi, y / phi, 0)))
scale = AA(2 / sqrt(1 + (phi - 1) ** 2 + (1 / phi - 1) ** 2))
p = Polyhedron(vertices=vertices)
s, m = polyhedron_to_cone_surface(p, scaling_factor=scale)
return p, s, m
[docs]def platonic_icosahedron():
r"""Produce a triple consisting of a polyhedral version of the platonic icosahedron,
the associated cone surface, and a ConeSurfaceToPolyhedronMap from the surface
to the polyhedron.
EXAMPLES::
sage: from flatsurf.geometry.polyhedra import platonic_icosahedron
sage: polyhedron,surface,surface_to_polyhedron = platonic_icosahedron() # long time (.9s)
sage: TestSuite(surface).run() # long time (see above)
"""
vertices = []
phi = AA(1 + sqrt(5)) / 2
F = NumberField(phi.minpoly(), "phi", embedding=phi)
phi = F.gen()
for i in range(3):
for s1 in range(-1, 3, 2):
for s2 in range(-1, 3, 2):
p = 3 * [None]
p[i] = s1 * phi
p[(i + 1) % 3] = s2
p[(i + 2) % 3] = 0
vertices.append(vector(F, p))
p = Polyhedron(vertices=vertices)
s, m = polyhedron_to_cone_surface(p)
return p, s, m