Thuật toán cặp điểm gần nhất

Question

Tôi đang cố triển khai một phiên bản đơn giản hơn của thuật toán này nhưng hoạt động tốt hơn thuật toán bậc hai. Ý tưởng của tôi về cơ bản là sắp xếp các điểm theo tọa độ x duy nhất và cố gắng giải quyết nó từ đó. Một khi tôi sắp xếp mảng của tôi điểm bằng x phối hợp, tôi muốn lặp qua mảng và về cơ bản bỏ qua các điểm có khoảng cách lớn hơn hai điểm đầu tiên tôi lấy.

Ví dụ: currentminDist = x;

Nếu hai điểm mà tôi đang xem có khoảng cách> x (chỉ bằng tọa độ x của nó), tôi bỏ qua điểm và di chuyển qua nó trong mảng.

Tôi có ý tưởng xuống, nhưng tôi là loại bị mắc kẹt về cách thực sự thực hiện điều này (đặc biệt là phần điều kiện). Tôi có một hàm trả về khoảng cách giữa hai điểm dựa trên tọa độ x của chúng.

Tôi nhầm lẫn về cách viết các điều kiện cho vòng lặp của mình vì tôi muốn bỏ qua một điểm nếu khoảng cách xảy ra quá xa và vẫn điền vào mảng của tôi sẽ chứa các câu trả lời cho các điểm gần nhất cho mỗi i (tôi là điểm hiện tại tôi đang xem).

Mọi mẹo hoặc chỉ đường sẽ được đánh giá cao. Tôi không hiểu nhiều về các thuật toán mã hóa nên nó khá bực mình.

Dưới đây là một phần của mã của tô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 là chức năng của tôi mà chỉ cần trả khoảng cách giữa hai điểm.

Cảm ơn!

Answer 1

nhanh Thuật toán sử dụng một KD-Tree
thuật toán này tạo ra một kd cây và sau đó tìm cặp gần nhất cho mỗi điểm. Việc tạo cây kd là O (n log n), và tìm người lân cận gần nhất của một điểm là O (logn). Tín dụng phải đến Wikipedia, trong một bài viết giải thích cách tạo cây kd và cách sử dụng chúng để tìm người hàng xóm gần nhất.

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 vào mã trong câu hỏi
Nếu bạn thực sự không lo lắng về sự phức tạp, vấn đề duy nhất với mã của bạn là bạn mong muốn nhưng không phải về phía sau. Chỉ cần lặp lại trong các vòng lặp bên trong và làm cho j đi (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; 
     } 
    } 
}