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

← →
Вова (2013-08-10 14:24) [0]

http://s57.radikal.ru/i157/1308/e8/e884547d4fa4.png

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

← →
ProgRAMmer Dimonych © (2013-08-10 23:58) [1]

Очень интересно, по каким критериям нужно будет выбирать положение искомого прямоугольника для, скажем, десятка исходных. Думаю, будет полезно пояснить конечную цель сего действа: откуда возникла задача и какое применение ожидает искомый алгоритм. Пока выглядит слегка по Реймонду Чену: «Автор вопроса разделил задачу на две части: лёгкую и невозможную» :)

← →
Германн © (2013-08-11 00:24) [2]

> откуда возникла задача и какое применение ожидает искомый
> алгоритм

Раскрой материала?

← →
Вова (2013-08-11 02:41) [3]

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

ну если искомыый будет слева, то он будет слева от всех объектов, а не между ними.

← →
ProgRAMmer Dimonych © (2013-08-11 03:31) [4]

> [2] Германн © (11.08.13 00:24)
> Раскрой материала?

Всё возможно. Но точные требования к решению ТС предъявить стесняется.

> [3] Вова (11.08.13 02:41)
> задача оттуда, что я знаю что искомый объект находится между
> двумя, тремя и т.д. другими(более того таких одинаковых
> объектов, один из которых нужно найти несколько, но тот
> что мне нужен находится между этими). таким образом в идеале
> хотелось бы иметь общий алгоритм, чтобы каждый раз не заморачиваться.
> Ну я ж сказал, что хотя бы для 3-4, с каждой стороны по
> одному....

«Найди то, не знаю что». Какими свойствами должен обладать объект, чтобы быть искомым?

> ну если искомыый будет слева, то он будет слева от всех
> объектов, а не между ними.

ОК. Почему для этого рисунка искомый объект не слева? Или (внезапно!) не сверху или не снизу?

← →
megavoid © (2013-08-11 10:51) [5]

на 2D :) bin packing похоже, ну или наоборот, ага, раскройка

← →
icWasya © (2013-08-12 12:44) [6]

Аффтар, уточните, красный прямоугольник должен
1) - иметь максимальный размер?(по ширине, по высоте???)
2) - касаться максимального количества других прямоугольников?
3) - что-то ещё?

← →
Вова (2013-08-12 13:20) [7]

1) да, и он не должен пересекать ни одного черного квадрата.
2) да.
3) Границы его также не должны выходить за самый большой черный прямоугольник в котором и находятся все объекты.

← →
Вова (2013-08-12 13:22) [8]

второе условие имеет более высокий приоритет чем первое.

← →
Вова (2013-08-12 13:27) [9]

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

Но ничего нельзя пересекать. Вот так.

← →
Sha © (2013-08-12 13:40) [10]

Вова (12.08.13 13:27) [9]

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

← →
Вова (2013-08-12 14:01) [11]

ну я же выше писал, я ищу объект. Ищу я их в прямоугольнике (в большом). Объектов в прямоугольнике много всяких разных. А есть такие которые присутствуют в нескольких экземплярах и для того чтобы искать именно нужный мне экземпляр (т.е. я мог бы искать например третий объект, но дело в том, что не факт, что первые 2 в данный момент вообще существуют), необходимо выделить область в котором он может находиться. Т.к. его там может и не быть вовсе. Причем я могу точно утверждать в каком месте по отношению к другим объектам будет искомый объект, т.к. их положение привязано друг к другу, т.е. если сдвинуть черный квадрат, то и сдвинется искомый объект. Прямоугольники используются потому что так проще, геометрия объекта не анализируется. Итого в частном случае можно чего то накалякать, но хочется изобрести алгоритм для общего случая, когда я передаю функции список объектов между которыми искать, а оно само решает в какой области это делать.

← →
Sha © (2013-08-12 14:10) [12]

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

Так где же прячется искомый объект?
В твоем красном прямоугольнике или в моем?

← →
Вова (2013-08-12 14:14) [13]

ммм, в моем. )

← →
Вова (2013-08-12 14:16) [14]

