CS 274: Computational Geometry (Spring 2005)
Delaunay Triangulation Project
Due 1 pm, May 4
20% of final grade
Implement a divide-and-conquer algorithm and
two incremental insertion algorithms
for constructing two-dimensional Delaunay triangulations.
Your implementations must use Guibas and Stolfi's quad-edge data structure
(with appropriate simplifications, if you wish).
You are responsible for reading and understanding the Guibas and Stolfi paper,
except Section 3, which may be safely skipped.
It's a long paper, so start early.
The purpose of this project is to burn an understanding of
Delaunay triangulations and planar subdivision data structures into your brain.
Divide-and-conquer algorithm
Implement the divide-and-conquer algorithm for which Guibas and Stolfi give
pseudocode.
Incremental insertion algorithms
Implement the incremental insertion algorithm for which Guibas and Stolfi give
pseudocode, using their suboptimal ``walking'' method for point location.
In addition, implement fast point location,
based on either conflict lists or a history dag (whichever you prefer).
Since you are using an edge-based data structure,
rather than a triangle-based data structure,
you will need to modify the point location data structure slightly.
Each quad-edge has four Data fields.
Two of these are used to reference the vertices of the quad-edge.
For point location based on conflict lists,
the other two Data fields may be used to reference
the lists of uninserted vertices
associated with the triangles on each side of the edge.
For point location based on a history dag,
the other two Data fields may be used to reference
the leaves of the dag
associated with the triangles on each side of the edge.
For conflict lists,
each uninserted vertex should maintain a reference to an oriented edge
of the triangle that contains the uninserted vertex.
For a history dag,
each leaf of the dag should maintain a reference to an oriented edge
of the triangle that the leaf represents.
Language
If you write in any language other than C, C++, or Java,
you are required to give me very complete instructions on how to
compile and run your code.
You may also be required to obtain for me an account with which I can
run your code.
If your submission does not run under Unix, I may need even more help.
(On my desk next to my Linux machine, I do have a Windows machine, but
I don't know a thing about how to compile code with it.)
Interface
Your program should use the same file formats as the program
Triangle.
Specifically, it should read a file with the suffix
.node,
and write a file with the suffix
.ele.
An advantage of using these file formats is that I provide test data.
-
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.
Another advantage is that you (and I) can use my
Show Me visualization program (included in the
Triangle distribution)
to view and print your input and output.
You can also use Triangle to check if you're producing correct triangulations.
(Note that Triangle uses a triangle-based data structure instead of quad-edges,
and its code will probably not be as helpful to you
as Guibas and Stolfi's pseudocode
in producing your quad-edge-based implementation.)
You should provide command-line switches, an input prompt,
or some other easy way to choose between
the divide-and-conquer and incremental methods;
between slow ``walking point location'' and fast point location;
and between randomized insertion and non-randomized insertion.
Randomized insertion should select
a permutation uniformly from all possible permutations.
Non-randomized insertion should
insert vertices in the order in which they appear in the input.
Geometric predicates
Insofar as possible, your algorithms should make all their arithmetic decisions
based on the results of InCircle and CCW (aka Orient2D) predicates.
Rather than writing your own, I suggest you download and blindly use
my robust predicates for floating-point inputs.
Borrowed code
You are welcome to use publicly available libraries or implementations of
the following, so long as none of them was produced by any of your classmates:
sorting, selection, trees, other fundamental non-geometric data structures,
command-line switch processing, file reading/writing,
and geometric primitives like the InCircle and CCW predicates.
You must write the quad-edge implementation and geometric algorithms all
by yourself.
Your submission
Send me an email with your submission attached as a tar or zip file.
If your code doesn't run under Unix,
special arrangements will need to be made.
You should also submit a report (on paper) that includes the following:
-
Instructions for compiling and running your code. If you use C/C++ and Unix,
relatively rudimentary instructions will probably do.
Be sure to document how to specify the input file, and how to choose
between different algorithms.
-
A table containing timings for each of your algorithms and
point location methods on
random points sets (top of this page) of 10,000, 100,000, and
1,000,000 points.
(If the ``walking'' method of point location takes longer than thirty minutes
on large point sets,
just note that you couldn't wait for it to terminate.)
Time only the randomized versions of the incremental insertion algorithm.
Try to exclude all file I/O from your timings if possible.
(If using a timer within your program isn't possible,
the Unix time command will do, although file I/O time will be
included.)
Why do you think the fastest algorithm is fastest?
-
Create an orderly point set, like a square grid whose vertices are given
in a structured order. Does failing to randomize the order of the
vertices significantly change the running time of
the incremental insertion algorithm with the fast point location method?
-
If you borrowed any code, please give full credit.
