Fokin' triangulation.

Triangulate.py

"""
Triangluation simulator.

Left mouse button: place a vertex.
Right mouse button: finalize a shape.
T: triangulate shapes.
"""
import math
from random import randint

import pygame
from pygame.locals import *

def compf(a, b, epsilon=0.00001):
    return (a + epsilon > b and a - epsilon < b)

def orient(p):
    assert len(p) == 3, 'must be a triangle'

    return (p[1][0] - p[0][0]) * (p[2][1] - p[0][1]) - \
           (p[2][0] - p[0][0]) * (p[1][1] - p[0][1]) > 0;

def in_tri(v, tri):
    # Barycentric coordinates.
    denom = ((tri[1][1] - tri[2][1]) * (tri[0][0] - tri[2][0]) + \
             (tri[2][0] - tri[1][0]) * (tri[0][1] - tri[2][1]))
    if compf(denom, 0.0): return False
    denom = 1.0 / denom

    # alpha = ((p2.y - p3.y)*(p.x - p3.x)  + (p3.x - p2.x)*(p.y - p3.y)) /
    #         ((p2.y - p3.y)*(p1.x - p3.x) + (p3.x - p2.x)*(p1.y - p3.y))
    alpha = denom * ((tri[1][1] - tri[2][1]) * (v[0] - tri[2][0]) \
                  +  (tri[2][0] - tri[1][0]) * (v[1] - tri[2][1]))
    if alpha < 0: return False

    # beta = ((p3.y - p1.y)*(p.x - p3.x) + (p1.x - p3.x)*(p.y - p3.y)) /
    #        ((p2.y - p3.y)*(p1.x - p3.x) + (p3.x - p2.x)*(p1.y - p3.y));
    beta = denom  * ((tri[2][1] - tri[0][1]) * (v[0] - tri[2][0]) \
                  +  (tri[0][0] - tri[2][0]) * (v[1] - tri[2][1]))
    if beta < 0: return False

    return (1.0 - alpha - beta) >= 0

def remove_ear(shape, ear):
    l = len(shape)
    return (shape[(ear-1) % l], shape[ear], shape[(ear+1) % l])

pygame.init()

display = pygame.display.set_mode((800, 600))
shapes = []
vertices = []
triangled = []

DaFont = pygame.font.SysFont("monospace", 14)

q = False
while not q:
    for evt in pygame.event.get():
        if evt.type == QUIT: q = True

        elif evt.type == MOUSEBUTTONDOWN:
            # Draw vertices with the left mouse button.
            if evt.button == 1 and evt.pos not in vertices:
                vertices.append(evt.pos)

            # Press any button but the left mouse button to finalize the shape.
            elif len(vertices) >= 3:
                shapes.append(vertices)
                vertices = []

        elif evt.type == KEYDOWN and evt.key == pygame.K_t:
            for s in xrange(len(shapes)):
                shape = shapes[s]

                # Use orientation of the top-left-most vertex.
                left = shape[0]; index = 0
                for x in xrange(len(shape)):
                    v = shape[x]
                    if v[0] < left[0] or (v[0] == left[0] and v[1] < left[1]):
                        left = v
                        index = x

                o = orient(remove_ear(shape, index))

                while len(shape) >= 3:
                    reflex = []
                    eartip = -1
                    tringl = []

                    # For each vertex in the shape
                    for i in xrange(len(shape)):
                        if eartip >= 0: break

                        # Create a triangle from vertex to adjacent vertices.
                        tri = remove_ear(shape, i)

                        prev= tri[0]
                        curr= tri[1]
                        next= tri[2]

                        # If polygon's orientation doesn't match that of the triangle,
                        # it's definitely a reflex and not an ear.
                        if orient(tri) != o:
                            reflex.append(i)
                            continue

                        # Test reflex vertices first.
                        for x in reflex:
                            # If we are testing ourselves, skip.
                            if shape[x] in tri: continue

                            # If any v in triangle, not ear.
                            elif in_tri(shape[x], tri): break

                        else:
                            # No reflexes, so we test all past current vertex.
                            for x in xrange(i+2, len(shape)):
                                if shape[x] in tri: continue
                                elif in_tri(shape[x], tri): break

                            # No vertices in the triangle, we are an ear.
                            else: eartip = i

                    if eartip == -1: break
                    tringl.append(remove_ear(shape, eartip))
                    del shapes[s][eartip]
                    triangled.append(tringl)
                del shapes[s]

    display.fill((255, 255, 255))

    for v in xrange(1, len(vertices)):
        pygame.draw.line(display, (0, 0, 0), vertices[v-1], vertices[v])

    for shape in shapes:
        if len(shape) < 3:
            pygame.draw.line(display, (0, 0, 0), shape[0], shape[1])
        else:
            pygame.draw.polygon(display, (0, 0, 0), shape)
            for x in xrange(len(shape)):
                display.blit(DaFont.render(str(x), 1, (0, 255, 0)), shape[x])

    for shape in triangled:
        for v in shape:
            # set last parameter to 0 to see the polygon filled!
            pygame.draw.polygon(display, (255, 0, 0), v, 1)

    pygame.display.update()