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()

Hi @Shaptic this is so nice, thank you very much! I have been studying your code to try and port to Processing Python mode 😄 :
This is my attempt at separating the triangulation logic:

"""
Triangluation simulator.
Left mouse button: place a vertex.
Right mouse button: finalize a shape.
T: triangulate shapes.
Based on https://gist.github.com/Shaptic/6297978
"""

import pygame
from pygame.locals import *

EPSILON = 0.00001  # Procesing has an Epsilon constant already!

def almost_equal(a, b):
    return abs(a - b) < EPSILON

def ccw(tri):
    assert len(tri) == 3, 'must be a triangle'
    a, b, c = tri
    return (b[0] - a[0]) * (c[1] - a[1]) > (b[1] - a[1]) * (c[0] - a[0])

def in_poly(p, points):
    # ray-casting algorithm based on
    # https://wrf.ecse.rpi.edu/Research/Short_Notes/pnpoly.html
    inside = False
    for i, (xi, yi) in enumerate(points):
        xj, yj = points[i - 1]  
        if ((yi > p[1]) != (yj > p[1])) and (p[0] < (xj - xi) * (p[1] - yi)
                                             / (yj - yi) + xi):
            inside = not inside  # an intersection was found
    return inside

def get_ear(shape, ear):
    return (shape[ear - 1], shape[ear], shape[(ear+1) % len(shape)])

def triangulate(original_shape):
    # Use orientation of the top-left-most vertex.
    shape = original_shape[:]
    left, starting_index = shape[0], 0
    for i, v in enumerate(shape):
        if v[0] < left[0] or (v[0] == left[0] and v[1] < left[1]):
            left = v
            starting_index = i
    orientation = ccw(get_ear(shape, starting_index))
    triangles = []
    while len(shape) >= 3:
        reflex_vertices = []
        eartip = -1
        for i, v in enumerate(shape):  # For each vertex in the shape
            if eartip >= 0:
                break
            triangle = get_ear(shape, i)  # A triangle from vertex to adjacents.
            # If polygon's orientation doesn't match that of the triangle,
            # it's definitely a reflex and not an ear.
            if ccw(triangle) != orientation:
                reflex_vertices.append(v)
                continue  # Test reflex vertices first.
            for rv in reflex_vertices:
                if rv in triangle:
                    continue  # If we are testing ourselves, skip.
                elif in_poly(rv, triangle):
                    break  # If any reflex vertex in triangle, not ear.
            else:  # No reflexes, so we test all past current vertex.
                for past_current_v in shape[i + 2:]:
                    if past_current_v in triangle:
                        continue
                    elif in_poly(past_current_v, triangle):
                        break  # No vertices in the triangle, we are an ear.
                else:
                    eartip = i
        if eartip == -1:
            break
        triangles.append(get_ear(shape, eartip))
        del shape[eartip] 
    return triangles

pygame.init()

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

mono_font = 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, shape in enumerate(shapes):
                triangulated_shapes.append(triangulate(shape))
                del shapes[s]

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

    for v in range(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 range(len(shape)):
                display.blit(mono_font.render(str(x), 1, (0, 255, 0)), shape[x])

    for shape in triangulated_shapes:
        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()