All the code for this project is available at https://github.com/anirudh-c/plane-sweep
I use an AVL tree implementation for representing the event and status lists for the plane sweep
algorithm. The same base class BST can be used for both by just providing alternate priority functions
that define how two points (events) or line segments (status list) can be ordered.
Also, the brute force and plane sweep algorithms are inherited from the same class _Algorithm which
can be extended for any line segment intersection algorithm.
The program keeps track of every comparison made while computing the line intersection. In the brute
force algorithm, every pair of line segments is compared. On the other hand for the plane sweep
algorithm, at each event point
To illustrate this, the program visualises each comparison performed in the algorithm via the GUI. I
have provided a few instances of the visualisations of comparisons between line segments in the
casts/ folder.
I time the executions of both algorithms for the given test cases. I run the algorithms 100 times for
each test case file and average the running times. The corresponding script is time.sh and
the test case files are in the tests/ folder.
| Test | # Line Segments | # Intersections | Brute Force | Plane Sweep | ||
|---|---|---|---|---|---|---|
| / | < | < | < | < | < | > |
| test-1 | 8 | 7 | 0.6541 | 0.6416 | ||
| test-2 | 8 | 9 | 0.6708 | 0.656 | ||
| test-3 | 16 | 23 | 0.6622 | 0.6628 | ||
| test-4 | 30 | 20 | 0.6882 | 0.643 | ||
| test-5 | 36 | 40 | 0.67120 | 0.6698 |
There isn’t too much of an execution time difference (which I believe is to do with the AVL tree implementation using recursion, which is slower in python compared to loops).
The usage and details of the graphic interface are available at the repository link provided above and also in the README.