Here are the timing files (GNUzip-compressed): ttimeu10000.node.gz, ttimeu100000.node.gz, and ttimeu1000000.node.gz. Here are some smaller test files for your pleasure (not compressed): tri.node, 4.node, box.node, spiral.node, flag.node, grid.node, dots.node, ladder.node, and 633.node.
Due 5:30 pm, Monday, March 10
25% of final grade
You may be able to skip this project if you're interested in
doing an unusually challenging second project, such as a volume mesh generator.
Speak to me if you want to explore this option.
Implement the star-based two-dimensional triangulation data structure of Blandford, Blelloch, Cardoze, and Kadow (without the compression, unless you want it). You may use linked lists for the vertex links, even though it's not space efficient. (I want you to understand the data structure and its interface more than actually realize its potential for memory efficiency.) Your library should have the ability to add and remove triangles, and to query the triangle adjoining an edge (on a chosen side of the edge). Your library should require the user to address triangles by their vertices; a triangle cannot be identified by a ``triangle number'' or pointer.
Next, implement an algorithm (your choice) that constructs two-dimensional Delaunay triangulations. Its asymptotic running time should be faster than quadratic for random points uniformly distributed in a square. Your implementation must use your Blandford et al. implementation as the sole representation of the triangulation.
Your code might become a component of your second project, so it's worth your while to debug it well.
If you implement gift-wrapping, use simple bucketing (with a square grid) and a search like the spiral search described by Su and Drysdale so that the triangulation speed is reasonable on uniformly distributed point sets. The number of buckets should depend on the number of input points—certainly there should never be more buckets than input points.
If you choose the incremental insertion algorithm, walking point location is acceptable, though a faster point location method is welcome. The combination of BRIO, a quadtree traversal, and walking from the last inserted vertex can be very fast yet easy to code. The method of simply checking every triangle in the mesh is not acceptable, because it will give you a quadratic-time algorithm.
If you want the fastest triangulator possible, consider the divide-and-conquer algorithm described in the paper by Guibas and Stolfi, below. (You can make it even faster by alternating between vertical and horizontal cuts.)
If you took CS 274 (Computational Geometry) from me in the past, you have already written a Delaunay triangulator. You are welcome to retrofit your old code to use the new data structure, and turn it in.
If you think your second project might be an advancing front mesh generator, the gift-wrapping algorithm would be good practice. If you think your second project might be a Delaunay mesh generator, you will be able to reuse incremental insertion code from this project.
The following paper is a good source for pseudocode for both the divide-and-conquer algorithm and the incremental insertion algorithm (with a lame version of walking point location). However, the pseudocode is written for an edge-based data structure. Converting it for the Blandford-Blelloch-Cardoze-Kadow data structure will take some effort.
An advantage of using these file formats is that you and I can use the Show Me visualization program that comes with Triangle to view and print your input and output. You can also use Triangle to check if you're producing correct triangulations.
You should also submit a report (on paper) that includes the following: