Это скорей всего известный какой-то алгоритм, просто я пока не сталкивался, и названия не знаю?
Дано много (очень много) прямоугольников заданных координатами противоположных углов (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
спасибо!