Эффективная точка внутри поиска границ прямоугольника

Question

Я работаю над редактором векторной карты, и у меня есть набор элементов, каждый из которых определяет ограничивающий прямоугольник в представлении. Когда мышь перемещается, я хочу выделить первый элемент , ограничивающий прямоугольник которого содержит текущее местоположение мыши. Прямо сейчас я использую простой список и просматриваю его, но, поскольку количество элементов может увеличиться, сложность O (n) текущего алгоритма поиска будет проблематичной для интерактивного приложения.

Каков будет лучший алгоритм / структура данных для этого?

Некоторые дополнительные ограничения / требования :

• Заполнение структуры данных ограничивающих рамок должно быть относительно быстрым (поскольку мне нужно делать это каждый раз, когда карта перемещается или изменяется масштаб или проекция).
• Алгоритм должен быть в состоянии найти всех соответствующих элементов (не только первый). Причина в том, что некоторые элементы карты могут иметь неправильную форму, поэтому простое сопоставление ограничивающих рамок недостаточно строго. Затем я бы просмотрел список совпадений и сделал какое-то точное совпадение.
• Порядок , в котором ящики были добавлены в набор , необходимо каким-то образом поддерживать - элемент карты, который рисуется над другим элементом, должен иметь приоритет при сопоставлении их ограничивающих ящиков .

Answer 1

После просмотра книг я нашел один ответ в Вычислительная геометрия книга (стр. 237 в 3 ^rd издание; 2008). Этот тип поиска часто называют пронзительным запросом и обычно реализуется с использованием деревьев сегментов .

Сложность:

• Запрос: O (log2n + k), где k - количество сообщенных ограничивающих рамок
• Структура данных использует O (n * log n) хранения
• Структура может быть построена за O (n * log n) времени

Answer 2

справочная таблица: пользователи, как правило, возвращаются к одним и тем же областям на экране (таким образом, показатель посещений на полях обычно низкий, а показатель посещений центров, как правило, высокий).поэтому мы можем использовать эти знания для улучшения нашей работы.
после нахождения точки один раз (может быть любым другим методом нахождения) вы можете кэшировать результаты в виде списка, и в следующий раз, когда пользователь посетит то же место, поиск будет O (1).Конечно, вам нужно будет сбросить кэш после добавления новой фигуры.

другая возможность использует Шаблон наблюдателя , каждая новая фигура будет регистрироваться в нужных точках (это может быть дорого, в зависимости от того, как часто фигура вставляется ...) и после того, какмышь находится в этой точке, все, что ей нужно сделать, это позвонить тому, кто зарегистрировался в этой точке.

Третья возможность, конечно, сократить вашу область поиска, как предложено @user unknown.эта возможность может быть объединена с таблицей поиска.

Answer 3

Если вы сортируете свои элементы по более низкому x-местоположению, вы можете пропустить все элементы до определенной точки.Если у вас есть второй список с верхним x-местоположением, вы знаете, когда закончите.

Другая идея: создать сетку, возможно, разбивающую всю область на 100x100 частей.Теперь выясните, в каких частях вашей сетки фигура перекрывается:

5
4
3    xx 
2  xxxx
1  xx
0
 0 1 2 3 4 5 

Для этой фигуры это будет (1,1), (1,2) (2,2) (2,3) Карта x * y Lists теперь будет содержать эту форму s для 4 местоположений (1,1) -> s, (1,2) -> s, ...

Если вы редковставки / удаления, но часто сравнения, это ускорит ваш поиск.Вы бы посещали только фигуры, связанные с определенной ячейкой, и исследовали точные координаты для них.