С этой задачей по идее должны часто стакливаться разработчики игр, различных редакторов и просто графических тулкитов.
А именно: допустим, у нас есть набор графических объектов. Для простоты примем, что они все имеют прямоугольную форму (в крайнем случае всегда можно описать прямоугольник вокруг многоугольника или эллипса и если этот объект прошёл первичные проверки допроверять уже точно), а их стороны параллельны осям координат. У нас есть некоторое окно, через которое пользователь эти объекты просматривает. То есть одновременно он может видеть и взаимодействовать не со всеми объектами, а только с теми, которые имеют пересечение с прямоугольником окна просмотра. Хоть у нас и 2D пространство, но у объектов должно быть что-то типа Z-индекса, чтобы если два из них наложились, то какой-то всегда рисовался поверх другого и не было неоднозначности (для простоты можно принять, что самым верхним объектом является тот, который последний добавлен в список, если мы хотим поднять объект, то удаляем его из списка и добавляем заново).
Теперь допустим, пользователь кликает или даже просто водит мышью по этому окну просмотра. Нужно при любом событии быстро определить, над чем находится указатель мыши (чтобы при наведении подсветить объект, а при клике выполнить какое-то действие). Это нужно сделать быстро, ведь обработчику движения мыши нельзя сильно тупить. Также необходимо легко менять координаты объектов (например, пользователь схватил объект и потащил его мышью, хотя тут можно считерить - запоминать какой объект тащим и дальнейшие операции всегда вести только с ним, а вносить реальные изменения в список лишь при отпускании мыши).
Я понимаю, что это по-любому реализовано в тысячах различных программ и игр и сами подходы должны быть общеизвестны. В какую сторону копать? Как называется сам этот процесс, какие можете посоветовать структуры данных для хранения объектов (простой словарь не подойдёт - ведь у нас есть две координаты, к тому же ещё и размеры объектов, которые могут сильно различаться)?
Или, возможно, я занимаюсь преждевременной оптимизацией и на самом деле, если объектов не миллионы (а даже в какой-нибудь стратегии обычно миллионов юнитов нет, как и в различных редакторах - человек просто не осилилт управлять мышью таким количеством объектов), то можно забить и делать тупой перебор обычного линейного списка и проверять, попадает ли мышь в bounding box?
