Это скорей всего известный какой-то алгоритм, просто я пока не сталкивался, и названия не знаю?
Дано много (очень много) прямоугольников заданных координатами противоположных углов (x1,y1), (x2,y2)
Прямоугольники не пересекаются.
И дана одна точка (x,y)
Нужно найти какому (или может никакому) прямоугольнику она принадлежит.

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

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


Это сообщение отредактировал(а) volatile - 6.7.2011, 00:20

Вот что пришло в голову. На словах долго объяснять, так что см картинку.



Добавлено через 2 минуты и 38 секунд
Для точки (1,1) подумай, как делать будешь 

afiskon, на твоей картинке стороны всех прямоугольников параллельны. В условии же этого нет. Но принцип, наверное, не измениться.

Думаю, что можно делать просто:

• Рассортировать прямоугольники по вертикали и по горизонтали.
• Бинарным делением отбросить прямоугольники, лежащие ниже и всыше точки.
• Бинарным делением отбросить те, что справа и слева.
• Если прямоугольники параллельны осям (как на картинке), останется один.
• Если не параллельны - проверить точку на принадлежность каждому из оставшихся перебором - не много перебирать придется.
• Как проверять - вот только что обсуждали.

1) Отсортировать по левому верхнему углу (по х, потом по у); искать сканирующей линией; получается O(NlogN) вроде как
(Если прямоугольники не прямые (не параллельные осям) тогда сортировать надо по мин x, потом мин y (или наоборот, в зависимости от сканирующей линии)
3) Простые прямоугольные (квадратные) кластеры (в каждом - список ссылок на пересекающий прямоугольник); хорошо работает, если прямоугольники распределены более менее равномерно
2) Если существенно не равномерно, то дерево (тоже самое что выше, но кластеры не одинаковые, а иерархические; делятся по заполнении)

А что, если отсортировать прямоугольники по длине и углу ралиус-вектора их центра? Мне кажется, это должно неплохо работать. И понадобится только одно бинарное дерево или массив для бинарного поиска.

Добавлено через 7 минут и 40 секунд
И еще. Вспомнился 100% рабочий быстрый алгоритм, который работает для любых выпуклых многоугольников. Нейронная сеть.

Добавлено через 9 минут и 40 секунд
Кстати, нейросети работают даже для пересекающихся многоугольинков.

Это сообщение отредактировал(а) afiskon - 5.7.2011, 07:53

и никто не говорит, что предлагают алгоритмы, если необходимо определять факт пересечения для множества точек.
Автор топика явно указал, что дается только одна точка, а в этом случае самым быстрым алгоритмом будет элементарный линейный поиск, однократный проход за O(N). А все остальное - O(NlogN), O(N^2)... Вот если мы заранее знаем, что у нас прямоугольники каким либо образом упорядочены (заранее даются сортированными), то тогда конечно, O(logN).

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


Earnest, Насчет NlogN, если вы не ошиблись, то, как привильно сказал Silent  ведь простой перебор всех прямоугольников будет N, то есть меньше чем NlogN. Но вероятно вы ошиблись именно в формуле, а сам алгоритм быстрее. я пока не соображу.

(Уточнение добавил в первый пост)
Уточнение к условию: Все прямоугольники паралельны/перпендикулярны осям! но размеры разные. могут быть высокие узкие, широкие низкие, и т.д. Прямоугольники статичны, то есть их можно отсортировать (время сортровки не считать!)
то есть сортируется один раз, и дальше поступает по одной точке, и надо быстро давать ответ какому пр-ку она принадлежит.

Если у кого какие идеи еще, велкам!

Это сообщение отредактировал(а) volatile - 6.7.2011, 01:10

Вот так прямо глядя в потолок вы взяли и определили самый быстрый алгоритм, ага  А если я вам скажу, что нейросеть можно оптимизировать до O(log(N)) ?

Как определить, что точка находится внутри выпуклой фигуры? Нужно, чтобы она находилась с определенной стороны по отношению к каждой из примой, образованной парой соседних точек фигуры. Прямая на плоскости задается линейным уравнением ax + by = c, притом для точек с одной стороны выполняется условие ax+by < c, а с другой ax + by > c. Таким образом несложно построить дерево (а фактически - нашу сеть) из таких проверок, приводящее нас к решению задачи. Первая проверка отсечет пол плоскости, вторая оставит "четверть" и так далее.

Второй день порываюсь спросить afiskon, какой тип нейронной сети вы имеете в виду? Судя по вашему описанию, речь идет о построении дерева решений, но это не совсем нейросетка. 

В любом случае, если иметь дело с неупорядоченным массивом, то получается прямой поиск за время O(N), если отсортировать каким-либо образом, то применяя хоть дерево решений, хоть бинарный поиск (по-сути, вариации одного и того же) время будет O(logN). Доступ за константное время только в распараллеленом прямом поиске (игра не стоит свеч), хэш-таблице (вопрос построения ключа), нейросетевой структуре, в качестве обертки параллельного прямого поиска (мало похоже на правду).

volatile, напишите, пожалуйста, как сделали в конце-концов - интересно. И, если можно, откуда взялась такая задача? Уже не первый раз всплывает такая постановка.

