Delaunay-triangulate a simple polygon using Triangle

triangulate_polygon.py

#!/usr/bin/python3
import triangle
from collections import OrderedDict

def triangulate(multipolygon):
    vertices = OrderedDict()
    indices = [[vertices.setdefault(co, len(vertices)) for co in poly] for poly in multipolygon]
    dt = triangle.triangulate({"vertices": list(vertices), "segments": [s for f in indices for s in pairs(f)]}, "p")
    segments = {s for poly in indices for s in pairs(poly)}
    triangles = {tuple(tri) for tri in dt["triangles"]}
    neighbors = {(b, a): tri for tri in triangles for (a, b) in pairs(tri)}
    boundary = [neighbors[s] for s in segments if s in neighbors]
    while boundary:
        tri = boundary.pop()
        if not tri or tri not in triangles:
            continue
        triangles.remove(tri)
        boundary.extend(neighbors.get((a, b)) for (a, b) in pairs(tri) if (b, a) not in segments)
    return list(vertices), triangles

def pairs(seq):
    it = iter(seq)
    first = prev = next(it)
    for here in it:
        yield prev, here
        prev = here
    yield here, first

def read_obj(filename):
    result, vertices = list(), list()
    for line in open(filename):
        if line[0] == "v":
            v, x, z, y = line.split()
            vertices.append((float(x), -float(y)))
        elif line[0] == "f":
            f, *verts = line.split()
            result.append([vertices[int(i) - 1] for i in verts])
    return result

poly = read_obj("polygons.obj")
vertices, triangles = triangulate(poly)
with open("triangles.obj", "w") as f:
    for v in vertices:
        print("v", v[0], 0, -v[1], file=f)
    for tri in triangles:
        print("f", *(i+1 for i in tri), file=f)