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 coordinate is 0 or 1 in at least one coordinate. 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 input 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 lines 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 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 your main task for this assignment.
Part I - Write a program that reads an integer N, then N lines, and prints all the intersection points among those lines. Don't worry about the tree yet: just store all the lines in an array, and use a brute force approach to test every pair. To determine whether two lines intersect, you will want to use the ccw() function as described in class:
int ccw(Point p0,Point p1,Point p2) {
double dx1,dx2,dy1,dy2;
dx1=p1.x-p0.x; dy1=p1.y-p0.y;
dx2=p2.x-p0.x; dy2=p2.y-p0.y;
if (dx1*dy2 > dy1*dx2) return 1;
if (dx1*dy2 < dy1*dx2) return -1;
if ((dx1*dx2 < 0) || (dy1*dy2 < 0)) return -1;
if ((dx1*dx1+dy1*dy1) < (dx2*dx2+dy2*dy2)) return 1;
return 0;
}
Determining the actual point of intersection 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).
You might find it helpful to see the data graphically. Download and compile the program psout.c that generates PostScript commands.
Part II - Write a program that reads an integer N, N lines, and a sequence of points from an input file. 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. Use a data structure that cuts the number of lines to be tested down to be proportional to log N.
Part III - Instrument your program from Part II to count the number of nodes and the average path length (external path length divided by number of nodes) for the trees that you construct. Include a table with these numbers, and a discussion of how they grow, in your writeup.
What to Submit Submit only your final (Part III) version of the code. See the checklist for additional details about the requirements for your program and the readme file.
Extra Credit. Convert your program to print out the all sets of three or more points that are collinear in a set of N points. This is not as hard as it looks: by duality this is equivalent to finding the places where three or more of a set of N lines intersect. Take a point (a, b) to correspond to the line ax + by = 1.