Hi gurus, this is a homework assignment on finding all closest pairs. I used a quad tree for my algorithm and its running time is compared to the naive algorithm. (I didn't use the java quad tree because I didn't know it existed...) My problem right now is that after I run my algorithm, it takes a long time to print the result. Naive algorithm's printing time reflects the time it took to run but my algorithm seems to take a much longer time compared to the reported runtime. ie. it reports taking 170 ms but wait 2 minutes before printing it. I'm not sure if I have memory leaks or something but it stops working if #of points exceeds 50k. Thanks in advance.
import java.util.*;
import java.lang.*;
import java.io.*;
class My2dPoint {
double x;
double y;
public My2dPoint(double x1, double y1) {
x=x1;
y=y1;
}
}
class qNode {
qNode LT;
qNode RT;
qNode LB;
qNode RB;
My2dPoint rep;
My2dPoint point;
double lMost;
double rMost;
double tMost;
double bMost;
int depth;
public qNode (double rmost, double lmost, double tmost, double bmost, My2dPoint r, My2dPoint p){
lMost=lmost;
rMost=rmost;
tMost=tmost;
bMost=bmost;
rep=r;
point=p;
LT=null;
RT=null;
LB=null;
RB=null;
}
}
class CompareByX implements Comparator<My2dPoint> {
public int compare(My2dPoint p1, My2dPoint p2) {
if (p1.x < p2.x) return -1;
if (p1.x == p2.x) return 0;
return 1;
}
}
class CompareByY implements Comparator<My2dPoint> {
public int compare(My2dPoint p1, My2dPoint p2) {
if (p1.y < p2.y) return -1;
if (p1.y == p2.y) return 0;
return 1;
}
}
/* An object of the above comparator class is used by java.util.Arrays.sort() in main to sort an array of points by x-coordinates */
class Auxiliaries {
public static double distSquared(My2dPoint p1, My2dPoint p2) {
double result;
result = (p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y);
if(result == 0){
result = Double.MAX_VALUE;
}
return result;
}
public static qNode makeRoot(My2dPoint [] list,int depth){
//System.out.println("MakeRoot()" );
if(list.length>=1){
CompareByY d = new CompareByY();
java.util.Arrays.sort(list,d);
double bMost=list[0].y;
double tMost=list[list.length-1].y;
CompareByX c = new CompareByX();
java.util.Arrays.sort(list,c);
double lMost=list[0].x;
double rMost=list[list.length-1].x;
qNode root = new qNode(rMost,lMost, tMost,bMost,list[0],null);
//makeQuadTree(list,root,0);
if(list.length>1){
makeQuadTree(list,root,depth);
}
return root;
}
else
return null;
}
public static void makeQuadTree(My2dPoint [] list, qNode root,int level){
//System.out.println("makeQuadTree()" );
//divide into 4 blocks and create sub tree
double bMost=root.bMost;
double tMost=root.tMost;
double lMost=root.lMost;
double rMost=root.rMost;
ArrayList<My2dPoint> list1 = new ArrayList<My2dPoint>();
ArrayList<My2dPoint> list2 = new ArrayList<My2dPoint>();
ArrayList<My2dPoint> list3 = new ArrayList<My2dPoint>();
ArrayList<My2dPoint> list4 = new ArrayList<My2dPoint>();
double xmid=(rMost-lMost)/2.0+lMost;
double ymid=(tMost-bMost)/2.0+bMost;
for(int i=0;i<list.length;i++){
if(list[i].x < xmid){
if(list[i].y<ymid)
list1.add(list[i]);
else
list3.add(list[i]);
}
else{
if(list[i].y<ymid)
list2.add(list[i]);
else{
list4.add(list[i]);
//System.out.println("List4 add:" +list[i].x +" "+list[i].y+"root.bMost:"+root.bMost);
}
}
}
//System.out.println("---List 1:"+list1.size()+" List 2:"+list2.size()+" List 3:"+list3.size()+" List 4:"+list4.size() +" 4bMost:"+root.bMost +" tMost:"+root.tMost+" rMost:"+root.rMost+" lMost:"+root.lMost );
//root.depth++;
root.LT=makeNode(root,list1,1);
root.RT=makeNode(root,list2,2);
root.LB=makeNode(root,list3,3);
root.RB=makeNode(root,list4,4);
if(root.depth<level){
level = root.depth;
}
}
public static qNode makeNode(qNode root, ArrayList <My2dPoint> tlist,int position){
//System.out.println("MakeNode():"+position );
My2dPoint [] list = tlist.toArray(new My2dPoint [tlist.size()]);
double xmid=(root.rMost-root.lMost)/2.0+root.lMost;
double ymid=(root.tMost-root.bMost)/2.0+root.bMost;
double bMost;
double tMost;
double lMost;
double rMost;
if(position==1){
bMost=root.bMost;
tMost=ymid;
lMost=root.lMost;
rMost=xmid;
//System.out.println("MakeNode() : 1tMost:"+tMost +" rMost:"+rMost );
}
else if(position==2){
bMost=root.bMost;
tMost=ymid;
lMost=xmid;
rMost=root.rMost;
//System.out.println("MakeNode() : 2tMost:"+tMost +" rMost:"+rMost );
}
else if(position==3){
bMost=ymid;
tMost=root.tMost;
lMost=root.lMost;
rMost=xmid;
//System.out.println("MakeNode() : 3tMost:"+tMost +" rMost:"+rMost );
}
else{
bMost=ymid;
tMost=root.tMost;
lMost=xmid;
rMost=root.rMost;
//System.out.println("MakeNode() : 4bMost:"+bMost +" tMost:"+tMost+" rMost:"+rMost+" lMost:"+lMost );
}
//if size ==0
qNode node = null;
if(list.length==0){
node = new qNode(rMost,lMost, tMost,bMost,null,null);
node.depth = root.depth+1;
//System.out.println("*MakeNode() 0 Only : rootdepth:" +node.depth );
}
else if(list.length==1){
node = new qNode(rMost,lMost, tMost,bMost,list[0],list[0]);
node.depth = root.depth+1;
//System.out.println("*MakeNode() 1 ONLY : rootdepth:" +node.depth );
}
else{
node = new qNode(rMost,lMost, tMost,bMost,list[0],null);
node.depth = root.depth+1;
//System.out.println("***MakeNode() RR : rootdepth:" +node.depth+"4bMost:"+bMost +" tMost:"+tMost+" rMost:"+rMost+" lMost:"+lMost );
makeQuadTree(list,node,node.depth);
}
return node;
}
public static void printTree(qNode root){
StringBuffer b = new StringBuffer();
for(int i=0;i < root.depth;i++){
b.append('-');
}
System.out.print("\n"+b.toString());
if(root!=null){
System.out.print("Depth:"+root.depth+" rep:");
if(root.rep != null){
System.out.print(" rep:" + root.rep.x + " "+root.rep.y);
}
if(root.point != null){
System.out.print(" point:" + root.point.x + " "+root.point.y);
}
if(root.LT!=null){
printTree(root.LT);
printTree(root.RT);
printTree(root.LB);
printTree(root.RB);
}
else
System.out.print("*no children ");
}
}
public static void closestPairs(My2dPoint [] points, qNode root, My2dPoint [] closest){
ArrayList<qNode> candidates = new ArrayList<qNode>();
candidates.add(root);
//for here
for(int i =0; i<points.length;i++){
//System.out.println("**looking for ("+i+") pair: "+points[i].x +" "+points[i].y);
closest[i]=query(points[i],candidates,0);
}
/*
for (int i = 0; i < closest.length; i++) {
System.out.println("!!Closest pair!! " + i + ": " +points[i].x + " " + points[i].y + " closest is( " + closest[i].x +", "+closest[i].y + " )");
}
*/
}
public static My2dPoint query(My2dPoint point, ArrayList<qNode> roots,int level){
//find closest representative point
int curlevel=0;
double minDist=Double.MAX_VALUE;//=distSquared(point,roots.get(0).rep);
double tmpDist=0.0;
My2dPoint curPoint=null;//= roots.get(0).rep;
for(int i=0;i<roots.size();i++){
if(roots.get(i).rep!=null){
//System.out.println("^rep point: "+roots.get(i).rep.x+ " "+roots.get(i).rep.y+ " minDist: "+minDist+ " tmpDist:"+tmpDist);
tmpDist=distSquared(point,roots.get(i).rep);
if(minDist > tmpDist){
//System.out.println("^^rep point: "+roots.get(i).rep.x+ " "+roots.get(i).rep.y+ " minDist: "+minDist+ " tmpDist:"+tmpDist);
minDist=tmpDist;
curPoint=roots.get(i).rep;
//System.out.println("^^^rep point: "+curPoint.x+ " "+curPoint.y+ " minDist: "+tmpDist+ " minDist: "+minDist+ " tmpDist:"+tmpDist);
}
}
}
//System.out.println("minimum distance is: "+minDist+ " ");
//Find boxes for next level
ArrayList<qNode> candidates = new ArrayList<qNode>();
for(int i=0;i<roots.size();i++){
if(roots.get(i).rep!=null && roots.get(i).point == null){
curlevel=roots.get(i).LT.depth;
//System.out.println("Checking next level: "+curlevel);
//Box1 LT
if(roots.get(i).LT.rep != null &&point.x<roots.get(i).LT.rMost + minDist && point.x>roots.get(i).LT.lMost - minDist && point.y >roots.get(i).LT.bMost - minDist&&point.y<roots.get(i).LT.tMost + minDist){
candidates.add(roots.get(i).LT);
}
//Box2 RT
if(roots.get(i).RT.rep != null &&point.x<roots.get(i).RT.rMost + minDist && point.x>roots.get(i).RT.lMost - minDist && point.y >roots.get(i).RT.bMost - minDist&&point.y<roots.get(i).RT.tMost + minDist){
candidates.add(roots.get(i).RT);
}
//Box3 LB
if(roots.get(i).LB.rep != null &&point.x<roots.get(i).LB.rMost + minDist && point.x>roots.get(i).LB.lMost - minDist && point.y >roots.get(i).LB.bMost - minDist&&point.y<roots.get(i).LB.tMost + minDist){
candidates.add(roots.get(i).LB);
}
//Box4 RB
if(roots.get(i).RB.rep != null &&point.x<roots.get(i).RB.rMost + minDist && point.x>roots.get(i).RB.lMost - minDist && point.y >roots.get(i).RB.bMost - minDist&&point.y<roots.get(i).RB.tMost + minDist){
candidates.add(roots.get(i).RB);
}
}
else if(roots.get(i).rep!=null && roots.get(i).point != null){
candidates.add(roots.get(i));
//curPoint=roots.get(i).point;
//System.out.println("minimum distance is: "+minDist+ " ");
//System.out.println("closest is( " + curPoint.x +", "+curPoint.y + " )");
}
else{
//System.out.println("root "+i+" is null");
}
}
//System.out.println("--List length: "+candidates.size()+"level: "+level +" curlevel: "+curlevel);
if(curlevel != level){
/*for(int i =0; i< candidates.size();i++){
System.out.println("##"+candidates.get(i).depth+" deep "+i+" position : "+candidates.get(i).rep.x+" "+candidates.get(i).rep.y);
}
*/
curPoint=query(point,candidates,level++);
}
//System.out.println("%%%%closest is( " + curPoint.x +", "+curPoint.y + " )");
return curPoint;
}
}
public class HW3 {
public static void main (String argv []) throws IOException {
int range = 1000000; // Range of x and y coordinates in points
System.out.println("Enter the number of points");
InputStreamReader reader1 = new InputStreamReader(System.in);
BufferedReader buffer1 = new BufferedReader(reader1);
String npoints = buffer1.readLine();
int numpoints = Integer.parseInt(npoints);
// numpoints is now the number of points we wish to generate
My2dPoint inputpoints [] = new My2dPoint [numpoints];
// array to hold points
int closest [] = new int [numpoints];
// array to record soln; closest[i] is index of point closest to i'th
int px, py;
double dx, dy, dist;
int i,j;
double currbest;
int closestPointIndex;
long tStart, tEnd;
for (i = 0; i < numpoints; i++) {
px = (int) ( range * Math.random());
dx = (double) px;
py = (int) (range * Math.random());
dy = (double) py;
inputpoints[i] = new My2dPoint(dx, dy);
}
// array inputpoints has now been filled
tStart = System.currentTimeMillis();
// find closest [0]
closest[0] = 1;
currbest = Auxiliaries.distSquared(inputpoints[0],inputpoints[1]);
for (j = 2; j < numpoints; j++) {
dist = Auxiliaries.distSquared(inputpoints[0],inputpoints[j]);
if (dist < currbest) {
closest[0] = j;
currbest = dist;
}
}
// now find closest[i] for every other i
for (i = 1; i < numpoints; i++) {
closest[i] = 0;
currbest = Auxiliaries.distSquared(inputpoints[i],inputpoints[0]);
for (j = 1; j < i; j++) {
dist = Auxiliaries.distSquared(inputpoints[i],inputpoints[j]);
if (dist < currbest) {
closest[i] = j;
currbest = dist;
}
}
for (j = i+1; j < numpoints; j++) {
dist = Auxiliaries.distSquared(inputpoints[i],inputpoints[j]);
if (dist < currbest) {
closest[i] = j;
currbest = dist;
}
}
}
tEnd = System.currentTimeMillis();
System.out.println("Naive Time taken in Milliseconds: " + (tEnd - tStart));
/* use for validity
for (i = 0; i < numpoints; i++) {
System.out.println("XPoint " + i + ": " + inputpoints[i].x + " " + inputpoints[i].y + " closest is: " + inputpoints[closest[i]].x+" "+inputpoints[closest[i]].y);
}
*/
//remove duplicates
tStart = System.currentTimeMillis();
CompareByX e = new CompareByX();
java.util.Arrays.sort(inputpoints,e);
ArrayList<My2dPoint> tmp = new ArrayList<My2dPoint>(); //(Arrays.asList(inputpoints));
tmp.add(inputpoints[0]);
int k=0;
i=0;
while(i< inputpoints.length){
if(tmp.get(k).x==inputpoints[i].x && tmp.get(k).y==inputpoints[i].y){
i++;
}
else{
tmp.add(inputpoints[i]);
k++;
i++;
}
}
My2dPoint [] list = tmp.toArray(new My2dPoint [tmp.size()]);
System.out.println("before: "+inputpoints.length+" after:"+list.length);
My2dPoint [] qClosest = new My2dPoint[list.length];
int depth=0;
qNode root = Auxiliaries.makeRoot(list,depth);
tEnd = System.currentTimeMillis();
Auxiliaries.closestPairs(list,root,qClosest);
System.out.println("Quadtree Time taken in Milliseconds: " + (tEnd - tStart)+ " tEnd:"+tEnd+" tStart:"+tStart);
System.out.println("Done");
//Auxiliaries.printTree(root);
for (i = 0; i < numpoints; i++) {
//System.out.println("XPoint " + i + ": " + inputpoints[i].x + " " + inputpoints[i].y + " closest is: " + inputpoints[closest[i]].x+" "+inputpoints[closest[i]].y);
}
}
}