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);
            } 
    }
}

400+ lines of code is a LOT to ask people to analyze who do this in their spare time... Focus on the areas that you think may be problematic. You haven't received any responses yet, probably because we all have better things to do than analyze this amount of complex code.

I have to do this at work, but then I am paid well over $100K per year to do so. Call it about $60USD / hour... :-)

Edited 4 Years Ago by rubberman: n/a

400+ lines of code is a LOT to ask people to analyze who do this in their spare time... Focus on the areas that you think may be problematic. You haven't received any responses yet, probably because we all have better things to do than analyze this amount of complex code.

I have to do this at work, but then I am paid well over $100K per year to do so. Call it about $60USD / hour... :-)

You are right rubberman, I apologize for the lack of document and comments... this was all done in a short time. I will break my code down but I'm not sure where the problem is. I think it might be the massive amount of object that's being created, but I'm not sure how those "memory leaks" can be avoided.

Main():
The main point of the code is to compare the runtime of finding closest point for all points in an array. Line 352 to 390 in my does does that. Line 397 to 426 constructs my quad tree and run the closest points algorithm.


Construction:
My algorithm uses quad tree, which is a data structure I defined but works like general quad trees. My quad tree is created from the list of nodes with the method

Auxiliaries.makeRoot()

. makeRoot() calls makeQuadTree(); which works with makeNode() recursively to fill in my quad tree. Here I recursive make new lists for each level's candidate points; line 102-105 of my code. <-- I'm noting this because I think my time delay is caused by the memory in the heap.

Algorithm:
The algorithm I call is called

Auxiliaries.closestPairs();

which takes each pair in the list and calls

query()

recursively. Line 243-259 determines the minimum distance from all the current candidate representative points (each node has a representative point unless it is a leaf and doesn't contain a point). Line 263-268 basically check all of the current candidates's children and see if they are with in distance to possibly contain a closer point. This will keep checking the next level until it hits bottom as the if statement in 280 it then returns that point as the closest to the one I'm looking for. <--I'm makein a new ArrayList for each level

Looking at this now, it doesn't seem I was crazy in wasting memory. I'm not sure what's causing my delay. I'm envious of your hourly rate ;) and thank for your help.

Never mind, I'm timing it at the wrong place. Something else is wrong with my algorithm that's slower than the naive algorithm...

Solved; my min distance was actually distance^2. One small bug causing my nlogn to be n^n...

Great! Sometimes, just jabbing a person in the ribs is enough to get them to solve their own problems! :-) IMHO, NOT asking for help, is worse than asking for it, and often not getting the answer handed to you on a plate is preferable, in that it forces you to reconsider your code. You did that, and solved your own problem, gaining knowledge in the process. Good work!

This question has already been answered. Start a new discussion instead.