( блин, тогда условие однозначно нельзя задать (

← →
Sha © (2013-08-12 14:16) [15]

и как оно должно это сообразить?

← →
Вова (2013-08-12 14:19) [16]

из возможных выбрать тот у кого длина "касаний" наибольшая?

← →
Вова (2013-08-12 14:21) [17]

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

← →
Sha © (2013-08-12 14:21) [18]

задача становится все чудесатее,
длина касаний может быть большой, но площадь - маленькой

← →
ProgRAMmer Dimonych © (2013-08-12 14:21) [19]

Я бы всё же рекомендовал рассказать, какая задача решается «на верхнем уровне». Может быть, прямоугольники окажутся и вовсе неудачной абстракцией. Ну или по крайней мере станет понятно вот это:

> т.е. я мог бы искать например третий объект, но дело в том, что не факт, что первые 2 в данный момент вообще существуют

и вот это:

> их положение привязано друг к другу, т.е. если сдвинуть черный квадрат, то и сдвинется искомый объект

← →
Sha © (2013-08-12 14:24) [20]

Давай вернемся к [10].

Сформулируй исходную задачу. И мы продолжим решать ее вместе:
ты - своими прямоугольниками, а мы - своими.

← →
Вова (2013-08-12 14:53) [21]

что значит на "Верхнем" уровне? я итак уже рассказал вроде.

Несколько экземпляров объекта, каждый из них может в каждый момент времени присутствовать или отсутствовать. А мне нужно проверить, так присутствует нужный мне экземпляр или отсутствует в текущий момент времени). Функция поиска объекта уже есть и не рассматривается. Остается задача выявить область поиска, экземпляры идентичны, а следовательно понять какой мы ищем можно только по окружению.

Частный случай - который видимо таки я и буду юзать - искомый объект находится под черным квадратом. (ну то есть под уже идентифицированным объектом, местоположение которого известно), либо слева, либо справа и т.д. Т.е. например, висит на стене картина, а под ней табличка, я идентифицировал картину, нужно найти табличку, но табличку не от соседней картины, которая висит рядом, а именно от этой. Тут возникает проблема, что если под нужной картиной висит еще одна картина, а под ней такая же табличка? т.е. область поиска нужно ограничить еще, а не искать от картины вниз до конца стены. И т.д. И в общем идея была в том, чтобы передать координаты идентифицированных картин и функция должна ограничить область поиска положением этих картин автоматом. И у меня нет никакого настроения каждый раз писать, что искать табличку нужно на 10 сантиметров ниже картины и т.п. Т.к. это расстояние придется во первых измерять, а во вторых оно не всегда одинаковое, поэтому все должно быть относительно.

Альтернативу прямоугольникам могут составить разве что круги. Просто в прямоугольник вписан объект и все.

> Функция поиска объекта уже есть и не рассматривается. Остается
> задача выявить область поиска

There must be some larger problem they are trying to solve, and they managed to break it down into two parts, the easy part and the impossible part, and they wanted help with the impossible part.

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

Положение таблички как-то регламентируется ведь? Например, «находится ниже картины и хотя бы частично пересекается с картиной в проекции на горизонтальную ось». Хотя в такой формулировке тоже не очень-то решаемо.

И, кстати, а почему не найти все картины и таблички, а потом сопоставлять их?

И в чем проблема?

Задай дельта-окрестность картины,
исключи из нее другие картины
и ищи там свою табличку.

← →
Вова (2013-08-12 15:06) [24]

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

← →
Вова (2013-08-12 15:13) [25]

> И, кстати, а почему не найти все картины и таблички, а потом
> сопоставлять их?

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

← →
Очень злой (2013-08-12 22:06) [26]

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

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

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

← →
Очень злой (2013-08-12 22:09) [27]

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

← →
Очень злой (2013-08-12 22:10) [28]

> и задача упрощается...

потому как у нас остается на 1 прямоугольник меньше.

← →
Очень Злой (2013-08-13 00:02) [29]

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

> На данный момент переводя на пример с картинами и табличками,
> у меня есть картина, под ней табличка, а гораздо ниже картины,
> есть еще одна табличка, которая мне нафиг не нужна, но
> которая как 2 капли воды похожа на нужную. И никакие объекты
> по прямой эти таблички не разделяют.

«Всё чудесатее и чудесатее».

как вписать прямоугольник между прямоугольниками Найти похожие ветки