
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.
x_1 y_1 x_2 y_2 x_3 y_3 ... x_k y_k
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.
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.
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.
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.
x_1 y_1 x_2 y_2where (x_1,y_1) and (x_2,y_2) are the endpoints of the segment. Coordiantes are floating point numbers.
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.