Поиск прямоугольника, который содержит точку

Question

В Java SE 7, я пытаюсь решить проблему, когда у меня есть серия Rectangles. Через какое-то взаимодействие с пользователем я получаю Point. Мне нужно найти (первый) прямоугольник, содержащий точку (если есть).

В настоящее время я делаю это с помощью самого наивного решения только для хранения прямоугольников в ArrayList и поиска содержащего Rectangle путем итерации по списку и использования . Проблема в том, что, поскольку это должно быть интерактивным для пользователя, этот метод начинает слишком медленным даже для относительно небольшого количества прямоугольников (скажем, 200).

Мой текущий код выглядит примерно так:

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

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

return null; 

Есть ли более умный способ решить эту проблему (а именно, в O (журнал N) вместо O (N), и/или с меньшим количеством звонки на , устраняя явно плохие кандидатуры раньше)?

Answer 1

Да, есть. Build 2 interval trees, который расскажет вам, существует ли прямоугольник между x1 и x2 и между y1 и y2. Затем, когда у вас есть координаты точки, выполните O (log n) поиск в обоих деревьях.

Это скажет вам, есть ли прямоугольники вокруг интересующей вас точки. Вам все равно нужно проверить, существует ли общий прямоугольник, заданный двумя деревьями.