closestpair.java

package compute;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;

public class closestpair {

    public static point[] naive(point[] pts){
        return _naive(pts, 0, pts.length-1);
    }
    public static point[] _naive(point[] pts, int s, int e){
        point[] is = new point[2];
        double minDist = Double.MAX_VALUE;
        for(int i=s;i<=e-1;i++){
            for(int j=i+1;j<=e;j++){
                double d = point.dist(pts[i], pts[j]);
                if( minDist>d ){
                    minDist=d;
                    is[0] = pts[i];
                    is[1] = pts[j];
                }
            }
        }
        return is;
    }

    public static point[] divideAndConquer(point[] pts){
        Arrays.sort(pts, (point o1, point o2) -> {
            if( o1.x<o2.x )
                return -1;
            if( o1.x==o2.x )
                return 0;
            return 1;
        });
        return _divideAndConquer(pts, 0, pts.length-1);
    }
    public static point[] _divideAndConquer(point[] pts, int s, int e){
        if(e-s+1<4){
            return _naive(pts, s, e);
        }

        double xmid;
        int nmid=(e+s)/2;
        if((e-s+1)%2==0){
            xmid = (pts[(e-s)/2].x+pts[(e-s)/2+1].x)/2;
        }else{
            xmid = pts[(e-s)/2].x;
        }

        point[] res;
        point[] ptsl = _divideAndConquer(pts, s, nmid);
        point[] ptsr = _divideAndConquer(pts, nmid+1, e);

        double minl = point.dist(ptsl[0], ptsl[1]);
        double minr = point.dist(ptsr[0], ptsr[1]);
        double minrl;
        if(minl<minr){
            minrl = minl;
            res = ptsl;
        }else{
            minrl = minr;
            res = ptsr;
        }

        ArrayList<point> alp = new ArrayList<>();
        for(int i=s;i<=e;i++){
            if( Math.abs(pts[i].x-xmid)<minrl )
                alp.add(pts[i]);
        }
        Collections.sort(alp, new Comparator<point>() {
            @Override
            public int compare(point o1, point o2) {
                if( o1.y<o2.y )
                    return -1;
                if( o1.y==o2.y )
                    return 0;
                return 1;
            }
        });

        for(int i=0;i<alp.size();i++){
            int j = i+1;
            point pti=alp.get(i), ptj;
            while( j<alp.size() && Math.abs(pti.y-(ptj=alp.get(j)).y)<minrl ){
                double tdist = point.dist(pti, ptj);
                if( tdist < minrl ){
                    minrl = tdist;
                    res[0] = pti;
                    res[1] = ptj;
                }
                j++;
            }
        }
        return res;
    }
}