Define the classes Point and CompareY in the same way as in programming exercise
ID: 671715 • Letter: D
Question
Define the classes Point and CompareY in the same way as in programming exercise 20.4.
Deine a class named Pair with the data fields p1 and p2 to represent two points, and a method named getDistance() that returns the distance between the two points.
Implement the follwoing methods,
Public static Pair getClosestPair(double[][] points)
public static Pair distance(Point[] pointsOrderedOnx, int low, int high, Point[]pointsOrderedOnY)
public static double distance(Point p1, Point p2)
public static double distance(double x1, double y1, double x2, double y2)
Explanation / Answer
Answer:
import java.util.*;
public class ClosestPair
{
public static class Point
{
public final double x;
public final double y;
public Point(double x,double y)
{
this.x=x;
this.y=y;
}
}
public static class Pair
{
public Point point1=null,point2=null;
public double distance=0.0;
Pair(Point point1,Point point2)
{
this.point1=point1;
this.point2=point2;
calculateDistance();
}
public void update(Point point1, Point point2, double distance)
{
this.point1=point1;
this.point2=point2;
this.distance=distance;
}
public void calculateDistance()
{
this.distance = distance(point1, point2);
}
public String toString()
{
return "("+point1+" , "+point2+") :"+distance;
}
}
public static double distance(Point p1, Point p2)
{
double xdist = p2.x - p1.x;
double ydist = p2.y - p1.y;
return Math.hypot(xdist, ydist);
}
public static void CompareY(List<? extends Point> points)
{
Collections.sort(points, new Comparator<Point>()
{
public int compare(Point point1, Point point2)
{
if(point1.y < point2.y)
return -1;
if(point1.y > point2.y)
return 1;
return 0;
}
});
}
public static void CompareX(List<? extends Point> points)
{
Collections.sort(points, new Comparator<Point>()
{
public int compare(Point point1, Point point2)
{
if(point1.x < point2.x)
return -1;
if(point1.x > point2.x)
return 1;
return 0;
}
});
}
public static Pair divideAndConquer(List<? extends Point> points)
{
List<Point> pointsSortedByX = new ArrayList<Point>(points);
CompareX(pointsSortedByX);
List<Point> pointsSortedByY = new ArrayList<Point>(points);
CompareY(pointsSortedByY);
return divideAndConquer(pointsSortedByX, pointsSortedByY);
}
private static Pair divideAndConquer(List<? extends Point> pointsSortedByX, List<? extends Point> pointsSortedByY)
{
int numPoints = pointsSortedByX.size();
int dividingIndex = numPoints >>> 1;
List<? extends Point> leftOfCenter = pointsSortedByX.subList(0, dividingIndex);
List<? extends Point> rightOfCenter = pointsSortedByX.subList(dividingIndex, numPoints);
List<Point> tempList = new ArrayList<Point>(leftOfCenter);
CompareY(tempList);
Pair closestPair = divideAndConquer(leftOfCenter, tempList);
tempList.clear();
tempList.addAll(rightOfCenter);
CompareY(tempList);
Pair closestPairRight = divideAndConquer(rightOfCenter, tempList);
if (closestPairRight.distance < closestPair.distance)
closestPair = closestPairRight;
tempList.clear();
double shortestDistance =closestPair.distance;
double centerX = rightOfCenter.get(0).x;
for (Point point : pointsSortedByY)
if (Math.abs(centerX - point.x) < shortestDistance)
tempList.add(point);
for (int i = 0; i < tempList.size() - 1; i++)
{
Point point1 = tempList.get(i);
for (int j = i + 1; j < tempList.size(); j++)
{
Point point2 = tempList.get(j);
if ((point2.y - point1.y) >= shortestDistance)
break;
double distance = distance(point1, point2);
if (distance < closestPair.distance)
{
closestPair.update(point1, point2, distance);
shortestDistance = distance;
}
}
}
System.out.println(closestPair);
return closestPair;
}
public static void main(String[] args)
{
Point[] points=new Point[5];
for(int i=0;i<points.length;i++)
{
points[i]=new Point(Math.random()*100,Math.random()*100);
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.