Discussion :

[souviron34]

Comme mentinonné sur le post Trinagluation Java, voici un certain nombre de codes et pointeurs sur Delaunay/Voronoi en C (1 en C++), avec diverses méthodes (incrémentales, sweep, divide and conquer).

La plupart dont 2D, mais un certain nombre 2D ET 3D.

Bien entendu, une mine essentielle d'informations/de codes sources est encore et toujours Graphics Gems (http://tog.acm.org/GraphicsGems/).

• Triangle
  

  A Two-Dimensional Quality Mesh Generator and Delaunay Triangulator.
  Version 1.3
  
  Show Me
  A Display Program for Meshes and More.
  Version 1.3
  
  Copyright 1996 Jonathan Richard Shewchuk
  School of Computer Science
  Carnegie Mellon University
  http://www.cs.cmu.edu/~quake/triangle.html

  http://www.cs.cmu.edu/~quake/triangle.html
  
  
• Voronoi. Méthode sweep (pas de commentaires dans le code)
  

  The author of this software is Steven Fortune. Copyright (c) 1994 by AT&T
  Bell Laboratories.

• qhull
  

  Qhull, Copyright (c) 1993-1999
  The National Science and Technology Research Center for
  Computation and Visualization of Geometric Structures
  (The Geometry Center)
  University of Minnesota
  400 Lind Hall

  
  
• konovoronoi
  

  /*
  * 2D & 3D Voronoi diagram and 2D Delaunay diagram program
  * with "Incremental method "
  * BY Yoichi KONO, Nov. 1995
  * original 1997/1/10 by kono@muraoka.info.waseda.ac.jp
  * modified 1997/5/06 by kono@muraoka.info.waseda.ac.jp
  *
  * feel free to ask me any question and to send any advice
  */

• Hull 1.0
  

  This program computes convex hulls, Delaunay triangulations, alpha shapes,
  and Voronoi volumes, using an incremental algorithm and exact arithmetic.
  Author:
  Ken Clarkson,
  clarkson@research.bell-labs.com,
  http://cm.bell-labs.com/who/clarkson.

  (oops.. J'ai copié/collé un peu vite.. Je revindrais avec l'adresse exacte).
  
  
• Gts
  

  Original Authors
  ----------------
  Stéphane Popinet popinet@lmm.jussieu.fr

• Dimension
  

  This code was developped in C++ and compiled with the ATT compiler CC.
  (c) O. Devillers, INRIA, 2004 route des Lucioles, BP 93, 06902 Sophia Antipolis
  Olivier.Devillers@sophia.inria.fr, (33) 93 65 77 63, Fax (33) 93 65 76 43
  http://www.inria.fr:/prisme/personne...devillers.html

  (le lien ne fonctionne plus)
  
  
• Detri
  

  Copyright (c) 1991-94 The Board of Trustees of the University of Illinois
  
  _______________________________________________________________________________
  _______________________ The Detri README File _________________________________
  
  Version 2.2
  Author: Ernst Mucke
  Department of Computer Science
  University of Illinois at Urbana-Champaign
  <mucke@cs.uiuc.edu>
  
  
  (See file Copyright for copyright information.)
  
  Detri 2.2 computes Delaunay triangulations of 3D point sets. It employs a
  variant of the randomized incremental-flip algorithm due to Edelsbrunner and
  Shah [4] (see file REFERENCES). The variant and its data structure is
  described in more detail in Mucke [8]. The time complexity of the code is
  roughly proportional to the number of triangles in the final triangulation.
  In the worst case, this is quadratic in the number of input points, but for
  most cases it is closer to linear. (For historical reasons, there is a
  command-line option that forces Detri to use the original, non-randomized
  incremental-flip algorithm of Barry Joe [2]. The use of this option is
  discouraged because the randomized version of the code is typically
  significantly faster than the non-randomized one.)
  
  The code uses three other packages: the utility functions of the Basic C
  Library, the Lia Library for long-integer arithmetic, and the SoS Library
  implementing a symbolic perturbation (see Edelsbrunner and Mucke [1]).

  
  
• Delaunay triangulation by straightline divide-and-conquer.
  

  /*
  ** Written by J. Stolfi on april 1993, based on an original
  ** implementation by Jim Roth (DEC CADM Advanced Group, May 1986).
  ** See the copyright notice at the end of this file.
  */
  /*
  ** Copyright notice:
  **
  ** Copyright 1996 Institute of Computing, Unicamp.

• Dct
  

  The program implements the worst-case optimal divide-and-conquer Delaunay
  triangulation algorithm as described in:
  
  Guibas, L. and Stolfi, J., "Primitives for the Manipulation
  of General Subdivisions and the Computation of Voronoi Diagrams, ",
  ACT TOG, 4(2), April, 1985.
  
  The algorithm is O(nlogn) time and O(n) space.
  
  Geoff Leach
  Department of Computer Science
  RMIT.
  gl@cs.rmit.edu.au

• GeomPack
  

  This is README file for GEOMPACK, which can be obtained by
  http://www.cs.ualberta.ca/~barry/
  or ftp://ftp.cs.ualberta.ca/pub/geompack
  ------------------------------------------------------------------------------
  
  FINAL NOTE (June 6, 1999):
  Geompack90 is now available from http://www.netcom.ca/~bjoe/index.htm
  GEOMPACK will remain here until my UofA account disappears.
  - Barry Joe
  ------------------------------------------------------------------------------
  
  August 18, 1996:
  I have now left University of Alberta. I no longer have time to support
  this version of GEOMPACK, but will keep it in this ftp directory until
  about October 31, 1996. A new version will likely be available some time
  in 1997. The e-mail address barry@cs.ualberta.ca will still exist for
  about a year; my new e-mail address is bjoe@netcom.ca. It may be several
  months before I can quickly reply to e-mail.
  - Barry Joe
  ------------------------------------------------------------------------------

Mon propre programme (incréméntal, 2D, triangulation seulement) sera mis d'ici ce soir.

[souviron34]

désolé l'ajout sera ce soir ou demain, pas le temps...