Как сравнить два ректа?

Различные алгоритмы, связанные с выводом графики.
arthur2
Продвинутый гуру
Продвинутый гуру
Аватара пользователя
 
Сообщения: 1598
Зарегистрирован: 23.01.2008 (Ср) 14:35

Как сравнить два ректа?

Сообщение arthur2 » 22.02.2011 (Вт) 6:59

Есть массив непересекающихся ректов - такого плана:
Изображение
Нужно пронумировать их слева направо и сверху вниз - приблизительно как сделал бы это человек.

Натолкните на мысль - как сравнить два ректа? какой раньше? А то у меня что-то громоздкое получается и не все случаи учитывающее :(
Вложения
Clipboard01.gif
(5.3 Кб) Скачиваний: 338
Последний раз редактировалось arthur2 22.02.2011 (Вт) 11:36, всего редактировалось 1 раз.
Артур
 
   

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16079
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: Как сравнить два ректа?

Сообщение Хакер » 22.02.2011 (Вт) 9:14

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

Не знаю, кто бы так отметил пятый и шестой...

Задача не формализуема, алгоритма не будет.
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

arthur2
Продвинутый гуру
Продвинутый гуру
Аватара пользователя
 
Сообщения: 1598
Зарегистрирован: 23.01.2008 (Ср) 14:35

Re: Как сравнить два ректа?

Сообщение arthur2 » 22.02.2011 (Вт) 9:23

arthur2 писал(а):приблизительно как упорядочил бы их человек

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

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16079
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: Как сравнить два ректа?

Сообщение Хакер » 22.02.2011 (Вт) 9:28

Таких алгоритмов (разных) можно придумать очень много. Но я не придумаю ни одного, котоый бы расставил числа так, как они расставлены на картинке.
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

arthur2
Продвинутый гуру
Продвинутый гуру
Аватара пользователя
 
Сообщения: 1598
Зарегистрирован: 23.01.2008 (Ср) 14:35

Re: Как сравнить два ректа?

Сообщение arthur2 » 22.02.2011 (Вт) 9:31

Хорошо, а как бы ты расставил те, что на картинке?
Разночтение, как я понимаю, здесь: 6, 7, 8, 5, так чтоли? А как тогда с девятым?
Артур
 
   

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16079
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: Как сравнить два ректа?

Сообщение Хакер » 22.02.2011 (Вт) 10:18

arthur2 писал(а):Хорошо, а как бы ты расставил те, что на картинке?

Я бы не расставлял, потому что мне это не нужно. Но я вижу многообразие алгоритмов. Оно есть. Ты его не видишь что-ли?
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

Денис
Доктор VB наук
Доктор VB наук
Аватара пользователя
 
Сообщения: 2734
Зарегистрирован: 07.11.2006 (Вт) 13:55
Откуда: Ейск, Краснодарский край

Re: Как сравнить два ректа?

Сообщение Денис » 22.02.2011 (Вт) 10:41

arthur2 писал(а):как сравнить два ректа? какой раньше?

Предлагаю такой вариант. Сканирующая линия движется из верхнего левого угла области в правый нижний угол. Линия наклонена на угол ~20 градусов (варьируя угол наклона, можно получать результаты разной объективности, визуально на прикрепленной картинке тот угол, что выбран, кажется наиболее подходящим).
Во время движении линии, отлавливаются пересечения с нею верхних левых углов ректов (другой вариант, пересечения с центрами ректов) и по результату отлова им выдаются порядковые номера.
Вложения
Clipboard01.png
пример
Программирование — богоизбранная дисциплина! Если бог и есть, то вселенную он скомпилировал, не иначе.

Proxy
Профессор VB наук
Профессор VB наук
Аватара пользователя
 
Сообщения: 2844
Зарегистрирован: 31.08.2007 (Пт) 4:41

Re: Как сравнить два ректа?

Сообщение Proxy » 22.02.2011 (Вт) 10:54

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

Если по аналогии с расположением окон на экране, то тут в большей степени от человека зависит то, как бы он их разместил. Тоже прямоугольники в какой-то мере. Я даже не берусь судить из каких соображений я это делаю, но явно не из отношения площадей прямоугольников, отношения высоты к ширине каждого прямоугольника и т.п. Сегодня так удобно, завтра иначе. Ну если представить эти прямоугольники листами бумаги, которые необходимо как-то разложить "по-умному", то пожалуй я бы их разложил в таком порядке, чтобы между ними оставалось как можно меньше незанятой области (чтобы оптимально можно было "состыковать"). Если подходить к вопросу с точки зрения эстетики, то, вполне возможно, придётся обратиться к золотому сечению.
Follow the white rabbit.

arthur2
Продвинутый гуру
Продвинутый гуру
Аватара пользователя
 
Сообщения: 1598
Зарегистрирован: 23.01.2008 (Ср) 14:35

Re: Как сравнить два ректа?

Сообщение arthur2 » 22.02.2011 (Вт) 11:33

Хакер писал(а):Я бы не расставлял, потому что мне это не нужно.
Угу, можно было бы ожидать - абстрактно порассуждаешь об вообще. Ты, конечно, очень часто и очень сильно помогаешь, но перед этим всю душу вынешь своей манерой ходить кругами и уворачиваться. Как всегда:
Артур писал(а):
Хакер писал(а):Twister, ты обломал весь кайф открытия того, что <нужное вставить исходя из контекста>, у Артура, и весь кайф созерцания процесса открытия и описания мыслей по этому поводу Артуром — у меня.
Кайф у тебя какой-то садисткий. Впрочем, давно подозревал.


Денис В общем, мысль интересная, спасибо :) Но вообще-то, расклад ведь может быть и с наклоном в другую сторону и даже в пределах одной картинки - в разные стороны - например, по кругу... Буду подумать :oops:

