Computational Geometry (Fall 2008)

Project 2 - Point location

The goal is to build a data structure for a decomposition of the plane that supports to locate the face containing a given point.

The running program should support the following operations.

• Read a DCEL from a file (constructed in Project 1) representing a decomposition of the plane.
• Input a query point interactively by using the mouse, and highlighting the face containing the query point.

A running program implementing one of the planar point location data structures in [BKOS, Chapter 6] or [ST86] is expected.

The project should be done in groups of up to three persons.

Deadline: Wednesday November 19, 2008, 9.15.

Note:The evaluation of the report and implementation will be part of the final grade.

Project 1 - Line segment intersection

The goal of the project is to be able to input line segments from the screen and a file, compute their intersections and to store them together with their intersections as a planar graph represented in a DCEL structure. A technical goal is to be able to handle DCEL's.

The running program should support the following operations.

• Be able to read a file containing a sequence of line segments. Each line should have the format:

      x_1 y_1 x_2 y_2
  

  where (x_1,y_1) and (x_2,y_2) are the endpoints of the segment. Coordiantes are floating point numbers.
• Adding new line segments interactively by using the mouse.
• Intersections between segments are to be reported and visualized by small circles.
• Save the computed DCEL in a file.
• Restore a DCEL from a file.

A running program implementing the sweep line algorithm in [BKOS, Chapter 2] and a report is expected.

The project should be done in groups of up to three persons.

Deadline: Wednesday October 8, 2008, 9.15.

Important note: The evaluation of the report and implementation will be part of the final grade.