Triangulations

An implementation and presentation of selected mesh generation algorithms. To view online, follow this link (requires a modern browser and won't work on a mobile device).

This is a presentation initially created for my talk during the Numerical Algorithms Seminar held at the University of Wrocław in 2015. The slides contain a theoretical description of the algorithms as well as their animated visualizations, computed live by their JavaScript implementations.

Covered Topics

• Polygon Triangulation,
• PSLG Triangulation,
• Quadratic Algorithm for PSLG Triangulation
• Delaunay Triangulation of a Point Set,
• Constrained Delaunay Triangulation of a PSLG,
• The Flip algorithm for CDT,
• Ruppert's Delaunay Refine Algorithm for Quality Triangulation.

Credit

The work was heavily inspired by Jonathan Schewchuk's Triangle library. Some examples are also reconstructions of the ones provided on the website.

References:

• Jonathan Richard Shewchuk, Delaunay Refinement Algorithms for Triangular Mesh Generation, Computational Geometry: Theory and Applications, 22(1-3):21-74, May 2002. (PostScript)
• Jim Ruppert, A Delaunay Refinement Algorithm for Quality 2-Dimensional Mesh Generation, Journal of Algorithms 18(3):548-585, May 1995. (PostScript available at Triangle's reference page)
• Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars, Computational Geometry: Algorithms and Applications, Third Ed., ch. 9, Springer-Verlag, March 2008. (PDF available at the book's website)
• Marshall Bern and David Eppstein, Mesh Generation and Optimal Triangulation, Computing in Euclidean Geometry, 23-90, Ding-Zhu Du and Frank Hwang (editors), World Scientific, Singapore, 1992. (PostScript at Triangle's reference page)

The presentation is made using the impress.js library. Thumbs up for the contributors!

License

This project is licensed under the terms of the MIT license.

This is not a Library

If you're looking for a JavaScript library implementing the outlined algorithms, this is not it. The purpose of the included implementation was solely to produce visualizations for the presentation. The algorithms are often asymptotically very suboptimal and even buggy.