Need some help doing this java lab.
public class Point { private double x, y; private boolean visited; /** get the Euclidean distance between two points */ public double getDistance(Point other) { //TODO return 0.0; //replace } @Override public String toString() { //TODO return ""; } }
import java.io.File; import java.io.IOException; import java.util.Arrays; import java.util.Scanner;
public class Path { private Point[] points; private double minX, minY; //min X and Y values, for setting canvas scale private double maxX, maxY; //maxes
/** construct a path from a given file */ public Path(String fileName) { //TODO }
/** returns the distance traveled going point to point, in order given in file */ public double getDistance() { //TODO
return 0.0; //replace }
@Override public String toString() { //TODO
return ""; } }
Given a file containing a list of (two-dimensional) points, develop a program that does the following: Distance: 48349.38596394375 Computes the "bounding box" of the set of points. That is, find the lower-left coordinate ixi, yl) and upper- right coordinate (x2, y2) of a rectangle that contains all points in the file. Construct a path visiting each point exactly once. The path always starts from the first point in the file. You construct the path in a greedy fashion, always going next to the closest unvisited point. Compute the total distance of the greedy path you found through the points The lab folder contains some example input files, as well as a program you can use to graphically display your solution. Here is one of the provided input files, points7.txt: 1.0 -2.1. -2.0 2.6 -2.0 The first line in the file contains a number n, the number of points in the path. The next lines are the pairs of points (space-separated X- and Y-coordinates) that make up the "path". 1. Begin by completing the class Point.java (starter code for all dasses provided). An abstraction of a two-dimensional location (wrapping X-and Y-coordinates into an object), a Point can do the following: Construct a new Point Store and return its X and Y-coordinate Store and return if it has been visited (when traversing a path, i.e. a series of points) Return the Euclidean distance (see the FAQ in the lab folder for info) between this point and another Point supplied as a parameter Retum a String representation of thic Point (an overridden costring method) All instance variables should be private; you should provide public getters and setters when necessary. 2. Complete the class Path.java. The Path type is simply a series of points, along with some statistics about the path. A Path can do the following: Store the sequence and number of points that define it Construct a new Path using the supplied String (representing a particular file) Store and return the minimum and maximum X- and Y-coordinates in the path (used by the GUI to set the scale of the drawing) Retum the ith Point on the path (the Point at a particular index location) Retum the total distance traveled, going from Point to Point (in file order) Retum a String representation of this path (an overridden tostring method) When you are confident that your Path class is working, you can uncomment the test code in the provided DrawPath.java file. Make sure the text files are in the right location in the root / project folder, NOT the "src" folder). Drawing points7.txt" in file order should look like the image below; if nothing draws, check #2 in the FAQ first. In addition, here are the sequential (non-greedy) distances for some of the provided files: points? mona-90.txt 213599.txt 11.63111361520796 1966.869.595750689 3910559.236-292267 3. Create a class GreedyPath.java that extends Path. GreedyPath should add the following: The points (and their order) of a path using the gready algorithm described previously GreedyPath should NOT re-dedare Path's array points (doing so will "hide" the super- class variable). GreedyPath should declare its own array, and fill it with values from the super-cass' array (initialized in the super-class' constructor) An overridden gel Distance method that returns the total distance traveled when traversing a path using greedy decision making An overridden get point method (returns the point at a particular index from the greedy path, not the original path) An overridden tostring method We assume paths always start at the first point in the file. From there, the greedy path goes to the next closest point that has not already been visited. For example, in points7.txt, starting at 10.0, 1.0), the next closest point is (1.0, 1.0). From 11.0, 1.0), the next closest point would be (0.0, 1.0), but since we already visited this one, the next best one is 2.0, 0.0), and so on. 3 You need to figure out which point is closest, given your current location. In the event of a tie, you should use the point that occurs first in the file. You will also need to keep track of whether each point has been visited or not (use Point objects' visited field). GreedyPath should first utilize a super (I call to initialize the original" path. Next, write a private helper method void findPath() that will find and store the points that comprise the "greedy path" (the points in greedy order), as well as calculate and store the total distance traveled traversing the path in this fashion. You can assume the input file will be well-formed and contain at least one point. Here are the greedy distances for some of the provided files: points.txt usal 3509.txt 11.575491222501476 60618.72690198878 48349.38596394375 If you are confident that your code is working properly, modify DrawPath to use a GreedyPath object (rather than a Path object). The variable can stay of type Path (this is polymorphism at work). You can modify the delayMs variable to make the animation run faster or slower (a value of 0 will cause it to draw as soon as possible without animation). Examples: mona-20%.txt D11 points7.txt mona-20k.txt Given a file containing a list of (two-dimensional) points, develop a program that does the following: Distance: 48349.38596394375 Computes the "bounding box" of the set of points. That is, find the lower-left coordinate ixi, yl) and upper- right coordinate (x2, y2) of a rectangle that contains all points in the file. Construct a path visiting each point exactly once. The path always starts from the first point in the file. You construct the path in a greedy fashion, always going next to the closest unvisited point. Compute the total distance of the greedy path you found through the points The lab folder contains some example input files, as well as a program you can use to graphically display your solution. Here is one of the provided input files, points7.txt: 1.0 -2.1. -2.0 2.6 -2.0 The first line in the file contains a number n, the number of points in the path. The next lines are the pairs of points (space-separated X- and Y-coordinates) that make up the "path". 1. Begin by completing the class Point.java (starter code for all dasses provided). An abstraction of a two-dimensional location (wrapping X-and Y-coordinates into an object), a Point can do the following: Construct a new Point Store and return its X and Y-coordinate Store and return if it has been visited (when traversing a path, i.e. a series of points) Return the Euclidean distance (see the FAQ in the lab folder for info) between this point and another Point supplied as a parameter Retum a String representation of thic Point (an overridden costring method) All instance variables should be private; you should provide public getters and setters when necessary. 2. Complete the class Path.java. The Path type is simply a series of points, along with some statistics about the path. A Path can do the following: Store the sequence and number of points that define it Construct a new Path using the supplied String (representing a particular file) Store and return the minimum and maximum X- and Y-coordinates in the path (used by the GUI to set the scale of the drawing) Retum the ith Point on the path (the Point at a particular index location) Retum the total distance traveled, going from Point to Point (in file order) Retum a String representation of this path (an overridden tostring method) When you are confident that your Path class is working, you can uncomment the test code in the provided DrawPath.java file. Make sure the text files are in the right location in the root / project folder, NOT the "src" folder). Drawing points7.txt" in file order should look like the image below; if nothing draws, check #2 in the FAQ first. In addition, here are the sequential (non-greedy) distances for some of the provided files: points? mona-90.txt 213599.txt 11.63111361520796 1966.869.595750689 3910559.236-292267 3. Create a class GreedyPath.java that extends Path. GreedyPath should add the following: The points (and their order) of a path using the gready algorithm described previously GreedyPath should NOT re-dedare Path's array points (doing so will "hide" the super- class variable). GreedyPath should declare its own array, and fill it with values from the super-cass' array (initialized in the super-class' constructor) An overridden gel Distance method that returns the total distance traveled when traversing a path using greedy decision making An overridden get point method (returns the point at a particular index from the greedy path, not the original path) An overridden tostring method We assume paths always start at the first point in the file. From there, the greedy path goes to the next closest point that has not already been visited. For example, in points7.txt, starting at 10.0, 1.0), the next closest point is (1.0, 1.0). From 11.0, 1.0), the next closest point would be (0.0, 1.0), but since we already visited this one, the next best one is 2.0, 0.0), and so on. 3 You need to figure out which point is closest, given your current location. In the event of a tie, you should use the point that occurs first in the file. You will also need to keep track of whether each point has been visited or not (use Point objects' visited field). GreedyPath should first utilize a super (I call to initialize the original" path. Next, write a private helper method void findPath() that will find and store the points that comprise the "greedy path" (the points in greedy order), as well as calculate and store the total distance traveled traversing the path in this fashion. You can assume the input file will be well-formed and contain at least one point. Here are the greedy distances for some of the provided files: points.txt usal 3509.txt 11.575491222501476 60618.72690198878 48349.38596394375 If you are confident that your code is working properly, modify DrawPath to use a GreedyPath object (rather than a Path object). The variable can stay of type Path (this is polymorphism at work). You can modify the delayMs variable to make the animation run faster or slower (a value of 0 will cause it to draw as soon as possible without animation). Examples: mona-20%.txt D11 points7.txt mona-20k.txt
