1

So I have a bounded plane (X axis range 0-1000, Y axis range 0-2000).
there are multiple points (x,y) in it, and a rectangle (4 points that makes the rectangle). Some points are in the rectangle and some aren't. like this: enter image description here

The rectangle is able to move and change it's size over time. while the points are static and won't change. I need to check what points are inside the rectangle after it changes.

Problem:
Giving a rectangle, what points are inside of it?

Set<Point> getPointsInsideRectangle(Rectangle rec);

My naive solution:
for each point

  • check if it inside the rectangle, if yes, add the point to a Point Set

return the Point Set

My thoughts:
It seems that iterating over all the points everytime the rectangle changes seems extremely not efficient with big CPU usage (there are many points). Something tells me to use HashMap but since the rectangle is a X range and a Y range (and not just 1 value), it seems I cannot use it.

My questions:
1. Is there a java data structure that can handle this situation?
2. if not, any thoughts on how to implement a data structure that holds all the points, and giving a rectangle, returns the points in it?

Ago
  • 313
  • 1
  • 2
  • 10
  • Well, how many points are you working with? Are you sure iterating through all points would actually be slow for your purposes? – xunatai Jun 21 '17 at 23:41
  • Divide your domain into cells, maybe about 25x25. Each cell can have its own set of points. Then, to find the points in a rectangle, identify which cells are (i) entirely inside the rectangle, (ii) partially inside the rectangle, (iii) outside the rectangle. Then you only need to check the individual points in the cells in category (ii). – Dawood ibn Kareem Jun 21 '17 at 23:55
  • I would try standard [Rectangle](http://docs.oracle.com/javase/8/docs/api/java/awt/Rectangle.html) and [Point](http://docs.oracle.com/javase/8/docs/api/java/awt/Point.html) – user85421 Jun 22 '17 at 00:20

3 Answers3

0

Just some random thoughts:

May try to create some kind of container for a specific range, like x from 0 to 100 and y from 0 to 100 l and repeat that with more containers like x from 100 to 200 and y from 0 to 100 etc and add your points to where they belong to. Something like

Class Container
{
Int minX;
Int maxX
Int minY;
Int maxY;

List<Point> points;

Check(int x, int y)
(
return x >= minX && x <= maxX && y >=           minY && y <= maxY;
)
}

Let's call the 4 points of the rectangle A (upper left), B (upper right), C (bottom right) and D (bottom left).

Start to check all containers with A.X and A.Y and then add the default range of a container to A.X and check again all containers that are not already in your bounds. Repeat till there's less than the default range left to B.X and then add what's left.

Same from A.X and A.Y to D.X and D.Y with Y decreased by the default container range and so on and so on.. .

Maybe even create containers containing containers to scale down the amount of comparissions even more.

This way you can check for containers which overlap with your rectangle and compare the points which are in these containers.

May even use multithreading to check the containers.

(Sorry for bad editing, I'm on my phone)

Edit Now that I reread that, I think this could results in a kind of tree structure

update A tree seems like the right thing to go for here: Range Tree (Wikipedia)

Example implementation: Java Range tree example ( by Robert Sedgewick and Kevin Wayne. )

DerDingens
  • 359
  • 4
  • 10
0

K-d tree (2d case) could be the starting point. It's rather simple to implement and fast enough.

Sample visualization:

enter image description here

Some links to java implementations: KDTree Implementation in Java

DAle
  • 8,990
  • 2
  • 26
  • 45
0

As other mentioned already, there are many data structures for spatial index:

  • Quadtrees
  • R-Trees (an R*Tree is an improved R-Tree)
  • KD-Trees

You have to perform a window query (sometimes called rectangle query or range query) on the index, where the query rectangle would be exactly your moving rectangle.

If you are looking for various implementations of such spatial data structures, have a look here (R*Tree, quadtrees, STR-loaded R-Tree), Or have a look at the PH-Tree, it is similar to a quadtree but much more efficient and inherently limited depth.

TilmannZ
  • 1,784
  • 11
  • 18