Посоветуйте быстрый алгоритм поиска отрезков, «задевающих» заданный отрезок.

ну тут три класса:

1. левее левой границы

2. правее правой границы

3. все остальные

Ответ очевиден, время O(N).

если хоть один из концов лежит между [x1; x2] то зацепил, не? можно в M потоках просматривать N отрезков, где M * N = кол-во отрезков суммарное.

если хоть один из концов лежит между [x1; x2] то зацепил

нет. Если левый левее левой, а правый правее правой, то зацепил. Но ни один из концов не лежит.

верно. можно еще и центр отрезка проверить тогда.

не нужно центр. Не путай, он тоже не при делах. Говорю же: есть левые, есть правые, а все остальные — зелёные.

т.е.

if(K2 < G1)
 // чёрный
else if(K1 > G2)
 // чёрный
else
 // зелёный

K это концы, а G это границы.

я не вижу в ОП посте конкретизации того, как отрезки будут заданы. если это пара значений, без какой либо семантики (не указывая где левое, а где правое), то придется еще и это определять.

Что значит «левое» и «правое»? Есть 1-мерная система координат, на ней расположены отрезки разной длины. Как они заданы - это вопрос реализации, а не алгоритма.

В свое время столкнулся с такой задачей, только у меня временные диапазоны были :-) В общем-то, правило простое: A,B - «эталонный» отрезок, An,Bn - тестируемый отрезок. Если (A<Bn) and (B>An) - то отрезки пересекаются.

у меня есть не алгоритм, но структура

поведение методов этой структуры будет задано соответствующим алгоритмом, не?

Если тебе нужно в одном наборе отрезков найти множество пересечений, то полезно будет отсортировать массив по левой или по правой точке.

поведение методов структуры? ну, почему бы и нет

Проверить 2 отрезка на касание - элементарно. Хитрость в максимальной скорости поиска кучи отрезков, когда этих отрезков миллион )

Была такая идея.

Чувак, серебряной пули не бывает. Есть задача определенной вычислительной сложности, есть варианты этой подзадачи. Если у тебя один эталонный отрезок и 100500 множест мелких отрезков, генерируемых постоянно и случайно - ничего кроме тупого перебора тебе не поможет, ибо всё остальное ещё хуже.

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

У меня 100500 мелких (и не мелких) отрезков не фиксированно, но меняется достаточно редко. Основная операция - это двигать зелёный отрезок и менять его длину.

Поэтому мне интересны алгоритмы, которые требуют хранения 100500 отрезков в каких-нибудь хитрых уструктурах, позволяющих их быстро находить. Деревья там всякие. Многомерные, мать их! То есть, отрезки могут добавляться или пропадать, тогда мы будем перестраивать наши хитрые структуры, но это происходит достаточно редко.

Это похоже на умный редактор кода. Он хранит хитрую структуру с именами функций и классов и позволяет очень быстро искать всякие там сущности языка программирования, а вот операция вставки в эти структуры достаточно редкая (вы написали новую функцию), хотя и тяжёлая (надо переиндексировать, перечитывать исходник).

Попал — это значит левый или правый конец внутри эталона. Строишь два индекса: один по возрастанию левого конца, другой по возрастанию правого. Для каждого индекса двоичным поиском выясняешь диапазон попадений. Объединяешь два результата и готово.

Пост не читал, сразу отвечал. Посыпаюсь пеплом.

это значит левый или правый конец внутри эталона.

Левый левее эталона, правый правее эталона :-)

Ну так построй «список списков», в котором хранятся отрезки, на первом уровне отрезки упорядочены по левому краю, на втором - по правому, и всё что тебе надо - пробежаться по части тпервого списка, выбирая из каждого элемента по порядку определённую последовательную часть элементов второго (вложенного) списка.

А можно сделать две таких структуры, одну по метрике [A,B], вторую по метрике [B,A].

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

крутой ты чувак, наверно. Я тоже столкнулся с этой задачей в свое время. Наверно каждый в свое время сталкивается с этой задачей!

придумайте мне пожалуйста, как описать одномерный отрезок сложной структурой а не двумя числами, блять!

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

Обычное дерево. Выбирай любое из кучи уже придуманных

Тогда да, дерево.

Тут я сильно не вникал, но вроде B-деревья подойдут. Там каждый узел хранит до некоего числа N дочерних узлов, в которых занесены интервалы. например максимум дочерних узлов - 3, Тогда дети корня хранят интервалы (-inf, K1), (K1, K2), (K2, +inf). Дети детей опять подразбивают интервал. А в листах хранятся непосредственно данные, содержащиеся в данном интервале.

Тогда поиск очень прост, ты откидываешь узлы, которые своим интервалом не попадают в твой.

