Computational Geometry (Fall 2010)

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 17, 2010, 23.59.

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₁ y₁ x₂ y₂
```
where (x₁,y₁) and (x₂,y₂) 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 8, 2010, 23.59.

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