Introduction to Geometric Algorithms
1 Line segment intersection
Finding line segment intersections is a recurrent and important task in many Geographic
Information Systems (GIS); see Chapter 2 of de Berg et al. for more background infor-
mation (electronic copy available from the library). Your main goal in this assignment is
to implement the classical plane sweep algorithm for nding line segment intersections,
as described in Section 2.1 of de Berg et al.
Implement the plane sweep algorithm in C/C++ or Java. In the case of C/C++,
write a program and a corresponding make le named Makefile (note the upper case M)
with a make rule1 named planesweep that can be invoked in Linux2 as follows:
$ make planesweep
The output of the above invocation of make must be an executable binary named
planesweep.bin. The binary must be able to be run as follows:
$ ./planesweep.bin [path]
[path] is a string that speci es the path to a text le that contains a set of line segments.
The contents of the input text le must be formatted according to the following example:
46.205,94.214,45.787,94.045
71.216,85.612,53.743,75.88
50.756,81.158,52.802,72.426
65.314,91.667,66.928,71.732
49.354,93.535,64.343,80.294
1For a quick introduction to the make utility, consult https://cs.adelaide.edu.au/users/
second/spc/12s2-spc-adelaide/lectures/spc16-sys12.pdf.
2For consistency, ensure that you compile and test your program on a Linux machine in the labs.
Semester 2 2017 Page 1 by Tat-Jun Chin
Each line in the input text le corresponds to a line segment. There are four numbers in
each line separated by commas, where the rst two numbers are the x and y coordinates
of the start point of the segment, and the last two numbers are the x and y coordinates of
the end point of the segment. The output of planesweep.bin is the set of intersections
of the given input line segments, printed to the standard output (a.k.a. the command
prompt). For the given example input above, the output is
66.038,82.728
63.308,81.208
where each line contains the x and y coordinates of an intersection point.
In the case of Java, write your program in the le named planesweep.java. Your
program must be able to be compiled and run3 as follows:
$ javac planesweep.java
$ java planesweep [path]
The input and output speci cations/formatting are the same as above.
1.1 Input generation
You may use my Matlab program4 to generate random line segments as testing inputs
to your program. A sample input with 100 line segments and 20 intersections generated
using my program is as follows:
0 10 20 30 40 50 60 70 80 90 1000
3For consistency, ensure that you compile and test your program on a Linux machine in the labs.
4https://cs.adelaide.edu.au/~tjchin/linesegments.zip
Semester 2 2017 Page 2 by Tat-Jun Chin
1.2 Degeneracy
For this assignment, you may assume that there are no degeneracies in the input line
segments. Speci cally, you may assume that
No start or end points have the same x or y coordinates.
No more than 2 line segments intersect at an intersection point.
1.3 Correctness of output
Ensure to check the correctness of your calculated intersection points by comparing with
the results of the O(N2) brute force method.
1.4 Output sensitivity
An important characteristic of the operation of plane sweep is the sensitivity of its
runtime to the number of intersection points. Speci cally, the complexity of plane
sweep for line segment intersection is O(N logN + klogN), where N is the number of
input line segments, and k is the number of intersections.
To verify that your implementation has the above complexity, conduct the following
two experiments:
Fix N to a suitable number (say, 200), then vary k = 1;2;::: until a suitably
large number. For each (N;k) combination, generate a suitable number (say, 20)
of input sets using the provided Matlab code. Subject each input set to your
program, and record the runtime. Then, calculate the average runtime for each
k, and plot the average runtime as a function of k in a graph. Verify that the
curve can be bounded closely from above by the curve (N logN +klogN) for a
suitable (remember also to plot this bounding curve).
Repeat the above experiment, but this time x k (say, to 20) and vary N. Again,
plot the average runtime and compare against the theoretical bound.
1.5 Web submission
Submit via the Web Submission System
All the les required to make/compile your code into an executable binary.
Semester 2 2017 Page 3 by Tat-Jun Chin
A PDF document containing the two graphs resulting from you experiments in
Section 1.4.
Store the assignment under your own SVN repository in the path
2017/s2/iga/Assignment1
The link to the Web Submission System used for this assignment is
https://cs.adelaide.edu.au/services/websubmission/
2 Due date and submission policy
This assignment is due by 11:59pm Wednesday 23 August. If your submission is
late the maximum mark you can obtain will be reduced by 25% per day (or part thereof)
past the due date or any extension you are granted.
3 Using other source code and libraries
You may use external C/C++ or Java libraries for balanced binary trees. However,
other aspects relating to the plane sweep algorithm must be implemented by yourself
without using or referencing external libraries/source codes.
4 Grading
I will manually run your code on di erent tests, and examine the graphs resulting from
your experiments. If it passes all tests you will get 25% of the overall course mark. There
will be no marks awarded on the basis of coding style, \amount" of code/comments
written, or assertions of \understanding".