Как вписать прямоугольник в многоугольник?

Question

[Listrigon]

Какой алгоритм позволяет вписать прямоугольник максимальной площади в линейный многоугольник, все углы которого прямые?

spoiler

Comments

[Wataru]

Он по клеточкам выравнен? Или может быть как угодно быть, просто все стороны горизонтальны/вертикальны?

[Wataru]

Listrigon, да, и что значит "линейный" многоугольник? Он как изогнутая колбаса - этакая ломаная с ненулевой шириной? Или что?

[mayton2019]

Если клеточек мало (допустим менше 200) то задачу можно решить комбинаторно. Просто генерируя все сочетания клеток и проверяя что прямоугольник "получился". Но формула здесь экспоненциальная поскольку добавление каждого очередной клеточки домножает количество проверяемых комбинаций.

Еще вариант - генетика. Мы случайно формируем прямоугольники. И пытаемся их улучшить. И выбираем лучший прямоугольник который снова участвует в отборе. Здесь асимптоматику лучше но алгоритм будет сложнее.

[Listrigon]

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

[Lynn «Кофеман»]

Должны ли стороны полученного прямоугольника быть параллельны сторонам исходной фигуры?

[Listrigon]

Lynn «Кофеман», Вообще наверное нет, но как мне кажется, если все углы 90 градусов у многоугольника, а значит все стороны либо параллельные либо перпендикулярны, то я у результирующего прямоугольника стороны будут параллельны сторонам

[dollar]

Listrigon,

не всегда

[Wataru]

Listrigon, Так а что значит "линейный" многоугольник?

[Listrigon]

Wataru, Все грани линии, имело ввиду, что без дуг, Безье и пр.

[Alexandroppolus]

Listrigon, так что насчет параллельности сторон прямоугольника сторонам многоугольника? Ты ответил "наверно".

[Listrigon]

Alexandroppolus, В идеале наверное лучше так (чтобы параллельно экрану.области видимости)

но если под углом проще, то тоже подойдет, так сказать лучше чем ничего

[Василий Банников]

Listrigon, а что если фигура - "змейка" по диагонали?
Тогда такой вертикально-горизонтальный прямоугольник будет сильно меньше, чем вписанный

[Alexandroppolus]

Listrigon,

но если под углом проще

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

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

[Listrigon]

Alexandroppolus, Задача в том, чтобы вписать текст внутрь такой фигуры полностью, для этого нужен прямоугольник. Горизонтальность чуть приоритетнее оптимальности, 99% процентов случаев это Г П С образные фигуры.

[Listrigon]

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

[Alexandroppolus]

Listrigon, с горизонтально-вертикальными всё просто: проводишь горизонтальную и вертикальную линии через каждый угол многоугольника, рисунок обзаводится сеткой. Так же легко определить прямоугольник, в который вписан многоугольник. Задача сводится к этой - https://leetcode.com/problems/maximal-rectangle/ , с той лишь разницей, что строки и столбцы могут быть разной ширины, и вернуть надо не площадь максимального прямоугольника, а его координаты. Вот копипаст моего решения с литкода, допили сам (дебаггер в помощь)

код

var largestRectangleArea = function(heights, currents) {
    let maxArea = 0;
    let lastH = 0;
    let currentsCount = 0;
    
    for (let i = 0; i <= heights.length; ++i) {
        let h = i < heights.length ? heights[i] : 0;
        let left = i;
        
        while (currentsCount && currents[currentsCount - 1].h > h) {
            const r = currents[--currentsCount];
            maxArea = Math.max(maxArea, r.h * (i - r.left));
            left = r.left;
        }
        
        if (h > 0 && (!currentsCount || currents[currentsCount - 1].h < h)) {
            if (currentsCount < currents.length) {
                const item = currents[currentsCount];
                item.left = left;
                item.h = h;
            } else {
                currents.push({left, h})
            }
            currentsCount++;
        }
    }
    
    return maxArea;
};

/**
 * @param {character[][]} matrix
 * @return {number}
 */
var maximalRectangle = function(matrix) {
    const heights = Array(matrix[0].length).fill(0);
    const currents = [];
    let max = 0;
    for (let i = 0; i < matrix.length; ++i) {
        const line = matrix[i];
        for (let j = 0; j < line.length; ++j) {
            heights[j] = line[j] === '1' ? heights[j] + 1 : 0;
        }
        max = Math.max(max, largestRectangleArea(heights, currents));
    }
    return max;
};

время работы O(N), где N - количество квадратиков в сетке. Функция maximalRectangle. Сетка обрабатывается построчно, для каждой строки берется решение из соседней задачи https://leetcode.com/problems/largest-rectangle-in...

[Listrigon]

Alexandroppolus, Спасибо большое, посмотрю.

[Alexandroppolus]

Listrigon,

задача не на каждый день

к сожалению, да.

[Wataru]

Alexandroppolus, Listrigon,
Нет, этот код, к сожалению, не решает приведенную задачу. Этот код ищет максимальный прямоугольник в гистограмме - т.е многоугольник выпуклый, и левый край всех строк выравнен. Поэтому она принимает не матрицу 0 и 1, а массив "высот" по всем строчкам.

Задачу с литкода за линию не решить, иначе там бы ограничения были бы побольше 200. Она решается за O(w^2*h), Надо перебрать левый и правый края прямоугольника, а дальше получить массив 0 и 1 - можно ли каждую строчку включить в прямоугольник на этой широте. А дальше уже одномерная задача поиска максимального отрезка решается за O(h).

[Alexandroppolus]

Wataru, "гистограмма" - это вторая ссылка в моем комменте. Она даётся на одномерном массиве и решается за O(N)

А по первой ссылке задача с двумерным массивом 0 и 1. Вот к ней приводится сабж. Причем идея решения восходит к "гистограмме". На каждой строке есть инфа по "высотам" для ячеек (которая накапливается с предыдущих строк), и по сути на каждой строке я решаю "гистограмму", так что в сумме будет O(w*h)

[Wataru]

Alexandroppolus, О, хитрая идея. Действительно.

[Adamos]

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

Answer 1

[Adamos]

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

Answer 2

[Wataru]

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

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

Но тут слишком много случаев. Это очень сложная задача строк этак на 1000 мозгодробящей геометрии.

Answer 3

[Sergey В.]

Попробуйте подумать - а как Вы (как человек) решаете эту задачу (визуально)?
Я:
1. Определил внутреннюю область (точку) многоугольника, которую "видят" как можно больше граней. Это - точка, в которой можно построить наибольшую по площади фигуру. Таких точек может быть несколько;
2. Строю в этой точке прямоугольник с наибольшей площадью (в вертикальной или горизонтальной ориентации);
3. Начинаю вертеть и смещать прямоугольник для достижения максимальной площади.
Уверен, что этот алгоритм можно переложить в программную реализацию.

Comments

[Listrigon]

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

[Sergey В.]

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

[Wataru]

BasiC2k,

Определил внутреннюю область (точку) многоугольника, которую "видят" как можно больше граней. Это - точка, в которой можно построить наибольшую по площади фигуру

В общем случае - вообще не факт.

Answer 4

[iingvaar]

Посмотрите это видео: https://youtu.be/QJC27E9bvqU
В нём дана идея алгоритма. Вкратце - это частный случай гипотезы Тёплица. Для нахождения вписанного прямоугольника можно особым образом "развернуть" фигуру в единичный квадрат и построить на нём функцию расстояний между всеми парами точек контура. Можно сделать это, например, с некоторым малым шагом дискретизации. Точки самопересечения построенной функции дадут координаты углов вписанного прямоугольника.