Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
"""" A triangulation
In Sage, the :class:`~sage.geometry.triangulation.point_configuration.PointConfiguration` and :class:`Triangulation` satisfy a parent/element relationship. In particular, each triangulation refers back to its point configuration. If you want to triangulate a point configuration, you should construct a point configuration first and then use one of its methods to triangulate it according to your requirements. You should never have to construct a :class:`Triangulation` object directly.
EXAMPLES:
First, we select the internal implementation for enumerating triangulations::
sage: PointConfiguration.set_engine('internal') # to make doctests independent of TOPCOM
Here is a simple example of how to triangulate a point configuration::
sage: p = [[0,-1,-1],[0,0,1],[0,1,0], [1,-1,-1],[1,0,1],[1,1,0]] sage: points = PointConfiguration(p) sage: triang = points.triangulate(); triang (<0,1,2,5>, <0,1,3,5>, <1,3,4,5>) sage: triang.plot(axes=False) Graphics3d Object
See :mod:`sage.geometry.triangulation.point_configuration` for more details. """
######################################################################## # Copyright (C) 2010 Volker Braun <vbraun.name@gmail.com> # # Distributed under the terms of the GNU General Public License (GPL) # # http://www.gnu.org/licenses/ ######################################################################## from six import iteritems
from sage.structure.richcmp import richcmp from sage.structure.element import Element from sage.rings.all import QQ, ZZ from sage.modules.all import vector from sage.misc.cachefunc import cached_method from sage.sets.set import Set from sage.graphs.graph import Graph
######################################################################## def triangulation_render_2d(triangulation, **kwds): r""" Return a graphical representation of a 2-d triangulation.
INPUT:
- ``triangulation`` -- a :class:`Triangulation`.
- ``**kwds`` -- keywords that are passed on to the graphics primitives.
OUTPUT:
A 2-d graphics object.
EXAMPLES::
sage: points = PointConfiguration([[0,0],[0,1],[1,0],[1,1],[-1,-1]]) sage: triang = points.triangulate() sage: triang.plot(axes=False, aspect_ratio=1) # indirect doctest Graphics object consisting of 12 graphics primitives """ zorder=2, pointsize=10, **kwds) for p in coord ])
else:
zorder=1, rgbcolor=(0,1,0), **kwds) for l in interior_lines ]) zorder=1, rgbcolor=(0,0,1), **kwds) for l in exterior_lines ])
zorder=0, rgbcolor=(0.8, 1, 0.8), **kwds) for t in triangulation if len(t)>=3 ])
plot_points + \ plot_interior_lines + plot_exterior_lines + \ plot_triangs
def triangulation_render_3d(triangulation, **kwds): r""" Return a graphical representation of a 3-d triangulation.
INPUT:
- ``triangulation`` -- a :class:`Triangulation`.
- ``**kwds`` -- keywords that are passed on to the graphics primitives.
OUTPUT:
A 3-d graphics object.
EXAMPLES::
sage: p = [[0,-1,-1],[0,0,1],[0,1,0], [1,-1,-1],[1,0,1],[1,1,0]] sage: points = PointConfiguration(p) sage: triang = points.triangulate() sage: triang.plot(axes=False) # indirect doctest Graphics3d Object """ **kwds) for p in coord ])
else:
thickness=2, texture=line_int, **kwds) for l in interior_lines ]) thickness=3, texture=line_ext, **kwds) for l in exterior_lines ])
else:
sum([ polygon3d([coord[t[0]], coord[t[1]], coord[t[2]]], texture = triang_int, **kwds) for t in interior_triangs ]) sum([ polygon3d([coord[t[0]], coord[t[1]], coord[t[2]]], texture = triang_ext, **kwds) for t in exterior_triangs ])
plot_points + \ plot_interior_lines + plot_exterior_lines + \ plot_interior_triangs + plot_exterior_triangs
######################################################################## class Triangulation(Element): """ A triangulation of a :class:`~sage.geometry.triangulation.point_configuration.PointConfiguration`.
.. WARNING::
You should never create :class:`Triangulation` objects manually. See :meth:`~sage.geometry.triangulation.point_configuration.PointConfiguration.triangulate` and :meth:`~sage.geometry.triangulation.point_configuration.PointConfiguration.triangulations` to triangulate point configurations. """ def __init__(self, triangulation, parent, check=True): """ The constructor of a ``Triangulation`` object. Note that an internal reference to the underlying ``PointConfiguration`` is kept.
INPUT:
- ``parent`` -- a :class:`~sage.geometry.triangulation.point_configuration.PointConfiguration`
- ``triangulation`` -- an iterable of integers or iterable of iterables (e.g. a list of lists). In the first case, the integers specify simplices via :meth:`PointConfiguration.simplex_to_int`. In the second case, the point indices of the maximal simplices of the triangulation.
- ``check`` -- boolean. Whether to perform checks that the triangulation is, indeed, a triangulation of the point configuration.
NOTE:
Passing ``check=False`` allows you to create triangulations of subsets of the points of the configuration, see :meth:`~sage.geometry.triangulation.point_configuration.PointConfiguration.bistellar_flips`.
EXAMPLES::
sage: p = [[0,1],[0,0],[1,0]] sage: points = PointConfiguration(p) sage: from sage.geometry.triangulation.point_configuration import Triangulation sage: Triangulation([(0,1,2)], points) (<0,1,2>) sage: Triangulation([1], points) (<0,1,2>) """
for i in triangulation ) for t in triangulation)
def point_configuration(self): """ Returns the point configuration underlying the triangulation.
EXAMPLES::
sage: pconfig = PointConfiguration([[0,0],[0,1],[1,0]]) sage: pconfig A point configuration in affine 2-space over Integer Ring consisting of 3 points. The triangulations of this point configuration are assumed to be connected, not necessarily fine, not necessarily regular. sage: triangulation = pconfig.triangulate() sage: triangulation (<0,1,2>) sage: triangulation.point_configuration() A point configuration in affine 2-space over Integer Ring consisting of 3 points. The triangulations of this point configuration are assumed to be connected, not necessarily fine, not necessarily regular. sage: pconfig == triangulation.point_configuration() True """
def _richcmp_(self, right, op): r""" Compare ``self`` and ``right``.
INPUT:
- ``right`` -- a triangulation
TESTS::
sage: pc = PointConfiguration([[0,0],[0,1],[1,0]]) sage: t1 = pc.triangulate() sage: from sage.geometry.triangulation.point_configuration import Triangulation sage: t2 = Triangulation([[2,1,0]], pc) sage: t1 is t2 False sage: t1 == t2 # indirect doctest True sage: t1 != Triangulation(((0,1),(1,2)), pc, check=False) True """
def __iter__(self): """ Iterate through the simplices of the triangulation.
EXAMPLES::
sage: PointConfiguration.set_engine('internal') # to make doctests independent of TOPCOM sage: pc = PointConfiguration([[0,0],[0,1],[1,0],[1,1],[-1,-1]]) sage: triangulation = pc.triangulate() sage: iter = triangulation.__iter__() sage: next(iter) (1, 3, 4) sage: next(iter) (2, 3, 4) sage: next(iter) Traceback (most recent call last): ... StopIteration """
def __getitem__(self, i): """ Access the point indices of the i-th simplex of the triangulation.
INPUT:
- ``i`` -- integer. The index of a simplex.
OUTPUT:
A tuple of integers. The vertex indices of the i-th simplex.
EXAMPLES::
sage: PointConfiguration.set_engine('internal') # to make doctests independent of TOPCOM sage: pc = PointConfiguration([[0,0],[0,1],[1,0],[1,1],[-1,-1]]) sage: triangulation = pc.triangulate() sage: triangulation[1] (2, 3, 4) """
def __len__(self): """ Returns the length of the triangulation.
TESTS::
sage: PointConfiguration.set_engine('internal') # to make doctests independent of TOPCOM sage: pc = PointConfiguration([[0,0],[0,1],[1,0],[1,1],[-1,-1]]) sage: triangulation = next(pc.triangulations()) sage: triangulation.__len__() 2 sage: len(triangulation) # equivalent 2 """
def _repr_(self): r""" Return a string representation.
TESTS::
sage: PointConfiguration.set_engine('internal') # to make doctests independent of TOPCOM sage: pc = PointConfiguration([[0,0],[0,1],[1,0],[1,1],[-1,-1],[2,2]]) sage: t = pc.triangulations() sage: next(t)._repr_() '(<1,4,5>, <2,4,5>)' """ #s = 'A triangulation' #s += ' in QQ^'+str(self.point_configuration().ambient_dim()) #s += ' consisting of '+str(len(self))+' simplices.'
def plot(self, **kwds): r""" Produce a graphical representation of the triangulation.
EXAMPLES::
sage: p = PointConfiguration([[0,0],[0,1],[1,0],[1,1],[-1,-1]]) sage: triangulation = p.triangulate() sage: triangulation (<1,3,4>, <2,3,4>) sage: triangulation.plot(axes=False) Graphics object consisting of 12 graphics primitives """
raise NotImplementedError('Plotting '+str(dim)+'-dimensional triangulations not implemented!')
def gkz_phi(self): r""" Calculate the GKZ phi vector of the triangulation.
The phi vector is a vector of length equals to the number of points in the point configuration. For a fixed triangulation `T`, the entry corresponding to the `i`-th point `p_i` is
.. MATH::
\phi_T(p_i) = \sum_{t\in T, t\owns p_i} Vol(t)
that is, the total volume of all simplices containing `p_i`. See also [GKZ1994]_ page 220 equation 1.4.
OUTPUT:
The phi vector of self.
EXAMPLES::
sage: p = PointConfiguration([[0,0],[1,0],[2,1],[1,2],[0,1]]) sage: p.triangulate().gkz_phi() (3, 1, 5, 2, 4) sage: p.lexicographic_triangulation().gkz_phi() (1, 3, 4, 2, 5) """
def enumerate_simplices(self): r""" Return the enumerated simplices.
OUTPUT:
A tuple of integers that uniquely specifies the triangulation.
EXAMPLES::
sage: pc = PointConfiguration(matrix([ ....: [ 0, 0, 0, 0, 0, 2, 4,-1, 1, 1, 0, 0, 1, 0], ....: [ 0, 0, 0, 1, 0, 0,-1, 0, 0, 0, 0, 0, 0, 0], ....: [ 0, 2, 0, 0, 0, 0,-1, 0, 1, 0, 1, 0, 0, 1], ....: [ 0, 1, 1, 0, 0, 1, 0,-2, 1, 0, 0,-1, 1, 1], ....: [ 0, 0, 0, 0, 1, 0,-1, 0, 0, 0, 0, 0, 0, 0] ....: ]).columns()) sage: triangulation = pc.lexicographic_triangulation() sage: triangulation.enumerate_simplices() (1678, 1688, 1769, 1779, 1895, 1905, 2112, 2143, 2234, 2360, 2555, 2580, 2610, 2626, 2650, 2652, 2654, 2661, 2663, 2667, 2685, 2755, 2757, 2759, 2766, 2768, 2772, 2811, 2881, 2883, 2885, 2892, 2894, 2898)
You can recreate the triangulation from this list by passing it to the constructor::
sage: from sage.geometry.triangulation.point_configuration import Triangulation sage: Triangulation([1678, 1688, 1769, 1779, 1895, 1905, 2112, 2143, ....: 2234, 2360, 2555, 2580, 2610, 2626, 2650, 2652, 2654, 2661, 2663, ....: 2667, 2685, 2755, 2757, 2759, 2766, 2768, 2772, 2811, 2881, 2883, ....: 2885, 2892, 2894, 2898], pc) (<1,3,4,7,10,13>, <1,3,4,8,10,13>, <1,3,6,7,10,13>, <1,3,6,8,10,13>, <1,4,6,7,10,13>, <1,4,6,8,10,13>, <2,3,4,6,7,12>, <2,3,4,7,12,13>, <2,3,6,7,12,13>, <2,4,6,7,12,13>, <3,4,5,6,9,12>, <3,4,5,8,9,12>, <3,4,6,7,11,12>, <3,4,6,9,11,12>, <3,4,7,10,11,13>, <3,4,7,11,12,13>, <3,4,8,9,10,12>, <3,4,8,10,12,13>, <3,4,9,10,11,12>, <3,4,10,11,12,13>, <3,5,6,8,9,12>, <3,6,7,10,11,13>, <3,6,7,11,12,13>, <3,6,8,9,10,12>, <3,6,8,10,12,13>, <3,6,9,10,11,12>, <3,6,10,11,12,13>, <4,5,6,8,9,12>, <4,6,7,10,11,13>, <4,6,7,11,12,13>, <4,6,8,9,10,12>, <4,6,8,10,12,13>, <4,6,9,10,11,12>, <4,6,10,11,12,13>) """
def fan(self, origin=None): r""" Construct the fan of cones over the simplices of the triangulation.
INPUT:
- ``origin`` -- ``None`` (default) or coordinates of a point. The common apex of all cones of the fan. If ``None``, the triangulation must be a star triangulation and the distinguished central point is used as the origin.
OUTPUT:
A :class:`~sage.geometry.fan.RationalPolyhedralFan`. The coordinates of the points are shifted so that the apex of the fan is the origin of the coordinate system.
.. note:: If the set of cones over the simplices is not a fan, a suitable exception is raised.
EXAMPLES::
sage: pc = PointConfiguration([(0,0), (1,0), (0,1), (-1,-1)], star=0, fine=True) sage: triangulation = pc.triangulate() sage: fan = triangulation.fan(); fan Rational polyhedral fan in 2-d lattice N sage: fan.is_equivalent( toric_varieties.P2().fan() ) True
Toric diagrams (the `\ZZ_5` hyperconifold)::
sage: vertices=[(0, 1, 0), (0, 3, 1), (0, 2, 3), (0, 0, 2)] sage: interior=[(0, 1, 1), (0, 1, 2), (0, 2, 1), (0, 2, 2)] sage: points = vertices+interior sage: pc = PointConfiguration(points, fine=True) sage: triangulation = pc.triangulate() sage: fan = triangulation.fan( (-1,0,0) ) sage: fan Rational polyhedral fan in 3-d lattice N sage: fan.rays() N(1, 1, 0), N(1, 3, 1), N(1, 2, 3), N(1, 0, 2), N(1, 1, 1), N(1, 1, 2), N(1, 2, 1), N(1, 2, 2) in 3-d lattice N """
@cached_method def simplicial_complex(self): r""" Return a simplicial complex from a triangulation of the point configuration.
OUTPUT:
A :class:`~sage.homology.simplicial_complex.SimplicialComplex`.
EXAMPLES::
sage: p = polytopes.cuboctahedron() sage: sc = p.triangulate(engine='internal').simplicial_complex() sage: sc Simplicial complex with 12 vertices and 16 facets
Any convex set is contractable, so its reduced homology groups vanish::
sage: sc.homology() {0: 0, 1: 0, 2: 0, 3: 0} """
@cached_method def _boundary_simplex_dictionary(self): """ Return facets and the simplices they bound
TESTS::
sage: triangulation = polytopes.hypercube(2).triangulate(engine='internal') sage: triangulation._boundary_simplex_dictionary() {(0, 1): ((0, 1, 3),), (0, 2): ((0, 2, 3),), (0, 3): ((0, 1, 3), (0, 2, 3)), (1, 3): ((0, 1, 3),), (2, 3): ((0, 2, 3),)}
sage: triangulation = polytopes.cube().triangulate(engine='internal') sage: triangulation._boundary_simplex_dictionary() {(0, 1, 2): ((0, 1, 2, 7),), (0, 1, 4): ((0, 1, 4, 7),), (0, 1, 7): ((0, 1, 2, 7), (0, 1, 4, 7)), (0, 2, 4): ((0, 2, 4, 7),), (0, 2, 7): ((0, 1, 2, 7), (0, 2, 4, 7)), (0, 4, 7): ((0, 1, 4, 7), (0, 2, 4, 7)), (1, 2, 3): ((1, 2, 3, 7),), (1, 2, 7): ((0, 1, 2, 7), (1, 2, 3, 7)), (1, 3, 7): ((1, 2, 3, 7),), (1, 4, 5): ((1, 4, 5, 7),), (1, 4, 7): ((0, 1, 4, 7), (1, 4, 5, 7)), (1, 5, 7): ((1, 4, 5, 7),), (2, 3, 7): ((1, 2, 3, 7),), (2, 4, 6): ((2, 4, 6, 7),), (2, 4, 7): ((0, 2, 4, 7), (2, 4, 6, 7)), (2, 6, 7): ((2, 4, 6, 7),), (4, 5, 7): ((1, 4, 5, 7),), (4, 6, 7): ((2, 4, 6, 7),)} """
@cached_method def boundary(self): """ Return the boundary of the triangulation.
OUTPUT:
The outward-facing boundary simplices (of dimension `d-1`) of the `d`-dimensional triangulation as a set. Each boundary is returned by a tuple of point indices.
EXAMPLES::
sage: triangulation = polytopes.cube().triangulate(engine='internal') sage: triangulation (<0,1,2,7>, <0,1,4,7>, <0,2,4,7>, <1,2,3,7>, <1,4,5,7>, <2,4,6,7>) sage: triangulation.boundary() frozenset({(0, 1, 2), (0, 1, 4), (0, 2, 4), (1, 2, 3), (1, 3, 7), (1, 4, 5), (1, 5, 7), (2, 3, 7), (2, 4, 6), (2, 6, 7), (4, 5, 7), (4, 6, 7)}) sage: triangulation.interior_facets() frozenset({(0, 1, 7), (0, 2, 7), (0, 4, 7), (1, 2, 7), (1, 4, 7), (2, 4, 7)}) """ in iteritems(self._boundary_simplex_dictionary()) if len(bounded_simplices) == 1)
@cached_method def interior_facets(self): """ Return the interior facets of the triangulation.
OUTPUT:
The inward-facing boundary simplices (of dimension `d-1`) of the `d`-dimensional triangulation as a set. Each boundary is returned by a tuple of point indices.
EXAMPLES::
sage: triangulation = polytopes.cube().triangulate(engine='internal') sage: triangulation (<0,1,2,7>, <0,1,4,7>, <0,2,4,7>, <1,2,3,7>, <1,4,5,7>, <2,4,6,7>) sage: triangulation.boundary() frozenset({(0, 1, 2), (0, 1, 4), (0, 2, 4), (1, 2, 3), (1, 3, 7), (1, 4, 5), (1, 5, 7), (2, 3, 7), (2, 4, 6), (2, 6, 7), (4, 5, 7), (4, 6, 7)}) sage: triangulation.interior_facets() frozenset({(0, 1, 7), (0, 2, 7), (0, 4, 7), (1, 2, 7), (1, 4, 7), (2, 4, 7)}) """ in iteritems(self._boundary_simplex_dictionary()) if len(bounded_simplices) == 2)
@cached_method def normal_cone(self): r""" Return the (closure of the) normal cone of the triangulation.
Recall that a regular triangulation is one that equals the "crease lines" of a convex piecewise-linear function. This support function is not unique, for example, you can scale it by a positive constant. The set of all piecewise-linear functions with fixed creases forms an open cone. This cone can be interpreted as the cone of normal vectors at a point of the secondary polytope, which is why we call it normal cone. See [GKZ1994]_ Section 7.1 for details.
OUTPUT:
The closure of the normal cone. The `i`-th entry equals the value of the piecewise-linear function at the `i`-th point of the configuration.
For an irregular triangulation, the normal cone is empty. In this case, a single point (the origin) is returned.
EXAMPLES::
sage: triangulation = polytopes.hypercube(2).triangulate(engine='internal') sage: triangulation (<0,1,3>, <0,2,3>) sage: N = triangulation.normal_cone(); N 4-d cone in 4-d lattice sage: N.rays() (-1, 0, 0, 0), ( 1, 0, 1, 0), (-1, 0, -1, 0), ( 1, 0, 0, -1), (-1, 0, 0, 1), ( 1, 1, 0, 0), (-1, -1, 0, 0) in Ambient free module of rank 4 over the principal ideal domain Integer Ring sage: N.dual().rays() (-1, 1, 1, -1) in Ambient free module of rank 4 over the principal ideal domain Integer Ring
TESTS::
sage: polytopes.simplex(2).triangulate().normal_cone() 3-d cone in 3-d lattice sage: _.dual().is_trivial() True """ raise NotImplementedError('Only base rings ZZ and QQ are supported') else:
def adjacency_graph(self): """ Returns a graph showing which simplices are adjacent in the triangulation
OUTPUT:
A graph consisting of vertices referring to the simplices in the triangulation, and edges showing which simplices are adjacent to each other.
.. SEEALSO::
* To obtain the triangulation's 1-skeleton, use :meth:`SimplicialComplex.graph` through ``MyTriangulation.simplicial_complex().graph()``.
AUTHORS:
* Stephen Farley (2013-08-10): initial version
EXAMPLES::
sage: p = PointConfiguration([[1,0,0], [0,1,0], [0,0,1], [-1,0,1], ....: [1,0,-1], [-1,0,0], [0,-1,0], [0,0,-1]]) sage: t = p.triangulate() sage: t.adjacency_graph() Graph on 8 vertices
""" lambda x,y: len(x-y)==1])
|