在一個盒子裏找到第二個點

Question

我正在尋找一種算法來找到最快的方法來找到盒子中的所有點2D（x，y）（盒子由2個點定義：lowerLeft和upperRight）。

想象一下，我們在2D空間中有200萬個點。

在那個2D空間中，我創建了一個從2點開始的盒子，一個是左下角，另一個是右上角。 獲取盒子中所有點的最快方法是什麼？ 下面是最壞情況下的java測試：循環每個點（200萬！）並確定它是否在盒子內。 我相信，如果點的名單先排序，我們可以變得更快...

您有什麼想法嗎？

public class FindPointsInBox { 
public static void main(String[] args) throws Exception { 
    // List of 2,000,000 points (x,y) 
    List<Point> allPoints = new ArrayList<Point>(); 
    for(int i=0; i<2000000; i++) { 
     allPoints.add(new Point(46 - (Math.random()), -74 - (Math.random()))); 
    } 

    // Box defined by 2 points: lowerLeft and upperRight 
    List<Point> pointsInBox = new ArrayList<Point>(); 
    Point lowerLeft = new Point(44.91293325430085, -74.25107363281245); 
    Point upperRight = new Point(45.3289676752705, -72.93820742187495); 

    Date t1 = new Date(); 

    // TODO: What is the fastest way to find all points contained in box 
    for(int i=0; i<allPoints.size(); i++) { 
     if(isPointInBox(allPoints.get(i), lowerLeft, upperRight)) 
      pointsInBox.add(allPoints.get(i)); 
    } 
    Date t2 = new Date(); 
    System.out.println(pointsInBox.size() + " points in box"); 
    System.out.println(t2.getTime()-t1.getTime() + "ms"); 
} 

private static boolean isPointInBox(Point p, Point lowerLeft, Point upperRight) { 
    return (
     p.getX() >= lowerLeft.getX() && 
     p.getX() <= upperRight.getX() && 
     p.getY() >= lowerLeft.getY() && 
     p.getY() <= upperRight.getY()); 
} 
} 

Answer 1

將你的空間分割成正方形的單元格。對於坐落在單元格中的每個單元格存儲點列表。對於給定的矩形首先找到與它相交的所有單元格，然後遍歷這些單元格中的點並測試它們中的哪些在矩形中。下面是代碼演示了此方法：

public class PointsIndex { 
    private final int width; 
    private final int height; 
    private final int rows; 
    private final int cols; 
    private final List<Point> [][] cells; 

    @SuppressWarnings("unchecked") 
    public PointsIndex (
     int width, int height, int rows, int cols) 
    { 
     this.width = width; 
     this.height = height; 
     this.rows = rows; 
     this.cols = cols; 

     cells = (List<Point> [][])new List<?> [rows][]; 
     for (int i = 0; i < rows; i++) 
      cells [i] = (List<Point> [])new List<?> [cols]; 
    } 

    public void addPoint (int x, int y) 
    { 
     int r = x * rows/width; 
     int c = y * cols/height; 

     List <Point> cell = cells [r][c]; 
     if (cell == null) 
     { 
      cell = new ArrayList<Point>(); 
      cells [r][c] = cell; 
     } 

     cell.add (new Point (x, y)); 
    } 

    public Point [] getPoints (int x, int y, int w, int h) 
    { 
     int r1 = x * rows/width; 
     int r2 = (x + w - 1) * rows/width; 
     int c1 = y * cols/height; 
     int c2 = (y + h - 1) * cols/height; 

     ArrayList<Point> result = new ArrayList<Point>(); 

     for (int r = r1; r <= r2; r++) 
      for (int c = c1; c <= c2; c++) 
      { 
       List <Point> cell = cells [r][c]; 
       if (cell != null) 
       { 
        if (r == r1 || r == r2 || c == c1 || c == c2) 
        { 
         for (Point p: cell) 
          if (p.x > x && p.x < x + w && p.y > y && p.y < y + h) 
           result.add (p); 
        } 
        else result.addAll (cell); 
       } 
      } 

     return result.toArray(new Point [result.size()]); 
    } 

    public static void main(String[] args) { 
     Random r = new Random(); 

     PointsIndex index = new PointsIndex(1000000, 1000000, 100, 100); 
     List <Point> points = new ArrayList<Point>(1000000); 

     for (int i = 0; i < 1000000; i++) 
     { 
      int x = r.nextInt(1000000); 
      int y = r.nextInt(1000000); 

      index.addPoint(x, y); 
      points.add (new Point (x, y)); 
     } 

     long t; 

     t = System.currentTimeMillis(); 
     Point [] choosen1 = index.getPoints(456789, 345678, 12345, 23456); 
     System.out.println (
      "Fast method found " + choosen1.length + " points in " + 
      (System.currentTimeMillis() - t) + " ms"); 

     Rectangle rect = new Rectangle (456789, 345678, 12345, 23456); 

     List <Point> choosen2 = new ArrayList<Point>(); 

     t = System.currentTimeMillis(); 
     for (Point p: points) 
     { 
      if (rect.contains(p)) 
       choosen2.add (p); 
     } 
     System.out.println(
      "Slow method found " + choosen2.size() + " points in " + 
      (System.currentTimeMillis() - t) + " ms"); 
    } 
} 

Answer 2

你的解決方案是線性的，你有沒有辦法做的更好，因爲你必須至少讀取輸入數據。

Answer 3

米哈伊爾斯的改進答案（我還不能評論），你可以利用四叉樹http://en.wikipedia.org/wiki/Quadtree。這是米哈伊爾正在談論的，我認爲，並且通過將空間劃分成網格來工作。如果分區中有很多點，它本身就被分割成一個小網格。

當選擇點時，可以比較分區的範圍，以便在包含的矩形與選擇矩形不相交時快速排除幾個點。

四叉樹平均需要O（n log n）操作才能創建，而選擇一堆點需要O（log n）。