java - search sorted list of rectangles

Question

I have a list of Rectangles, created in the usual way with:

List<Rectangle> rects = new ArrayList<>();

Some Rectangles are added (all with non-zero width and height). The number of Rectangles the List contains can be anywhere between 0 and 10,000, and will typically be between 4,000 and 6,000.

The list is sorted by ascending X-coordinate of the Rectangle origin, and then by ascending Y-coordinate for duplicate X-coordinates (though two or more rectangles with the same X-coordinate is rare).

I've verified the sorting is being done correctly (I'm using Collections.sort with a custom comparator).

I need a method that takes as input two ints, x and y, and returns the first Rectangle found containing the point (x,y), or null if no Rectangle in the list contains that point.

public Rectangle findContainingRectangle(int x, int y)

The naive method, which does give the desired functionality, is to just loop through the list and call the contains method on each Rectangle, but that is much too slow.

The List will be modified while the program is running, but at an insignificant rate compared to the rate at which the List needs to be searched, so an algorithm that requires a relatively slow initialization is fine.

I've looked at Collections.binarySearch but couldn't figure out how it might be used. I don't have much experience with Java so if there's another Collection that could be used similarly to a List but better suited to the type of search I need, then that's great (I have read the documentation on things like Maps and Sets but didn't recognize any advantage).

Answer 1

While maintaining a sorted list, you could use a binary search on the 'X' coordinate to find the candidates of the rectangles that contain the wanted 'X', and after which, use binary search on the 'Y' coordinate.

You should implement the binary search yourself, I can't see a way you can use the Collections.binarySearch method.

expected complexity: O(log n) as n the number of rectangles. (It's a bit more because you might have duplicates)

However ,to do so, you should keep the array sorted while adding other instances, (sort after every insert).

Answer 2

Use HashSet. Map isn't appropriate here since you're not creating key-value pairs, and a Stream doesn't fit in this context either.

Be sure to override equals() and hashCode() in Rectangle, as described here: Why do I need to override the equals and hashCode methods in Java?

Answer 3

You can search your list using parallel stream like this

public Rectangle findContainingRectangle(final int x, final int y) {
    List<Rectangle> rectangles = new ArrayList<>();

    Rectangle rec = rectangles.parallelStream().filter((r)->{
        if(r.getX()==x && r.getY()==y){
            return true;
        }
        return false;
    }).findFirst().get();
    return rec;
}

Answer 4

Just run binary search a bunch of times - since the probability of same x is low as you say it wont take many times so it will still be logn

a) run binary search

b) remove item if found - and keep index where it was found

c) repeat binary search at a) with the remaining list until null is returned

d) then you have a small array of indexes and you can see which one is the smallest

e) then reinsert the removed elements at the designated spots

Answer 5

You can create a Map.

Map is the best way to associate two values. You can associate the 'x' value and its first position in your List. Then you only have to loop from the first 'x' position to another 'x' in your list.

If you don't find the 'x' on the Map, they don't have the good rectangle on your list.

With this way you don't explore all bad 'x' entry.

Answer 6

You can try and see a performance of a stream. I am not sure it will be fast enough but you can test it.

Rectangle rec = rects.stream().filter((r)->{
            return r.contains(x, y);
        }).findFirst().get();