I've just finished coding triangulation / convex poly reduction functions for use with pymunk (triangulate.py), and thought it might be of general interest to people here. I hope someone will find a use for it. Please not that optimal speed was never a consideration, nor was an optimal triangulation/convexisation. I'm not really a geometry or optimisation nut, so I didn't set my sights too high.
If that doesn't make any sense, here's what the two functions do:
triangulate - takes a list of points that form any polygon that doesn't self intersect, and breaks it down into a list of triangles.
convexise - takes a list of triangles (such as from the previous function) and does a cheap-and-nasty non-optimal reduction into convex polys.
Also included is the little program (triangulate_test.py) I threw together for testing. Useful for a quick visualisation of what it does.
Regards,
Rawlyn.
triangulate.py:
Code: Select all
from pymunk.vec2d import Vec2d
from pymunk.util import is_clockwise, calc_area, is_convex
### "hidden" functions
def _is_corner(a,b,c):
# returns if point b is an outer corner
return not(is_clockwise([a,b,c]))
def _point_in_triangle(p,a,b,c):
# measure area of whole triangle
whole = abs(calc_area([a,b,c]))
# measure areas of inner triangles formed by p
parta = abs(calc_area([a,b,p]))
partb = abs(calc_area([b,c,p]))
partc = abs(calc_area([c,a,p]))
# allow for potential rounding error in area calcs
# (not that i've encountered one yet, but just in case...)
thresh = 0.0000001
# return if the sum of the inner areas = the whole area
return ((parta+partb+partc) < (whole+thresh))
def _get_ear(poly):
count = len(poly)
# not even a poly
if count < 3:
return [], []
# only a triangle anyway
if count == 3:
return poly, []
# start checking points
for i in range(count):
ia = (i-1) % count
ib = i
ic = (i+1) % count
a = poly[ia]
b = poly[ib]
c = poly[ic]
# is point b an outer corner?
if _is_corner(a,b,c):
# are there any other points inside triangle abc?
valid = True
for j in range(count):
if not(j in (ia,ib,ic)):
p = poly[j]
if _point_in_triangle(p,a,b,c):
valid = False
# if no such point found, abc must be an "ear"
if valid:
remaining = []
for j in range(count):
if j != ib:
remaining.append(poly[j])
# return the ear, and what's left of the polygon after the ear is clipped
return [a,b,c], remaining
# no ear was found, so something is wrong with the given poly (not anticlockwise? self-intersects?)
return [], []
def _attempt_reduction(hulla, hullb):
inter = [vec for vec in hulla if vec in hullb]
if len(inter) == 2:
starta = hulla.index(inter[1])
tempa = hulla[starta:]+hulla[:starta]
tempa = tempa[1:]
startb = hullb.index(inter[0])
tempb = hullb[startb:]+hullb[:startb]
tempb = tempb[1:]
reduced = tempa+tempb
if is_convex(reduced):
return reduced
# reduction failed, return None
return None
def _reduce_hulls(hulls):
count = len(hulls)
# 1 or less hulls passed
if count < 2:
return hulls, False
# check all hulls in the list against each other
for ia in range(count-1):
for ib in range(ia+1, count):
# see if hulls can be reduced to one
reduction = _attempt_reduction(hulls[ia], hulls[ib])
if reduction != None:
# they can so return a new list of hulls and a True
newhulls = [reduction]
for j in range(count):
if not(j in (ia,ib)):
newhulls.append(hulls[j])
return newhulls, True
# nothing was reduced, send the original hull list back with a False
return hulls, False
### major functions
def triangulate(poly):
"""
triangulates poly and returns a list of triangles
poly: list of points that form an anticlockwise polygon (self-intersecting polygons won't work, results are... undefined)
"""
triangles = []
remaining = poly[:]
# while the poly still needs clipping
while len(remaining) > 2:
# rotate the list:
# this stops the starting point from getting stale which sometimes a "fan" of polys, which often leads to poor convexisation
remaining = remaining[1:]+remaining[:1]
# clip the ear, store it
ear, remaining = _get_ear(remaining)
if ear != []:
triangles.append(ear)
# return stored triangles
return triangles
def convexise(triangles):
"""
reduces a list of triangles (such as returned by triangulate()) to a non-optimum list of convex polygons
triangles: list of anticlockwise triangles (a list of three points) to reduce
"""
# fun fact: convexise probably isn't a real word
hulls = triangles[:]
reduced = True
# keep trying to reduce until it won't reduce any more
while reduced:
hulls, reduced = _reduce_hulls(hulls)
# return reduced hull list
return hulls
Code: Select all
import pygame
from pygame.locals import *
from triangulate import *
"""
quick demo of using triangulate.py to triangulate/convexise(?) a concave polygon
not good code as such, but functional and cheap
display:
thick red line: drawn polygon
medium blue lines: triangles after triangulation
thin white lines: convex polygons after convexisation(?)
input:
click points (in clockwise order)* to draw a polygon
press space to reset
* triangulate() and convexise() actually work on anticlockwise polys to match pymunk,
but this demo's coords are upside-down compared to pymunk (pygame style),
so click clockwise to compensate :)
"""
# init pygame
pygame.init()
screen = pygame.display.set_mode((640, 480))
pygame.display.set_caption('triangulate test')
class PolyPoints(object):
def __init__(self, points):
self.poly = [Vec2d(point) for point in points]
self.triangles = triangulate(self.poly)
self.convexes = convexise(self.triangles)
# init clicked points
clicked_points = []
poly = PolyPoints(clicked_points)
quit = False
while not(quit):
# handle imput
for event in pygame.event.get():
if event.type == QUIT:
quit = True
if event.type == MOUSEBUTTONDOWN:
clicked_points += [event.pos]
poly = PolyPoints(clicked_points)
if event.type == KEYDOWN:
if event.key == K_SPACE:
clicked_points = []
poly = PolyPoints(clicked_points)
# clear screen
screen.fill((0,0,0))
# draw poly
if len(clicked_points) == 1:
pygame.draw.circle(screen, (150,0,0), clicked_points[0], 10, 0)
if len(clicked_points) > 1:
pygame.draw.lines(screen, (150,0,0), True, clicked_points, 20)
# draw triangles
if len(poly.triangles) > 0:
for triangle in poly.triangles:
pygame.draw.lines(screen, (0,0,200), True, triangle, 12)
# draw hulls
if len(poly.convexes) > 0:
for convex in poly.convexes:
pygame.draw.lines(screen, (255,255,255), True, convex, 2)
# update screen
pygame.display.update()
