In Java, what is the best way of storing and testing if a point lies within a set of planes?

Question

I have done a lot of research trying to find the best way of doing this but can't come up with a good and simple solution.

On a 2D plane, I have values such as [x1=10, y1=10, x2=30, y2=20], [x1=50, y1=60, x2=80, y2=100] and so on which make up numerous different rectangles (can be a large amount of rectangles). I need to test if a given point [x=15, y=15] lies within one of the rectangles and get which rectangle it lies within. I also need to be able to add and remove individual rectangles from the list. What is the best and least resource intensive way of storing the numerous rectangles and looping through them to see if a given point lies within one of them?

I have tried creating an object to hold two points for each rectangle and storing all of them in a Map although when looping through the objects in the Map several times per second java can't seem to keep up.

Does anyone know of a better way of doing this?

Answer 1

First of all if want to check if a point is inside a rectangle (position is a point in a rectangle class, as are width, height):

public boolean contains(Point point)
{

    return (point.getX() >= position.getX() && point.getX() <= position.getX() + width) 
            && 
            (point.getY() >= position.getY() && point.getY() <= position.getY() + height);
}

in terms of checking if the point is inside of rectangles, you could store your rectangles in a Quadtree: https://en.wikipedia.org/wiki/Quadtree

and search the quadtree, with the point you want to test, the quadtree will only return rectangles near that point, so are doing significantly less comparisons