Найти прямоугольники, содержащие точку - эффективный алгоритм
Добрый день.
My situation:
In two-dimensional space. Input: a set of rectangles (overlapping rectangles too). Rectangles coordinates are integer type. There are any constraints on rectangle-size and rectangle-location (only extent of integer). Any rectangle haven't width=0 or height=0. I need to find: all rectangles that contain entered point (with integer coordinates).Questions:
What is the efficient structure to keep rectangles? What alghorithm is efficient in this case? And what algorithm is efficient only for adding rectangles without removing?Спасибо :-).