Saturday, November 9, 2013

Incremental constrained Delaunay triangulation prototype



Delaunay triangulation is a huge subject and it can become very hard when we reach some refinements like constrained triangulation, incremental algorithm, quad-edge data structure... that are globally part of the computational geometry theory.

But there are several applications and they can be very impressive. Of course my mind is focused on artificial intelligence and I think especially of the pathfinding through navigation mesh.

This article is the first of a serie about concepts and algorithms related to computational geometry. It is an illustration of Delaunay triangulation through a demo prototype.

Just click on the board to add new constrained edges:



This demo and the underlying library I wrote are direct implementations of the following article:

Fully Dynamic Constrained Delaunay Triangulation (2003)

The underlying data structure behind the library is the quad-edge:


No comments:

Post a Comment