2 Java methods and a sorting algorithm
**Hello all. ** I want to implement the Shamos algorithm using java an a couple of methods.I will provide the structure of the algorithm,the methods that I need to implement and other classes that I have at my disposal.Also I will share what I've written so far and any ideas that I may have. I'm new to java,hence why I need help, but I will try and be as concise an coherent with my post as possible.Therefore I require help if possible in implementing the code .Thank you
The algorithm:
-
If n ≤ 3 find the closest points by brute force and stop.
-
Find a vertical line V such that divides the input set into two disjoint subsets PL and PR of size as equal as possible . Points to the left or on the line belong PL and points to the right or on the line belong to PR. No point belongs to both since the sets are disjoint.
-
Recursively find the distance δL of a closest pair of points in PL and the distance δR of a closest pair in PR.
-
Let δ = min(δL, δR). The distance of a pair of closest points in the input set P is either that of the points found in the recursive step (i.e., δ) or consists of the distance between a point in PL and a point in PR. (a) The only candidate points one from PL and one from PR must be in a vertical strip consisting of a line at distance δ to the left of the line V and a line at distance δ to the right of V (b) Let YV be an array of the points within the strip sorted by non-decreasing y coordinate (i.e., if i ≤ j then YV [i] ≤ YV [j]). (c) Starting with the first point in YV and stepping trough all except the last, check the distance of this point with the next 7 points (or any that are left if there are not as many as 7). If a pair is found with distance strictly less than δ then assign this distance to δ.
-
Return δ. ->Bottom line is that,it uses a conceptual sweep line and recursion to find the closest points in the Euclidean space. ** Now the methods: ** •public static int closestPair(pointSet P). -this does methods the preparatory work for the recursive part of the algorithm and calls the method closestPairAux for the recursive part.
•public static int closestPairAux(Point [] X, Point [] Y). -this method carries out the recursive part of the algorithm; that is, the bulk of the work. Other methods and classes that I can use: -> A point is represented in the plane by an object of the class Point. This does the obvious thing; it holds the x and y coordinates as numbers so that if P is an object of type Point then P.x and P.y ->The set of input points is represented by an object of the class PointSet. As this is a set there can be no repetition of a point and we cannot assume any ordering on the elements.
• public static PointSet getPoints(String f). This opens a file called f and reads points from it.
• public Point nextPoint(PointSet P). This is used to iterate over the points in P The algorithm closestPair is implemented by the method
• public static Point closestPair(PointSet P).
- if n = 2 then return (x1 − x2)^2 + (y1 − y2)^2
- else
- d ← 0
- for i ← 1 to n − 1 do 5…. for j ← i + 1 to n do 6…….. t ← (xi − xj)^2 + (yi − yj)^2
- ………if t < d then
- …………..d ← t
- return d….the closestPair algorithm
•public static PointSet generatePoints(int n). This returns a set of n points, whose coordinates are integers.
•public Point[] sort(char c). This returns the points in the point set in an array sorted in non-decreasing order by coordinate as indicated by the parameter c. This parameter takes either the value ‘x’ or the value ‘y’, an exception UnknownSortOptionException is raised otherwise. ** This what I wrote so far:**
I decide that the first method should do the trivial case,n=<3, and then call the aux method.
throws TrivialClosestPairException, UnknownSortOptionException
{
int sqrDist = 0;// a method form the Poirnt class that calculate the square distance between this point and another point
Point[] x = P.sort('x');
Point[] x = P.sort('y');
if (P.size() <= 3) {
// the trivial case
sqrDist = PointSet.naiveClosestPair(P);
return sqrDist;
} else {
sqrDist = closestPairAux(x, y);
}
return sqrDist;
}```
****Is this method defined as it should?****
****An the second one:****
```markup
public static int closestPairAux(Point[] X, Point[] Y)
throws TrivialClosestPairException, UnknownSortOptionException
{
}```
****Which I need big time help on this one.**Any help?
**
****Thoughts:****
-call this method recursively, and the parameters are given as two sorted arrays, it is probably wise to divide the X array into two halves and call it recursively on each
-I shouldn't form Yv explicitely, so I guess I should iterate through all corresponding points in Y and if they are within Yv, then do the comparison for the smallest distance
-as for Y, I guess it is probably good to divide it as well, so I don't iterate through all points at each call but the divided Ys should probably contain corresponding points
like all points in Pl should also be in the corresponding half of the Y-array
****I'm new to java and any help will be great.Thank you in advance and thanks for your consideration of my post****
throws TrivialClosestPairException, UnknownSortOptionException
{
if (X.length<4){
return PointSet.naiveClosestPair(new PointSet (X));
}
int v = X[(int) Math.ceil(( (double) X.length/2)-1)].getX();
Point[] PL = Arrays.copyOfRange(X,(int) 0,(int) Math.ceil(X.length/2));
Point[] PR = Arrays.copyOfRange(X,(int) Math.floor(X.length/2), (int) X.length-1);
int d = Math.min(closestPairAux(PL,Y),closestPairAux(PR,Y));
Point[] shrtDist = new Point[Y.length];
int n = 0;
for (int i = 0; i <Y.length; i++)
{
int a = Y[i].getX();
if ((v-a)*(v-a) <= d)
{
shrtDist[n] = Y[i];
}
}
for (int i =0; i< shrtDist.length -1; i++)
{
for (int r = i+1; r <shrtDist.length-1 && r< i + 7; r ++){
d = Math.min(d, shrtDist[i].sqrDist(shrtDist[r]));
}
}
return d;
```
Be back later. Friends havin a drag show lol xD
Hello wasn't here actually suppose to be X instead of Y?
int n = 0;
for (int i = 0; i <Y.length; i++)
{
int A = X[i].getX();
if ((V-A)*(V-A) <= distance)
{
shortDist[n] = Y[i];
}
}
Or was it suppose to be ? code]Point[] shortDist = new Point[Y.length];
int n = 0;
for (int i = 0; i <Y.length; i++)
{
int A = Y[i].getY();--since V is the middle by X
if ((V-A)*(V-A) <= distance)
{
shortDist[n] = Y[i];
}
}
[/code] Also I took your advice and picked a nice spot to try and do it myself…I dit it…and I came up with something similar….so for example imagine the code from this page but without this part
int n = 0;
for (int i = 0; i <Y.length; i++)
{
int A = Y[i].getX();
if ((V-A)*(V-A) <= distance)
{
shortDist[n] = Y[i];
}
}
for (int i =0; i< shortDist.length -1; i++)
{
for (int r = i+1; r <shortDist.length-1 && r< i + 7; r ++){
d = Math.min(d, shortDist[i].sqrDist(shortDist[r]));
}
}```
And I get the same result...so my questions is what was the purpose of this part of the code?Since the min is computed here
```markupint d = Math.min(closestPairAux(PL,Y),closestPairAux(PR,Y));```
Thanks
I have a method that does the following thing. public static void getRuntimes(int p, int t, String f) does the following: (a) Generates p sets of points for various sizes starting from 10 (the sets are not random so that experiments are repeatable). (b) Finds a closest pair of points using naiveClosestPair and closestPair, and takes the cpu times for these. (c) Records the worst case times for each algorithm implementation taken over the p sets (note that it is pefectly possible that the worst case runtimes for the two algorithm implementations occur for different sets). (d) Repeats the above with sets of size 20, 30, … , 10t. (e) Outputs the result for each iteration on the file named f in the format input-set-size naiveClosestPair-worst-case-runtime ClosestPair-worst-case-runtime
When I create the following class
public class Tests {
public static void main(String [ ] args)
{
ClosestPair method = new ClosestPair();
method.getRuntimes(400, 10, "f");
}
}```
I get the error
Testing with 400 sets of 10 points .Exception in thread "main" java.lang.NullPointerException
What shoould I do.?