狄诺尼三角网

问题描述：

有谁知道狄洛尼（delaunay）三角网的生成算法，就是一个小程序，在VC环境下的。
知道的帮帮忙，多谢了

问题解答：

point.pyclass Point: def __init__(self,x,y): self.x = x self.y = y def getSide(self,v1,v2): e = ((self.y - v1.y) * (v2.x - v1.x)) - ((v2.y - v1.y) * (self.x - v1.x)) if e>0: return -1 elif e == 0: return 0 else: return 1 triangle.pyimport mathfrom point import Pointclass Triangle: def __init__(self,v1,v2,v3): self.v1 = v1 self.v2 = v2 self.v3 = v3 self.getCenterAndRadius() def getTuple(self): return (self.v1,self.v2,self.v3) def getCenterAndRadius(self): v1 = self.v1 v2 = self.v2 v3 = self.v3 eps = 0.000001 if abs(v1.y - v2.y) < eps and abs(v2.y - v3.y) < eps: return None if abs(v2.y - v1.y) < eps: m2 = -(v3.x - v2.x) / float(v3.y - v2.y) mx2 = (v2.x + v3.x) / 2. my2 = (v2.y + v3.y) / 2. xc = (v2.x+v1.x) / 2. yc = m2*(xc - mx2) + my2 elif abs(v3.y - v2.y) < eps: m1 = -(v2.x - v1.x) / float(v2.y - v1.y) mx1 = (v1.x + v2.x) / 2. my1 = (v1.y + v2.y) / 2. xc = (v3.x + v2.x) / 2. yc = m1 * (xc - mx1) + my1 else: m1 = -(v2.x - v1.x) / float(v2.y - v1.y) m2 = -(v3.x - v2.x) / float(v3.y - v2.y) mx1 = (v1.x + v2.x) / 2. mx2 = (v2.x + v3.x) / 2. my1 = (v1.y + v2.y) / 2. my2 = (v2.y + v3.y) / 2. xc = (m1 * mx1 - m2 * mx2 + my2 - my1) / float(m1 - m2) yc = m1 * (xc - mx1) + my1 self.vc = Point(xc, yc) dx = v2.x - xc dy = v2.y - yc rsqr = dx * dx + dy * dy self.radius = math.sqrt(rsqr) def inCircle(self,v): dx = v.x - self.vc.x dy = v.y - self.vc.y drsqr = dx * dx + dy * dy xc = self.vc.x yc = self.vc.y dx = self.v2.x - xc dy = self.v2.y - yc rsqr = dx * dx + dy * dy if drsqr <= rsqr: return True else: return False def printTriangle(self): print '-'*15, 'triangle start', '-'*15 print self.v1.x, self.v1.y print self.v2.x, self.v2.y print self.v3.x, self.v3.y print '-'*15, 'triangle end', '-'*15delaunay.pyfrom triangle import Trianglefrom point import PointMAXSIZE = 150def makeTriangulate(ptlist): trianglelist = [None]*MAXSIZE complete = [False]*MAXSIZE for i in range(MAXSIZE): complete.append(False) edgeslist = [[None]*MAXSIZE for row in range(2)] xmin = ptlist[0].x ymin = ptlist[0].y xmax = xmin ymax = ymin ptnum = len(ptlist) #print ptnum for i in range(1,ptnum): if ptlist[i].x < xmin: xmin = ptlist[i].x if ptlist[i].x > xmax: xmax = ptlist[i].x if ptlist[i].y < ymin: ymin = ptlist[i].y if ptlist[i].y > ymax: ymax = ptlist[i].y dx = xmax - xmin dy = ymax - ymin if dx > dy: dmax = dx else: dmax = dy xmid = (xmax + xmin) / 2. ymid = (ymax + ymin) / 2. newpt = Point(xmid - 2 * dmax, ymid - dmax) ptlist.append(newpt) newpt = Point(xmid, ymid + 2 * dmax) ptlist.append(newpt) newpt = Point(xmid + 2 * dmax, ymid - ymax) ptlist.append(newpt) #ptlist[ptnum + 1].x = xmid - 2 * dmax #ptlist[ptnum + 1].y = ymid - dmax #ptlist[ptnum + 2].x = xmid #ptlist[ptnum + 2].y = ymid + 2 * dmax #ptlist[ptnum + 3].x = xmid + 2 * dmax #ptlist[ptnum + 3].y = ymid - ymax triangle = Triangle(ptlist[ptnum], ptlist[ptnum+1], ptlist[ptnum+2]) trianglelist[0] = triangle complete[0] = False ntri = 0 for i in range(ptnum): nedge = -1 j = -1 while j < ntri: j += 1 if not complete[j] and trianglelist[j]: inc = trianglelist[j].inCircle(ptlist[i]) if inc: edgeslist[0][nedge+1] = trianglelist[j].v1 edgeslist[1][nedge+1] = trianglelist[j].v2 edgeslist[0][nedge+2] = trianglelist[j].v2 edgeslist[1][nedge+2] = trianglelist[j].v3 edgeslist[0][nedge+3] = trianglelist[j].v3 edgeslist[1][nedge+3] = trianglelist[j].v1 nedge += 3 trianglelist[j] = trianglelist[ntri] complete[j] = complete[ntri] j -= 1 ntri -= 1 for j in range(nedge): if edgeslist[0][j] and edgeslist[1][j] : for k in range(j+1,nedge+1): if edgeslist[0][k] and edgeslist[1][k]: if edgeslist[0][j] == edgeslist[1][k]: if edgeslist[1][j] == edgeslist[0][k]: edgeslist[0][j] = None edgeslist[0][k] = None edgeslist[1][j] = None edgeslist[1][k] = None for j in range(nedge+1): if edgeslist[0][j] and edgeslist[1][j]: ntri += 1 trianglelist[ntri] = Triangle(edgeslist[0][j],edgeslist[1][j],ptlist[i]) complete[ntri] = False i = -1 while i<ntri: i += 1 if trianglelist[i]: if not (trianglelist[i].v1 in ptlist[0:ptnum] and trianglelist[i].v2 in ptlist[0:ptnum] and trianglelist[i].v3 in ptlist[0:ptnum]): trianglelist[i] = trianglelist[ntri] i -= 1 ntri -= 1 else: trianglelist[i] = trianglelist[ntri] i -= 1 ntri -= 1 return trianglelist[:ntri+1]

太乱了！！

楼上的代码没有用回车断句啊，看得好晕