Печать страницы - Перекрытие интевалов

Название: Перекрытие интевалов
Отправлено: Igors от Сентябрь 16, 2009, 13:35

Здравствуйте

Есть массив интервалов. Каждый интервал задан парой значений float [t0, t1]. Гарантируется что t0 <= t1. Для простоты можно полагать что это интервалы времени. Интервалы могут быть как угодно большими (в пределах float) и перекрываться произвольно.

Нужно: для интервала X найти все элементы массива с которыми он перекрывается. Сам X может быть как элементом массива так и нет.

Спвсибо

Название: Re: Перекрытие интевалов
Отправлено: Winstrol от Сентябрь 16, 2009, 13:43

Что если для интервалов [a1;a2] и [b1;b2] ввести отношение порядка и отсортировать все это дело?
[a1;a2] < [b1;b2] ==true , если a2<b1

Интервалы [a1;a2] < [b1;b2]==false [b1;b2]< [a1;a2] ==false перекрываются.

Название: Re: Перекрытие интевалов
Отправлено: Igors от Сентябрь 16, 2009, 14:49

Цитата: Winstrol от Сентябрь 16, 2009, 13:43

Пусть есть такие интервалы

A1(0, 100);
A2(10, 20);
A2(30, 40);

Тогда сортированный порядок A2, A3, A1. Значит для интервала X(1, 2) получаем: перекрытий нет. Хммм... неверно :)

Название: Re: Перекрытие интевалов
Отправлено: Kagami от Сентябрь 16, 2009, 15:01

1. Сортируем интервалы сначала по t0, а если они одинаковы, то по t1.
2. Начинаем перебирать отсортированные интервалы по порядку.
2.1. Если конечное значение (t1) проверяемого интервала меньше начального (t0) значения очередного интервала из списка, то выходим из цикла.
2.2. Если t0 проверяемого интервала больше t1 очередного интервала из списка, то переходим к следующему.
2.3. Если оба условия выше не выполнились, то у нас есть пересечение.

Название: Re: Перекрытие интевалов
Отправлено: Igors от Сентябрь 16, 2009, 16:03

Цитата: Kagami от Сентябрь 16, 2009, 15:01

Все так, но это сокращает прямой перебор только в 2 раза

Название: Re: Перекрытие интевалов
Отправлено: SimpleSunny от Сентябрь 16, 2009, 19:36

Кормен. Алгоритмы: Построение и анализ. 2 изд.
Глава 14.3 Деревья отрезков.
Там на основе красно-черных деревьев приводится алгоритм поиска со сложностью O(lg n) одного такого отрезка.
В упражнениях предлагают найти алгоритм для поиска всех таких отрезков со сложностью O (min (n, k * lg n)). k - количество таких отрезков.
Стоит также обратить внимание на заключительные замечания в ней ссылаются на работу со сложностью поиска все таких отрезков O (k + lg n).

Название: Re: Перекрытие интевалов
Отправлено: Kagami от Сентябрь 16, 2009, 23:16

На самом деле он сокращает больше. Помимо того что используется только две проверки, в п.2.1 мы выходим из цикла до окончания полного перебора как только понимаем что искать больше нечего.

Название: Re: Перекрытие интевалов
Отправлено: Igors от Сентябрь 17, 2009, 14:22

Цитата: Kagami от Сентябрь 16, 2009, 23:16

Согласен, но хочется большего :) Предположим у нас всего 10К интервалов (очень мало), в среднем имеем 5К проверок - жирновато.

Цитата: SimpleSunny от Сентябрь 16, 2009, 19:36

Спасибо за интересную наводку. Я видел "красно-черные деревья" в std::set но те ли это деревья - не знаю :)

Однако все это выглядит пугающе сложно, а место для этой задачи у меня скромное - всего лишь подзадача для другой. Поэтому хочется решить подешевле/попроще но без прямого перебора. Здесь я могу несколько изменять задачу. Допустим я могу обеспечить что поиск выполняется только для интервалов которые сами в массиве. Тогда тупая реализация выглядит так:

Код:

CInterval inter[num];
...
for  (int i = 0; i < num - 1; ++i) {
  for (int j = i + 1; j < num; ++j) {
    if (Intersect(inter[i], inter[j]))
     DoProcess(inter[i], inter[j]);
  }
}

Как сделать это поумнее?

Название: Re: Перекрытие интевалов
Отправлено: SimpleSunny от Сентябрь 17, 2009, 15:58

Если ~~деревья кажутся страшными~~ нет такой необходимости заметно снизить скорость поиска, то могу предложить только улучшенный вариант с сортировкой (на обновленную постановку задачи).
1. Сортируем интервалы по левой границе.
2. Перебираем все интервалы.
3. Данный интервал будет пересекаться с интервалами, которые находятся "справа" от текущего и у которых Левая граница < правой границы текущего интервала. Т. е. задача стоит в том, чтобы найти такой элемент "x", для которого

