Сравнение двух ректов

Есть массив непересекающихся ректов - такого плана:

Прикреплённая картинка

Нужно пронумировать их слева направо и сверху вниз - приблизительно как упорядочил бы их человек.

Натолкните на мысль - как сравнить два ректа? какой раньше? А то у меня что-то громоздкое получается и не все случаи учитывающее

[offtop]
А можно как-то сделать, чтобы вложенную картинку видно было?
[img]http://forum.sources.ru/index.php?act=Attach&type=post&id=2835716&attach_id=7355[/img]
[/offtop]

Сообщение отредактировано: Артур - 23.02.11, 03:52

Я бы попробовал проводить горизонтальные прямые. Движемся такими прямыми сверху вниз. Если пересклись с прямоугольником - это наш кандиат на первого. Если при движении вниз пересеклись с еще одним прямоугольником, который левее кандидата, и при этом кандидат еще не "кончился", значит меняем кандидата на того, что левее. Если кандидат кончился, а левее никого нет - обзываем его найденным, исключаем из рассмотрения и повторяем процедуру сначала.

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

Естественно, если есть массив координат прямоугольников, то проведение прямых сводится к сравнению координат вершин без всяких прямых.

Upd:
Обобщая вышесказанное прямоугольник a раньше b, если все его координаты левее и верхняя грань a выше нижней грани b, при условии что эти прямоугольники не входят в множество, образующее окружность, или перевернутую арку.

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

Сообщение отредактировано: Yakudza - 22.02.11, 06:12

Спасибо! Хорошее направление мысли

Ещё бы какие-нибудь варианты...

В общем случае "человекообразность" запараметризовать не получится. В данном же случае - на рисунке - с точки зрения "человеческой" сортировки "сверху" приоритетнее, чем "слева". Предлагаю отсортировать прямоугольники по значению y*y*x по возрастанию, где x и y - абсцисса и ордината центра прямоугольника, начало координат - в левом верхнем углу.
В случае с дугами тоже сработает, но только на определённых участках.

Можно взять центры прямоугольников и работать только с ними.

Далее - образовать горизонтальные ряды, где считается, что две точки находятся в одном ряду, если угол наклона между ними не более 45 градусов. В принципе получается то же, что и у Yakudzы, только работаем с точками.

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

Цитата ss @ 22.02.11, 10:40

В данном же случае - на рисунке - с точки зрения "человеческой" сортировки "сверху" приоритетнее, чем "слева"

рисунок сделан от балды. А направление слева направо и затем уже сверху вниз - всё-таки должно быть.

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

Цитата ss @ 22.02.11, 10:40

Предлагаю отсортировать прямоугольники по значению y*y*x по возрастанию

Откровенно говоря, не понял принципа Что нам дает квадрат топа, почему нужно умножать на х?

Давно бы уже взял и попробовал. И посмотрел, работает или нет. А потом уже начали бы разбираться, почему.
Ты просил вариантов - я чисто эмпирически родил тебе простой способ без стопицот формул и нейронных сетей, работающий в некоторых частных случаях...
Посмотри на рисунок, представь (или нарисуй) центры прямоугольников. Подумай, как количественно описать два прямоугольника на одной горизонтали так, чтобы один выгодно отличался от другого. Проще всего - x*y. (Немало величин в физике и математике количественно равно площади...) Меньше площадь - меньше порядковый номер. Меньше - лучше.
Теперь подумай, как поставить "правый верхний" прямоугольник в более выгодное положение, чем "левый нижний"... Чего проще: ниже - хуже, значит, ниже - больше, значит, умножаем ещё раз на y.
Воображение хорошо работает? Представь себе это тело - x*y*y - и представь себе такое тело для каждого прямоугольника. Вроде бы всё понятно...
Ясен перец, что коллизии возможны, но также понятно, что в общем случае эту задачу не решить простым жонглированием координатами.
Не прокатит квадрат высоты - возводи в куб! Дёшево и сердито. И выход в четвёртое измерение

Цитата Артур @ 22.02.11, 03:37

Нужно упорядочить их слева направо и сверху вниз - приблизительно как упорядочил бы их человек.

Я - человек.
Я бы не стал их переставлять - оставил, как есть.
Если требуется поступить, как поступил бы человек - самое простое решение: ничего не переставлять.
И попробуйте мне доказать, будто существует решение лучше моего!

andriano, на картинке желаемый результат - пронумерованные прямоугольники.

andriano

Цитата ss @ 22.02.11, 18:19

на картинке желаемый результат - пронумерованные прямоугольники

Угу. Ну, это я сам виноват - вопрос некорректно сформулировал Вопрос исправил

Артур, написал бы хоть, чем закончилось.

Да пока особо ничем Появились более неотложные вещи

Пока алгоритм у меня такой:

1. Изначально ректы упорядочены по верхней левой точке (3,2,4,1 и т.д).

2. Находим у каждого ректа ближайшего соседа справа.
Выбираем среди тех, чей top не ниже дна текущего, а дно не выше топа текущего. Из нескольких подходящих выбирается верхний.

3. Если справа нет соседей - значит это конец ряда

4. Если рект ни для кого не сосед справа - значит это начало ряда.
5. Соединяем все концы рядов с началами следующих рядов.

6. После прохода могут остаться неприкаянные ректы и даже неприкаянные ряды - ищем от первого такого неприкаянного соседа слева и вставляем нашего неприкаянного на место

Сообщение отредактировано: Артур - 06.03.11, 17:41