检查点的数组是矩形的数组里面呢？

本文介绍了检查点的数组是矩形的数组里面呢？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我有顶点列表和区域（其是正方形/矩形）形状的列表。顶点具有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 - 34 - 5 - 67 - 8 - 9

对于一个3x3的网格。目前，它是以下形式：

1 - 1 - 12 - 2 - 23 - 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.