Это сообщение отредактировал(а) Skevalt - 6.7.2011, 09:13

Условие if(ax+by+c > 0) - это обычный перцептрон. Уже небольшая нейросеть. У нас их много - получаем большую нейросеть. Строить и обходить ее в целях оптимизации следует подобно тому, как строят и обходят бинарные деревья.

оптимизация займет время, не так ли? Silent имел в виду алгоритм без предварительной обработки.
с предварительной обработкой (за O(NlogN)) и без нейронных сетей все чудно ищется за O(logN). А с привлечением дополнительной памяти - за O(1). и чейто я сомневаюсь, что оптимизация нейронной сети не сложнее сортировки

Добавлено через 7 минут и 7 секунд
а, Вы же написали:

построение такого дерева те же O(NLogN), только коэффициент поболе, чем у сортировки. плюс надо память под дерево.

Да, я как-то не заметила про одну точку, и не совсем корректно написала: первый N Относится к числу точек, а второй (под логарифмом) к прямоугольникам; время сортировки не учитывалось.
Если точка конкретно одна, и прямоугольники никак не упорядочены, то линейный поиск - самое оно. Другое дело, что в зависимости от условий задачи возможно, что начальное упорядочивание прямоугольников будет полезно. 
Что касается сетей и прочих изысков, то для одного запроса не стоит огород городить. Даже если прямоугольников будет тысяча, никто не заметит. Так что чем проще метод, тем лучше.
Например, у меня есть несколько тысяч или даже сотен тысяч граф. объектов, которые нужно вывести на экран. У всех хранятся прямоугольники-экстенты. Так вот при сравнении экстентов с текущим экраном я использую тупой линейный просмотр всего массива (проверяется пересечение с текущим экраном). И никаких задержек из-за этого, даже при быстрой прокрутке/масштабировании. Т.е. нужно смотреть, что у вас делается после \ вместе с поиском.
Прямоугольники лучше хранить нормализованными, если есть возможность - тогда каждая проверка сводится к 2 двойным условиям...

Добавлено @ 12:41

Ну вот, оказывается все же не одна точка...

Вопрос, что значит "быстро ответить". Если это интерактив, то можно тоже не париться (см. мой пример). Разве что для красоты.
Для ускорения можно и дерево решений построить, и отсортировать - все будет искать за log от числа прямоугольников.
Но дерево решений придется перестраивать каждый раз при добавлении / удалении прямоугольников. 

Я кажется внимательно рассмотрел каждое предложение.
Так попробую пообсуждать некоторые мысли. Прошу только не обижаться.  
Моя цель не обидеть кого-то, а докопаться до истины. А то всяко бывает...


Так. стоп.
У каждого прямоугольника две стороны, по какой сортировать?
Нельзя же отсортировать сразу по двум. значит 2 индекса.
По вертикали и по горизонтали. Опять два индекса, один по вертикали, другой по горизонтали?
Итого 2 направления X 2 стороны = 4 индекса получается.  Дальше,
Допустим 4-мя бинарными поисками мы таки нашли в 4 индексах границы. Что дальше?
Как отбросить неподходящие? мозги не работают. Индексы разные ведь.
Получается надо пробегать все прямоугольники в 1 индексе левее найденного
во 2 правее найденного, в 3 выше найденного, в 4 ниже найденного.
Получается мы пробежали по всему массиву 2 раза, и это не считая 4 бинарных поисков.
Имхо, быстрее простой перебор.


Здесь есть один сущесвенный недостаток. Если я правильно понял, нужно сортировать массив каждый раз на каждую новую точку, чтобы она приходилась на центр. Это слишком медленно. Условие сортировать массив только один раз в начале!
И чтоб эта сортировака работала на любые будущие точки. Как в бинарном поиске.


Ух... Что-то страшное, Никогда не сталкивался, честно признаюсь.
И инфу пока не искал по этому вопросу. Надеюсь обойтись чем-то более знакомым.
И конечно, надо будет заполнить пробел в знаниях как нибудь в любом случае. спасибо.


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


baldina, А как? извините мою тупость. Вы деревья имеете ввиду или бинарный поиск? Последний как-то не встравивается у меня никак. Над деревьями пока серьёзно не задумывался.


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

например k-d деревья. на плоскости это 2-d дерево.
придуманы и другие структуры, но в любом случае структура должна быть двумерной, либо наихудшая производительность поиска будет линейна

baldina,
Это кажется, как раз в точку, и заодно убивает следующий мой вопрос про то-же самое но с параллелепипедами, то есть 3D
спасибо!

Это ведь правда мудрая мысль. Наверняка у тебя есть чем заняться, кроме ускорения поиска прямоугольников. Сначала убедись, что ускорять надо, а уже потом трать на это время. Всего-то нужно инкапсулировать функцию запроса, чтобы потом ее можно было легко переписать не тревожа остальной код - если будут тормоза. И вообще, как сказал кто-то из гуру, "самый надежный код - тот, которого нет".

Но, на всякий случай, на будущее:

