Algorithme de paires de points le plus proche

Question

J'essaie de mettre en œuvre une version plus simple de cet algorithme, mais qui fonctionne mieux que l'algorithme quadratique. Mon idée consiste essentiellement à trier les points par coordonnées x seulement et essayer de résoudre à partir de là. Une fois que j'ai trié mon tableau de points par coordonnées x, je veux parcourir le tableau et sauter des points dont la distance est plus grande que les deux premiers points que j'ai pris.

Par exemple, mon currentminDist = x; Si les deux paires de points que je regarde ont une distance> x (seulement par sa coordonnée x dist), j'ignore le point et le dépasse dans le tableau.

J'ai l'idée en bas, mais je suis un peu coincé sur la façon de réellement mettre en œuvre cela (en particulier la partie condition). J'ai une fonction qui me renvoie la distance entre deux points en fonction de leur coordonnée x. Je suis confus sur comment écrire réellement mes conditions pour ma boucle puisque je veux ignorer un point si la distance se trouve être trop loin et remplir toujours mon tableau qui contiendra les réponses pour les points les plus proches pour chaque i (je suis le point actuel que je regarde).

Des conseils ou des instructions seraient grandement appréciés. Je ne suis pas très au courant des algorithmes de codage, donc c'est assez frustrant.

Voici une partie de mon code:

for (i = 0; i < numofmypoints; i++) 
     { 
      for (int j = i + 1; (j < numpofmypoints) && ((inputpoints[j].x - inputpoints[i].x) < currbest); j++) 
      { 
       currdist = Auxilary.distbyX(inputpoints[i],inputpoints[j]); 

       if (currdist < bestdist) 
       { 
       closest[i] = j; 
       bestdist = currdist; 

       } 
      } 
     } 

distbyX est ma fonction qui retourne juste la distance entre deux points.

Merci!

Answer 1

algorithme rapide en utilisant un KD-Tree
Cet algorithme crée un arbre kd et trouve alors la paire la plus proche pour chaque point. La création du kd-tree est O (n log n), et trouver le voisin le plus proche d'un point est O (logn). Le crédit doit aller à Wikipedia, qui dans un article explique comment créer des kd-arbres et comment les utiliser pour trouver le voisin le plus proche.

import java.util.*; 

public class Program 
{ 
    public static void main(String[] args) 
    { 
     List<Point> points = generatePoints(); 
     Point[] closest = new Point[points.size()]; 

     KDTree tree = new KDTree(points, 0); // WILL MODIFY 'points' 

     for (int i = 0; i < points.size(); i++) 
     { 
      closest[i] = tree.findClosest(points.get(i)); 
     } 

     for (int i = 0; i < points.size(); i++) 
     { 
      System.out.println(points.get(i) + " is closest to " + closest[i]); 
     } 
    } 

    private static List<Point> generatePoints() 
    { 
     ArrayList<Point> points = new ArrayList<Point>(); 
     Random r = new Random(); 

     for (int i = 0; i < 1000; i++) 
     { 
      points.add(new Point(r.nextInt() % 1000, r.nextInt() % 1000)); 
     } 

     return points; 
    } 
} 

class Point 
{ 
    public static final Point INFINITY 
     = new Point(Double.POSITIVE_INFINITY, 
        Double.POSITIVE_INFINITY); 

    public double[] coord; // coord[0] = x, coord[1] = y 

    public Point(double x, double y) 
    { 
     coord = new double[] { x, y }; 
    } 

    public double getX() { return coord[0]; } 
    public double getY() { return coord[1]; } 

    public double distance(Point p) 
    { 
     double dX = getX() - p.getX(); 
     double dY = getY() - p.getY(); 
     return Math.sqrt(dX * dX + dY * dY); 
    } 

    public boolean equals(Point p) 
    { 
     return (getX() == p.getX()) && (getY() == p.getY()); 
    } 

    public String toString() 
    { 
     return "(" + getX() + ", " + getY() + ")"; 
    } 

    public static class PointComp implements Comparator<Point> 
    { 
     int d; // the dimension to compare in (0 => x, 1 => y) 

     public PointComp(int dimension) 
     { 
      d = dimension; 
     } 

     public int compare(Point a, Point b) 
     { 
      return (int) (a.coord[d] - b.coord[d]); 
     } 
    } 
} 

class KDTree 
{ 
    // 2D k-d tree 
    private KDTree childA, childB; 
    private Point point; // defines the boundary 
    private int d; // dimension: 0 => left/right split, 1 => up/down split 

    public KDTree(List<Point> points, int depth) 
    { 
     childA = null; 
     childB = null; 
     d = depth % 2; 

     // find median by sorting in dimension 'd' (either x or y) 
     Comparator<Point> comp = new Point.PointComp(d); 
     Collections.sort(points, comp); 

     int median = (points.size() - 1)/2; 
     point = points.get(median); 

     // Create childA and childB recursively. 
     // WARNING: subList() does not create a true copy, 
     // so the original will get modified. 
     if (median > 0) 
     { 
      childA = new KDTree(
       points.subList(0, median), 
       depth + 1); 
     } 
     if (median + 1 < points.size()) 
     { 
      childB = new KDTree(
       points.subList(median + 1, points.size()), 
       depth + 1); 
     } 
    } 

    public Point findClosest(Point target) 
    { 
     Point closest = point.equals(target) ? Point.INFINITY : point; 
     double bestDist = closest.distance(target); 
     double spacing = target.coord[d] - point.coord[d]; 
     KDTree rightSide = (spacing < 0) ? childA : childB; 
     KDTree otherSide = (spacing < 0) ? childB : childA; 

     /* 
     * The 'rightSide' is the side on which 'target' lies 
     * and the 'otherSide' is the other one. It is possible 
     * that 'otherSide' will not have to be searched. 
     */ 

     if (rightSide != null) 
     { 
      Point candidate = rightSide.findClosest(target); 
      if (candidate.distance(target) < bestDist) 
      { 
       closest = candidate; 
       bestDist = closest.distance(target); 
      } 
     } 

     if (otherSide != null && (Math.abs(spacing) < bestDist)) 
     { 
      Point candidate = otherSide.findClosest(target); 
      if (candidate.distance(target) < bestDist) 
      { 
       closest = candidate; 
       bestDist = closest.distance(target); 
      } 
     } 

     return closest; 
    } 
} 

Fix au code dans la question
Si vraiment vous ne vous inquiétez pas de la complexité, le seul problème avec votre code est que vous regardez vers l'avant, mais pas en arrière. Il suffit de dupliquer la boucle interne et faire j aller (i - 1)-0:

Point[] points = sort(input()); 
int[] closest = new int[points.length]; 

for (int i = 0; i < points.length; i++) 
{ 
    double bestdist = Double.POSITIVE_INFINITY; 

    for (int j = i + 1; (j < points.length) && ((points[j].x - points[i].x) < bestdist); j++) 
    { 
     double currdist = dist(points[i], points[j]); 

     if (currdist < bestdist) 
     { 
      closest[i] = j; 
      bestdist = currdist; 
     } 
    } 
    for (int j = i - 1; (j >= 0) && ((points[i].x - points[j].x) < bestdist); j--) 
    { 
     double currdist = dist(points[i], points[j]); 

     if (currdist < bestdist) 
     { 
      closest[i] = j; 
      bestdist = currdist; 
     } 
    } 
}