import java.util.Comparator;

/** * Point.java. * Models a two dimensional point as a Cartesian coordinate (x, y) * in Quadrant I (x >= 0 and y >= 0). This class is designed to be * immutable. * * @author: Dean Hendrix (dh@auburn.edu) * @version: 2017-02-08 * */ public final class Point implements Comparable {

/** Compare two points with respect to the slope each makes with this point. */ public final Comparator slopeOrder = new ComparePointsBySlope();

/** x,y coordinates of this point. */ private final int x; private final int y;

/** * Create a point from the given x and y coordinates. If either x or y is * negative, throw an IllegalArgumentException. */ public Point(int x, int y) { this.x = 0; this.y = 0; }

/** * Return a string representation of this point. * * THIS METHOD IS PROVIDED FOR YOU AND MUST NOT BE CHANGED. */ @Override public String toString() { return "(" + x + ", " + y + ")"; }

/** * Indicates whether some object is equal to this Point. A Point (x1, y1) is * equal to this Point (x0, y0) if and only if x0 == x1 and y0 == y1. All * six properties of the equals method specified in the Object class are * met. * * THIS METHOD IS PROVIDED FOR YOU AND MUST NOT BE CHANGED. */ @Override public boolean equals(Object obj) { if (obj == null) { return false; } if (obj == this) { return true; } if (!(obj instanceof Point)) { return false; } Point that = (Point) obj; return (this.x == that.x) && (this.y == that.y); }

/** * Compares this point with the specified point for order. Returns a * negative integer, zero, or a positive integer if this point is less * than, equal to, or greater than the specified point. Points are ordered * first by y value and then by x value. All three properties of compareTo * as specified in the Comparable interface are met, and this * implementation is consistent with equals. */ @Override public int compareTo(Point that) { int x0 = x, x1 = that.x, y0 = y, y1 = that.y; if (y0

/** * Computes the slope of the line segment between this point (x0, y0) and * the specified point (x1, y1). Slope is computed as (y1 - y0) / (x1 - x0), * so the direction of the slope is from this point to the specified point. * The slope of a horizontal line segment is positive zero; the slope of a * vertical line segment is positive infinity; the slope of a degenerate * line segment (where this point and the specified point are the same) is * negative infinity. */ public double slopeTo(Point that) { if (that.x == x && that.y == y) return Double.NEGATIVE_INFINITY; double dx = that.x - x, dy = that.y - y; if (dy == 0.0) return +0.0; if (dx == 0.0) return Double.POSITIVE_INFINITY; return dy / dx; } /** * Defines a total order for Points based on the slope that two specified points * make with this point. */ private class ComparePointsBySlope implements Comparator { /** * Compares two specified points p1 and p2 for order. Returns a negative * integer, zero, or a positive integer if p1 is less than, equal to, or * greater than p2. All three properties of the compare method as * specified in the Comparator interface are met. */ @Override public int compare(Point p1, Point p2) { if (slopeTo(p1) slopeTo(p2) || (slopeTo(p1) == slopeTo(p2) && p1.compareTo(p2) == 1)) return 1; else return 0; } } }

import java.util.Collection; import java.util.Iterator; import java.util.SortedSet; import java.util.TreeSet;

/** * Line.java * Models a line segment as a sorted set of points. * * @author Dean Hendrix (dh@auburn.edu) * @version 2017-02-08 * */ public class Line implements Comparable, Iterable { SortedSet line; /** * Creates a new line containing no points. * * THIS METHOD IS PROVIDED FOR YOU AND MUST NOT BE CHANGED. */ public Line() { line = new TreeSet(); } /** * Creates a new line with containing all distinct collinear points in the * Collection c. */ public Line(Collection c) {

} /** * Adds the point p to this line if p is collinear with all points already * in the line and p itself is not already in the line. Returns true if this * line is changed as a result, false otherwise. */ public boolean add(Point p) { return false; } /** * Returns the first (minimum) point in this line or null if this line * contains no points. */ public Point first() { return null; } /** * Returns the last (maximum) point in this line or null if this line * contains no points. */ public Point last() { return null; } /** * Returns the number of points in this line. */ public int length() { return -99; }

/** * Compares this line with the specified line for order. Returns a negative * integer, zero, or a positive integer if this line is less than, equal to, * or greater than the specified line. Lines are ordered first by their * first point then by their last point. An empty line is less than any * non-empty line, and all empty lines are equal. All three properties of * compareTo as specified in the Comparable interface are met, and this * implementation is consistent with equals. */ @Override public int compareTo(Line that) { return -99; }

/** * Provide an iterator over all the points in this line. The order in which * points are returned must be ascending natural order. */ @Override public Iterator iterator() { return null; } /** * Return true if this line's first and last points are equal to the * parameter's first and last points. Empty lines are equal to each other * but are not equal to any non-empty line. * * THIS METHOD IS PROVIDED FOR YOU AND MUST NOT BE CHANGED. */ @Override public boolean equals(Object obj) { if (obj == null) { return false; } if (obj == this) { return true; } if (!(obj instanceof Line)) { return false; } Line that = (Line) obj; if ((this.length() == 0) && (that.length() == 0)) { return true; } if ((this.length() == 0) && (that.length() != 0)) { return false; } if ((this.length() != 0) && (that.length() == 0)) { return false; } return (this.first().equals(that.first())) && (this.last().equals(that.last())); } /** * Return a string representation of this line. * * THIS METHOD IS PROVIDED FOR YOU AND MUST NOT BE CHANGED. */ @Override public String toString() { if (length() == 0) { return ""; } StringBuilder s = new StringBuilder(); for (Point p : line) { s.append(p + " -> "); } s = s.delete(s.length() - 4, s.length()); return s.toString(); } }

import java.io.File; import java.util.Arrays; import java.util.Collection; import java.util.Iterator; import java.util.Scanner; import java.util.SortedSet; import java.util.TreeSet;

/** * Extractor.java. Implements feature extraction for collinear points in * two dimensional data. * * @author Dean Hendrix (dh@auburn.edu) * @version 2017-02-08 * */ public class Extractor { /** raw data: all (x,y) points from source data. */ private Point[] points; /** lines identified from raw data. */ private SortedSet lines; /** * Builds an extractor based on the points in the file named by filename. */ public Extractor(String filename) {

} /** * Builds an extractor based on the points in the Collection named by pcoll. * * THIS METHOD IS PROVIDED FOR YOU AND MUST NOT BE CHANGED. */ public Extractor(Collection pcoll) { points = pcoll.toArray(new Point[]{}); } /** * Returns a sorted set of all line segments of exactly four collinear * points. Uses a brute-force combinatorial strategy. Returns an empty set * if there are no qualifying line segments. */ public SortedSet getLinesBrute() { lines = new TreeSet(); return lines; } /** * Returns a sorted set of all line segments of at least four collinear * points. The line segments are maximal; that is, no sub-segments are * identified separately. A sort-and-scan strategy is used. Returns an empty * set if there are no qualifying line segments. */ public SortedSet getLinesFast() { lines = new TreeSet(); return lines; } }

import java.util.Arrays; import java.util.SortedSet;

/** * ExtractorClient.java. * Demonstrates feature extraction on sample data. * * @author Dean Hendrix (dh@auburn.edu) * @version 2017-02-08 */ public class ExtractorClient {

/** Sample point data. */ private static Point[] p = new Point[] { // l1 new Point(1, 0), new Point(1, 1), new Point(1, 2), new Point(1, 3), new Point(1, 4), // l2 new Point(3, 0), new Point(3, 1), new Point(3, 2), new Point(3, 3), new Point(3, 4), // l3 new Point(30, 5), new Point(31, 5), new Point(32, 5), new Point(33, 5), new Point(34, 5), // l4 new Point(30, 6), new Point(31, 6), new Point(32, 6), new Point(33, 6), new Point(34, 6), // l5 new Point(15, 9), new Point(16, 10), new Point(17, 11), new Point(18, 12), new Point(19, 13), // l6 new Point(19, 9), new Point(18, 10), /ew Point(17, 11), appears in l5 above; don't want duplicate new Point(16, 12), new Point(15, 13), };

/** * Drives execution. */ public static void main(String[] args) { Extractor cl = new Extractor(Arrays.asList(p)); SortedSet bruteLines = cl.getLinesBrute(); System.out.println("Brute: "); printLines(bruteLines); SortedSet fastLines = cl.getLinesFast(); System.out.println("Fast: "); printLines(fastLines); } /** * Prints an enumeration of the given set of lines. */ private static void printLines(SortedSet lines) { int count = 0; for (Line line : lines) { System.out.println(++count + ": " + line); } System.out.println(); } }

/*

Brute: 1: (1, 0) -> (1, 1) -> (1, 2) -> (1, 3) 2: (1, 0) -> (1, 1) -> (1, 2) -> (1, 4) 3: (3, 0) -> (3, 1) -> (3, 2) -> (3, 3) 4: (3, 0) -> (3, 1) -> (3, 2) -> (3, 4) 5: (1, 1) -> (1, 2) -> (1, 3) -> (1, 4) 6: (3, 1) -> (3, 2) -> (3, 3) -> (3, 4) 7: (30, 5) -> (31, 5) -> (32, 5) -> (33, 5) 8: (30, 5) -> (31, 5) -> (32, 5) -> (34, 5) 9: (31, 5) -> (32, 5) -> (33, 5) -> (34, 5) 10: (30, 6) -> (31, 6) -> (32, 6) -> (33, 6) 11: (30, 6) -> (31, 6) -> (32, 6) -> (34, 6) 12: (31, 6) -> (32, 6) -> (33, 6) -> (34, 6) 13: (15, 9) -> (16, 10) -> (17, 11) -> (18, 12) 14: (15, 9) -> (16, 10) -> (17, 11) -> (19, 13) 15: (19, 9) -> (18, 10) -> (17, 11) -> (16, 12) 16: (19, 9) -> (18, 10) -> (17, 11) -> (15, 13) 17: (16, 10) -> (17, 11) -> (18, 12) -> (19, 13) 18: (18, 10) -> (17, 11) -> (16, 12) -> (15, 13)

Fast: 1: (1, 0) -> (1, 1) -> (1, 2) -> (1, 3) -> (1, 4) 2: (3, 0) -> (3, 1) -> (3, 2) -> (3, 3) -> (3, 4) 3: (30, 5) -> (31, 5) -> (32, 5) -> (33, 5) -> (34, 5) 4: (30, 6) -> (31, 6) -> (32, 6) -> (33, 6) -> (34, 6) 5: (15, 9) -> (16, 10) -> (17, 11) -> (18, 12) -> (19, 13) 6: (19, 9) -> (18, 10) -> (17, 11) -> (16, 12) -> (15, 13)

*/

Identifying Line Segments in 2D Data COMP 2210 Assignment Problem Overview This assignment will explore an example feature ertraction problem. Feature extraction is a subproblem of pattern recognition and is also used in areas such as statistical analysis, computer vision, and image processing. For example, an image processing problem may use a feature extraction algorithm t identity particular shapes or regions in a digitized image In this assignment, we're going to focus on a very simple feature extraction problem: Given a set of points in two-dimensional space, identify every subset of four or more points that are collinear. For example, given the set of points depicted in Figure 1 your program would detect the three groups of collinear points as depicted by the line segments in Figure 2 5 2 1 3 4 6 7 8 3 5 6 7 8 Figure 2: Three collinear groups identified. Figure 1: A set of 13 points As always, we want our solution to be useful at scale. For example, Figure 3 plots 100,000 points and Figure 4 shows the 34 collinear groups identified by blue line segments. Each collinear group in Figure 4 is composed of far more than four points; four is just the minimum number of points to qualify for the collinear pattern that we're looking for. In the general problem statement we will refer to line segments instead of collinear groups, where each line segment must contain at least four points Problem Statement: Given a set of N distinct points in Quadrant I of the Cartesian plane, identify every line segment that connects a subset of four or more of the points. Each point will be specified as an (ar, y) pair where r and y are non-negative int values. For example, the thirteen points in Figures 1 and 2 are: (1,7), (2, 2), (2, 5 (3, 1), (4, 4), (5, 3), (5, 6), (6, 6), (7, 1), (7, 3), 7, 4), (7,9), 8, 8) You must solve this problem in terms of the classes and methods described in the following sections. Identifying Line Segments in 2D Data COMP 2210 Assignment Problem Overview This assignment will explore an example feature ertraction problem. Feature extraction is a subproblem of pattern recognition and is also used in areas such as statistical analysis, computer vision, and image processing. For example, an image processing problem may use a feature extraction algorithm t identity particular shapes or regions in a digitized image In this assignment, we're going to focus on a very simple feature extraction problem: Given a set of points in two-dimensional space, identify every subset of four or more points that are collinear. For example, given the set of points depicted in Figure 1 your program would detect the three groups of collinear points as depicted by the line segments in Figure 2 5 2 1 3 4 6 7 8 3 5 6 7 8 Figure 2: Three collinear groups identified. Figure 1: A set of 13 points As always, we want our solution to be useful at scale. For example, Figure 3 plots 100,000 points and Figure 4 shows the 34 collinear groups identified by blue line segments. Each collinear group in Figure 4 is composed of far more than four points; four is just the minimum number of points to qualify for the collinear pattern that we're looking for. In the general problem statement we will refer to line segments instead of collinear groups, where each line segment must contain at least four points Problem Statement: Given a set of N distinct points in Quadrant I of the Cartesian plane, identify every line segment that connects a subset of four or more of the points. Each point will be specified as an (ar, y) pair where r and y are non-negative int values. For example, the thirteen points in Figures 1 and 2 are: (1,7), (2, 2), (2, 5 (3, 1), (4, 4), (5, 3), (5, 6), (6, 6), (7, 1), (7, 3), 7, 4), (7,9), 8, 8) You must solve this problem in terms of the classes and methods described in the following sections