Computational Geometry (Fall 2006)

Project 3 - Finding the shortest path for a point robot

The goal is to be able to find a shortest path for a point robot in an environment of polygonal obstacles.

The running program should support the following operations.

• Read a set of polygons from a file. Each line should be the description of a closed polygon in clockwise order

    x_1 y_1 x_2 y_2 x_3 y_3 ... x_k y_k
  

• Input a start and end position of the robot interactively by using the mouse, and highlighting a shortest path for the robot between the two points.

A running program implementing of the algorithm in [BKOS, Chapter 15] is expected.

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

Deadline: Thursday Januar 11, 2007.

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

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: Thursday November 23, 2006, 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: Friday October 13, 2006, 11.15.

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