三角网算法
Ⅰ 土方量的几种计算方法
土方量的计算 土方工程主要依据竖向设计进行土方工程计算及土方施工、塑造、整理园林建设场地。 土方量计算一般根据附有原地形等高线的设计地形来进行，但通过计算，有时反过来又可以修订设计图中的不足，使图纸更完善。土方量的计算在规划阶段无须过分精确，故只需估算，而在作施工图时，则土方工程量就需要较精确计算。土方量的计算方法有： 1. 体积法：用求体积的公式进行土方估算。 2. 断面法：是以一组等距（或不等距）的相互平行的截面将拟计算的地块、地形单体（如山、溪涧、池、岛等）和土方工程（如堤、沟渠、路堑、路槽等）分截成"段"，分别计算这些"段"的体积，再将各段体积累加，以求得该计算对象的总土方量。 3. 方格网法：方格网法是把平整场地的设计工作与土方量计算工作结合在一起进行的。方格网法的具体工作程序为： 在附有等高线的施工现场地形图上作方格网控制施工场地，依据设计意图，如地面形状、坡向、坡度值等。确定各角点的设计标高、施工标高，划分填挖方区，计算土方量，绘制出土方调配图及场地设计等高线图。 土方施工按挖、运、填、夯等施工组织设计安排未进行，以达到建设场地的要求而结束。
Ⅱ 德洛内三角算法（Delaunay triangulation）基本方法是怎样的，说的详细些，另外与三维空间连接性有什么关
哈哈，刚好做了这道题～感情你也是学测量的？
荷兰气候学家A•H•Thiessen提出了一种根据离散分布的气象站的降雨量来计算平均降雨量的方法，即将所有相邻气象站连成三角形，作这些三角形各边的垂直平分线，于是每个气象站周围的若干垂直平分线便围成一个多边形。用这个多边形内所包含的一个唯一气象站的降雨强度来表示这个多边形区域内的降雨强度，并称这个多边形为泰森多边形。如图5-6-1，其中虚线构成的多边形就是泰森多边形。泰森多边形每个顶点是每个三角形的外接圆圆心。泰森多边形也称为Voronoi图，或dirichlet图。
图5-6-1泰森多边形
泰森多边形的特性是：
1、每个泰森多边形内仅含有一个离散点数据；
2、泰森多边形内的点到相应离散点的距离最近；
3、位于泰森多边形边上的点到其两边的离散点的距离相等。
泰森多边形可用于定性分析、统计分析、邻近分析等。例如，可以用离散点的性质来描述泰森多边形区域的性质；可用离散点的数据来计算泰森多边形区域的数据；判断一个离散点与其它哪些离散点相邻时，可根据泰森多边形直接得出，且若泰森多边形是n边形，则就与n个离散点相邻；当某一数据点落入某一泰森多边形中时，它与相应的离散点最邻近，无需计算距离。
在泰森多边形的构建中，首先要将离散点构成三角网。这种三角网称为Delaunay三角网。
对于泰森多边形（即Delaunay三角网）内的Delaunay三角形的构建方法应为：
1、凸包生成；
2、环切边界法凸包三角剖分；
3、离散点内插。
Delaunay三角形产生准则的最简明的形式是：任何一个Delaunay三角形的外接圆的内部不能包含其它任何点。它的最大化最小角原则是：每两个相邻的三角形构成的凸四边形的对角线，在相互交换后，六个内角的最小角不再增大。
而泰森多边形（即Delaunay三角网）的构建步骤应为：
1、离散点自动构建三角网，即构建Delaunay三角网。对离散点和形成的三角形编号，记录每个三角形是由哪三个离散点构成的。
2、找出与每个离散点相邻的所有三角形的编号，并记录下来。这只要在已构建的三角网中找出具有一个相同顶点的所有三角形即可。
图5-6-6泰森多边形的建立
3、对与每个离散点相邻的三角形按顺时针或逆时针方向排序，以便下一步连接生成泰森多边形。排序的方法可如图5-6-6所示。设离散点为o。找出以o为顶点的一个三角形，设为A；取三角形A除o以外的另一顶点，设为a，则另一个顶点也可找出，即为f；则下一个三角形必然是以of为边的，即为三角形F；三角形F的另一顶点为e，则下一三角形是以oe为边的；如此重复进行，直到回到oa边。
4、计算每个三角形的外接圆圆心，并记录之。
5、根据每个离散点的相邻三角形，连接这些相邻三角形的外接圆圆心，即得到泰森多边形。对于三角网边缘的泰森多边形，可作垂直平分线与图廓相交，与图廓一起构成泰森多边形。
怎么只能插入一张图片啊.......晕.......
Ⅲ 狄诺尼三角网
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]
Ⅳ Delaunay三角构网的发展
三角网格自动剖分技术的研究起源于20世纪70年代，主要为了满足航空、数学、地学等领域解决实际问题的需要。1972年，Lawson第一次提出了构造平面Delaunay三角化的着名算法——局部变换法(Local Transformation Algorithm)，又称为换边算法(Flipping Algorithm)。1981年，英国Bath大学数学分校的Bowyer(1981)和澳大利亚悉尼大学的 Waston(1981)分别给出了一种构造D维空间点集的Delaunay三角化的增量算法，此算法的思路与局部变换法不同，后来被称为Bowyer Waston算法。随着应用深入，单纯的平面三角网格已经不能满足现有的需求，比如在地质领域里处理断层时，对断层出露线的处理是必须作为限定条件出现在Delaunay三角化中(陈学习等，2005)，就需要进行约束Delaunay剖分。然而，在不做任何处理的情况下进行Delaunay剖分不是一定能完成的(Chew，1989；杨钦，2001)，需要在现有限定条件中新插入点进行细分处理。于是，1989年Chew首次提出Delaunay细分算法，其基本算法思想是先将限定线段分成更小的线段，然后将细分单元顶点进行Delaunay三角剖分。该算法在二维问题中被形象地称为边界细分(Boundary Subdivide，BS)算法。Ruppert(1995)对BS算法进行了扩展，通过单元细分的方式，生成比较均匀的二维网格。2002年Shewchuk对Chew和Ruppert的网格生成算法进行了统一，用于生成非均匀网格，适合于数值计算使用，并对非流形域(nonmanifold domains)网格生成进行了研究。
至此，平面二维Delaunay网格生成的理论技术已基本成熟(杨钦，2005)。然而，在实际的三角网格剖分过程中，计算时间与存储空间将是制约实际需求的瓶颈(Øyvind，2000)。当离散点集达到海量级时，进行三角网格生成就不得不考虑效率问题。在进行底层数据结构设计时，合理的数据结构可以提高算法的执行效率。具有拓扑关系描述的数据结构，不仅在构建Delaunay三角网时能提高效率，而且能为后续的使用分析带来便利。和构建三维Delaunay三角网格相比，平面Delaunay相对简单得多，在建立拓扑关系时，通常只考虑点、边和三角形之间的拓扑，即使这样，至今仍没有统一的拓扑数据结构来进行Delaunay网格剖分。广义图拓扑数据结构在欧洲国家引起愈来愈多的关注(Øyvind，2000；Lienhardt，1989，1994；Yvon et al.，2000)，并得到了许多实际的应用(Mallet，2002；Michael et al.，1998；Yvon et al.，1996)，如GoCAD软件就已经采用GMaps作为拓扑数据模型，能够非常灵活的管理三角网格。GMaps可以扩展到任意维数，它不仅仅局限于二维三角形或三维四面体，可以表达任意形状的形体，甚至是非流形单元(Yvon et al.，2000)。本章采用GMaps拓扑数据结构进行Delaunay平面三角网格剖分研究，并对其进行扩展，使其能够方便地进行点的插入和删除，从而可以通过引入虚拟钻孔实现地质模型的细化。
Ⅳ 山区道路开挖用DTM三角网计算是否可行
摘要 三角网结构DTM是利用地面离散的高程点通过一定的算法连接成空间三角网结构的地面模型，此过程为建立三角网DTM过程。建立三角网DTM的原始数据为地面高程点的三维坐标，联三角网，生成三角网结构DTM。三角网结构DTM在工程测量中，可用于场地平整、河道开挖、筑堤等土方量计算及水库的容水量计算。
Ⅵ 请问工程测量中四等三角网和四等水准的精度
四等三角网最弱点点位误差5cm，平均边长2Km，测角中误差<2.5秒，最弱边误差<1/45000，四等水准相对起算点<20mm，一般是对测量过程指标有所限制，如每公里全中误差小于10mm，闭合差小于20mm*sqr(L)。
工程测量中三角网是水平控制网中的一种布设形式。由若干个三角形连结构成的三角网。中国二等三角测量和大部分三、四等三角锁测量采用这种形式。这种网控制面积大，几何条件多，图形结构强，有利于检查角度观测质量。
(6)三角网算法扩展阅读：
基本概念
三角网是由一系列连续三角形构成的网状的平面控制图形，是三角测量中布设连续三角形的两种主要扩展形式，同时向各方向扩展而构成网状，优点为点位分布均匀、各点之间互相牵制、图形强度较高，缺点是扩展较缓慢。
三角网是实现地形三维可视化，数字地面模型（Digital Terrain Model，简称DTM）是一种很有效的途径。
DTM主要是由栅格和不规则三角网（Triangulated Irregular Network，简称TIN）两种数据格式来表示，相比于栅格TIN具有许多优点，几乎能适用于任何复杂的地形，所以TIN是目前DTM常采用的一种格式。
Ⅶ 泰森多边形法的泰森多边形的建立步骤
建立泰森多边形算法的关键是对离散数据点合理地连成三角网，即构建Delaunay三角网。建立泰森多边形的步骤如下：
1、离散点自动构建三角网，即构建Delaunay三角网。对离散点和形成的三角形编号，记录每个三角形是由哪三个离散点构成的；
2、找出与每个离散点相邻的所有三角形的编号，并记录下来。这只要在已构建的三角网中找出具有一个相同顶点的所有三角形即可；
3、对与每个离散点相邻的三角形按顺时针或逆时针方向排序，以便下一步连接生成泰森多边形。排序的方法可如图所示。设离散点为o。找出以o为顶点的一个三角形，设为A；取三角形A除o以外的另一顶点，设为a，则另一个顶点也可找出，即为f；则下一个三角形必然是以of为边的，即为三角形F；三角形F的另一顶点为e，则下一三角形是以oe为边的；如此重复进行，直到回到oa边；
4、计算每个三角形的外接圆圆心，并记录之；
5、根据每个离散点的相邻三角形，连接这些相邻三角形的外接圆圆心，即得到泰森多边形。对于三角网边缘的泰森多边形，可作垂直平分线与图廓相交，与图廓一起构成泰森多边形。
参考
泰森多边形的建立
Ⅷ Delaunay三角剖分算法的准则特性
准则:
要满足Delaunay三角剖分的定义，必须符合两个重要的准则：
1、空圆特性：Delaunay三角网是唯一的（任意四点不能共圆），在Delaunay三角形网中任一三角形的外接圆范围内不会有其它点存在。如下图所示：
2、最大化最小角特性：在散点集可能形成的三角剖分中，Delaunay三角剖分所形成的三角形的最小角最大。从这个意义上讲，Delaunay三角网是“最接近于规则化的“的三角网。具体的说是指在两个相邻的三角形构成凸四边形的对角线，在相互交换后，六个内角的最小角不再增大。如下图所示：
特性:
以下是Delaunay剖分所具备的优异特性：
1.最接近：以最近的三点形成三角形，且各线段(三角形的边)皆不相交。
2.唯一性：不论从区域何处开始构建，最终都将得到一致的结果。
3.最优性：任意两个相邻三角形形成的凸四边形的对角线如果可以互换的话，那么两个三角形六个内角中最小的角度不会变大。
4.最规则：如果将三角网中的每个三角形的最小角进行升序排列，则Delaunay三角网的排列得到的数值最大。
5.区域性：新增、删除、移动某一个顶点时只会影响临近的三角形。
6.具有凸多边形的外壳：三角网最外层的边界形成一个凸多边形的外壳。
我的一点想法，提取边界，（所有点的x,y坐标已知）
步骤
1.建立一个已有边界点队列，初始为空
2.首先找第一点（x,y），提取y坐标最小值的点，若存在相同y坐标，任意取一点即可
3.将该点(x,y)加入边界点队列
4.从(x,y)点开始，标记该点位发起点，依次遍历除了边界点队列中已存在点以外的所有点（x1,y1）。
5.计算x y 与 x1, y1之间的仰角关系，找出所有中仰角最小的点(x1,y1),可通过两点之间的斜率进行计算，注意存在正负关系,(存在相同仰角关系，因此还需要记录两点之间的长度，当仰角相同时取长度短的点)
6.将该点（x1,y1）加入边界队列（从此步骤开始，重复步骤3，4, 5）迭代，直到一直检索到最初始点后，边界计算完成
献丑了，看错题目当成二维坐标。
三维坐标可能麻烦些，我的一些想法，个人未验证过，仅供提示，希望有所帮助
步骤
1.提取z坐标最小的点，若存在多个点，任意取一点。
2.建立一个连接线记录队列，初始为空
3.遍历所有该点以外的所有点，找出仰角最小的点，以这两点的连接线记录。
4.遍历除了连接线记录队列中已有连接线端点外的所有点(x,y,z)，计算该连接线与点(x,y,z)组成的平面，与除了这平面三点以外的所有其他点与该平面的垂距关系（存在正负关系），若所有其他点都在该平面的同侧，即正负关系一致，则确定该三点平面为边界三角形的一个，将三角形的三边加入连接线记录队列
5.（从本步骤开始，以该边界三角网的除初始边外的另两边进行步骤4的迭代，当迭代到找不到除已有连接线记录队列中点以外的符合条件的点为止）
这样就完成的所有边界点的计算了。
对于你的算法，我感觉有所纰漏，边界三角形的边也有可能被多个三角形所共用的。
个人愚见，未经验证，请勿拍砖
Ⅹ c++用三角网生成等高线算法
1）任取一个参考点作为起始点P1，找出P1附近的一个参考点P2，以两点连线为基边，计算其直线方程。
2）再在附近找第三个点。取到前两点的距离平方和最小的点作为候选点，以该三点作圆，判断周围是否有落入该圆的点。如果有，则该三角形不是狄洛尼三角形，再选用第二个候选参考点进行同样的操作，直到没有其他参考点落入外接圆内为止，则该三角形就是狄洛泥三角形。
3）分边以该三角形的一边作为基边，用同样的方法形成其他三角形。直到所有参考点都参与构造狄洛尼三角网为止。