Test: Delaunay Triangulation

YouTube Preview Image




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


  • 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


One Response to “Test: Delaunay Triangulation”

  1. memo says:

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