[Tutor] OO triangulation

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


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



More information about the Tutor mailing list