Betacantrips/ bits/ triangulate polygons

Let's say you have a polygon and (for some reason) you want to break it into triangles. Brave man! Here are some resources which may be helpful to you.

I'm working on some simple Python code to do this without too much pain nor speed. So far I only have the monotone polygons part working, and it's so not production-quality, but here it is.

import math

def orient_2d(x1, y1, x2, y2, x3, y3):
# Assuming a is at (0, 0)
# 1/2 | xb*yc - xc*yb | 
xb = x2-x1
yc = y3-y1
xc = x3-x1
yb = y2-y1
return xb*yc - xc*yb

class Point(object):
def __init__(self, idx, x, y, chain=None):
    self.idx = idx
    self.x = x
    self.y = y
    self.chain = chain

def __cmp__(self, p2):
    if self.x < p2.x: return -1
    if self.x == p2.x and self.y < p2.y: return -1
    if self.x == p2.x and self.y == p2.y:
    print "duplicate points, oh no!!"
    return 0
    return 1

def chain_cmp(self, p2):
    if self.x < p2.x: return -1
    if self.x > p2.x: return 1
    if self.x == p2.x and self.chain and p2.chain:
    # decide based on chain order (arbitrary)
    if self.chain < p2.chain: return -1
    if self.chain > p2.chain: return 1
    if self.chain == p2.chain:
        # preserve chain order
        if self.idx < p2.idx and self.chain == -1:
        # pts ccw, so smaller idx is "first"
        return -1
        if self.chain == 1 and self.idx > p2.idx:
        # pts cw so bigger idx is "first"
        return -1
        return 1



def __repr__(self):
    return "Point(%d, %d, %d, %s)" % (self.idx, self.x, self.y, self.chain)

def monotone(pts):
mypts = [Point(i, pts[i][0], pts[i][1]) for i in range(len(pts))]
mini = min(mypts).idx # index of min pt
maxi = max(mypts).idx # index of max pt
if mini < maxi: # wrap around the correct way
    topchain = (mypts+mypts)[maxi:(mini+len(mypts))]
    botchain = mypts[mini:maxi]
else:
    topchain = mypts[maxi:mini]
    botchain = (mypts+mypts)[mini:(maxi+len(mypts))]
for p in topchain: p.chain = 1
for p in botchain: p.chain = -1
queue = list(mypts)
queue.sort(Point.chain_cmp)
stack = [queue[0], queue[1]]
idxs = []
print topchain, botchain
lp = queue[1]
for p in queue[2:]:
    if lp.chain != p.chain:
    # Connect everything in reflex chain
    p2 = stack.pop(-1)
    while stack:
        p3 = stack.pop(-1)
        print "diagonal between", p.idx, p2.idx
        # orient triangle ccw
        if p.chain == 1:
        idxs.append((p.idx, p3.idx, p2.idx))
        else:
        idxs.append((p.idx, p2.idx, p3.idx))
        p2 = p3
    stack = [lp, p]
    else:
    # Walk back along the reflex chain, adding diagonals
    # as long as possible
    print "stack is", stack
    while len(stack) > 1:
        p2, p3 = stack[-1], stack[-2]
        angle = orient_2d(p.x, p.y, p2.x, p2.y, p3.x, p3.y)
        # angle is pos for CCW, neg for CW
        # CCW is "visible" on top chain, CW is "visible" on bot chain
        print "angle", angle, "p.chain", p.chain
        if angle * p.chain < 0: break
        print "diagonal2 between", p.idx, p3.idx
        idxs.append((p.idx, p2.idx, p3.idx))
        stack.pop(-1)

    stack.append(p)
    lp = p
return (pts, idxs)

if __name__ == "__main__":
pts = [(0, 0), (-100, 100), (-100, 310), (20, 400), (200, 325),
       (150, 320), (40, 300), (40, 200), (100, 110)]
# oops, sorted them:
##    pts = [(0, 0), (-100, 100), (100, 110), (40, 200), (40, 300), (-100, 310),
##       (150, 320), (200, 325), (20, 400)]
newpts = []
for p in pts: #rotate
    newpts.append((p[1], p[0]))

print monotone(newpts)

Blue Sky design by Jonas John.