Как вычислить наибольший прямоугольник в многограннике?

Question

[gleb_kudr]

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

.

Алгоритмическая формулировка задачи.
Имеется пиксельная координатная сетка с нарисованным в ней выпуклым многогранником. Координаты вершин неизвестны, но известно, что все пиксели внутри многогранника имеют значение true, а все снаружи - значение false. Известно начало координат - точка (0,0) и конец координат (xMax, yMax).

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

Существует подобная задача общего уровня с произвольной матрицей www.drdobbs.com/database/the-maximal-rectangle-pro... но я уверен, что для выпуклого многоугольника есть существенно более быстрое решение.

Answer 1

[vdem]

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

Comments

[gleb_kudr]

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

[Deerenaros]

@gleb_kudr вряд ли, в том смысле что функция не очень простая и представлена в трёх измерениях.

[Deerenaros]

@gleb_kudr я к тому, что максимумов точно будет несколько, впрочем градиентный спуск - вполне себе вариант

[Eddy_Em]

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

Answer 2

[Андрей]

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

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

Возможно, Вам хватит быстродействия 2*O(N^2) (дважды полный перебор диагональных вершин вдоль периметра многоугольника) ?

Comments

[gleb_kudr]

>никакие две соседние вершины вписанного прямоугольника не могут одновременно НЕ принадлежать периметру многоугольника

Спасибо, интересный факт, кстати, не такой уж тривиальный.

Answer 3

[Сергей]

Я бы сначала нашел положения прямых отсечения.
Например для каждого угла нашел бы точки пересечения цветного изображения с границами изображения (первые true). Исходя из этих точек, для каждой прямой можно построить её формулу Ax+By+C = 0 (причем по 2 прямые будут параллельны, и по 2 перпендикулярны, т.е. буду отличаться только константой C и знаком A или B)

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

Answer 4

[lookid]

Угол поворота вам известен. Следовательно вы можете построить 4 вектора: из центра в каждый угол. И с каким-нибудь шагом приближаться к центру по этим векторам. Чем больше шаг, тем меньше времени, но грубее получится посчитать. Получаете в итоге 4 точки прямоугольника. Ищете с наименьшей длинной. Подгоняете остальные по её длину. Может есть что-то быстрее. Не проверял.

Comments

[vdem]

Угол неизвестен, судя по условию.

[gleb_kudr]

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

Answer 5

[Deerenaros]

Да ладно вам... Надеюсь производные все умеют считать.

Теперь давайте посмотрим внимательно на прямоугольник. Как считается его площадь? Ах да, S = a*b, это геометрия 7го класса, если не математика 4го.

Ок, теперь можно посмотреть на многоугольник, в который надо прямоугольник вписать. Ну, он неприятный, да, однако кое-что известно. А именно - "прямые отсечения", как нам сказал @begemot_sun, вообще в данной задаче многоугольник лучше хранить в виде прямых. Ну да не суть, просто вычислений будет чуть больше. Ок, теперь что мы делаем. Мы строим функцию. Да да - самую банальную функцию. Функцию S(\phi) = a(\phi)*b(\phi). Как это получить - оставлю вам, там немного геометрии 7го класса.

Ну да, но вот вопрос, а что с ней вообще делать? Внимание ответ - поиск экстремума в общем случае - задача сложная =) Даже wolframalpha здесь бессильна (впрочем конкретно в этом случае это даже невозможно). Так что здесь имеют место быть только оптимизации - метод градиентного спуска или метод "отжига". Гуглите, читайте, реализуйте.

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

P.S. Не пытайтесь просить кого-то решить задачу за Вас на таких ресурсах. Во-первых, это моветон. Во-вторых, ресурс здесь чтобы подсказать решение задачи, но не решить её ВМЕСТО Вас. Конкретно этот случай потребует часов 10 вспоминания матана средней школы, что не очень приятно. Учитывая ЗП в 2k/час, думаю это будет дороговато.

UPD. Внезапно осенило, что зависимость будет чуть сложнее. В том смысле, что это будет не просто S(\phi), а S(\phi, a) = a*b(\phi, a). Ну да, задача будет сложнее. То есть это уже самый ни на что есть матан - максимум функции от двух переменных.

Comments

[gleb_kudr]

>Не пытайтесь просить кого-то решить задачу за Вас на таких ресурсах. Во-первых, это моветон. Во-вторых, ресурс здесь чтобы подсказать решение задачи, но не решить её ВМЕСТО Вас.

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

[Eddy_Em]

>Учитывая ЗП в 2k/час
Ну и не отвечайте. А люди с ЗП 20т.р. в месяц будут отвечать.

[Deerenaros]

@gleb_kudr @Eddy_Em Ладно, ладно. Прошу прощение, поторопился. Просто почему-то открыл не тот профиль и там было... плачевно.

@gleb_kudr По поводу алгоритмов: подозреваю их нет. К слову, о синусах и косинусах я не писал, но подозревал, так что Вы на верном пути. В общем ситуация такая - делаем функцию, а там разные оптимизации есть. Впрочем, функция обязана быть довольно гладкой, так что можно и итерациями с небольшим шагом (градус/пиксель) пройти и выбрать максимум. Даже на больших изображениях это будет не очень накладно: T(w, h) = max(w, h)*360.