Zone-Theorem-on-Arrangement

Concepts:

Zone Theorem- The zone of a line L in an arrangement is the set of faces that L intersects.

In an arrangement of n lines the complexity of the zone of any line is O(n).

Arrangement of Lines- The arrangement of a set of lines is the subdivision of the plane by that set of lines.

Simple Arrangement- Arrangement of lines with no two lines being parallel, and no more than two lines intersecting at one point.

A Simple Arrangement has (n choose 2) vertices, n^2 edges, and (n choose 2) + n + 1 faces.

An arrangement can be constructed by an incremental algorithm. For each new line, 'l', we find the leftmost face, F, that 'l' intersects. Then we traverse the halfedges of F until we find the halfedgewhere 'l' leaves the face. We place a vertex at this point, and then we traverse the halfedges of the face on the other side of the intersected halfedge. The walk ends when 'l' exits the rightmost face it intersects. This construction of the arrangement takes O(n^2) time because for each of our n lines we add to the arrangement, we traverse O(n) halfedges of the faces it intersects.

Bounding Box- A box just large enough that it contains all intersections of lines in the arrangement. When a bounding box is constructed, all edges and faces of the arrangement become bounded.

Planar Straight Line Graph (PSLG)- A graph such that it can be embedded in a plane and all edges are straight lines. This means the graph can be drawn so that there is no line segments that intersect anywhere but at their endpoints.

Functions:

counter-clockwise test- Checks the orientation of three consecutive points a, b , c. Returns 1 if abc are oriented counter-clockwise. Returns -1 if abc is oriented clockwise. Returns 0 if abc are collinear.

Line Intersection Test- Given two lines with endpoints a1, a2 and b1, b2 respectively, these lines intersect if ccw(a1, a2, b1) and ccw(a1, a2, b2) have different orientations and if ccw(b1, b2, a1) and ccw(b1, b2, a2) have different orientations as well.

Data Structure: Half Edge (Doubly Connected Edge List)- Node- reference to arbitrary outgoing edge as well as coordinates in plane.

Face-
  reference to arbitrary incident edge
  
HalfEdge-
  reference to origin node, next halfedge in the current face, previous halfedge(optional), twin halfedge, and incident face

Tools: Processing 3

Plan: Program will begin by creating a bounding box of size determined by the Processing window size. Then a random number of lines will be generated. Each line will be guaranteed to intersect at least one line already in the plane in order to ensure an interesting arragement. Each line will have endpoints on the bounding box in order to simulate the construction of a bounding box around the intersections of an arrangement of lines of arbitrary size. As a line is added, the arrangement will be built incrementally using a simple walk that places vertices and halfedges. Once all lines are placed the final product will be a PSLG. The user will be able to add a line to this arrangement and the simple walk will be run again highlighting the path taken in order to add the line to the PSLG. The added line will automatically extend to have endpoints on the bounding box in order to simulate an unbounded line passing through the bounding box into the arrangement.