This is in Java. Write a program that reads N points, specified by their 2D coor
ID: 3817397 • Letter: T
Question
This is in Java.
Write a program that reads N points, specified by their 2D coordinates, and outputs any set of four or more collinear points (i.e., points on the same line). The obvious brute-force algorithm requires O(N4) time. However, there is a better algorithm that makes use of sorting and runs in O(N2 log N) time.
Your program should read input from a text file called points.txt that is in the same directory as your java source and class files. The file should contain the coordinates of a set of points in the format shown below:
(2, 3) (4, 4) (-1, 2) (1, 0) (10, 10) (-1, 0) (3, 3) (-1, -1) (0, 1) (7, 5) (7, 8) (-4, 5) (9, 10)
You must use the name “points.txt” for your input file and you can hardcode the filename in your Java program. For testing we will use different sets of points in a file with the same name - “points.txt”.
The x and y coordinates of the points can be integers only.
Your program should calculate if there are any sets of four or more points that lie on the same line and output the sets. In the above example, there is a set of four points that lie on the line y = x, and, another set of five other points, that line on the line y = x+1. There is another set of four collinear points too – you could find that out.
Your program should determine these collinear point sets and output them in the format shown below. Note that in each set, points are sorted by their x-axis value.
Found these sets of four of more collinear points:
Set 1 (4 points): (-1, -1) (3, 3) (4, 4) (10, 10)
Set 2 (5 points): (-1, 0) (0, 1) (2, 3) (7, 8) (9, 10)
…
Explanation / Answer
--------------------------------------------------------------------
points.txt
(2, 3) (4, 4) (-1, 2) (1, 0) (10, 10) (-1, 0) (3, 3) (-1, -1) (0, 1) (7, 5) (7, 8) (-4, 5) (9, 10)
---------------------------------------------------------------------
Point.java
import java.util.Comparator;
public class Point implements Comparable<Point> {
private final int x; // x coordinate
private final int y; // y coordinate
// create the point (x, y)
public Point(int x, int y) {
this.x = x;
this.y = y;
}
public double slopeTo(Point r) {
// same point
if((r.y == this.y) && (r.x == this.x) )
return Double.NEGATIVE_INFINITY;
// vertical
if(r.x == this.x)
return Double.POSITIVE_INFINITY;
// horizontal
if(r.y == this.y)
return 0;
double d = r.y - this.y;
double n = r.x - this.x;
return d/n;
}
// comparing y-coordinates and breaking ties by x-coordinates
public int compareTo(Point that) {
if(this.y > that.y)
return 1;
else if(this.y < that.y)
return -1;
else if(this.x > that.x)
return 1;
else if(this.x < that.x)
return -1;
else
return 0;
}
public String toString() {
return "(" + x + ", " + y + ")";
}
}
---------------------------------------------------------------------
Brute.java
import java.util.*;
import java.io.*;
public class Brute {
private ArrayList<ArrayList<Point>> results;
private Point[] points;
public Brute(){
}
private Brute(Point[] points){
this.points = points;
collinear(points);
}
private void collinear(Point[] points){
results = new ArrayList<ArrayList<Point>>();
int l = points.length;
if(l<4){
return;
}
Arrays.sort(points);
for(int a=0; a<l; a++)
for(int b=a+1; b<l; b++)
for(int c=b+1; c<l; c++)
for(int d=c+1; d<l; d++){
double ab = points[a].slopeTo(points[b]);
double ac = points[a].slopeTo(points[c]);
double ad = points[a].slopeTo(points[d]);
if(ab == ac && ac == ad){
ArrayList<Point> p = new ArrayList<Point>();
p.add(points[a]);
p.add(points[b]);
p.add(points[c]);
p.add(points[d]);
for(int test=d+1; test<l; test++){
double test_slop = points[a].slopeTo(points[test - 1]);
for(int e=test; e<l; e++){
double ae = points[a].slopeTo(points[e]);
if(test_slop == ae) {
p.add(points[e]);
}
}
}
results.add(p);
}
}
}
private String toStr(){
StringBuilder sb = new StringBuilder();
int k = 1;
for(ArrayList<Point> alp : results){
boolean first = true;
sb.append("Set " + k + "(" + alp.size() + " points) : ");
k++;
for(Point p : alp){
if(!first)
sb.append(" ");
sb.append(p);
first = false;
}
sb.append(" ");
}
return sb.toString();
}
static Point[] readDataFromFile() {
Point[] points = null;
try{
File file = new File("./points.txt");
FileInputStream fis = new FileInputStream(file);
byte[] data = new byte[(int) file.length()];
fis.read(data);
fis.close();
String str = new String(data, "UTF-8");
str = str.replace(" ","");
str = str.replace(")("," ");
str = str.replace("(","");
str = str.replace(")","");
String[] pts = str.split(" ");
points = new Point[pts.length];
for(int i=0; i<pts.length; i++) {
String[] splt_pts = pts[i].split(",");
points[i] = new Point(Integer.parseInt(splt_pts[0]), Integer.parseInt(splt_pts[1]));
}
} catch (Exception e){
System.err.println("Error: " + e.getMessage());
}
return points;
}
public static void main(String[] args) {
Point[] points = readDataFromFile();
Brute p = new Brute(points);
System.out.println(p.toStr());
}
}
----------------------------------------------------------------
Output: java Brute
Set 1(4 points) : (-1, -1) (3, 3) (4, 4) (10, 10)
Set 2(5 points) : (-1, 0) (0, 1) (2, 3) (7, 8) (9, 10)
Set 3(4 points) : (-1, 0) (0, 1) (2, 3) (9, 10)
Set 4(4 points) : (-1, 0) (0, 1) (7, 8) (9, 10)
Set 5(4 points) : (-1, 0) (2, 3) (7, 8) (9, 10)
Set 6(4 points) : (1, 0) (0, 1) (-1, 2) (-4, 5)
Set 7(4 points) : (0, 1) (2, 3) (7, 8) (9, 10)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.