Сортировать только по минимуму. Либо по максимуму. Разницы особой нет, зависит от  вида запросов. 
А размер (длину-ширину) учитывать уже при запросе, это ведь просто.

Добавлено через 8 минут и 48 секунд

Вовсе не все, а только до того прямоугольника, координата которого >= точки запроса (это если отсортировано по минимумам). И оставлять для дальнейшей проверки только те прямоугольники, у которых мин+длина <= точки запроса. То же самое по другой координате. Полученные списки пересечь.
Можно вообще оставить только один индекс, а попадание по другой координате проверять явно (для каждого прямоугольника из найденной последовательности). Число проверяемых прямоугольников существенно уменьшается.

Хорошо, давайте разберемся с этим.

Вот простейший случай 9 одинаковых кубиков. Кубики отсортированы по левому краю, порядковые номера в индексе показаны.
Допустим точка попала в центр. По индексу она попала между 6 и 7.
Итак с 7 по 9 мы точно отбрасываем. Необходимый кубик где-то ниже или равен 6. (т.е. в диапазоне 1...6)
Начинаем с 6 и вниз. До какого пробегать?

т.е меня интересует что поставить вместо END

for (int i= 6; i>END; --i)
   if (совпали?)
      break;

ИМХО простой перебор вседа самый долгий. Ну, если, конечно, у Вас не пара-тройка прямоугольников. Но я не утверждаю, что мое предложение самое быстрое.

Я поленился расписывать совсоем уж детально. Поэтому Вы и поняли это как многократные пробежки. Попробую уточнить.

• Отсортировать действительно надо 4 раза. Отдельно по кажой границе прямоугольников. Но Вы пишете, что время сотрировки значения не имеет - так что хоть 400 раз, но заранее - до поступления запроса на поиск точки (как я понял).
• Отбрасывать прямоугольники лежащие выше точки надо используя сортировку по нижней границе, ниже - по верхней и т.д. Отбрасывать надо из всего набора, естественно.
• Поиск в сортированном массиве надо проводить никак не пробежкой, а бинарным делением, например. Если на память ограничений нет, можно заранее построить бинарные деревья - быстрее будет.
• Закономерный вопрос - как отбрасывать, чтобы было быстро. Не размеры же массива каждый раз переустанавливать. На этот вопрос я не отвечу - все зависит от возможностей конкретного языка програмирования: какие в нем имеются структуры данных и сколь они быстры.

Еще раз - на звание разработчика самых быстрых алгоритмов я не претендую  

Да, ты прав, я спутала с одномерными интервалами. Ранее вроде предполагалось, что прямоугольники не пересекаются. Но проекции их запросто могут.
И доп. индексы тоже особо не спасают, т.к. скорее все запутывают. Можно, конечно, делать как предлагает Y: "отбрасывать" - фактически, вычислять пересечение  множеств - 2 или 4 (если по всем сторонам индексировать), но как-то это чересчур. 
Лучше уж кластеры.
ЗЫ
Есть еще способ отобразить плоскость в линию с помощью фракталов. В этом случае точки плоскости упорядочиваются в соответствии со своим порядком на фрактальной линии. Но это как-то слишком кучеряво для данной задачи.

В принципе к-д дерево, что предложил baldina и приводит к-мерное пространство к одномерной системе. 
(Это я своими словами.   , но помоему не далеко от сути ?)
Трудность только построить эффективное дерево автоматически...

Не, это как раз не очень трудно... похоже на деревья решений. Смысл в том, что каждый раз нужно выбрать "наиболее разделяющее" значение.
Просто страшно поначалу, потому что слова все такие умные. Это я свои впечатления излагаю, как раз недавно с Decision Tree разбиралась. Оказалось, если не сильно умничать со всякими там улучшениями, ничего страшного. Главное, действительно быстро (и строит и классифицирует).
Но это, конечно, не сведение к одномерной системе, а линейный классификатор. Но не в терминах суть.
Если у тебя есть время \ возможность \ желание заморачиваться, попробуй. Решение в самом деле красивое. 

 Подскажи, пожалуйста, где описано хорошо, коротко и, желательно, почти без примеров. Мне тоже интересно.
 

В Вики, конечно. Читать английский вариант. Потом идешь по ссылке на алгоритм ID3. Там где-то рядом есть и код, но не читабелен, имхо. Проще разобраться и написать самому. Без примеров вряд ли что-то найдешь; причем почему-то примеры всегда на редкость дебильные; при этом все про дискретный случай и про булевские функции (да\нет). Но для небулевских (несколько классов) строится точно так же (все эти энтропии и прочая хрень). Про действительные переменные тоже можно что-то найти, но в основном додумывается, после погружения в тему. Я весь поиск начинала с Вики, оттуда по ссылкам и т.д. По старой привычке храню не ссылки, а скачиваю документы, поэтому ссылками не поделюсь. Но найти не проблема.

У прямоугольников всегда все стороны параллельны

Это сообщение отредактировал(а) I_Am_Rock - 11.7.2011, 14:36

Если про эту задачу, то, когда я писал, параллельность задана не была.
Если вообще - то это, звиняюсь, как?

вроде как по вашему адресу
http://en.wikipedia.org/wiki/R-tree