Proxy ты не понял :) Нужно не перераспределить, а просто пронумеровать. Хотя, скорее - это я не вполне корректно сформулировал :oops:
Артур
 
   

iGrok
Артефакт VBStreets
Артефакт VBStreets
 
Сообщения: 4247
Зарегистрирован: 10.05.2007 (Чт) 16:11
Откуда: Сетевое сознание

Re: Как сравнить два ректа?

Сообщение iGrok » 22.02.2011 (Вт) 13:33

arthur2 писал(а):Хотя, скорее - это я не вполне корректно сформулировал :oops:

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

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

Дашь формальную задачу - будет помощь, будет алгоритм. А пока их можно дать пару сотен тысяч, и все будут соответствовать начальному условию, НО тебе не подойдут, потому что ты имел в виду другое.

Вот определись, что же ты имеешь в виду - тогда и с алгоритмом можно будет помочь.
label:
cli
jmp label

arthur2
Продвинутый гуру
Продвинутый гуру
Аватара пользователя
 
Сообщения: 1598
Зарегистрирован: 23.01.2008 (Ср) 14:35

Re: Как сравнить два ректа?

Сообщение arthur2 » 22.02.2011 (Вт) 15:26

iGrok писал(а):Какого ты хочешь ответа на некорректный вопрос?
Иногда трудно сформулировать вопрос сразу же корректно и безукоризненно. Даже понять сложно, чего именно нужно добиться. Именно во время обсуждения такие вопросы обычно и уточняются. Кстати - спасибо Proxy - вопрос я немного уточнил :)
iGrok писал(а):Вот определись, что же ты имеешь в виду
Вот и помоги определиться - раз видишь, что формулировка не фонтан :)
iGrok писал(а):НО тебе не подойдут, потому что ты имел в виду другое
Мне подойдет ЛЮБОЙ способ пронумеровать ректы, который со стороны будет выглядеть логичным и оправданным. Толко не надо в ответ говорить, что рандомно - тоже логично :) Или что то, как я разместил пятерку - никому в голову не придет. Достаточно, что основную массу ректов пронумеруют приблизительно так.

Скажем так: как бы лично ты пронумеровал ректы на картинки? И какой бы алгоритм предложил именно к тому способу, которым лично ты бы их пронумеровал?
Артур
 
   

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16079
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: Как сравнить два ректа?

Сообщение Хакер » 22.02.2011 (Вт) 15:34

arthur2 писал(а):
Вот определись, что же ты имеешь в виду


Вот и помоги определиться - раз видишь, что формулировка не фонтан :)

Артур, помоги найти песню. Там поётся: «На-на-на, пу ла ла ла, оу йе».

Что? Любая песня подходит под это? Ну подскажи, какая больше всех подходит.
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

Debugger
Продвинутый гуру
Продвинутый гуру
Аватара пользователя
 
Сообщения: 1657
Зарегистрирован: 17.06.2006 (Сб) 15:11

Re: Как сравнить два ректа?

Сообщение Debugger » 22.02.2011 (Вт) 15:55

Надо отметить, что у прямоугольников, стоящих "в ряд" (то есть 1-4, 6-10, 11-14) пересекаются проекции на ось Y. Отсюда можно придумать алгоритм:
1. Взять самый верхний непронумерованный прямоугольник.
2. Найти все непронумерованные прямоугольники, проекции которых на ось Y пересекаются с выбранным в пункте 1.
3. Пронумеровать все найденные и выбранные прямоугольники слева направо (сортировка по оси X).
4. Перейти к шагу 1, если не всё пронумеровано.

