Ортогональный поиск

Материал из Викиконспекты
Версия от 21:00, 19 апреля 2012; Proshev (обсуждение | вклад) (Новая страница: «== Простейший случай == Пусть дана прямая с точками на ней и отрезок. Необходимо указать, к...»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Простейший случай

Пусть дана прямая с точками на ней и отрезок. Необходимо указать, какие из изначальных точек лежат на этом отрезке.

Данная задача решается с помощью функций из STL - 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);
}

Сбалансированное дерево поиска

Квадро дерево

Инкрементальное квадо дерево