/* * Auteur : JM Vuong * Studie nummer : 1263234 * Datum : 4 maart 2007 */import java.util.ArrayList;import java.util.List;public class Pair { private Point a; private Point b; private double distance; public Pair (Point a, Point b){ this.a = a; this.b = b; this.distance = distance(a,b); } public Point get_point_a(){ return a; } public Point get_point_b(){ return b; } public double get_distance(){ return this.distance; } public String toString(){ return String.format("%s - %s distance %f", a,b,distance); } public static void main(String[] args){ Point b = new Point(3,58,30); Point e = new Point(1000, 5, 300); Point c = new Point(2,31,100); Point a = new Point(1,22,1000); Point d = new Point(-1,3, 200); List<Point> t = new ArrayList<Point>(); t.add(b); t.add(e); t.add(c); t.add(a); t.add(d); System.out.println("Algorithm says : "+find_closests(t)); for(Point p : t) for (Point p2 : t) if (p != p2) System.out.println(new Pair(p,p2)); } public static Pair find_closests (List<Point> in){ return find_closest (Sort.sort_by_x(in), Sort.sort_by_y(in)); } public static Pair find_closest( List<Point> sortedx, List<Point> sortedy ){ if (sortedx.size() == 3){ Pair a = new Pair(sortedx.get(0), sortedx.get(1)); Pair b = new Pair(sortedx.get(0), sortedx.get(2)); Pair c = new Pair(sortedx.get(1), sortedx.get(2)); return min(a,min(b,c)); } if (sortedx.size() == 2){ Pair a = new Pair(sortedx.get(0), sortedx.get(1)); return a; } if (sortedx.size() == 1 || sortedx.size() == 0){ return null; } List<List<Point>> by_x = Sort.divide(sortedx); List<List<Point>> by_y = Sort.divide(sortedy); Pair a = find_closest (by_x.get(0), by_y.get(0)); Pair b = find_closest (by_x.get(1), by_y.get(1)); double mindistance = min(a,b).get_distance(); int L = by_x.get(0).get(by_x.get(0).size() - 1).get_x(); // L ArrayList<Point> bla = new ArrayList<Point>(); for(Point p : sortedy){ if(p.get_x() > L - mindistance && p.get_x() < L + mindistance) bla.add(p); } Pair minp = minimum_pair (bla, null); if (minp instanceof Pair && minp.get_distance() < mindistance) return minp; else if (a.get_distance() < b.get_distance()) return a; else return b; } public static Pair minimum_pair (List<Point> inlist, Pair minpair){ if(inlist.isEmpty()) return minpair; int count = 0; Point a = inlist.remove(0); while(count < 16){ Point b; if(inlist.size() <= count) break; else b = inlist.get(count); count++; if(minpair != null) minpair = minpair.get_distance() < new Pair(a,b).get_distance() ? minpair : new Pair(a,b); else minpair = new Pair(a,b); } return minimum_pair (inlist, minpair); } public static double distance (Point a, Point b){ double dx = Math.abs((double)a.get_x() - (double)b.get_x()); double dy = Math.abs((double)a.get_y() - (double)b.get_y()); return Math.sqrt(dx*dx + dy*dy); } public static Pair min (Pair a, Pair b){ return a.get_distance() < b.get_distance() ? a : b; }}