CODEWITHSUNDEEP
javajava-2d
CmdrMoozy
CmdrMoozy

Reputation: 3931

Finding Rectangle which contains a Point

In Java SE 7, I'm trying to solve a problem where I have a series of Rectangles. Through some user interaction, I get a Point. What I need to do is find the (first) Rectangle which contains the Point (if any).

Currently, I'm doing this via the very naieve solution of just storing the Rectangles in an ArrayList, and searching for the containing Rectangle by iterating over the list and using contains(). The problem is that, because this needs to be interactive for the user, this technique starts to be too slow for even a relatively small number of Rectangles (say, 200).

My current code looks something like this:

// Given rects is an ArrayList<Rectangle>, and p is a Point:

for(Rectangle r : rects)
{
    if(r.contains(p))
    {
        return r;
    }
}

return null;

Is there a more clever way to solve this problem (namely, in O(log n) instead of O(n), and/or with fewer calls to contains() by eliminating obviously bad candidates early)?

Upvotes: 1

Views: 397

Answers (1)

Chandranshu
Chandranshu

Reputation: 3669

Yes, there is. Build 2 interval trees which will tell you if there is a rectangle between x1 to x2 and between y1 and y2. Then, when you have the co-ordinates of the point, perform O(log n) searches in both the trees.

That'll tell you if there are possibly rectangles around the point of interest. You still need to check if there is a common rectangle given by the two trees.

Upvotes: 3

Related Questions