Source code for flatsurf.geometry.similarity

# ****************************************************************************
#  This file is part of sage-flatsurf.
#
#        Copyright (C) 2016-2020 Vincent Delecroix
#                      2020-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.misc.cachefunc import cached_method

from sage.structure.element import MultiplicativeGroupElement, parent
from sage.structure.unique_representation import UniqueRepresentation

from sage.categories.groups import Groups

from sage.all import Rings

from sage.modules.free_module_element import vector
from sage.groups.group import Group
from sage.rings.integer import Integer
from sage.rings.integer_ring import ZZ
from sage.modules.free_module_element import FreeModuleElement

from sage.structure.element import is_Matrix

ZZ_0 = Integer(0)
ZZ_1 = Integer(1)
ZZ_m1 = -ZZ_1


[docs] class Similarity(MultiplicativeGroupElement): r""" Class for a similarity of the plane with possible reflection. Construct the similarity (x,y) mapsto (ax-by+s,bx+ay+t) if sign=1, and (ax+by+s,bx-ay+t) if sign=-1 """ def __init__(self, p, a, b, s, t, sign): r""" Construct the similarity (x,y) mapsto (ax-by+s,bx+ay+t) if sign=1, and (ax+by+s,bx-ay+t) if sign=-1 """ if p is None: raise ValueError("The parent must be provided") if parent(a) is not p.base_ring(): raise ValueError("wrong parent for a") if parent(b) is not p.base_ring(): raise ValueError("wrong parent for b") if parent(s) is not p.base_ring(): raise ValueError("wrong parent for s") if parent(t) is not p.base_ring(): raise ValueError("wrong parent for t") if parent(sign) is not ZZ or not sign.is_unit(): raise ValueError("sign must be either 1 or -1.") self._a = a self._b = b self._s = s self._t = t self._sign = sign MultiplicativeGroupElement.__init__(self, p)
[docs] def sign(self): return self._sign
[docs] def is_translation(self): r""" Return whether this element is a translation. EXAMPLES:: sage: from flatsurf.geometry.similarity import SimilarityGroup sage: S = SimilarityGroup(QQ) sage: S((1,2)).is_translation() True sage: S((1,0,3,-1/2)).is_translation() True sage: S((0,1,0,0)).is_translation() False """ return self._sign.is_one() and self._a.is_one() and self._b.is_zero()
[docs] def is_half_translation(self): r""" Return whether this element is a half translation. EXAMPLES:: sage: from flatsurf.geometry.similarity import SimilarityGroup sage: S = SimilarityGroup(QQ) sage: S((1,2)).is_half_translation() True sage: S((-1, 0, 0, 2)).is_half_translation() True sage: S((0,1,0,0)).is_half_translation() False """ return ( self._sign.is_one() and (self._a.is_one() or ((-self._a).is_one())) and self._b.is_zero() )
[docs] def is_orientable(self): return self._sign.is_one()
[docs] def is_rotation(self): r""" Check whether this element is a rotation EXAMPLES:: sage: from flatsurf.geometry.similarity import SimilarityGroup sage: S = SimilarityGroup(QQ) sage: S((1,2)).is_rotation() False sage: S((0,-1,0,0)).is_rotation() True sage: S.one().is_rotation() True """ return self.is_one() or (self.det().is_one() and not self.is_translation())
[docs] def is_isometry(self): r""" Check whether this element is an isometry EXAMPLES:: sage: from flatsurf.geometry.similarity import SimilarityGroup sage: S = SimilarityGroup(QQ) sage: S.one().is_isometry() True sage: S((0,1,0,0)).is_isometry() True sage: S((0,1,0,0,-1)).is_isometry() True sage: S((1,1,0,0)).is_isometry() False sage: S((3,-1/2)).is_isometry() True """ det = self.det() return det.is_one() or (-det).is_one()
[docs] def det(self): r""" Return the determinant of this element """ return self._sign * (self._a * self._a + self._b * self._b)
def _mul_(self, right): r""" Composition EXAMPLES:: sage: from flatsurf.geometry.similarity import SimilarityGroup sage: S = SimilarityGroup(QQ) sage: S((1,2)) * S((3,-5)) == S((4,-3)) True sage: from itertools import product sage: a1 = S((0,2,0,0,1)) sage: a2 = S((1,0,0,0,-1)) sage: a3 = S((1,1,0,0)) sage: a4 = S((1,0,-1,1)) sage: a5 = S((2,-1,3/5,2/3,-1)) sage: for g1,g2,g3 in product([a1,a2,a3,a4,a5], repeat=3): ....: assert g1.matrix()*g2.matrix() == (g1*g2).matrix() ....: assert (g1*g2).matrix()*g3.matrix() == (g1*g2*g3).matrix() """ a = self._a * right._a - self._sign * self._b * right._b b = self._b * right._a + self._sign * self._a * right._b s = self._a * right._s - self._sign * self._b * right._t + self._s t = self._b * right._s + self._sign * self._a * right._t + self._t sign = self._sign * right._sign P = self.parent() return P.element_class(P, a, b, s, t, sign) def __invert__(self): r""" Invert a similarity. TESTS:: sage: from flatsurf.geometry.similarity import SimilarityGroup sage: S = SimilarityGroup(QQ) sage: from itertools import product sage: for a in [S((0,2,0,0,1)), S((1,0,0,0,-1)), S((1,1,0,0)), ....: S((1,0,-1,1)), S((2,-1,3/5,2/3,-1))]: ....: assert (a*~a).is_one() and (~a*a).is_one() """ P = self.parent() sign = self._sign det = self.det() a = sign * self._a / det b = -self._b / det return P.element_class( P, a, b, -a * self._s + sign * b * self._t, -b * self._s - sign * a * self._t, sign, ) def _div_(self, right): det = right.det() inv_a = right._sign * right._a inv_b = -right._b inv_s = -right._sign * right._a * right._s - right._sign * right._b * right._t inv_t = right._b * right._s - right._a * right._t a = (self._a * inv_a - self._sign * self._b * inv_b) / det b = (self._b * inv_a + self._sign * self._a * inv_b) / det s = (self._a * inv_s - self._sign * self._b * inv_t) / det + self._s t = (self._b * inv_s + self._sign * self._a * inv_t) / det + self._t return self.parent().element_class( self.parent(), self.base_ring()(a), self.base_ring()(b), self.base_ring()(s), self.base_ring()(t), self._sign * right._sign, ) def __hash__(self): return ( 73 * hash(self._a) - 19 * hash(self._b) + 13 * hash(self._s) + 53 * hash(self._t) + 67 * hash(self._sign) ) def __call__(self, w, ring=None): r""" Return the image of ``w`` under the similarity. Here ``w`` may be a convex polygon or a vector (or something that can be indexed in the same way as a vector). If a ring is provided, the objects returned will be defined over this ring. TESTS:: sage: from flatsurf.geometry.similarity import SimilarityGroup sage: S = SimilarityGroup(AA) sage: a = S((1,-1,AA(2).sqrt(),0)) sage: a((1,2)) (4.414213562373095?, 1) sage: a.matrix()*vector((1,2,1)) (4.414213562373095?, 1, 1) sage: from flatsurf.geometry.similarity import SimilarityGroup sage: SG = SimilarityGroup(QQ) sage: from flatsurf import Polygon sage: p = Polygon(vertices=[(0, 0), (1, 0), (1, 1), (0, 1)]) sage: g = SG.an_element()**2 sage: g (x, y) |-> (25*x + 4, 25*y + 10) sage: g(p) Polygon(vertices=[(4, 10), (29, 10), (29, 35), (4, 35)]) sage: g(p, ring=AA).category() Category of convex simple euclidean polygons over Algebraic Real Field """ if ring is not None and ring not in Rings(): raise TypeError("ring must be a ring") from flatsurf.geometry.polygon import EuclideanPolygon if isinstance(w, EuclideanPolygon) and w.is_convex(): if ring is None: ring = self.parent().base_ring() from flatsurf import Polygon try: return Polygon(vertices=[self(v) for v in w.vertices()], base_ring=ring) except ValueError: if not self._sign.is_one(): raise ValueError("Similarity must be orientation preserving.") # Not sure why this would happen: raise if ring is None: if self._sign.is_one(): return vector( [ self._a * w[0] - self._b * w[1] + self._s, self._b * w[0] + self._a * w[1] + self._t, ] ) else: return vector( [ self._a * w[0] + self._b * w[1] + self._s, self._b * w[0] - self._a * w[1] + self._t, ] ) else: if self._sign.is_one(): return vector( ring, [ self._a * w[0] - self._b * w[1] + self._s, self._b * w[0] + self._a * w[1] + self._t, ], ) else: return vector( ring, [ self._a * w[0] + self._b * w[1] + self._s, self._b * w[0] - self._a * w[1] + self._t, ], ) def _repr_(self): r""" TESTS:: sage: from flatsurf.geometry.similarity import SimilarityGroup sage: S = SimilarityGroup(QQ) sage: S.one() (x, y) |-> (x, y) sage: S((1,-2/3)) (x, y) |-> (x + 1, y - 2/3) sage: S((-1,0,2/3,3)) (x, y) |-> (-x + 2/3, -y + 3) sage: S((-1,0,2/3,3,-1)) (x, y) |-> (-x + 2/3, y + 3) """ R = self.parent().base_ring()["x", "y"] x, y = R.gens() return "(x, y) |-> ({}, {})".format( self._a * x - self._sign * self._b * y + self._s, self._b * x + self._sign * self._a * y + self._t, ) def __eq__(self, other): r""" TESTS:: sage: from flatsurf.geometry.similarity import SimilarityGroup sage: S = SimilarityGroup(QQ) sage: S((1,0)) == S((1,0)) True sage: S((1,0)) == S((0,1)) False sage: S((1,0,0,0)) == S((0,1,0,0)) False sage: S((1,0,0,0,1)) == S((1,0,0,0,-1)) False """ if other is None: return False if type(other) == int: return False if self.parent() != other.parent(): return False return ( self._a == other._a and self._b == other._b and self._s == other._s and self._t == other._t and self._sign == other._sign ) def __ne__(self, other): return not (self == other)
[docs] def matrix(self): r""" Return the 3x3 matrix representative of this element EXAMPLES:: sage: from flatsurf.geometry.similarity import SimilarityGroup sage: S = SimilarityGroup(QQ) sage: S((1,-2/3,1,1,-1)).matrix() [ 1 -2/3 1] [-2/3 -1 1] [ 0 0 1] """ P = self.parent() M = P._matrix_space_3x3() z = P._ring.zero() o = P._ring.one() return M( [ self._a, -self._sign * self._b, self._s, self._b, +self._sign * self._a, self._t, z, z, o, ] )
[docs] def derivative(self): r""" Return the 2x2 matrix corresponding to the derivative of this element EXAMPLES:: sage: from flatsurf.geometry.similarity import SimilarityGroup sage: S = SimilarityGroup(QQ) sage: S((1,-2/3,1,1,-1)).derivative() [ 1 -2/3] [-2/3 -1] """ M = self.parent()._matrix_space_2x2() return M([self._a, -self._sign * self._b, self._b, self._sign * self._a])
[docs] class SimilarityGroup(UniqueRepresentation, Group): r""" The group of possibly orientation reversing similarities in the plane. This is the group generated by rotations, translations and dilations. """ Element = Similarity def __init__(self, base_ring): r""" TESTS:: sage: from flatsurf.geometry.similarity import SimilarityGroup sage: TestSuite(SimilarityGroup(QQ)).run() sage: TestSuite(SimilarityGroup(AA)).run() """ self._ring = base_ring Group.__init__(self, category=Groups().Infinite()) @cached_method def _matrix_space_2x2(self): from sage.matrix.matrix_space import MatrixSpace return MatrixSpace(self._ring, 2) @cached_method def _matrix_space_3x3(self): from sage.matrix.matrix_space import MatrixSpace return MatrixSpace(self._ring, 3) @cached_method def _vector_space(self): from sage.modules.free_module import VectorSpace return VectorSpace(self._ring, 2) def _element_constructor_(self, *args, **kwds): r""" TESTS:: sage: from flatsurf.geometry.similarity import SimilarityGroup sage: S = SimilarityGroup(QQ) sage: S((1,1)) # translation (x, y) |-> (x + 1, y + 1) sage: V = QQ^2 sage: S(V((1,-1))) (x, y) |-> (x + 1, y - 1) sage: S(vector((1,1))) (x, y) |-> (x + 1, y + 1) """ if len(args) == 1: x = args[0] else: x = args a = self._ring.one() b = s = t = self._ring.zero() sign = ZZ_1 # TODO: 2x2 and 3x3 matrix input if isinstance(x, (tuple, list)): if len(x) == 2: s, t = map(self._ring, x) elif len(x) == 4: a, b, s, t = map(self._ring, x) elif len(x) == 5: a, b, s, t = map(self._ring, x[:4]) sign = ZZ(x[4]) else: raise ValueError( "can not construct a similarity from a list of length {}".format( len(x) ) ) elif is_Matrix(x): # a -sb # b sa if x.nrows() == x.ncols() == 2: a, c, b, d = x.list() if a == d and b == -c: sign = ZZ_1 elif a == -d and b == c: sign = ZZ_m1 else: raise ValueError("not a similarity matrix") elif x.nrows() == x.ncols() == 3: raise NotImplementedError else: raise ValueError("invalid dimension for matrix input") elif isinstance(x, FreeModuleElement): if len(x) == 2: if x.base_ring() is self._ring: s, t = x else: s, t = map(self._ring, x) else: raise ValueError("invalid dimension for vector input") else: p = parent(x) if self._ring.has_coerce_map_from(p): a = self._ring(x) else: raise ValueError( "element in {} cannot be used to create element in {}".format( p, self ) ) if (a * a + b * b).is_zero(): raise ValueError("not invertible") return self.element_class(self, a, b, s, t, sign) def _coerce_map_from_(self, S): if self._ring.has_coerce_map_from(S): return True if isinstance(S, SimilarityGroup): return self._ring.has_coerce_map_from(S._ring) def _repr_(self): r""" TESTS:: sage: from flatsurf.geometry.similarity import SimilarityGroup sage: SimilarityGroup(QQ) Similarity group over Rational Field """ return "Similarity group over {}".format(self._ring)
[docs] def one(self): r""" EXAMPLES:: sage: from flatsurf.geometry.similarity import SimilarityGroup sage: SimilarityGroup(QQ).one() (x, y) |-> (x, y) sage: SimilarityGroup(QQ).one().is_one() True """ return self.element_class( self, self._ring.one(), # a self._ring.zero(), # b self._ring.zero(), # s self._ring.zero(), # t ZZ_1, ) # sign
def _an_element_(self): r""" Return a typical element of this group. EXAMPLES: sage: from flatsurf.geometry.similarity import SimilarityGroup sage: SimilarityGroup(QQ)._an_element_() (x, y) |-> (3*x + 4*y + 2, 4*x - 3*y - 1) sage: SimilarityGroup(QQ).an_element() (x, y) |-> (3*x + 4*y + 2, 4*x - 3*y - 1) .. SEEALSO:: :meth:`sage.structure.parent.Parent.an_element` which relies on this method and should be called instead """ return self(3, 4, 2, -1, -1)
[docs] def is_abelian(self): return False
[docs] def base_ring(self): return self._ring
[docs] def similarity_from_vectors(u, v, matrix_space=None): r""" Return the unique similarity matrix that maps ``u`` to ``v``. EXAMPLES:: sage: from flatsurf.geometry.similarity import similarity_from_vectors sage: V = VectorSpace(QQ,2) sage: u = V((1,0)) sage: v = V((0,1)) sage: m = similarity_from_vectors(u,v); m [ 0 -1] [ 1 0] sage: m*u == v True sage: u = V((2,1)) sage: v = V((1,-2)) sage: m = similarity_from_vectors(u,v); m [ 0 1] [-1 0] sage: m * u == v True An example built from the Pythagorean triple 3^2 + 4^2 = 5^2:: sage: u2 = V((5,0)) sage: v2 = V((3,4)) sage: m = similarity_from_vectors(u2,v2); m [ 3/5 -4/5] [ 4/5 3/5] sage: m * u2 == v2 True Some test over number fields:: sage: K.<sqrt2> = NumberField(x^2-2, embedding=1.4142) sage: V = VectorSpace(K,2) sage: u = V((sqrt2,0)) sage: v = V((1, 1)) sage: m = similarity_from_vectors(u,v); m [ 1/2*sqrt2 -1/2*sqrt2] [ 1/2*sqrt2 1/2*sqrt2] sage: m*u == v True sage: m = similarity_from_vectors(u, 2*v); m [ sqrt2 -sqrt2] [ sqrt2 sqrt2] sage: m*u == 2*v True """ if u.parent() is not v.parent(): raise ValueError if matrix_space is None: from sage.matrix.matrix_space import MatrixSpace matrix_space = MatrixSpace(u.base_ring(), 2) if u == v: return matrix_space.one() sqnorm_u = u[0] * u[0] + u[1] * u[1] cos_uv = (u[0] * v[0] + u[1] * v[1]) / sqnorm_u sin_uv = (u[0] * v[1] - u[1] * v[0]) / sqnorm_u m = matrix_space([cos_uv, -sin_uv, sin_uv, cos_uv]) m.set_immutable() return m