Skip to topic
|
Skip to bottom
Jump:
TModeling
TModeling Web
TModeling Web Home
Changes
Notify
Index
Search
Webs
BioGeometry
Main
TModeling
TWiki
Edit
Attach
Printable
TModeling.DelaunayTessellation
r1.1 - 19 Feb 2005 - 18:10 - Main.guest
topic end
Start of topic |
Skip to actions
The Delaunay Tessellation is the dual of a Voronoi diagram. Given a finite set of sites, the tessellation contains the convex hull of every subset that can lie on the boundary of a sphere with empty interior. Usually, points are assumed to be (or perturbed to be) in general position, so that all convex hulls are simplices. Here is a 2-d [[http://www.cs.unc.edu/~snoeyink/demos/crust][demo]]. ---+++ Papers & 2d Delaunay triangulation code * Leonidas J. Guibas, Jorge Stolfi: Primitives for the Manipulation of General Subdivisions and Computation of Voronoi Diagrams. ACM Transactions on Graphics 4(2): 74-123 (1985) http://doi.acm.org/10.1145/282918.282923 (Introduces and uses the quad-edge data structure; skim the first half, and read the incremental algorithm and divide & conquer algorithm that are given in full detail.) * Dani Lischinski, Incremental Delaunay Triangulation, "Graphics Gems IV", Academic Press, 1994. (I need to scan this paper) [[http://www.cse.ucsc.edu/~pang/160/f98/Gems/GemsIV/delaunay/][C++ code here]] (An implementation of Guibas & Stolfi's quad-edge and incremental Delaunay in C++.) * In case you want to see it, [[%ATTACHURL%/crust.zip][source code for my demo implementation in Java]]. This uses triangle-based data structure that has fewer pointers than the quad edge, but is a little harder to do the swap. * [[http://www.cs.unc.edu/~snoeyink/demos/tripod/home.html][Tripod]]: this point-based data structure uses the fewest pointers and has the best, but needs to be completed to an implementation. This would be worth a publication. [[%ATTACHURL%/tripod.zip][Code & 3 page draft description.]] * J. R. Shewchuk. [[%ATTACHURL%/triangle.pdf][Triangle]]: engineering a 2d quality mesh generator and Delaunay triangulator. In First Workshop on Applied Computational Geometry. Association for Computing Machinery, May 1996. (This is one of the most popular implementations, because it is robust yet still fast.) ---+++ 3d Delaunay code * Incremental triangulation in 3d -- designed to work well for protein data, which is evenly spaced and limited precision. [[%ATTACHURL%/MSRIDel3d-liusnoe.pdf][Comparison paper here.]] [[%ATTACHURL%/del3d.zip][bare bones C version]] [[http://www.cs.unc.edu/~liuy/research/tess3/][C++ version]] Detailed technical paper in progress with [[Main.YuanxinLiu][Leo]].) * Qhull * Pyramid -- Main.JackSnoeyink - 17 Feb 2005
to top
End of topic
Skip to action links
|
Back to top
Edit
|
Attach image or document
|
Printable version
|
Raw text
|
More topic actions
Revisions: | r1.1
|
Total page history
|
Backlinks
You are here:
TModeling
>
DelaunayTessellation
to top
Copyright © 1999-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki?
Send feedback