[Tutor] triangulation

[Shi Mu]

the Internet is down for one day and so wonderful to have so many
responses. i have checked all the links you guys mentioned. what i
want is delaunay triangulation and the available ones online are
written in C, Java and FORTRAN. I want to see some in Python because
it is hard for me to figure out using python to do Fortune's sweeping
line algorithm. Is python is not good in doing that kind of
computation or some other reason?
Thanks a lot for all of your responses!!!

On 11/9/05, Gregor Lingl <glingl at aon.at> wrote:
>
>
> Alex Hunsley schrieb:
> > Shi Mu wrote:
> >
> >
> >>is there any sample code of triangulation? many thanks!
> >>
> >>
> >
> > Yes, probably.
> >
>
>
> Indeed, there is.
> See attachment
>
> regards
> Gregor
>
> >
> > _______________________________________________
> > Tutor maillist  -  Tutor at python.org
> > http://mail.python.org/mailman/listinfo/tutor
> >
> >
>
> --
> Gregor Lingl
> Reisnerstrasse 3/19
> A-1030 Wien
>
> Telefon: +43 1 713 33 98
> Mobil:   +43 664 140 35 27
>
> Website: python4kids.net
>
>
> ## Run this program and create a polygon without
> ## intersecting edges by clicking the vertices with the mouse
>
> from Tkinter import *
>
> def area2(A,B,C):
>     """2 * Flaeche des 2D-Dreiecks ABC"""
>     return (A[0]-C[0])*(B[1]-C[1]) - (A[1]-C[1])*(B[0]-C[0])
>
> def insideTriangle(A, B, C, P):
>     """Liegt P im Dreieck ABC?,
>     ABC sind im Gegenuhrzeigersinn angenommen!"""
>     return area2(A,B,P)>=0 and area2(B,C,P)>=0 and area2(C,A,P)>=0
>
> def triangulate(poly):
>     tri = []
>     while len(poly) > 2:
>         triaFound = False
>         count = 0
>         while not triaFound and count < len(poly): #n:
>             count += 1
>             A, B, C = poly[:3]
>             if area2(A, B, C) >= 0:
>                 for P in poly[3:]:
>                     if insideTriangle(A,B,C,P):
>                         break
>                 else:
>                     tri.append( (A,B,C) )
>                     poly.remove(B)
>                     triaFound = True
>             poly.append(poly.pop(0))
>         if count == len(poly): # n:
>             print "Not a simple polygon"
>             return None
>     return tri
>
>
> class CvDefPoly(Canvas):
>     def __init__(self, root):
>         Canvas.__init__(self, root, bg="white", cursor="crosshair")
>         self.v = ()
>         self.rWidth, self.rHeight = 10.0, 7.5
>
>         self.bind("<Configure>", self.repaint)
>         self.bind("<Button-1>", self.mousePressed)
>
>         self.done = False
>
>     def mousePressed(self, event):
>         if self.done:
>             self.done = False
>             self.v = ()
>         x ,y = self.fx(event.x), self.fy(event.y)
>         if self.v:
>             x0, y0 = self.v[:2]
>             if abs(x-x0)<self.rWidth*0.01 and abs(y-y0)<self.rHeight*0.01:
>                 self.done = True
>         if not self.done:
>                 self.v += (x,y)
>         self.repaint(None)
>
>     def iX(self,x):
>         return self.centerX + x/self.pixelSize
>     def iY(self,y):
>         return self.centerY - y/self.pixelSize
>     def fx(self,x):
>         return (x-self.centerX)*self.pixelSize
>     def fy(self,y):
>         return (self.centerY - y)*self.pixelSize
>
>     def repaint(self, event):
>         items = self.find_all()
>         for item in items:
>             self.delete(item)
>         if event:
>             self.w, self.h = event.width, event.height
>         w,h = self.w, self.h
>         self.minX = self.minY = 2.0
>         self.maxX, self.maxY = w-3.0, h-3.0
>         dx, dy = self.maxX-self.minX, self.maxY-self.minY
>         self.centerX = 2.0 + dx/2.0
>         self.centerY = 2.0 + dy/2.0
>         self.pixelSize = max(self.rWidth/dx, self.rHeight/dy)
>
>         left = self.iX(-self.rWidth/2.0)
>         right = self.iX(self.rWidth/2.0)
>         bottom = self.iY(-self.rHeight/2.0)
>         top = self.iY(self.rHeight/2.0)
>
>         self.create_rectangle(left,top,right,bottom, outline="red")
>         if len(self.v) > 1:
>             x,y = self.v[:2]
>             self.create_rectangle(self.iX(x)-2, self.iY(y)-2,
>                                   self.iX(x)+2, self.iY(y)+2, outline="green")
>         if len(self.v) > 3:
>             if self.done:
>                 v = []
>                 sv = self.v[:]
>                 while sv:
>                     a,b=sv[:2]
>                     v.extend([self.iX(a), self.iY(b)])
>                     sv = sv[2:]
>                 self.create_polygon( v, fill="", outline="blue")
>             else:
>                 coo = list(self.v[2:])
>                 while coo:
>                     x1,y1 = coo[:2]
>                     self.create_line(self.iX(x),self.iY(y),
>                                      self.iX(x1),self.iY(y1),fill="blue")
>                     x,y=x1,y1
>                     coo  = coo[2:]
>
> def ccw(poly):
>     n = len(poly)
>     k = poly.index(min(poly))
>     return area2(poly[k-1], poly[k], poly[(k+1)%n]) > 0
>
> def color(n):
>     return "#%02x%02x%02x" % (255-n,0,n)
>
> class PolyTria(Tk):
>     def __init__(self):
>         Tk.__init__(self)
>         self.geometry("500x300-10+50")
>         self.title("Define polygon vertices by clicking")
>         CvPolyTria(self).pack(expand=1, fill="both")
>
> class CvPolyTria(CvDefPoly):
>     def repaint(self, event):
>         doit = False
>         if len(self.v)>3 and self.done:
>             poly = []
>             v = self.v[:]
>             while v:
>                 p = tuple(v[:2])
>                 poly.append(p)
>                 v = v[2:]
>             if not ccw(poly):
>                 poly.reverse()
>             tri = triangulate(poly)
>             doit = True
>         CvDefPoly.repaint(self, event)
>         if doit:
>             anz = len(tri)
>             diff = 255//anz
>             for i,t in enumerate(tri):
>                 (x1,y1),(x2,y2),(x3,y3) = t
>                 t = (self.iX(x1),self.iY(y1),self.iX(x2),self.iY(y2),self.iX(x3),self.iY(y3))
>                 self.create_polygon(t, fill=color(i*diff), outline="black")
>
> if __name__ == "__main__":
>     PolyTria().mainloop()
>
>
>