Ортогональный поиск
Содержание
Простейший случай
Пусть дана прямая с точками на ней и отрезок. Точки даны в отсортированном порядке. Необходимо указать, какие из изначальных точек лежат на этом отрезке.
Данная задача решается с помощью функций из STL - upper_bound и lower_bound.
upper_bound возвращает наименьшее значение больше данного, lower_bound - наибольшее значение меньше данного.
Рассмотрим на примере:
Код реализации:
template<class RauIter, class OutIter, class Scalar> OutIter range_search(RauIter p, RauIter q, OutIter out)
{
return std::copy(lower_bound(p, q, l), upper_bound(p, q, r), out);
}
Сбалансированное дерево поиска
Переходим к двумерному случаю. Пусть дано некоторое множество точек на плоскости. Нам необходимо ответить, какие именно из них лежат в некотором заданном прямоугольнике.
Для этого возьмем любое сбалансированное дерево поиска и слегка модернизируем его для более быстрой работы.
В каждом узле будем хранить точки, которые входят в его поддерево.
Теперь для ответа нам нужно спуститься отрезком по дереву и, если все поддерево лежит в отрезке, сразу выдавать его, если нет - спускаться дальше.
