Drawing square triangulations

,

The story so far:

  1. I introduced the tabular method by showing how to count the triangulations of a convex polygon;
  2. I used the tabular method to count the number of ways to triangulate an oriented \(n×n\) square using only lines joining the \(4n\) integer points around the edge of the square and so solve Project Euler problem 270;
  3. I used the svgwrite Python package to draw the triangulations of a convex polygon using Scalable Vector Graphics; and
  4. I read Appendix J of the SVG specification and used the advice therein to shrink the size of the generated SVG.

So now I’ve got all the pieces in place for the last step: drawing the triangulations of an oriented \(n×n\) square. As in the case of ordinary convex polygons, the product of the number of triangulations in each component becomes the Cartesian product of the triangulations themselves, and this can be generated using Python’s itertools.product. The original triangulation algorithm had ten cases, but here that would become very repetitive. Luckily there’s some commonality, so I can use a helper function (the function maybe) to reduce that to four cases:

from itertools import product

def maybe(side):
    """If side is valid (that is, it has at least two elements), return a
    tuple with side as the only element. Otherwise, return the empty
    tuple.

    """
    if len(side) >= 2: return side,
    else: return ()

def triangulations(p):
    """Generate the triangulations of the convex polygon whose sides are
    given by the sequence p. Each element of p must by a sequence
    whose elements are the vertices along that side of the polygon.

    """
    assert(len(p) >= 3)

    # Base case: exactly one way to triangulate a triangle.
    if len(p) == 3 and all(len(side) == 2 for side in p):
        yield [tuple(side[0] for side in p)]
        return

    # The first, second and last sides of the polygon. 
    a, b, z = p[0], p[1], p[-1]

    # Case A: distinguished edge removed as part of an ear.
    if len(a) > 2 or len(z) > 2 or len(p) > 3:
        u = ((z[-2], a[1]),) + maybe(a[1:]) + p[1:-1] + maybe(z[:-1])
        for t in triangulations(u):
            yield [(a[0], a[1], z[-2])] + t
    if len(a) == 2 and (len(b) > 2 or len(p) > 3):
        for t in triangulations(((a[0], b[1]),) + maybe(b[1:]) + p[2:]):
            yield [(a[0], a[1], b[1])] + t

    # Case B: distinguished edge removed as part of triangle whose
    # third vertex is the j'th interior vertex on side i.
    for i in range(1, len(p) - 1):
        for j in range(1, len(p[i]) - 1):
            if len(a) > 2 or i > 1:
                u = ((a[0], p[i][j]),) + (p[i][j:],) + p[i+1:]
                v = ((p[i][j], a[1]),) + maybe(a[1:]) + p[1:i] + (p[i][:j+1],)
                for s, t in product(triangulations(u), triangulations(v)):
                    yield s + [(a[0], a[1], p[i][j])] + t

    # Case C: distinguished edge removed as part of triangle whose
    # third vertex is the corner between sides i and i + 1.
    for i in range(1, len(p) - 2):
        if len(a) > 2 or i > 1:
            u = ((a[0], p[i][-1]),) + p[i+1:]
            v = ((p[i][-1], a[1]),) + maybe(a[1:]) + p[1:i+1]
            for s, t in product(triangulations(u), triangulations(v)):
                yield s + [(a[0], a[1], p[i][-1])] + t

The drawing code is a straightforward (if a bit long-winded) transformation of the code I wrote for the convex polygon case, with the optional addition of circles to mark the integer points along the sides. I’ve used the SVG <symbol> element to define a re-usable symbol for the \(4n\) circles on one of the squares. This symbol is then referenced by multiple <use> elements, each with different x and y attributes.

from itertools import cycle
from svgwrite import Drawing
from geometry import Vector

def draw_triangulations(n, filename, size, columns, edge_style,
                        triangle_styles=(), circle_style=None):
    """Draw the triangulations of an oriented nxn square using only lines
    joining the 4n integer points around the edge of the square.

    Save the resulting image into filename as SVG. The other arguments
    specify the size in pixels of each square, the number of columns
    in the drawing, and the styles for drawing the edges, the circles
    marking the 4n integer points, and the triangles.

    """
    fill_styles = cycle(triangle_styles)
    square = (tuple((0, i)     for i in range(n + 1)),
              tuple((i, n)     for i in range(n + 1)),
              tuple((n, n - i) for i in range(n + 1)),
              tuple((n - i, 0) for i in range(n + 1)))
    tt = list(triangulations(square))
    rows = (len(tt) + columns - 1) // columns
    spacing = 1.2
    margin = Vector(1, 1) * (spacing - 1)
    drawing_size = ((Vector(columns, rows) * spacing + margin) * size).map(round)
    drawing = Drawing(debug=False, filename=filename, size=drawing_size)
    triangle_paths = [drawing.path(**s) for s in triangle_styles]
    for p in triangle_paths:
        drawing.add(p)
    triangle_paths = cycle(triangle_paths)
    edge_group = drawing.g(**edge_style)
    drawing.add(edge_group)
    if circle_style:
        circle_symbol = drawing.symbol(id="c")
        drawing.add(circle_symbol)
        circle_group = drawing.g(**circle_style)
        drawing.add(circle_group)
        for v in (Vector(v) for side in square for v in side[1:]):
            circle = drawing.circle(((v + margin) * size / n).map(round),
                                    round(size / (n * 8)))
            circle_symbol.add(circle)
    for i, triangulation in enumerate(tt):
        origin = (Vector(i % columns, i // columns) * spacing + margin) * n
        edges = set()
        for triangle in triangulation:
            a, b, c = (((v + origin) * size / n).map(round) for v in triangle)
            if triangle_styles:
                path = next(triangle_paths)
                path.push(['M'] + list(a) + ['l'] + list(b - a)
                          + ['l'] + list(c - b) + ['z'])
            for edge in ((a, b), (b, c), (c, a)):
                edges.add(Vector(sorted(edge)))
        path = drawing.path()
        edge_group.add(path)
        last = None
        for start, end in edges:
            if last is None:
                path.push(['M'] + list(start))
            else:
                path.push(['m'] + list(start - last))
            path.push(['l'] + list(end - start))
            last = end
        if circle_style:
            origin = ((origin - margin) * size / n).map(round)
            circle_group.add(drawing.use("#c", x=origin[0], y=origin[1]))
    drawing.save()

Here are the 30 ways to triangulate the \(2×2\) square. (Compare them with the corresponding diagram on the Project Euler site.)

>>> colours = '#BBBB88 #CCC68D #EEDD99 #EEC290 #EEAA88'.split()
>>> triangle_styles = [dict(fill=c) for c in colours]
>>> edge_style = dict(stroke='black', stroke_width=2)
>>> circle_style = dict(fill='black')
>>> draw_triangulations(2, 'squares2.svg', 100, 10, edge_style, triangle_styles, circle_style)

And for the pièce de résistance, the 604 ways to triangulate the \(3×3\) square:

>>> draw_triangulations(3, 'squares3.svg', 50, 20, edge_style, triangle_styles)