1

ボックス内にあるすべてのポイント 2D (x、y) を見つけるための最速の方法を取得するアルゴリズムを探しています (ボックスは 2 つのポイントで定義されます: lowerLeft と upperRight)。

2D 空間に 200 万点あるとします。

その 2D 空間で、2 つの点からどこかにボックスを作成します。1 つは左下、もう 1 つは右上です。ボックスにあるすべてのポイントを取得する最速の方法は何ですか? 最悪のシナリオの 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を利用できます。これはミハイルが話していることだと思いますが、空間をグリッドに分割することで機能します。パーティションに多くのポイントがある場合、それ自体が小さなグリッドに分割されます。

ポイントを選択するとき、パーティションの範囲を比較して、それらを含む長方形が選択長方形と交差しない場合、いくつかのポイントをすばやく除外できます。

四分木では、作成に平均で 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 に答える