Usage and demonstration of the performance and effectiveness of essential data structures, generics, collections, and elementary sorting algorithms
Table of Contents
Lecture Slides & Presentation
Brute Collinear Points Implementation
Implemented using an algorithm that found all of the combinations (
N choose 4), not the permutations (number of tuples is
N^4), and then found the line segments by iterating through the combinations. Used Java’s built-in
Array utilities to naturally sort the points and to copy arrays as needed to maintain idempotency of certain operations.
Fast Collinear Points Implementation
FastCollinearPoints using the recursive Mergesort algorithm from the lecture slides. Implemented said algorithm using an auxiliary array. Didn’t use a cutoff to insertion sort when the sort array hit a certain size (7 was recommended) nor did I use a check to see if the sort array was already sorted. Decided that the improvements weren’t necessary since all performance requirements were met.
To decide if to add a found line segment, I compared the first point in the found line segment to the base point. If the two were equal, then I added the line segment. This ensured that a line segment was only added once while also not needing to check Point coordinates or the composition of existing line segments.
compareTo() method for a natural sort and used that method in a Comparator private class which was returned by the
slopeOrder() method. Implemented a
slopeTo() method to calculate the slope of two points.