Shrinking SVG

,

In “Scalable vector triangulations” I used the svgwrite package to draw the 429 triangulations of an oriented convex nonagon. But there was something unsatisfactory about the size of the resulting image: 1.2 MiB seems rather large for an image which has 3003 triangles and 6435 lines. A look at the source reveals three sources of wasted space:

  1. The coordinates of the line endpoints and polygon vertices are formatted with an unnecessary 14 digits of precision. For example:

    <line stroke="black" stroke-width="2" 
     x1="58.682408883346525" x2="88.30222215594891"
     y1="99.2403876506104" y2="82.13938048432696" />

    Clearly the coordinates need to be rounded to the nearest integer.

  2. Attributes like stroke="black" stroke-width="2" are repeated for each <line> element, and attributes like fill="#eee" are repeated for each <polygon> element. The very useful “Appendix J: Minimizing SVG File Sizes” in the SVG specification suggests grouping objects into <g> elements to avoid repetition of attributes. That is, instead of:

    <line stroke="black" stroke-width="2" x1="38" x2="81" y1="98" y2="10" />
    <line stroke="black" stroke-width="2" x1="4" x2="81" y1="28" y2="10" />
    <line stroke="black" stroke-width="2" x1="4" x2="4" y1="28" y2="71" />
    <line stroke="black" stroke-width="2" x1="4" x2="38" y1="71" y2="98" />
    ...

    I should output:

    <g stroke="black" stroke-width="2">
      <line x1="38" x2="81" y1="98" y2="10" />
      <line x1="4" x2="81" y1="28" y2="10" />
      <line x1="4" x2="4" y1="28" y2="71" />
      <line x1="4" x2="38" y1="71" y2="98" />
      ...
    </g>
  3. Appendix J also recommends using <path> elements to condense the representation of a series of lines. That is instead of:

    <line x1="38" x2="81" y1="98" y2="10" />
    <line x1="4" x2="81" y1="28" y2="10" />
    <line x1="4" x2="4" y1="28" y2="71" />
    <line x1="4" x2="38" y1="71" y2="98" />
    ...

    I should output a single <path> element with multiple M (move to) and L (draw line to) commands:

    <path d="M 38 98 L 81 10 M 4 28 L 81 10 M 4 28 L 4 71 M 4 71 L 38 98..." />

    (Actually I ended up using the m and l commands, which take relative coordinates.) Similarly, <polygon> elements can be replaced by <path> elements, using the z (close path) command.

With these improvements implemented, the code for doing the drawing now looks like this:1

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

def draw_triangulations(n, filename, radius, columns, edge_style, triangle_styles=()):
    """Draw the triangulations of an oriented n-sided convex polygon and
    save it into filename as SVG. Other arguments specify the radius in
    pixels of each polygon, the number of columns in the drawing, and
    the styles for drawing the edges and the triangles.

    """
    polygon = [Vector(1, 0).rotated(i * 2 * pi / n) for i in range(n)]
    tt = list(triangulations(polygon))
    rows = (len(tt) + columns - 1) // columns
    spacing = 2.1
    margin = Vector(1, 1) * (spacing - 2)
    size = ((Vector(columns, rows) * spacing - margin) * radius).map(round)
    drawing = Drawing(debug=False, filename=filename, size=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)
    for i, triangulation in enumerate(tt):
        origin = Vector(i % columns, i // columns) * spacing + Vector(1, 1)
        edges = set()
        for triangle in triangulation:
            a, b, c = (((v + origin) * radius).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
    drawing.save()

The code for generating the triangulations remains unchanged:

from itertools import product

def triangulations(p):
    """Generate the triangulations of the convex polygon
    whose vertices are given by the sequence p. Each triangulation is
    output as a list of triangles, each triangle being a sequence of
    three vertices.

    >>> list(triangulations(tuple('abcd')))
    [[('a', 'b', 'd'), ('b', 'c', 'd')], [('a', 'b', 'c'), ('a', 'c', 'd')]]
    >>> [sum(1 for _ in triangulations(range(i))) for i in range(3, 8)]
    [1, 2, 5, 14, 42]

    """
    n = len(p)
    if n == 2:
        yield []
    elif n == 3:
        yield [p]
    else:
        for k in range(1, n - 1):
            for u, v in product(triangulations(p[:k + 1]), triangulations(p[k:])):
                yield u + [(p[0], p[k], p[-1])] + v

As does the drawing code:

edge_style = dict(stroke='black', stroke_width=2)
triangle_styles = [dict(fill='#eee')]
draw_triangulations(9, 'nonagon.svg', 50, 33, edge_style, triangle_styles)

The resulting improvement in the SVG file size is dramatic: the nonagon triangulations are now about a sixth of their former size: down from about 1.2 MiB to about 204 KiB.

It ought to be possible to do even better than this, by using the <symbol> element to define re-usable symbols for the repeated parts. (See this post for an example of using <symbol>.)


  1.  This is written in Python 3. In Python 2 the built-in function round() returns a float, so it doesn’t produce quite such small SVG: the rounded co-ordinates come out as 59.0 instead of 59. You could use lambda x:int(round(x)) instead.