В соответствии с этим алгоритмом, нумерация получается как раз как на картинке.
Программист - это локальный бог (С) Я

arthur2
Продвинутый гуру
Продвинутый гуру
Аватара пользователя
 
Сообщения: 1598
Зарегистрирован: 23.01.2008 (Ср) 14:35

Re: Как сравнить два ректа?

Сообщение arthur2 » 22.02.2011 (Вт) 15:57

Хакер писал(а):помоги найти песню. Там поётся: «На-на-на, пу ла ла ла, оу йе».
В таком случае, предполагается, что ты ищешь песню, но не можешь сформулировать, какую именно, а собеседник помогает тебе это сформулировать. Если бы пример был настоящим, на конкретной песне - почти наверняка можно было бы помочь человеку, даже если в первой формулировке было бы всё так печально, как ты сутрировал.

К тому же, в моём вопросе всё же несколько больше конкретики.
Артур
 
   

arthur2
Продвинутый гуру
Продвинутый гуру
Аватара пользователя
 
Сообщения: 1598
Зарегистрирован: 23.01.2008 (Ср) 14:35

Re: Как сравнить два ректа?

Сообщение arthur2 » 22.02.2011 (Вт) 15:59

Debugger ух ты! уже теплее :D Спасибо!
Артур
 
   

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16079
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: Как сравнить два ректа?

Сообщение Хакер » 22.02.2011 (Вт) 16:16

Debugger писал(а):Надо отметить,

Это совершенно не всегда.

Артут похож на человека, которому нравится, что его кормят из ложечки. Сам думай давай.
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

arthur2
Продвинутый гуру
Продвинутый гуру
Аватара пользователя
 
Сообщения: 1598
Зарегистрирован: 23.01.2008 (Ср) 14:35

Re: Как сравнить два ректа?

Сообщение arthur2 » 22.02.2011 (Вт) 16:28

Хакер писал(а):Артут похож на человека, которому нравится, что его кормят из ложечки. Сам думай давай.
Я похож на человека, которому легче решить задачу, когда её с кем-то обсуждаешь. Даже от того, что кто-то не понял то, что ты пытаешься сказать - начинаешь переформулировать и многие вещи для самого себя проясняются.
Хакер писал(а):я вижу многообразие алгоритмов. Оно есть. Ты его не видишь что-ли?
я большого разнообразия не видел, а то, что видел, мне не очень нравилось. Сейчас начинают проступать контуры, которые мне начинают нравиться.
Артур
 
   

iGrok
Артефакт VBStreets
Артефакт VBStreets
 
Сообщения: 4247
Зарегистрирован: 10.05.2007 (Чт) 16:11
Откуда: Сетевое сознание

Re: Как сравнить два ректа?

Сообщение iGrok » 22.02.2011 (Вт) 17:25

arthur2 писал(а):Или что то, как я разместил пятерку - никому в голову не придет.

Ну, как минимум, тебе - пришло.

Думаю, даже вариант с "рандомно" придёт в голову как минимум одному человеку.

arthur2 писал(а):Достаточно, что основную массу ректов пронумеруют приблизительно так.

Ключевое слово "приблизительно".

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

Лично я - 1, 2, 3, 4, 6, 7, 8, 5, 11, 12, 9, 10, 13, 14.
Или 1, 2, 3, 4, 5, 8, 7, 6, 11, 12, 9, 10, 14, 13.

Очень простой алгоритм - отсортировать по:
X + Y = 1, 2, 6, 7, 3, 11, 8, 4, 5, 12, 9, 13, 10, 14
X * Y = 1, 6, 2, 3, 11, 7, 4, 8, 5, 12, 9, 13, 10, 14
X + 2 * Y = 1, 2, 3, 6, 7, 4, 8, 5, 11, 9, 12, 10, 13, 14
X + 3 * Y = 1, 2, 3, 4, 6, 7, 5, 8, 11, 9, 10, 12, 13, 14
label:
cli
jmp label

arthur2
Продвинутый гуру
Продвинутый гуру
Аватара пользователя
 
Сообщения: 1598
Зарегистрирован: 23.01.2008 (Ср) 14:35

Re: Как сравнить два ректа?

Сообщение arthur2 » 22.02.2011 (Вт) 18:26

