0

頂点のリストと領域（正方形/長方形）のリストがあります。頂点にはx座標とy座標があり、領域には（x、y、高さ、幅）があります。すべての頂点/領域について、どの頂点がどの領域にあるかを効率的に確認するにはどうすればよいですか？

編集：

これは私がこれを行うために書いたコードです。

                if (!g.getVertices().isEmpty()) {

                for (int i = 0; i < g.getVertices().size(); i++) {

                    Vertex v = g.getVertices().get(i);
                    Point vertexPoint = new Point(v.getX(), v.getY());

                    for (int j = 0; j < g.getNumberOfRegions(); j++) {

                        int x = g.getRegions().get(j).getX();
                        int y = g.getRegions().get(j).getY();
                        int height = g.getRegions().get(j).getHeight();
                        int width = g.getRegions().get(j).getWidth();

                        Grid regionGrid = new Grid(j+1, x, y, height, width);

                        Rectangle regionRectangle = new Rectangle(x, y, height, width);
                        if (regionRectangle.contains(vertexPoint)) {
                            System.out.println("Vertex " + v + " lies inside region " + regionGrid.getRegionID());
                        }
                    }

                }
            }

編集2：これを使用して領域を生成しましたが、グリッド内の各領域に左から右にregionIDを割り当てる方法が必要です。例えば：

1 - 2 - 3
4 - 5 - 6 
7 - 8 - 9

3x3グリッドの場合。現時点では、次の形式になっています。

1 - 1 - 1
2 - 2 - 2
3 - 3 - 3

                for (int i = 0; i < rowValue; i++) {

                for (int j = 0; j < columnValue; j++) {

                    Grid r = new Grid(0, 20 + i * size, 20 + j * size, size, size);
                    r.setRegionID(j + 1);
                    g.addRegion(r);
                }

            }
4

3 に答える 3

2

頂点が正方形または円の内側にあるかどうかのチェックは、O（1）で実行できます。ライブラリ関数または初等数学でそれを行うことができます。したがって、作成できるWorksアルゴリズムはO（#vertices * #regions）です。頂点と領域をX軸、次にY軸で並べ替えて最適化を試み、確実にfalseが返されることを確認しないようにすることができます。しかし、悲観的なシナリオでは、まだO（#vertices * #regions）の時間があります。

于 2012-08-05T14:38:33.703 に答える
2

おそらく、コアJavaライブラリ自体を使用できます。

    List<Rectangle2D.Double> rectangles = Arrays.asList(
                                                new Rectangle2D.Double(0d, 0d, 100d, 100d),
                                                new Rectangle2D.Double(100d, 0d, 100d, 100d),
                                                new Rectangle2D.Double(0d, 100d, 100d, 100d),
                                                new Rectangle2D.Double(100d, 100d, 100d, 100d));

    Point2D.Double aPoint = new Point2D.Double(30d, 40d);

    for (Rectangle2D.Double rectangle:rectangles){
        if (rectangle.contains(aPoint)){
            System.out.println(rectangle + " has the point " + aPoint);
        }
    }
于 2012-08-05T14:49:00.077 に答える
1

JTSを使用している間、平面ジオメトリの操作は非常に簡単です。使用しているオブジェクトをJTS固有に変換してみることができます。

于 2012-08-05T14:34:33.380 に答える