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

[arthur2]

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

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

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

[Хакер]

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

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

Задача не формализуема, алгоритма не будет.

[arthur2]

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

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

[Хакер]

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

[arthur2]

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

[Хакер]

Хорошо, а как бы ты расставил те, что на картинке?

Я бы не расставлял, потому что мне это не нужно. Но я вижу многообразие алгоритмов. Оно есть. Ты его не видишь что-ли?

[Денис]

как сравнить два ректа? какой раньше?

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

[Proxy]

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

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

[arthur2]

Я бы не расставлял, потому что мне это не нужно.

Угу, можно было бы ожидать - абстрактно порассуждаешь об вообще. Ты, конечно, очень часто и очень сильно помогаешь, но перед этим всю душу вынешь своей манерой ходить кругами и уворачиваться. Как всегда:

Twister, ты обломал весь кайф открытия того, что <нужное вставить исходя из контекста>, у Артура, и весь кайф созерцания процесса открытия и описания мыслей по этому поводу Артуром — у меня.

Кайф у тебя какой-то садисткий. Впрочем, давно подозревал.

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

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

[iGrok]

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

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

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

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

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

[arthur2]

Какого ты хочешь ответа на некорректный вопрос?

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

Вот определись, что же ты имеешь в виду

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

НО тебе не подойдут, потому что ты имел в виду другое

Мне подойдет ЛЮБОЙ способ пронумеровать ректы, который со стороны будет выглядеть логичным и оправданным. Толко не надо в ответ говорить, что рандомно - тоже логично Или что то, как я разместил пятерку - никому в голову не придет. Достаточно, что основную массу ректов пронумеруют приблизительно так.

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

[Хакер]

Вот определись, что же ты имеешь в виду

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

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

Что? Любая песня подходит под это? Ну подскажи, какая больше всех подходит.

[Debugger]

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

В соответствии с этим алгоритмом, нумерация получается как раз как на картинке.

[arthur2]

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

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

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

[arthur2]

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

[Хакер]

Надо отметить,

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

Артут похож на человека, которому нравится, что его кормят из ложечки. Сам думай давай.

[arthur2]

Артут похож на человека, которому нравится, что его кормят из ложечки. Сам думай давай.

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

я вижу многообразие алгоритмов. Оно есть. Ты его не видишь что-ли?

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

[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.

Очень простой алгоритм - отсортировать по:
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

[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.

Оба варианта кажутся мне вполне логичными. А вот как их алгоритмизировать - не представляю Если взять за основу любой из этих рядов: как сформулировать, в чем здесь принцип?

Очень простой алгоритм

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

[iGrok]

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

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

[Хакер]

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

По алгориту Debugger-а: 5-ый должден быть 4-ым, а 4-ый — 5-ым. Но самое главное, высота первого в строчке ректа влияет на судьбу нумерации последующих, хотя совершенно не должна. Сузить высоту первого ректа до 1 px, и половина ректов в строке не будут совпадать своей Y-проекцией с Y-проекцией первого ректа.

[Хакер]

Артуру предлагается привести разнумеровку для пограничной ситуации: пронумеровать клетки одного цвета на шахматной доске.

[Debugger]

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

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

Но я не придумаю ни одного, котоый бы расставил числа так, как они расставлены на картинке.

Ты это сказал, как будто таких алгоритмов в природе нет.

Алгоритм Debugger-а — неустойчивая ерунда.

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

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

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

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

[Хакер]

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

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

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

Ты это сказал, как будто таких алгоритмов в природе нет.

Вот именно, твой как раз по этому критерию не подходит.

[Debugger]

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

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

[iGrok]

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

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

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

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

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

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

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

[arthur2]

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

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

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

Они нумеруются друг за другом сверху вниз.
То же самое и при движении вправо.

[arthur2]

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

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

[Хакер]

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

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

[iGrok]

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

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

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

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

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