iGrok писал(а):Лично я - 1, 2, 3, 4, 6, 7, 8, 5, 11, 12, 9, 10, 13, 14.
Или 1, 2, 3, 4, 5, 8, 7, 6, 11, 12, 9, 10, 14, 13.
Оба варианта кажутся мне вполне логичными. А вот как их алгоритмизировать - не представляю :( Если взять за основу любой из этих рядов: как сформулировать, в чем здесь принцип?

iGrok писал(а):Очень простой алгоритм
как-то результат не выглядит слишком последовательным, да и алгоритм тоже :) Что-то в этом принципе есть, но только, кажется, для каждого случая нужно подбирать свой коэффициент.
Артур
 
   

iGrok
Артефакт VBStreets
Артефакт VBStreets
 
Сообщения: 4247
Зарегистрирован: 10.05.2007 (Чт) 16:11
Откуда: Сетевое сознание

Re: Как сравнить два ректа?

Сообщение iGrok » 22.02.2011 (Вт) 19:06

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

А оба моих варианта, хоть и кажутся более логичными, алгоритмизируются гораздо сложнее. Я, например, сходу не могу придумать подходящего алгоритма.
label:
cli
jmp label

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16079
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: Как сравнить два ректа?

Сообщение Хакер » 22.02.2011 (Вт) 19:16

Алгоритм Debugger-а — неустойчивая ерунда. Мало того, что он не до конца определяет алгоритм (в рамках существующего описания можно предложить кучу способов), неустойчив, так он ещё и против приведённой картинки.

По алгориту Debugger-а: 5-ый должден быть 4-ым, а 4-ый — 5-ым. Но самое главное, высота первого в строчке ректа влияет на судьбу нумерации последующих, хотя совершенно не должна. Сузить высоту первого ректа до 1 px, и половина ректов в строке не будут совпадать своей Y-проекцией с Y-проекцией первого ректа.
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16079
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: Как сравнить два ректа?

Сообщение Хакер » 22.02.2011 (Вт) 19:19

Артуру предлагается привести разнумеровку для пограничной ситуации: пронумеровать клетки одного цвета на шахматной доске.
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

Debugger
Продвинутый гуру
Продвинутый гуру
Аватара пользователя
 
Сообщения: 1657
Зарегистрирован: 17.06.2006 (Сб) 15:11

Re: Как сравнить два ректа?

Сообщение Debugger » 22.02.2011 (Вт) 22:54

По алгориту Debugger-а: 5-ый должден быть 4-ым, а 4-ый — 5-ым.

Разве? Мы "выбираем" третий прямоугольник, с ним "пересекаются" 1, 2, 4. Сортируем их. Во второй выборке мы возьмем пятый прямоугольник.
В общем-то, это было против
Но я не придумаю ни одного, котоый бы расставил числа так, как они расставлены на картинке.

Ты это сказал, как будто таких алгоритмов в природе нет.
Хакер писал(а):Алгоритм Debugger-а — неустойчивая ерунда.

Да, неустойчивая. Но не надо так жестко.
algo.png

Левый нумеруется нормально, но если их сдвинуть чуть плотнее по оси Y, то нумерация собъется.

Денис
Как подбирать угол? Можно придумать пример для каждого угла, с которым это не прокатит.

Как заставить компьютер пронумеровать прямоугольнички так, чтобы у человек (с высокой вероятностью) не смог определить, кто пронумеровал - компьютер или его другой человек (вариант теста Тьюринга)?
Программист - это локальный бог (С) Я

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16079
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: Как сравнить два ректа?

Сообщение Хакер » 22.02.2011 (Вт) 23:08

Debugger писал(а):Мы "выбираем" третий прямоугольник,

Третий с точки зрения чего?
Картинки?

С точки зрения картинки, 5-ый находится левее 4-го, значит и номера у них будут не {5, 4}, а {4, 5}.
Debugger писал(а):Ты это сказал, как будто таких алгоритмов в природе нет.

Вот именно, твой как раз по этому критерию не подходит.
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

Debugger
Продвинутый гуру
Продвинутый гуру
Аватара пользователя
 
Сообщения: 1657
Зарегистрирован: 17.06.2006 (Сб) 15:11

Re: Как сравнить два ректа?

Сообщение Debugger » 23.02.2011 (Ср) 0:37

С точки зрения картинки, 5-ый находится левее 4-го, значит и номера у них будут не {5, 4}, а {4, 5}.

