检查点的数组是矩形的数组里面呢？ [英] Check if an array of points is inside an array of rectangles?

问题描述

我有顶点列表和区域（其是正方形/矩形）形状的列表。顶点具有x和y坐标，和一个区域具有（X，Y，高度和宽度）。我怎样才能有效地检查哪些顶点位于该地区的每个顶点/地区？

编辑：

这是code我写的做到这一点。

 如果（！g.getVertices（）的isEmpty（））{                的for（int i = 0; I＆LT; g.getVertices（）大小（）;我++）{                    顶点v = g.getVertices（）得到（一）。
                    点vertexPoint =新的点（v.getX（），v.getY（））;                    对于（INT J = 0; J＆LT; g.getNumberOfRegions（）; J ++）{                        INT X = g.getRegions（）获得（J）.getX（）。
                        。INT Y = g.getRegions（）获得（J）.getY（）;
                        INT高度= g.getRegions（）获得（J）.getHeight（）。
                        INT宽度= g.getRegions（）获得（J）.getWidth（）。                        格regionGrid =新格第（j + 1，X，Y，高度，宽度）;                        矩形regionRectangle =新的Rectangle（X，Y，高度，宽度）;
                        如果（regionRectangle.contains（vertexPoint））{
                            的System.out.println（顶点+ V +谎言里地区+ 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＆LT; rowValue;我++）{                对于（INT J = 0; J＆LT; columnValue; J ++）{                    网格R =新的网格（0，20 +我*的大小，20 + J *的大小，尺寸，大小）;
                    r.setRegionID第（j + 1）;
                    g.addRegion（R）;
                }            }
 

解决方案

检查，如果一个顶点是一个正方形内或圆可以在O完成（1）。你可以用库函数或初等数学做到这一点。所以作品的算法可以创建为O（#vertices * #regions）。你可以尝试通过X轴排序顶点和地区，然后通过Y轴进行优化，尽量消除检查肯定返回false。但目前看来，在悲观的情况下，你仍然有O（#vertices * #regions）时间。

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

            }

解决方案

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.

这篇关于检查点的数组是矩形的数组里面呢？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！