Добрый день.
Моя ситуация:
Вопросы:
Спасибо :-).
R-Tree - лучшая структура данных, подходящая для этого варианта использования. R-деревья - это древовидные структуры данных, используемые для методов пространственного доступа, то есть для индексирования многомерной информации, такой как географические координаты, прямоугольники или многоугольники. Информация о всех прямоугольниках может храниться в виде дерева, поэтому поиск будет легким.
Wikipedia, short ppt и исследовательская статья поможет вам понять концепцию.
В java вы можете использовать shape.contains
Но в целом, если предположить, что прямоугольник определяется (x, y, width, height), вы делаете
if (pt.x >= x && pt.x <= x + width & pt.y >= y & pt.y <= y + height)...
Если у вас есть все ваши прямоугольники в коллекции, вы можете перебирать коллекцию и находить те, которые содержат точку
Прямоугольник (left, top, right, bottom) содержит точку (x, y), если left < x < right и top < y < bottom (при условии, что координаты увеличиваются вниз, что имеет место с большинством аппаратных средств, которые я видел; если ваши координаты увеличиваются вверх, тем больше традиционно математический случай, swap top и bottom). Вы не будете намного эффективнее, чем тест.
Если вы рассматриваете прямоугольник как "содержащий" точку, если она также находится на границе, замените все < на <=.
Что касается того, что делать с коллекцией прямоугольников... я не знаю. Я бы подумал, что список, отсортированный по координатам углов, сделает что-то, но я не вижу в этом большой пользы... в лучшем случае вы бы сократили свой список вещей, чтобы проверить половину, в среднем (в худшем случае все еще требуется проверить все). Половина целой чертовой партии все еще может быть много.:)
Кажется, что ваш набор прямоугольников может быть динамическим ( "... для добавления прямоугольников..." ). В этом случае - 2D Дерево интервала может быть решением.
Вот простое решение.