600.488 Programming Project

Due: Monday, May 4, 1998

If you choose to do the programming project, your program should be written in Java, and should provide functionality for the subdivision or 3-D convex polytope interfaces, either as input or output. I will supply the specification of these interfaces. A project that takes a subdivision or 3-D polytope as input includes any of the following:

  1. planar point-location (input: Subdivision; output: PointLocator)
  2. ray-shooting against a convex polytope (input: Polytope3D; output: RayShooter)
  3. vector-normal querying (input: Polytope3D) (input: Polytope3D; output: VectorQuerier)

A project that produces a subdivision or 3-D polytope as output includes any of the following:

  1. 3-dimensional convex hull (input: An Enumeration of Point3D; output: Polytope3D)
  2. Voronoi diagram of a set of points in the plane (input: An Enumeration of Point2D; output: Subdivision)
  3. Delaunay triangulation of a set of points in the plane (input: An Enumeration of Point2D; output: Subdivision)
  4. Computing the arrangement and trapezoidal diagram of a set of line segments in the plane (input: An Enumeration of Segment (in 2d); output: Subdivision)
  5. Computing an arrangement of lines in the plane (input: An Enumeration of Line2D (in 2d); output: Subdivision)
  6. Triangulating the interior of a simple polygon (input: Polygon; output: Subdivision)
Please send the professor, Michael Goodrich, an e-mail message addressed to goodrich@cs.jhu.edu, indicating your preference by Wednesday, April 22, 1998. At most 3 students will be allowed to be working on the same project topic, and all projects must be 100% individual efforts. No group projects will be allowed.

Whichever project you choose, you must turn in a report describing your project, including its source code.

Note: You are encouraged to use the interfaces and built-in code from JDSL: A Data Structures Library in Java as well as the Java interfaces that I have developed for these projects. If you want to download all of these interfaces in one shot, just download the Bundle tar file.