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], pts[i]) 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, queue]
idxs = []
print topchain, botchain
lp = queue
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, p))

print monotone(newpts)
``````

Blue Sky design by Jonas John.