Start with that. Please post the stack trace of that exception

Solved

Posted on 2008-11-17

Can you guys look at my code and let me know how to improve it? I'm finding the closed set of points (X,Y) in 2D plane. I need to do it in O(n^2) and O(nlogn). O(n^2) was easy. My problems are on the Divide and Conquer approach. I've been up two days trying to do it, but I can't seem to get it right. I couldn't check my method completely because I got a null pointer exception when I sorted my array by the X-coordinate. I'm sure I'll have more errors. Also I'm not sure if this was the correct approach, I followed this:

http://www.cs.mcgill.ca/~cs251/ClosestPair/ClosestPairDQ.html

Also how do I keep track of which points are the closest ones..... my method only return the distance between the closest points

http://www.cs.mcgill.ca/~c

Also how do I keep track of which points are the closest ones..... my method only return the distance between the closest points

```
double dL;
double dR;
double d;
double stVal = Double.POSITIVE_INFINITY;
public double closestPoints(int l, int r)
{
if((r - l) ==2){
stVal=array[0].eucDist(array[1]); //eucDist computes distance between two points
return stVal;
}
if((r-l)<2){
stVal=stVal-1;
return stVal;
}
int median = (r-l)/2;
dL = closestPoints(l, median);
dR = closestPoints(median+1, r);
double d;
if(dL<=dR)
d=dL;
else
d=dR;
Point[] Y;
int n = 0;
//next two for loops compute the number of Points with X < = than d
for(int i = median; Math.abs(array[i].getX())<=d; i--){
n++;
}
for(int i=median+1; Math.abs(array[i].getX())<=d; i++){
n++;
}
Y = new Point[n];
int index = 0;
//next two for loops fill Y with points that have X value < = than d
for(int i = median; Math.abs(array[i].getX())<=d; i--){
Y[index]=array[i];
index++;
}
for(int i=median+1; Math.abs(array[i].getX())<=d; i++){
Y[index]=array[i];
index++;
}
Arrays.sort(Y, new Point.CompY()); //sort Y by increasing Y coordinate
double dY = Double.POSITIVE_INFINITY;
for(int i=0; i<=array.length-2; i++)
{
for(int j=i+1; j<=array.length-1; j++)
{
//xx, yy initialized alreay doubles xx = Math.pow((array[i].getX()-array[j].getX()), 2);
yy = Math.pow((array[i].getY()-array[j].getY()), 2);
dY = Math.sqrt(xx+yy);
if(dY < d)
{
d = dY;
}
}
}
return d;
}
-----------------------------------------------------------
public static void main(String[] args) {
MyClass class = new MyClass("Points.txt");
Arrays.sort(driver.array, new Point.CompX());
MyClass.closestPoints(0, MyClass.array.length);
```

4 Comments

Start with that. Please post the stack trace of that exception

Exception in thread "main" java.lang.ArrayIndexOutOfB

at project.myClass.closestPoi

at project.myClass.closestPoi

at project.myClass.closestPoi

at project.myClass.closestPoi

at project.myClass.closestPoi

at project.myClass.closestPoi

at project.myClass.closestPoi

at project.myClass.closestPoi

at project.myClass.closestPoi

at project.myClass.closestPoi

at project.FindPoints.main(cl

where line 131:

dL = closestPoints(l, median);

line 140:

dR = fcp(median+1, r);

line 14 on main class

myClass.closestPoints(0, myClass.array.length);

Title | # Comments | Views | Activity |
---|---|---|---|

Which XML parser should I used for my requirement | 11 | 49 | |

Unable to open debugger port in Intellij idea | 6 | 37 | |

word0 challenge | 3 | 30 | |

MS Access Customer Order Pickers Picking List Auto Choose Locations | 55 | 38 |

Join the community of 500,000 technology professionals and ask your questions.

Connect with top rated Experts

**19** Experts available now in Live!