Version 1.0

SUMMARY: This project will implement part of the Kirkpatrick structure for point
location in a planar subdivision.  It is an alternative to the trapezoidal maps
discussed in class and is based on triangulations.  This approach was originally
published by Kirkpatrick 1983, but is perhaps best explained in the lecture
notes of Prof. David Mount: http://www.cs.umd.edu/class/fall2014/cmsc754/Lects/lectX04.pdf

DETAILS:
- The original Kirkpatrick algorithm is general enough to operate on any planar
subdivision by enclosing the subdivision in a triangle.  For the purposes of
this project we restrict our focus to planar subdivisions where the interior of
the subdivision is already a triangle and the exterior face of the subdivision
is the region outside the triangle.  As an additional simplification, we will
assume that the interior of the subdivision is a triangulation.  (The full
Kirkpatrick algorithm would triangulate the input subdivision and label the
triangles with faces of the original subdivision.)

- For us, the input is in the following format:
-- first line, just one integer, n (the number of points)
   each point has an ID from 1 to n; the half-edges have ID 1 to 6n-12;
   the triangles have ID from 1 to 2n-4. In the file, these objects
   appear in the order of their IDs
-- next n lines: two integers, a semicolon, followed possibly by an integer.
   the first two integers on line j+1 are meant to be the x and y-coordinates 
   of point  with ID j; the information after the semicolon 
   is useful only in the output.
-- next 6n-12 lines: four integers, followed by a semicolon, followed possibly
   by data we can ignore for this project. These four lines represents a
   half-edge of the plane triangulation, with the four integers being the
   origin ID (integer 1 to n), twin ID (integer 1 to 6n-12), next ID, and 
   triangle_ID (integer 1 to 2n-4).
-- next 2n-4 lines: one integer, followed by a semicolon, followed possibly 
   by several integers. The first integer represents the ID of one of the
   half-edges bordering the triangles. Half-edges go counter-clockwise
   around a face.

Data Structure Implementation:
Follow the guidelines on pages 3 and 4 of the lecture notes to implement the
Kirkpatrick structure.  While the query algorithm should be straightforward to
implement against your data structure, we will not implement the query in the
interest of limiting this project's scope. We will not implement the full
data structure, just two levels of it's levels.

I suggest the use of a geometry library
supporting WKT, polygons, geometric union, convex hull and triangulations.  One
such library is called JTS Topology Suite for Java. Another is at http://www.cgal.org/

Output File:
- The format of the output files will be the same as the format of the input
files, except for the information following the semicolon.
In the input, disregard everything after the semicolon.
In the output, for each vertex, include after the semicolon the ID of the
corresponding input vertex.  And for each face, include the ID of the
input faces intersected by this face.

Submit C++ or Java code, reading "input.txt" and writing "output.txt".
In addition, submit four different input files on which you tested your code.
If you have any questions, please contact the instructor.