5 0.00 0.12 0.23 1.00 1.00 0.41 0.00 0.52 1.00 0.20 0.30 1.00 0.00 0.40 0.10 0.00 1.00 0.35 0.10 1.00 0.25 0.80 0.60 0.50 0.95 0.10 0.11 0.50
Input format. For simplicity, you may assume that all the lines cross the unit square (where both coordinates are between 0 and 1), and that you only have to work with points and line segments in that region. Use the following input format:
5 0.00 0.12 0.23 1.00 1.00 0.41 0.00 0.52 1.00 0.20 0.30 1.00 0.00 0.40 0.10 0.00 1.00 0.35 0.10 1.00 0.25 0.80 0.60 0.50 0.95 0.10 0.11 0.50 |
|
The input begins with an integer N, then N lines, each defined by four real numbers that give the endpoints of the line segments. Since they represent intersections with the edge of the unit square, each line segment endpoint has at least one coordinate with value 0 or 1. Following the N lines is a sequence of pairs of points (also four reals per input line).
You do not have to worry about handling all possible degenerate cases, but you shouldn't completely ignore them, either. Certainly you will want to get your program working on straightforward inputs before worrying about degenerate examples such as three lines intersecting in a point, or where precision in the calculation affects a decision. In your design, you should be cognizant of places where your program might be exposed to trouble for a degenerate case, whether or not you get around to fixing it up. In your readme.txt file, be sure to explain which kinds of input you have thought about.
A possible solution method. An arrangement is the planar subdivision defined by the lines. The diagram below is the arrangement for the set of lines given above. Every point in the unit square falls into some region; every region is bounded by some subset of the line segments. Your task is to be able to determine quickly whether or not two given input points fall into the same region or not.
One way to solve this problem is to build a binary tree with internal nodes corresponding to line segments and external nodes corresponding to regions in the plane, as shown in the example. This is similar to a 2D tree. A search in this tree involves comparing a point against the line segment at the root, then going left if it is on one side and right if it is on the other side. If the search for two points ends up at the same external node, they must be in the same region. There are at most N*N regions and one external node corresponding to each region, so we expect that the time should be proportional to log(N*N) = 2 log N for random data. Figuring out how to build this tree for arbitrary lines is the main challenge of this assignment.
Getting started. You will need some geometry primitives: a test whether a point is on one side of a line or the other and a routine to compute the intersection point of two lines. The former is essentially the ccw() function from lecture and the book. The latter requires some high-school geometry, coupled with some computer-science considerations having to do with precision and degenerate cases (lines consisting of a single point, parallel lines, and so forth).
Output. For each pair of query points, indicate whether or not they are separated by a line, and if they are, print out one such line. Also, instrument your program to count the number of external nodes and the average path length (external path length divided by number of external nodes) for the trees that you construct. Include a table with these numbers, and a discussion of how they grow, in your writeup.
Deliverables. Organize your program into natural modules, e.g., Point.java, LineSegment.java, and PointLocator.java. We will assume that your main client (that reads in the lines and processes the point pairs) is in PointLocator.java.