В первой выборке будут учавствовать прямоугольники 1, 2, 3 и 4. Потому что их проекции на ось пересекаются с проекцией самого верхнего (3) прямоугольника. И сначала отсортируется группа (1, 2, 3, 4) по оси X. Потом, во второй выборке будет учавствовать только прямоугольник, подписанный под номером "5".
iGrok, надо откуда-то взять коэффициенты. В задаче подразумевается участие человека, думаешь переложить это на него?
Программист - это локальный бог (С) Я

iGrok
Артефакт VBStreets
Артефакт VBStreets
 
Сообщения: 4247
Зарегистрирован: 10.05.2007 (Чт) 16:11
Откуда: Сетевое сознание

Re: Как сравнить два ректа?

Сообщение iGrok » 23.02.2011 (Ср) 2:06

Хакер, то, что предложил Debugger действительно выдаст ровно то распределение, которое написал Артур.
В первую выборку (3 - верхний) попадут 1, 2, 3, 4; во вторую - 5; в третью (7 - верхний) - 6, 7, 8, 9, 10; и уже под конец (12 - верхний) - 11, 12, 13, 14.

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

Но если №5 опустить так, чтобы он пересёкся с №7, но ещё не пересёкся с №8, тогда будет попа.

Debugger писал(а):iGrok, надо откуда-то взять коэффициенты. В задаче подразумевается участие человека, думаешь переложить это на него?

Я думаю, что не надо маяться ерундой. Вообще.

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

А подбирать алгоритм, который выдаст "наиболее правильное распределение" - бесполезно, т.к. оно "правильное" только с точки зрения человека, да и то не каждого. Да и для любого предложенного алгоритма можно будет найти пару ситуаций, в которых он выдаст чушь. То есть с точки зрения алгоритма всё будет "как надо", а с точки зрения человека - рандом.
label:
cli
jmp label

arthur2
Продвинутый гуру
Продвинутый гуру
Аватара пользователя
 
Сообщения: 1598
Зарегистрирован: 23.01.2008 (Ср) 14:35

Re: Как сравнить два ректа?

Сообщение arthur2 » 23.02.2011 (Ср) 7:17

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

Получаем алгоритм, который выдаст первый ряд IGrok-а :)

На втором шаге может быть так, что слева несколько ректов друг под другом, которые не ниже и не выше текущего.
Изображение
Они нумеруются друг за другом сверху вниз.
То же самое и при движении вправо.
Вложения
rects.GIF
(2.61 Кб) Скачиваний: 260
Артур
 
   

arthur2
Продвинутый гуру
Продвинутый гуру
Аватара пользователя
 
Сообщения: 1598
Зарегистрирован: 23.01.2008 (Ср) 14:35

Re: Как сравнить два ректа?

Сообщение arthur2 » 23.02.2011 (Ср) 8:08

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

Изначально ректы распределены в том порядке, в котором встречается их верхний левый угол. С точки зрения человека это ерунда какая-то: 3, 2, 4, 1, 5, 7, 8, 6, 10, 9, 12, 11, 13, 14. Человек править замучается.
Артур
 
   

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16079
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: Как сравнить два ректа?

Сообщение Хакер » 23.02.2011 (Ср) 10:46

iGrok писал(а):Хакер, то, что предложил Debugger действительно выдаст ровно то распределение, которое написал Артур.
В первую выборку (3 - верхний) попадут 1, 2, 3, 4; во вторую - 5; в третью (7 - верхний) - 6, 7, 8, 9, 10; и уже под конец (12 - верхний) - 11, 12, 13, 14.

Обоснуй, почему картиночный-5 не попадёт в первую выборку.
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

iGrok
Артефакт VBStreets
Артефакт VBStreets
 
Сообщения: 4247
Зарегистрирован: 10.05.2007 (Чт) 16:11
Откуда: Сетевое сознание

Re: Как сравнить два ректа?

Сообщение iGrok » 23.02.2011 (Ср) 14:09

Хакер писал(а):Обоснуй, почему картиночный-5 не попадёт в первую выборку.

Его проекция на ось Y не пересекается с таковой от 3-го. Берётся же не первый, а "самый верхний".

arthur2 писал(а):1. Двигаемся сверху вниз построчно до первого ректа.
2. Ищем слева ближайший рект, который не ниже текущего.
3. Вставляем его перед текущим, продолжаем двигаться влево, пока ректы не кончатся.
4. Теперь двигаемся вправо, пока ректы не кончатся.

Получаем алгоритм, который выдаст первый ряд IGrok-а :).

Эмм.. "двигаемся влево"/"вправо" - как? От чего и по какой траектории? Потому что теперь и я не вижу, каким же образом ты при таком алгоритме получил мой ряд. :)
label:
cli
jmp label

След.

Вернуться в Графика

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1

    TopList