# Triangle – Delaunay Triangulator

Triangle – Delaunay Triangulator

eryar@163.com

Abstract. Triangle is a 2D quality mesh generator and Delaunay triangulator. Triangle was created as part of the Quake project in the school of Computer Science at Carnegie Mellon University by Jonathan R. Shewchuk. Triangle is a small C program and its Delaunay refinement algorithm for quality mesh generation is a hybrid one. It includes divide-and-conquer and incremental insertion algorithms and sweepline Delaunay triangulation algorithm. This paper is focused on the usage of the Triangle and visualization the triangulation result in OpenSceneGraph.

Key words. Triangle, Delaunay Triangulator, Mesh Generator

1. Introduction

Triangle可以生成精确的Delaunay三角剖分，限定Delaunay三角剖分（Constrained Delaunay Triangulation），Conforming Delaunay Triangulation，Voronoi图（Voronoi Diagrams）和高质量的三角网格，即生成的网格中没有瘦长的三角形，所以适用于有限元分析（Finite Element Analysis）。

Figure 1.1 Triangle – A 2D Quality Mesh Generator and Delaunay Triangulator

http://www.cs.cmu.edu/~quake/triangle.html

```#define REAL double
#define ANSI_DECLARATORS
#include \"triangle.h\"
#undef REAL```

2. Triangle Usage

Triangle有很多开关，可以选择三角剖分和生成网格的方式，如下图所示：

Figure 2.1 Options for the Triangle

Figure 2.2 Triangle Usage

Figure 2.3 Nodes and Triangles data generated by Triangle

Figure 2.4 Triangulation Mesh Generated by Triangle[-pc]

Figure 2.5 Triangulation Mesh Generated by Triangle[-pqc]

3. Displaying Meshes

Figure 3.1 Displaying the Meshes by ShowMe

```std::string TriangleMesh::ReadLine(std::ifstream &theFile)
{
std::string theBuffer;

do
{
getline(theFile, theBuffer);

// skip comment here.
if (\'#\' == theBuffer[0])
{
}
else
{
}
}

return theBuffer;
}

void TriangleMesh::BuildMesh(const std::string& aPolyFile)
{
std::stringstream ss;

std::string theNodeFileName(aPolyFile + \".node\");
std::string theElementFileName(aPolyFile + \".ele\");

std::ifstream theNodeFile(theNodeFileName.c_str());
std::ifstream theElementFile(theElementFileName.c_str());

Standard_Integer theIndex = 0;
Standard_Integer theNodeCount = 0;
Standard_Integer theTriangleCount = 0;

Standard_Integer theIndex1 = 0;
Standard_Integer theIndex2 = 0;
Standard_Integer theIndex3 = 0;

Standard_Real x = 0.0;
Standard_Real y = 0.0;

ss >> theNodeCount;

ss.str(\"\");
ss.clear();

ss >> theTriangleCount;

mMesh = new Poly_Triangulation(theNodeCount, theTriangleCount, Standard_True);

TColgp_Array1OfPnt2d& theNodes2d = mMesh->ChangeUVNodes();

for (Standard_Integer n = 1; n <= theNodeCount; ++n)
{
ss.str(\"\");
ss.clear();

ss >> theIndex >> x >> y;

theNodes2d.SetValue(theIndex, gp_Pnt2d(x, y));
}

Poly_Array1OfTriangle& theTriangles = mMesh->ChangeTriangles();

for (Standard_Integer t = 1; t <= theTriangleCount; ++t)
{
ss.str(\"\");
ss.clear();

ss >> theIndex >> theIndex1 >> theIndex2 >> theIndex3;

theTriangles.SetValue(theIndex, Poly_Triangle(theIndex1, theIndex2, theIndex3));
}
}```

Figure 3.2 Generate Smiley Face Mesh by Triangle [-pc]

Figure 3.3 Generate Smiley Face Mesh by Triangle [-pqc]

4. Conclusions

5. References

1. Jonathan R. Shewchuk. Triangle: http://www.cs.cmu.edu/~quake/triangle.html

2. Jonathan R. Shewchuk, Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangualtor, Springer-Verlag, Berlin, 1996

3. 汪嘉业 王文平 屠长河 杨承磊. 计算几何及应用.  科学出版社. 2011

4. 王成恩. 面向科学计算的网格划分与可视化技术. 科学出版社. 2011

5. 周培德. 计算几何－算法设计与分析. 清华大学出版社. 2008

6. Berg M D著 邓俊辉译. 计算几何－算法与应用. 清华大学出版社. 2009