Ограничивающий прямоугольник с максимальным периметром для набора точек

Question

Я довольно долго пытался с этой, казалось бы, простой проблемой. Мне задан набор точек (которые я еще упростил до выпуклой оболочки), и моя задача - найти прямоугольник (не обязательно ориентированный по оси), который охватывает все из них, не имеет дополнительного пространства (так что это плотно облегающие точки) и имеет максимально возможный периметр. Для меня не было проблем найти минимальный, но это оказалось более жестким орешком, чтобы взломать. При поиске минимального ограничивающего прямоугольника я мог использовать предположение, что одна из сторон прямоугольника всегда выровнена с одной из сторон корпуса, но здесь я не вижу такого случая здесь. Я пропустил что-то больно очевидное? Единственный способ, который я мог придумать до сих пор, - проверить антиподальные пары точек, если они могут проецироваться на стороны прямоугольника и использовать некоторый триггер, чтобы максимизировать функцию, но я просто потерял себя в расчетах.

Заранее благодарен!

Answer 1

Сначала вычислите выпуклую оболочку вашего точечного набора.

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

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

Для каждого законного выбора верхнего, левого, нижнего и правого вы должны вычислить максимальное значение a * sin (theta) + b * cos (theta) для фиксированных a и b в некотором диапазоне тета. Напомним, что тригг a * sin (theta) + b * cos (theta) = sqrt (a^2 + b^2) cos (theta-arctan (b/a)). Вы оцениваете функцию на границах вашего интервала и где производная равна нулю (в arctan (b/a) плюс любое целое число pi), и вы золотой.