Russian Qt Forum
Ноябрь 23, 2024, 04:46 *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

Войти
 
  Начало   Форум  WIKI (Вики)FAQ Помощь Поиск Войти Регистрация  

Russian Qt Forum > Forum > Программирование > Алгоритмы > Перекрытие интевалов
Страниц: [1]   Вниз
« предыдущая тема следующая тема »
  Печать  
Автор Тема: Перекрытие интевалов  (Прочитано 14261 раз)
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« : Сентябрь 16, 2009, 13:35 »
Здравствуйте

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

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

Спвсибо
Записан
Winstrol
Гость
« Ответ #1 : Сентябрь 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 перекрываются.
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #2 : Сентябрь 16, 2009, 14:49 »
Цитата: 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 перекрываются.

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

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

Тогда сортированный порядок A2, A3, A1. Значит для интервала X(1, 2) получаем: перекрытий нет. Хммм... неверно  Улыбающийся
Записан
Kagami
Гость
« Ответ #3 : Сентябрь 16, 2009, 15:01 »
1. Сортируем интервалы сначала по t0, а если они одинаковы, то по t1.
2. Начинаем перебирать отсортированные интервалы по порядку.
2.1. Если конечное значение (t1) проверяемого интервала меньше начального (t0) значения очередного интервала из списка, то выходим из цикла.
2.2. Если t0 проверяемого интервала больше t1 очередного интервала из списка, то переходим к следующему.
2.3. Если оба условия выше не выполнились, то у нас есть пересечение.
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #4 : Сентябрь 16, 2009, 16:03 »
Цитата: Kagami от Сентябрь 16, 2009,  15:01
1. Сортируем интервалы сначала по t0, а если они одинаковы, то по t1.
2. Начинаем перебирать отсортированные интервалы по порядку.
2.1. Если конечное значение (t1) проверяемого интервала меньше начального (t0) значения очередного интервала из списка, то выходим из цикла.
2.2. Если t0 проверяемого интервала больше t1 очередного интервала из списка, то переходим к следующему.
2.3. Если оба условия выше не выполнились, то у нас есть пересечение.
Все так, но это сокращает прямой перебор только в 2 раза
Записан
SimpleSunny
Гость
« Ответ #5 : Сентябрь 16, 2009, 19:36 »
Кормен. Алгоритмы: Построение и анализ. 2 изд.
Глава 14.3 Деревья отрезков.
Там на основе красно-черных деревьев приводится алгоритм поиска со сложностью O(lg n) одного такого отрезка.
В упражнениях предлагают найти алгоритм для поиска всех таких отрезков со сложностью O (min (n, k * lg n)). k - количество таких отрезков.
Стоит также обратить внимание на заключительные замечания в ней ссылаются на работу со сложностью поиска все таких отрезков O (k + lg n).
« Последнее редактирование: Сентябрь 16, 2009, 20:38 от SimpleSunny » Записан
Kagami
Гость
« Ответ #6 : Сентябрь 16, 2009, 23:16 »
На самом деле он сокращает больше. Помимо того что используется только две проверки, в п.2.1 мы выходим из цикла до окончания полного перебора как только понимаем что искать больше нечего.
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #7 : Сентябрь 17, 2009, 14:22 »
Цитата: Kagami от Сентябрь 16, 2009,  23:16
На самом деле он сокращает больше. Помимо того что используется только две проверки, в п.2.1 мы выходим из цикла до окончания полного перебора как только понимаем что искать больше нечего.
Согласен, но хочется большего Улыбающийся Предположим у нас всего 10К интервалов (очень мало), в среднем имеем 5К проверок - жирновато.

Цитата: SimpleSunny от Сентябрь 16, 2009,  19:36
Кормен. Алгоритмы: Построение и анализ. 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]);
  }
}
Как сделать это поумнее?
« Последнее редактирование: Сентябрь 17, 2009, 14:34 от Igors » Записан
SimpleSunny
Гость
« Ответ #8 : Сентябрь 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). А так бинарный поиск с возможными улучшениями исходя из особенностей интервалов.
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #9 : Сентябрь 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;
};
Сортируем точки и идем по ним. Каждая новая точка либо "закрывает" имеющийся интервал, либо "открывает" новый.  Что дальше - пока не знаю, подумаю.
Записан
SimpleSunny
Гость
« Ответ #10 : Сентябрь 17, 2009, 23:27 »
Может тогда все таки стоит использовать деревья? Ничего страшного в них нет, есть же готовые реализации как для С++, так и для С, хоть и не так много (к примеру http://www.geocities.com/wkaras/gen_cpp/avl_tree.html).

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

Но все это имеет смысл, если накладные расходы построение дерева окупят поиск.
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #11 : Сентябрь 18, 2009, 18:30 »
Цитата: SimpleSunny от Сентябрь 17, 2009,  23:27
Может тогда все таки стоит использовать деревья? Ничего страшного в них нет, есть же готовые реализации как для С++, так и для С, хоть и не так много (к примеру http://www.geocities.com/wkaras/gen_cpp/avl_tree.html).

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

Но все это имеет смысл, если накладные расходы построение дерева окупят поиск.
По задаче окупаемость практически гарантирована. Алгоритм в книге я понял, на мой взгляд он ничем не отличается от одномерного BSP (parent знает границы в которых лежат его children). Но вот возни с ним довольно много. Поскольку мне нужно проверить "каждый с каждым" я надеюсь есть лучший способ. Сделаю - отпишусь Улыбающийся
А за книгу в любом случае спасибо
Записан
Tonal
Гость
« Ответ #12 : Сентябрь 22, 2009, 07:40 »
А если все интервалы уже в дерево засунуты, то одним проходом по дереву разве не выдёргиваются все пересечения?
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #13 : Сентябрь 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  Улыбающийся
Записан
SimpleSunny
Гость
« Ответ #14 : Сентябрь 23, 2009, 20:55 »
Действительно красиво для постановки задачи "все со всеми".
Записан
Страниц: [1]   Вверх
  Печать  
« предыдущая тема следующая тема »
 
Перейти в:  


Страница сгенерирована за 0.088 секунд. Запросов: 22.