# eryar

posts - 456, comments - 590, trackbacks - 0, articles - 0

Triangle - Delaunay Triangulator

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

#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 theBuffer;

do
{
getline(theFile, theBuffer);

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

else
{
= false;
}
}

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
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
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
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

### Feedback

@Mr Li

@D

@付振宇
Hi 付振宇,

Triangle的用法请参考Figure 2.2 Triangle Usage 中红色线框中的部分。

Best Regards,
Shing Liu
@eryar

@付振宇

@eryar

“#include "triangle.h"

@付振宇
Hi 付振宇，

~~~~~~~~~~~~~~~~~~~~~~~~~

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

~~~~~~~~~~~~~~~~~~~~~~~~~~

Best Regards,
Shing Liu
@eryar

#define REAL double
#define ANSI_DECLARATORS

#define NO_TIMER
#define TRILIBRARY

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

@付振宇

REAL *pointattributelist;
int *pointmarkerlist;
int numberofpointattributes;

int *trianglelist;
REAL *triangleattributelist;
REAL *trianglearealist;
int *neighborlist;
int numberoftriangles;
int numberofcorners;
int numberoftriangleattributes;*/

int *segmentlist;
int *segmentmarkerlist;
int numberofsegments;
REAL *holelist;
int numberofholes;

REAL *regionlist;
int numberofregions;

int *edgelist;
int *edgemarkerlist;
REAL *normlist;
int numberofedges;

@LI

/* Data structure for command line switches and file names. This structure */
/* is used (instead of global variables) to allow reentrancy. */

struct behavior {

/* Switches for the triangulator. */
/* poly: -p switch. refine: -r switch. */
/* quality: -q switch. */
/* minangle: minimum angle bound, specified after -q switch. */
/* goodangle: cosine squared of minangle. */
/* vararea: -a switch without number. */
/* fixedarea: -a switch with number. */
/* maxarea: maximum area bound, specified after -a switch. */
/* usertest: -u switch. */
/* regionattrib: -A switch. convex: -c switch. */
/* weighted: 1 for -w switch, 2 for -W switch. jettison: -j switch */
/* firstnumber: inverse of -z switch. All items are numbered starting */
/* from `firstnumber'. */
/* edgesout: -e switch. voronoi: -v switch. */
/* neighbors: -n switch. geomview: -g switch. */
/* nobound: -B switch. nopolywritten: -P switch. */
/* nonodewritten: -N switch. noelewritten: -E switch. */
/* noiterationnum: -I switch. noholes: -O switch. */
/* noexact: -X switch. */
/* order: element order, specified after -o switch. */
/* nobisect: count of how often -Y switch is selected. */
/* steiner: maximum number of Steiner points, specified after -S switch. */
/* incremental: -i switch. sweepline: -F switch. */
/* dwyer: inverse of -l switch. */
/* splitseg: -s switch. */
/* nolenses: -L switch. docheck: -C switch. */
/* quiet: -Q switch. verbose: count of how often -V switch is selected. */
/* usesegments: -p, -r, -q, or -c switch; determines whether segments are */
/* used at all. */
/* */
/* Read the instructions to find out the meaning of these switches. */

int poly, refine, quality, vararea, fixedarea, usertest;
int regionattrib, convex, weighted, jettison;
int firstnumber;
int edgesout, voronoi, neighbors, geomview;
int nobound, nopolywritten, nonodewritten, noelewritten, noiterationnum;
int noholes, noexact, nolenses;
int incremental, sweepline, dwyer;
int splitseg;
int docheck;
int quiet, verbose;
int usesegments;
int order;
int nobisect;
int steiner;
REAL minangle, goodangle;
REAL maxarea;

/* Variables for file names. */

#ifndef TRILIBRARY
char innodefilename[FILENAMESIZE];
char inelefilename[FILENAMESIZE];
char inpolyfilename[FILENAMESIZE];
char areafilename[FILENAMESIZE];
char outnodefilename[FILENAMESIZE];
char outelefilename[FILENAMESIZE];
char outpolyfilename[FILENAMESIZE];
char edgefilename[FILENAMESIZE];
char vnodefilename[FILENAMESIZE];
char vedgefilename[FILENAMESIZE];
char neighborfilename[FILENAMESIZE];
char offfilename[FILENAMESIZE];
#endif /* not TRILIBRARY */

}; /* End of `struct behavior'. */

Best Regards,
Shing Liu
@eryar

@LI

@付振宇