Добавление немного сложней, на форуме сложно объяснить.

Вроде суть передал, сам я имел дело только с R-деревьями - тем же самым, но на плоскости

я в самом деле не знаю в чем меряют сложность структур и что это вообще такое, но интуитивно пара (a, a) ничуть не сложнее пары (b, b) если все что надо от a и b — это обладать линейным порядком

То, что «отрезок» может быть на самом деле проекцией более сложной сущности, ты конечно не в курсе? Ну типа что «время начала» и «время окончания» являются свойством «поездки», в которой есть 100500 других данных типа «водитель», «маршрут», «описание груза» и т.п.? И держать в памяти миллионов временных это свосем не то же самое, что держать в памяти 10 миллионов поездок

Ты можешь к каждому отрезку хоть фильм на DVD прицепить, только это к делу не относится

Не усложняй

«Не усложняй» говори процессору с малым кэшом L3.

Перебирать каждый раз все 100500 не нужно. Добавь к свойствам отрезка результат проверки одного. Ну и дёргай саму проверку при его создании и изменении его границ. Тогда при отрисовке все нужные данные уже будут получены.

Поэтому мне интересны алгоритмы, которые требуют хранения 100500 отрезков в каких-нибудь хитрых уструктурах, позволяющих их быстро находить. Деревья там всякие. Многомерные, мать их! То есть, отрезки могут добавляться или пропадать, тогда мы будем перестраивать наши хитрые структуры, но это происходит достаточно редко.

правда «редко»?

тогда 2 массива. Сортированных. В одном левые концы, в другом правые концы.

Сложность поиска O(log(N)) (поиск дихотомией)

Сложность вставки нового отрезка O(N), но ты сказал, что это «редко».

Можно и дерево(2 дерева вместо массивов). Тогда сложность поиска и вставки O(log(N)), сложность поиска O(log(N)). Однако поиск примерно в 10 раз дольше(т.е. асимптота та же, но сама скорость ниже), расход памяти примерно тоже в 10 раз больше. Алгоритм сложнее намного.

Если дерево красно-чёрное бинарное, то в худшем случае время поиска равно удвоенной высоте, а высота равна двоичному логарифму. В случае сбалансированного дерева скорость поиска равна логарифму или логарифму+1. Но скорость вставки ниже, чем для красно-чёрного.

«Не усложняй» говори процессору с малым кэшом L3.

про преждевременную оптимизацию слышал?

ну типа

struct segment {//отрезок
  double x1;
  double x2;
};

segment segs[N]; // в этом массиве мы храним отрезки
segment *lss[N]; // в этом массиве мы храним указателе на отрезки отсортированные по лев. концу
segment *rss[N]; // а в этом по правому

я не вижу в ОП посте конкретизации того, как отрезки будут заданы. если это пара значений, без какой либо семантики (не указывая где левое, а где правое), то придется еще и это определять.

ну я исхожу из того, что K1 левый, а K2 правый. Т.е. K1<K2.

А почему именно L3?

Если памяти не жалко, бьешь измерение на кучу интервалов фиксированной или не очень фиксированной длинны (зависит от распеределения отрезков). К каждому интервалу приделываешь список отрезков, которые соприкасются с этим интервалом. Когда надо найти отрезки - получаешь список интервалов, которые соприкасаются с зеленым интервалом, получаешь список отрезков которые соприкасаются. Проверяешь только их. Можно еще сделать точнее, т.е. разграничивать поместился ли отрезок в интевал или только касается его.

class Segment
{
  // ...
  public:

  int intersects ( Segment const& o ) const throw()
  {
    return left() <= o.right() && o.left() <= right();
  }
};

class IntersectTest
{
  Segment m_seg;
public:
  IntersectTest ( Segment const& seg ) throw() : m_seg(seg)
  {
  }

  int operator()(Segment const& other ) const throw()
  {
    return m_seg.intersects(other);
  }
};

std::vector<Segment> seg;
// заполняем тут массив seg сегментами

Segment pattern; // инициализируем сегмент, пересечение с которым проверяем

// получаем диапазон сегментов, которые пересекают заданный.
std::vector<Segment>::iterator last_intersected = std::partition ( seg.begin(), seg.end(), IntersectTest(pattern) ); 

Можно partition разбить на 2 вызова, сделав не одну функцию а 2-полу теста из Segment::intersects. С этой же идеей - городить деревянные структуры в памяти. У меня сегменты хранятся в виде 64-битных значений: старшие 32 бита - длина отрезка, младшие 32 - его начало, все целочисельное. Работает достаточно быстро для моих применений.

