Check if an array of points is inside an array of rectangles?

Question

I have a list of vertices and a list of regions (which are square/rectangle) shaped. Vertex has x and y coordinates, and a region has (x, y, height and width). How can I efficiently check which vertex lies in which region for every vertex/region?

EDIT:

This is the code I wrote to do this.

                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());
                        }
                    }

                }
            }

EDIT 2: I used this to generate the regions, but I need a way to assign each region in the grid a regionID from left to right. For example:

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

for a 3x3 grid. At the moment it is in the following form:

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);
                }

            }

score 2 · Accepted Answer · answered Aug 05 '12 at 14:38

2

checking if a vertex is inside a square or a circle can be done in O(1). you can do it with library function or elementary math. so the works algorithm you can create is O(#vertices * #regions). you can try to optimise by sorting the vertices and regions by X-axis and then by Y-axis and try to eliminate checking that for sure return false. but seems that in pessimistic scenario you will still have O(#vertices * #regions) time.

answered Aug 05 '12 at 14:38

piotrek

13,982
13
79
165

I have updated the original post with source code. Can you see any improvements that can be made? – RikudouSennin Aug 05 '12 at 14:50
if your get(x) works in O(1) then your algorithm works in O(#vertices * #regions). if, as a result, you need list of pairs (vertex, region) then there can be O(#vertices * #regions) such pairs, so your algorithm is optimal. if you can have your result more compact e.g. at most 1 region for each vertex then faster algorithm is probably possible – piotrek Aug 05 '12 at 15:05

score 2 · Answer 2 · answered Aug 05 '12 at 14:49

You can probably use the Core Java libraries itself:

    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);
        }
    }

Mateusz Chromiński · Answer 3 · 2018-04-05T19:48:19.097

1

Working with plane geometry is extremely easy while using JTS. You can try convert the objects you are using to JTS-specific.

edited Apr 05 '18 at 19:48

answered Aug 05 '12 at 14:34

Mateusz Chromiński

2,742
4
28
45

Check if an array of points is inside an array of rectangles?

3 Answers3

Linked