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

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

crop3.jpg.

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

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

Существует подобная задача общего уровня с произвольной матрицей www.drdobbs.com/database/the-maximal-rectangle-pro... но я уверен, что для выпуклого многоугольника есть существенно более быстрое решение.
  • Вопрос задан
  • 4473 просмотра
Решения вопроса 2
@vdem
Можно попробовать нечто вроде бинарного поиска. Т.е. в первую очередь взять горизонталь из середины верхней половины, и вторую из середины нижней половины. Дальше найти левую и правую вертикали по этим горизонталям хотя бы простым сканированием точек, т.е. чтобы "нащупать" края изображения. И дальше - рекурсией середину верхней половины делим на верхнюю и нижнюю, то же с нижней половиной, направление поиска вертикальных границ изображения уже известно. Методом ветвей и границ отсекаем варианты, когда найденная площадь начинает уменьшаться. Как-то так.
Ответ написан
В случае выпуклого многоугольника (кстати, многогранник - это термин "из 3D") никакие две соседние вершины вписанного прямоугольника не могут одновременно НЕ принадлежать периметру многоугольника (поскольку в противном случае мы имеем возможность расширять прямоугольник в сторону этих двух вершин, получая большую итоговую площадь).

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

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

Далее задача была бы легкой - это максимизация площади прямоугольника углы которого лежат на этих 4х прямых. 100% такая задача уже где-то описана в мат литературе, на крайний случай решить её итерационными методами.
Ответ написан
Комментировать
@lookid
Угол поворота вам известен. Следовательно вы можете построить 4 вектора: из центра в каждый угол. И с каким-нибудь шагом приближаться к центру по этим векторам. Чем больше шаг, тем меньше времени, но грубее получится посчитать. Получаете в итоге 4 точки прямоугольника. Ищете с наименьшей длинной. Подгоняете остальные по её длину. Может есть что-то быстрее. Не проверял.
Ответ написан
Deerenaros
@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). Ну да, задача будет сложнее. То есть это уже самый ни на что есть матан - максимум функции от двух переменных.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы