Перекрытие интевалов

[Igors]

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

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

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

Спвсибо

[Winstrol]

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

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

[Igors]

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

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

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

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

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

[Kagami]

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

[Igors]

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

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

[SimpleSunny]

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

[Kagami]

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

[Igors]

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

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

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

Спасибо за интересную наводку. Я видел "красно-черные деревья" в 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]);
  }
}

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

[SimpleSunny]

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

Код

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

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

[Igors]

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

Код:

struct CInterval {
 float mBeg, mEnd;
};

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

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

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

[SimpleSunny]

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

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

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

[Igors]

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

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

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

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

[Tonal]

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

[Igors]

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

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

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

- создаем 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 

[SimpleSunny]

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