Implement one of the following algorithms:
What your clasmates are implementing
Feel free to work in groups of two, although I will expect a better job from a group of two. Also feel free to come and discuss the algorithms with me. I've described each of these algorithms in class and have also made papers available that describe the algorithms in more detail. Two of the papers are available on the web, and the third is in a JACM issue that is available the CS reading room (Soda 681).
Note: Source code for some of these algorithms is available on the web. If you choose to do a problem, please do not look at anyone elses source until you have handed in your implementation. You should feel free, however, to use other peoples code for various subroutines such as implementing a heap. Make sure you reference the code.
I have made some code for incremental Delaunay Triangulation available, which you might find useful for either of the first two algorithms. This is taken from the book "Graphics Gems IV", edited by Paul Heckbert, Academic Press, 1994. A copy of the associated chapter is available outside my door. The code is also available as part of a compressed tar file associated with the book. You might find, however, that it is just as easy if not easier to design your code from scratch since deciphering the code is not trivial. Also, as I mentioned in class, you might find a triangle based representation simpler (the code uses the quadedge representation). If you do use any part of the code, make sure to note in your code which parts you used.
You might also find Jonathan Shewchuk's Show-me code (showme.c) useful for plotting a set of triangles, or boundaries. It compiles for me using
gcc -o showme showme.c -I/usr/sww/X11R6/include -L/usr/sww/X11R6/lib -lX11
and for drawing triangles you can use .ele and .node
files.
Jim Rupert. ``A Delaunay Refinement Algorithm for Quality 2-Dimensional Mesh Generation.'' Journal of Algorithms, 18(3):548-585, May 1995.The test data files: (Note: these use the Poly format from Jonathan Schewchuk's Triangle code) Note that all data is included in a bounding box. This simplifies the problem of dealing with exterior triangles (all triangles in the box are considered interior). In your implementation you don't need to remove the triangles in the exterior (between box and surface) nor in the "holes". You can therefore ignore the "holes" data at the end of the .poly files. If you do chose to remove the triangles, however, you can use the "holes" data by starting at each triangle with the hole point and removing triangles outwards until you hit a boundary segment. If you choose to remove them please state this in your results.
Michael Garland and Paul Heckbert. ``Fast Polygonal Approximation of Terrains and Height Fields.'' CMU-CS-95-181, CS Dept, Carnegie Mellon U., Sept. 1995.The algorithm I want you to implement is number III in the paper (the version I described in class).
The test data files: (Note: these are binary files in STM format)
The following files contain C++ code for reading data in the STM (Simple Terrain Model) format. (stmops.c and stmops.h)
Paul B. Callahan and S. Rao Kosaraju. ``A Decomposition of Multi-Dimensional Point-Sets with Applications to k-Nearest-Neighbors and n-Body Potential Fields.'' JACM, 42(1):67-90, January 1995
Available for copying in the CS reading room.
Points can be generated in the Kuzmin model by first generating a random point p within a circle of radius 1. This can be done by generating a random point within a square [-1,1],[-1,1] and throwing the point out if it is not in the circle and trying again. Now scale the radius by
In particular
Repeat this process for each pont.
You can use a similar technique in 3 dimensions (by generating points in a unit cube). For the scaling, however, you should use
in 3 dimensions.