First of all, familiarize yourself with the rules for the exam project.

Part 1 of the exam project is to implement the algorithm described in the textbook, Exercise 2.14.

Input to the program is a sequence of line segments, S, and a query point, p. The text output is a sequence (without duplicates) of all the line segments from S that are visible from p, as defined in the exercise. In addition, you must produce some graphical output that clearly shows the result of your computation, as described below. Remember to confer with the rules regarding data format. In test files, p should be specified on the first line and S on the subsequent lines.

You must use the half-line sweep technique suggested in the exercise and obtain the O(n log n) running time, with one exception described below. So, for the sweep, you should use an event queue and a status, as described in Chapter 2 of the textbook. You must use the overall design philosophy introduced in Chapter 1 of the textbook, i.e., you should first design your algorithm for input in so-called "general position", and only after that consider and handle special cases, preferably in the tests used by your algorithm. Your description of your implementation in your report must include a section on how the geometric tests you use are computed. Furthermore, special cases should be identified and tests should demonstrate that they are handled correctly.

See the rules below for further requirements.

 

---