тогда 2 массива. Сортированных. В одном левые концы, в другом правые концы.
Сложность поиска O(log(N))

Во-первых, ищется не один отрезок, а множество отрезков.

Во-вторых, если распределение неравномерное - например, 75% отрезков имеют длину в 75% интервала, оценки резко меняются (в сочетаниии с «во-первых»).

если отделить «мух от котлет», то есть хранить точки отдельно в сортированном множестве, а информация об отрезках (от какой до какой они идут) отдельно, то задача сводится к банальному поиску в сортированном масссиве, то есть O(log n) и не надо избретать лишних сущностей

тогда 2 массива. Сортированных. В одном левые концы, в другом правые концы. Сложность поиска O(log(N))

Во-первых, ищется не один отрезок, а множество отрезков.

дык массив отрезков это и есть «множество отрезков». В чём проблема?

Во-вторых, если распределение неравномерное - например, 75% отрезков имеют длину в 75% интервала, оценки резко меняются (в сочетаниии с «во-первых»).

Асимптота не меняется. Доказательство у Кнута есть. Я не силён в матане. Но ты сам подумай, на сколько дольше методом дихотомии искать ФИО в телефонном справочнике(бумажном), даже в том случае, если почти все ФИО на букву «Х». Да ненасколько. Ты всё равно каждый раз делишь множество пополам, и нет никакой разницы, что в обоих половинах почти все фамилии на «Х». Число разбиений от этого не меняется.

Ты путаешь с конечными множествами значений. Да, если тебе надо отсортировать числа «0000000000000100000000000000000000000000000010000», то как не крути, у тебя получится два сильно разных множества: одно с «11», а второе с кучей нулей. Медиану тут выбрать невозможно, т.к. мощность алфавита равна 2, и делить пополам в принципе не получится. Но у нас отрезки(я брал double), множество значений double в любом случае БОЛЬШЕ множества отрезков, потому ты _всегда_ можешь поделить _пополам_ _любой_ интервал.

1. Отсортировать, 2. перебрать. Проще простого.

Кажись, алгоритм назывался "перебор слиянием".

если отделить «мух от котлет», то есть хранить точки отдельно в сортированном множестве, а информация об отрезках (от какой до какой они идут) отдельно, то задача сводится к банальному поиску в сортированном масссиве, то есть O(log n) и не надо избретать лишних сущностей

+1

однако там два массива.

А вообще есть эквивалентная задача:

василий пупкин родился DATE_B, и умер DATE_D. Имеются N других людей(с датами рождения/смерти). Надо узнать, с какими людьми мог пересекаться василий пупкин.

Решение очевидно: надо исключить множество тех, кто умер до рождения василия. И множество тех, кто родился после смерти василия. Для этого нужна БД, с датами, и два индекса: индекс рождения и индекс смерти. Я думаю, составить запрос SQL ни у кого не составит труда.

Кажись, алгоритм назывался «перебор слиянием».

Обычный поиск в отсортированном массиве, единственное, ищем не равный, а ближайший не больший. (а в другом ближайший не меньший).

Ну а потом сливаем два найденных массива по пересечению (AND). Хотя IRL слияние обычно неявное делать, например сначала пометить все зелёными, а потом пометить часть чёрным, и ещё часть чёрным. Это уж я не знаю как нужно ТСу.

Ну так поиск-то ведется в двух массивах одновременно: чешем по зеленому, видим начало отрезка, двигаемся по черному вплоть до этой же точки и т.д.

Ну так поиск-то ведется в двух массивах одновременно: чешем по зеленому, видим начало отрезка, двигаемся по черному вплоть до этой же точки и т.д.

не. не нужно чесать, массивы отсортированы, достаточно найти нужный эл-т, а дальше просто инкремент (для дерева centr-round).

Но ты сам подумай, на сколько дольше методом дихотомии искать ФИО в телефонном справочнике(бумажном), даже в том случае, если почти все ФИО на букву «Х»

У ТС задача не найти всех на букву «X», а найти всех начинающихся на буквы А..Х и заканчивающихся на буквы В...Я, если говорить твоим примером. Сделать оценку возьмешься сам?

У ТС задача не найти всех на букву «X», а найти всех начинающихся на буквы А..Х и заканчивающихся на буквы В...Я, если говорить твоим примером. Сделать оценку возьмешься сам?

я уже всё выше расписал. Если так нравится аналогия про словари, то открой для себя т.н. обратный словарь. см. http://ru.wikipedia.org/wiki/Обратный_словарь

Я предлагаю ТСу сделать «два словаря». И искать сначала в первом, потом во втором. Это дважды по O(log(N)), т.е. O(log(N)). А дальше он получит почти готовый список своих отрезков.

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