# [Tutor] OO triangulation

János Juhász janos.juhasz at VELUX.com
Wed Sep 19 11:10:34 CEST 2007

```Dear Tutors,

years ago.
The sample is working finally.
First time I made the triangulation with recursion, but I reached the
recursion limit very shortly.
So I changed the recursion to a queue.

################
class Triangulation:
def __init__(self, points=None):
self.UpdateList = []
if points:
self.points = points
else:
self.NewPointSet()

def Triangulate(self):
self.triangles = []
if self.points:
self.SortPoints()
self.RemoveDuplicates()
self.MakeSnake()
self.Simplify()

def SortPoints(self):
self.points.sort(lambda p1,p2: cmp(p1[0], p2[0]) or cmp(p1[1],
p2[1]))

def RemoveDuplicates(self):
newpoints = []
prevpoint = None
for p in self.points:
if p != prevpoint:
newpoints.append(p)
prevpoint = p
self.points = newpoints

def MakeSnake(self):
for i in xrange(len(self.points)-1):
a = self.points[i];            b = self.points[i+1]
t1 = Triangle([None, b, a]);   t2 = Triangle([None, a, b])
self.triangles.append(t1);     self.triangles.append(t2)
t1.neighbours[0] = t2;         t2.neighbours[0] = t1
for i in xrange(len(self.points)-2):
t1 = self.triangles[i*2];      t2 = self.triangles[i*2 + 1]
t3 = self.triangles[i*2 + 2];  t4 = self.triangles[i*2 + 3]
t1.neighbours[2] = t3;         t3.neighbours[1] = t1
t2.neighbours[1] = t4;         t4.neighbours[2] = t2

t1 = self.triangles[0];        t2 = self.triangles[1]
t1.neighbours[1] = t2;         t2.neighbours[2] = t1

t1 = self.triangles[-2];       t2 = self.triangles[-1]
t1.neighbours[2] = t2;         t2.neighbours[1] = t1

def Simplify(self):
self.UpdateList = self.triangles[:]
while self.UpdateList:
NextToCheck = self.UpdateList.pop()
NextToCheck.Update(self.UpdateList)

def NewPointSet(self, pointnum=100):
self.points = ([[random.randint(1,420), random.randint(1,380)] for
x in xrange(pointnum)])
##          0
##         TOP
##        /   \
##       /     \
##    2 /       \ 1
##     /         \
##    /           \
##1 LEFT---------RIGHT 2
##          0
class Triangle:
def __init__(self, points=[None, None, None]):
self.points = points
self.neighbours = [None, None, None]

def CCW(self, a, b, c): ## return 2 * Triangle Area
try:
return (b[0] - a[0])*(c[1] - a[1]) - (b[1] - a[1])*(c[0] -
a[0])
except:
return 0

def InCircle(self, a, b, c, p):
x21 = b[0] - a[0]; y21 = b[1] - a[1]; x23 = b[0] - c[0]; y23 =
b[1] - c[1]
x41 = p[0] - a[0]; y41 = p[1] - a[1]; x43 = p[0] - c[0]; y43 =
p[1] - c[1]
return (y41*x23+x41*y23) * (x43*x21-y43*y21) > (y43*x21+x43*y21) *
(x41*x23-y41*y23);

def Update(self, UpdateList):
for p in self.points:
if self.HaveToSwap(p):
self.Swap(p)
UpdateList += self.neighbours
UpdateList += self.BottomTriangle(p).neighbours

def HaveToSwap(self, p1):
if p1 in self.points:
if self.NextPoint(p1) == None:
p2 = self.PrevPoint(p1)
tOpp = self.BottomTriangle(p1)
p3 = tOpp.PrevPoint(p2)
return (self.CCW(p2,p1,p3) > 0)
if self.PrevPoint(p1) == None:
p2 = self.NextPoint(p1)
tOpp = self.BottomTriangle(p1)
p3 = tOpp.NextPoint(p2)
return (self.CCW(p3,p1,p2) > 0)
C = p1
A = self.PrevPoint(C)
D = self.NextPoint(C)
t2 = self.BottomTriangle(C)
p = t2.NextPoint(D)
if None in (A, C, D, p):
return 0
return self.InCircle(A, C, D, p)
return 0

def Swap(self, C):                          ##           Ta2  Ta2
""" Swap a triangle pair """            ##         /    \       /
\
D  = self.NextPoint(C)                  ##       /  a2   \     /
a2  \
A  = self.PrevPoint(C)                  ##      A---------B
A---------B
t2 = self.BottomTriangle(C)             ##    / | \       | \  / |
/ | \
B  = t2.NextPoint(D)                    ##    a1|   \ t2  | a1
|self /   |
a1 = self.BottomTriangle(D)             ##      |self \   | d2  |
/ t2  | d2
d1 = self.BottomTriangle(A)             ##    \ |       \ | /  \ |
/       | /
a2 = t2.BottomTriangle(D)               ##      C---------D
C---------D
d2 = t2.BottomTriangle(A)               ##       \   d1  /     \
d1  /
Ta2 = a2.NextPoint(B)                   ##        \     /      \
/
Td1 = d1.NextPoint(C)                   ##          Td1        Td1

self.points = [A, C, B];        t2.points = [D, B, C]
self.neighbours = [t2, a2, a1]; t2.neighbours = [self, d1, d2]

d1.SetTriangle(Td1 ,t2);        a2.SetTriangle(Ta2, self)

def NextPoint(self, p):
return self.points[(self.points.index(p)+1)%3]

def PrevPoint(self, p):
return self.points[(self.points.index(p)+2)%3]

def BottomTriangle(self, p):
return self.neighbours[self.points.index(p)]

def SetTriangle(self, p, tri):
self.neighbours[self.points.index(p)] = tri

import wx

class DrawingFrame(wx.Frame):
def __init__(self, parent, id, title, fileName=None):
wx.Frame.__init__(self, parent, id, title, style =
wx.DEFAULT_FRAME_STYLE | wx.WANTS_CHARS | wx.NO_FULL_REPAINT_ON_RESIZE)
self.Bind(wx.EVT_PAINT, self.onPaintEvent)
self.SetSizeHints(minW=250, minH=200)
self.SetSize(wx.Size(450, 450))
self.SetBackgroundColour(wx.WHITE)
self.CreateStatusBar()

retri = menu.Append(-1, "100 new points", "100 new points")
retri = menu.Append(-1, "1000 new points", "1000 new points")
retri = menu.Append(-1, "10000 new points", "10000 new points")
self.Show()

def Retriangulate100(self, evt):
triang.NewPointSet(100)
start = time.clock()
triang.Triangulate()
stop = time.clock()
self.Refresh()
st = 'Triangulating 100 points takes %.2f seconds' % (stop-start)
self.SetStatusText(st)

def Retriangulate1000(self, evt):
triang.NewPointSet(1000)
start = time.clock()
triang.Triangulate()
stop = time.clock()
self.Refresh()
st = 'Triangulating 1000 points takes %.2f seconds' % (stop-start)
self.SetStatusText(st)

def Retriangulate10000(self, evt):
triang.NewPointSet(10000)
start = time.clock()
triang.Triangulate()
stop = time.clock()
self.Refresh()
st = 'Triangulating 10000 points takes %.2f seconds' %
(stop-start)
self.SetStatusText(st)

def onPaintEvent(self, event):
dc = wx.PaintDC(self)
dc.BeginDrawing()
for tri in triang.triangles:
if None in tri.points: continue
dc.DrawPolygon(tri.points)
cx, cy = (0,0)
for p in tri.points:
cx += p[0]/3
cy += p[1]/3
r = ((p[0]-cx)**2 + (p[1]-cy)**2)**0.5
#dc.DrawCircle(cx, cy, 2)

dc.EndDrawing()

class App(wx.App):
def OnInit(self):
frame = DrawingFrame(None, -1, "Triangulation")
self.SetTopWindow(frame)
frame.Show()
return 1

if __name__ == '__main__':
import random
import time
triang = Triangulation()
triang.NewPointSet(1000)
triang.Triangulate()

app = App(0)
app.MainLoop()
##############

Yours sincerely,
______________________________
János Juhász

```