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.
- http://www.mema.ucl.ac.be/~wu/Poly2Tri/poly2tri.html
- http://www.cs.umd.edu/class/spring2007/cmsc754/Lects/lect07.pdf
- http://www.cs.unc.edu/~dm/CODE/GEM/chapter.html
- http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/PolyPart/polyPartition.htm
- http://www.cs.ucsb.edu/~suri/cs235/Triangulation.pdf
- http://www.amanith.org/forum/viewtopic.php?pid=43
- http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK4/NODE186.HTM -- as far as I can tell, this means that you can triangulate polygons using the constrained Delaunay triangulation and get a "nice" triangulation out of it.
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)