Найти прямоугольники, содержащие точку - эффективный алгоритм

Добрый день.

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).

Find rectangles that contain entered point.

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?

Спасибо :-).

Ответы на вопрос(5)

Ваш ответ на вопрос