**Features**

- Library implementing divide and conquer Delaunay triangulation algorithm based on “Primitives for the manipulation of general subdivisions and the computation of Voronoi” paper by Guibas and Stolfi.
- Opengl based test checking triangulation correctness (shown in video).

**Downloads**:

**Report**

The test is composed of three projects: a library, which imlpements a divide and conquer delaunay triangulation algorithm, and two tests to check its correctness. One of the tests is an opengl application showing the triangulation (watch the video).

The development of the algorithm is based on the quad edge structure proposed by Guibas and Stolfi. It’s easy to implement because the paper is very well explained and it has a pseudocode of the algorithm. I recommend skipping part three of the paper if you don’t want to see the mathematical details. The difficult part of the development was to get a representation of the quad-edge structure in C++.

**Technology**

- C++
- Opengl
- Glut for Win32
- Microsoft Visual Studio 2008 Proffessional Edition
- Subversion
- Redmine

**Develop/Build/Test Machine Specs **

- Intel(R) Core(TM) i7 CPU 920 @ 2.67GHz
- 3072 Mb RAM
- GeForce GTX 260GS (256 MB)
- Nvidia Driver Version: 181.20
- Microsoft Windows XP Professional SP3 x86

**Resources**

- “Primitives for the manipulation of general subdivisions and the computation of Voronoi” by Guibas and Stolfi.
- Delaunay Triangulation, Wikipedia
- Triangle: A Two-Dimensional Quality Mesh Generator and Delaunay Triangulator by Jonathan Richard Shewchuk
- Graphics Gems IV. Chapter “Incremental Delaunay Triangulation” source code, by Dani Lischinski
- Quad-edge Data Structure and Library by Paul Heckbert

hi

Can I used it for reading my 3d Points , and How ?

thanks