1

我正在寻找一种算法来获得最快的方法来找到一个盒子中的所有点 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());
}
}
4

3 回答 3

4

改进 Mikhails 的答案（我还不能评论）你可以利用四叉树http://en.wikipedia.org/wiki/Quadtree。这就是米哈伊尔所说的，我认为，并且通过将空间划分为网格来工作。如果一个分区中有很多点，则它本身被划分为一个小网格。

When selecting points one can then compare the extents of the partitions to quickly exclude several points if their containing rectangle does not intersect with your selection rectangle.

四叉树的创建平均需要 O(n log n) 操作，而选择一堆点需要 O(log n)。

于 2013-02-13T13:42:01.503 回答
3

将您的空间分成方形单元格。对于每个单元格存储位于单元格中的点列表。对于给定的矩形，首先找到与其相交的所有单元格，然后遍历这些单元格中的点并测试其中哪些在矩形中。这是演示这种方法的代码：

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");
    }
}
于 2013-02-13T13:32:19.997 回答
2

你的解决方案是线性的，你没有办法做得更好，因为你至少要读取输入数据。

于 2013-02-13T13:34:46.907 回答