

In [1]:

    
from collections import defaultdict

Is a triangulated surface orientable?

Each triangle is stored as a tuple of its vertices. Each vertex is labeled with a non negative integer.

A triangulation of a surface is stored as a simple graph. Each triangle in the triangulation is stored in the corresponding node in the graph. Two nodes in the graph are connected when the triangles stored inside them share a common edge.

Remark: a graph is cubic if a triangulated surface is 2D manifold without a boundary.



In [2]:

    
class Triangle:
    """
    A triangle is represented as a list of its
    vertices (labeled with natural numbers).
    """
    def __init__(self, vertices, neighbours=None):
        assert len(vertices) == 3, 'A triangle should have 3 vertices'
        self.vertices = sorted(vertices)
        self.neighbours = neighbours if neighbours is not None else set()
        
    @property
    def edges(self):
        """
        Return the generator of edges 'in the positive direction'.
        """
        v, n = self.vertices, len(self.vertices)
        return ((v[i], v[(i + 1) % n]) for i in range(n))

    def contains_edge(self, edge):
        '''
        Return True if the triangle contains the given edge. 
        '''
        return set(edge) <= set(self.vertices)
    
    def neighbour_edge(self, edge):
        '''
        Return the neighbouring triangle that shared the edge with out triangle.
        If no such neighbouring triangle exists an Exception is raised.
        '''
        neighbour = [n for n in self.neighbours if n.contains_edge(edge)]
        assert len(neighbour) == 1
        return neighbour[0]

Example triangulations: a set of triangles that represents a torus and a projective plane.



In [3]:

    
torus_triangles = [
    (0, 1, 6), (0, 4, 6), (1, 6, 7), (1, 2, 7), (2, 7, 4), (2, 0, 4), (4, 5, 8), (4, 6, 8), (6, 3, 8),
    (6, 7, 3), (3, 7, 5), (7, 4, 5), (0, 1, 5), (1, 5, 8), (1, 2, 8), (2, 8, 3), (2, 0, 3), (0, 5, 3),
]

projective_plane_triangles = [
    (1, 2, 7), (1, 7, 3), (2, 7, 5), (7, 3, 6), (2, 3, 5), (4, 5, 7),
    (7, 4, 6), (2, 6, 3), (4, 5, 3), (4, 6, 2), (1, 3, 4), (4, 1, 2),
]

First we create a graph from the set of triangles. No ordered structure is computed here.



In [4]:

    
def create_triangulation(triangles):
    '''
    Create a triangulation from a set of triangles. 
    '''
    n = max([max(triangle) for triangle in triangles]) + 1
    triangles = [Triangle(triangle) for triangle in triangles]
    # For each vertex compute the set of triangles containing the vertex.    
    vertex_triangles = defaultdict(set)
    for triangle in triangles:
        for vertex in triangle.vertices:
            vertex_triangles[vertex].add(triangle)
    # Make connection between neighbourhood triangles.
    for triangle in triangles:
        for (v1, v2) in triangle.edges:
            neighbour = (vertex_triangles[v1] & vertex_triangles[v2]).difference((triangle,))
            assert len(neighbour) == 1
            triangle.neighbours.add(neighbour.pop())
        # Each triangle should have exactly 3 neighbours (2D manifold without a boundary)
        assert len(triangle.neighbours) == 3
    return triangles

An oriented version of a triangle is represented as a tuple (triangle, orientation). In it we define helper functions enext and fnext.



In [5]:

    
class OrientedTriangle:
    def __init__(self, triangle, orientation):
        self.triangle = triangle
        self.orientation = orientation
            
    @property
    def is_positively_oriented(self):
        return self.orientation in [0, 1, 2]

    @property
    def get_leading_edge(self):
        edge = list(self.triangle.edges)[self.orientation & 3]
        return edge if self.is_positively_oriented else tuple(reversed(edge))

    @property
    def enext(self):
        """
        Get the next orientation of the same type.
        """
        orientation = (((self.orientation & 3) + 1) % 3) + (self.orientation & 4)
        return OrientedTriangle(self.triangle, orientation)
    
    @property
    def fnext(self):
        '''
        Compute return the value of fnext for the oriented triangle.
        '''
        reversed_edge = tuple(reversed(self.get_leading_edge))
        # Get the neighbour that shares the leading edge with our triangle.
        neighbour = self.triangle.neighbour_edge(reversed_edge)
        return OrientedTriangle(neighbour, 0).orient_triangle(reversed_edge)

    def same_orientation(self, triangle):
        return self.is_positively_oriented == triangle.is_positively_oriented

    def orient_triangle(self, edge):
        """
        Orient the triangle so that the given edge is its lead edge. Return self.
        """
        es, re = list(self.triangle.edges), tuple(reversed(edge))        
        self.orientation = es.index(edge) if edge in es else es.index(re) + 4
        return self

Finally: a function which checks whether a given triangulation is orientable.



In [6]:

    
def orientable(triangles):
    '''
    Is a triangulation orientable?
    '''
    return is_orientable(OrientedTriangle(create_triangulation(triangles)[0], 0))

def is_orientable(oriented_triangle):
    triangle = oriented_triangle.triangle
    chosen_orientation = getattr(triangle, 'orientation', None)
    if chosen_orientation is None:
        triangle.orientation = oriented_triangle.orientation
        t1 = oriented_triangle.fnext
        t2 = oriented_triangle.enext.fnext
        t3 = oriented_triangle.enext.enext.fnext
        return is_orientable(t1) and is_orientable(t2) and is_orientable(t3)
    else:
        return oriented_triangle.same_orientation(OrientedTriangle(triangle, chosen_orientation))



In [7]:

    
orientable(torus_triangles)









    Out[7]:





True



In [8]:

    
orientable(projective_plane_triangles)









    Out[8]:





False