Самый близкий алгоритм точек точек

Question

Я пытаюсь реализовать более простую версию этого алгоритма, но который работает лучше, чем квадратичный алгоритм. Моя идея состоит в том, чтобы отсортировать точки только по координате x и попытаться решить ее оттуда. Как только я сортирую свой массив точек по координате x, я хочу перебирать массив и в основном пропускать точки, расстояние которых больше, чем первые две точки, которые я взял.

Например, my currentminDist = x;

Если две пары точек, на которые я смотрю, имеют расстояние> x (только по его координате x), я игнорирую точку и перемещаю ее в массиве.

У меня есть идея, но я как бы зациклен на том, как на самом деле реализовать это (особенно часть состояния). У меня есть функция, которая возвращает мне расстояние между двумя точками, основанное на их координате x.

Я смущен тем, как писать мои условия для моего цикла, так как я хочу игнорировать точку, если расстояние слишком далеко и по-прежнему заполняет мой массив, который будет содержать ответы для ближайших точек для каждого i (я являюсь текущим пунктом, на который я смотрю).

Любые советы или указания были бы весьма полезными. Я не очень хорошо разбираюсь в алгоритмах кодирования, поэтому он довольно расстраивает.

Вот часть моего кода:

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 моя функция, которая просто возвращает расстояние между двумя точками.

Спасибо!

Answer 1

Быстрый алгоритм с использованием KD-Tree
Этот алгоритм создает KD-дерево, а затем находит ближайшую пару для каждой точки. Создание kd-дерева - это O (n log n), и найти ближайшего соседа точки O (logn). Кредит должен перейти в Wikipedia, который в одной статье объясняет, как создавать kd-деревья, а также как использовать их для поиска ближайшего соседа.

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

Исправление к коду в вопросе
Если вы действительно не беспокоиться о сложности, единственная проблема с вашим кодом, что вы смотрите вперед, но не назад. Просто дублировать внутреннюю петлю и сделать j идти от (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; 
     } 
    } 
}