Код

C++ (Qt)
(mas[x].left <= current.right) && (mas[x + 1].left > current.right)

. Тогда найдя такой элемент "x", все элементы расположенные между "x" и текущим будут пересекаться с текущим.
Тогда просто необходимо будет разработать процедуры поиска, эффективную за прямой перебор.
Если интервалы равномерно распределены на числовой плоскости, то можно использовать "интерполяционный поиск", как его обозвал Кнут. Его отличие от бинарного поиска состоит в том, чтобы не делить отрезок всегда на 2 равные части, а предугадывать наличие ключа в определенном месте, если известно примерный закон распределения чисел. Но это только для большего количества данных (~2 ^ 16). А так бинарный поиск с возможными улучшениями исходя из особенностей интервалов.

Название: Re: Перекрытие интевалов
Отправлено: Igors от Сентябрь 17, 2009, 18:07

Алгоритма пока ясно не вижу, но есть задумка. Что если работать не с интервалами а разбить их на 2 точки?

Код:

struct CInterval {
 float mBeg, mEnd;
};

struct CPoint {
 float Get( void ) const { return mBegin ? mInter->mBeg : mInter->mEnd; } 

// data
 CInterval * mInter;
 bool          mBegin;
};

Сортируем точки и идем по ним. Каждая новая точка либо "закрывает" имеющийся интервал, либо "открывает" новый. Что дальше - пока не знаю, подумаю.

Название: Re: Перекрытие интевалов
Отправлено: SimpleSunny от Сентябрь 17, 2009, 23:27

Может тогда все таки стоит использовать деревья? Ничего страшного в них нет, есть же готовые реализации как для С++, так и для С, хоть и не так много (к примеру http://www.geocities.com/wkaras/gen_cpp/avl_tree.html (http://www.geocities.com/wkaras/gen_cpp/avl_tree.html)).

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

Но все это имеет смысл, если накладные расходы построение дерева окупят поиск.

Название: Re: Перекрытие интевалов
Отправлено: Igors от Сентябрь 18, 2009, 18:30

Цитата: SimpleSunny от Сентябрь 17, 2009, 23:27

По задаче окупаемость практически гарантирована. Алгоритм в книге я понял, на мой взгляд он ничем не отличается от одномерного BSP (parent знает границы в которых лежат его children). Но вот возни с ним довольно много. Поскольку мне нужно проверить "каждый с каждым" я надеюсь есть лучший способ. Сделаю - отпишусь :)
А за книгу в любом случае спасибо

Название: Re: Перекрытие интевалов
Отправлено: Tonal от Сентябрь 22, 2009, 07:40

А если все интервалы уже в дерево засунуты, то одним проходом по дереву разве не выдёргиваются все пересечения?

Название: Re: Перекрытие интевалов
Отправлено: Igors от Сентябрь 23, 2009, 17:52

Цитата: Tonal от Сентябрь 22, 2009, 07:40

Выдергиваются, но проход рекурсивный и это нежелательно/неприятно. Вообще дерево здесь ("найти всех") совсем не так эффективно как обычно. Оно позволит только исключить некоторые ветви, что конечно, быстрее перебора. Но на этом достижения заканчиваются - о логарифмах говорить не приходится, если ветка не отсечена, надо топать дальше по ее левому ноду, а то и по по обоим. Зачем же мне возиться с деревом если оно скоростью не блещет?

Реализовал такой алгоритм и скоростью доволен:

- создаем 2 точки (вход/выход) для каждого интервала (см предыдущие посты)
- сортируем точки и перебираем их одну за одной. Два варианта:
- точка "конец интервала". Тогда просто удаляем интервал из списка открытых интервалов.
- точка "начало интервала". Тогда этот интервал перекрывается со всеми открытыми. Фиксируем (выдаем на гора) все перекрытия. После этого добавляем интервал в список открытых интервалов.

Организация списка открытых интервалов очевидна, все операции очень быстрые и память на список выделяется 1 раз (до цикла). Алгоритм легко "запечатывается" в класс

Код:

struct CIntervalLookup {
    CIntervalLookup( CInterval * intr, size_t count ); // can be also a vector, list etc
  ~CIntervalLookup( void );                                  // destroys internal points and lists

    bool NextInters( size_t theIndex[2] );               // returns false if no more overlapped intervals 
                                                                     // otherwise fills theIndex with 2 indices
     ....
};

Voila :)

Название: Re: Перекрытие интевалов
Отправлено: SimpleSunny от Сентябрь 23, 2009, 20:55

Действительно красиво для постановки задачи "все со всеми".

Russian Qt Forum

Программирование => Алгоритмы => Тема начата: Igors от Сентябрь 16, 2009, 13:35