[OpenWalnut] 2D Delaunay Triangulation

[Mathias Goldau]

Hi,

is there some code for a Delaunay Triangulation available? I know I can 
employ CGAL for this, but I need to modify the Delaunay-Triangulation 
criteria and this seems not possible inside of CGAL:

The geometric traits has to be a model of the concept 
DelaunayTriangulationTraits_2 which refines the concept 
TriangulationTraits_2. In particular this concept provides the 
side_of_oriented_circle predicate which, given four points p,q,r,s 
decides the position of the point s with respect to the circle passing 
through p, q and r. The side_of_oriented_circle predicate actually 
defines the Delaunay triangulation. Changing this predicate allows to 
build variant of Delaunay triangulations for different metrics such that 
L1 or L∞ metric or any metric defined by a convex object. However, the 
user of an exotic metric must be careful that the constructed 
triangulation has to be a triangulation of the convex hull which means 
that convex hull edges have to be Delaunay edges. This is granted for 
any smooth convex metric (like L2) and can be ensured for other metrics 
(like L∞) by the addition to the point set of well chosen sentinel points.

If not I will contribute one, as I've a deadline very soon.

Cheers,
math

-- 
Universität Leipzig
Fakultät für Mathematik und Informatik
Institut für Informatik
Augustusplatz 10, 04109 Leipzig
Phone: +493419732283