三角網演算法
Ⅰ 土方量的幾種計算方法
土方量的計算 土方工程主要依據豎向設計進行土方工程計算及土方施工、塑造、整理園林建設場地。 土方量計算一般根據附有原地形等高線的設計地形來進行，但通過計算，有時反過來又可以修訂設計圖中的不足，使圖紙更完善。土方量的計算在規劃階段無須過分精確，故只需估算，而在作施工圖時，則土方工程量就需要較精確計算。土方量的計算方法有： 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）分邊以該三角形的一邊作為基邊，用同樣的方法形成其他三角形。直到所有參考點都參與構造狄洛尼三角網為止。