Dear Tutors,
I made an OO style triangulation based on an old C progam I made about 10
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.
I am interested about your opinions about the OO style.
It hasn't got too much comments, but probably readable.
################
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()
menu = wx.Menu()
retri = menu.Append(-1, "100 new points", "100 new points")
self.Bind(wx.EVT_MENU, self.Retriangulate100, retri)
retri = menu.Append(-1, "1000 new points", "1000 new points")
self.Bind(wx.EVT_MENU, self.Retriangulate1000, retri)
retri = menu.Append(-1, "10000 new points", "10000 new points")
self.Bind(wx.EVT_MENU, self.Retriangulate10000, retri)
menuBar = wx.MenuBar()
menuBar.Append(menu, "Retriangulate")
self.SetMenuBar(menuBar)
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
_______________________________________________
Tutor maillist - Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor
