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

Я пытаюсь установить прямоугольник вокруг набора из 8 2D-точек, пытаясь минимизировать закрытую область.

Пример:

Прямоугольник можно масштабировать и поворачивать. Однако он должен оставаться прямоугольником.

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

Однако это не похоже на лучшее решение.

Есть ли лучший способ сделать это?

Ответ 1

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

Первый шаг - вычислить выпуклую оболочку. Насколько это реально экономит, зависит от распределения ваших данных, но для точек, выбранных равномерно с единичного диска, ожидается, что количество точек на корпусе будет O (n ^ 1/3). Есть количество способов сделать это:

Если точки уже отсортированы по одной из их координат, алгоритм сканирования Грэма делает это в O (n). Для каждой точки в данном порядке подключите ее к предыдущим двум в корпусе, а затем удалите каждую новую точку (единственный кандидат - соседние с новой точкой) на новом корпусе.
Если точки не отсортированы, алгоритм подарочной упаковки - это простой алгоритм, который выполняется в O (n * h). Для каждой точки на корпусе, начиная с самой левой точки входа, проверьте каждую точку, чтобы увидеть, является ли она следующей точкой на корпусе. h - количество точек на корпусе.
алгоритм Чена promises O (n log h), но я не совсем изучил, как это работает.
_{другая идея simle заключалась бы в сортировке точек по их азимуту, а затем удалении вогнутых. Однако сначала это похоже только на O (n + sort), но я боюсь, что на самом деле это не так.}

В этот момент проверка каждого угла, собранного до сих пор, должна быть достаточной (как было созвано мной и Оливером Чарльвертом, и для которых Евгений Клев [ предложил суть доказательства)). Наконец, позвольте мне обратиться к соответствующей ссылке в Lior Kogan answer.

Для каждого направления ограничивающая рамка определяется теми же четырьмя (не обязательно разными) точками для каждого угла в этом интервале. Для направлений кандидата вы получите хотя бы один произвольный выбор. Поиск этих точек может показаться задачей O (h ^ 2) до тех пор, пока вы не поймете, что крайности для рамки с выравниванием по оси - это те же крайности, с которых вы начинаете слияние, и что последовательные интервалы имеют свои экстремальные точки, одинаковые или последовательные, Назовем крайние точки A,B,C,D по часовой стрелке, а соответствующие линии, ограничивающие ограничивающий прямоугольник, A,B,C,D.

Итак, сделайте математику. Область ограничивающего прямоугольника задается символом |a,c| * |b,d|. Но |a,c| - это только вектор (AC), проецируемый в направление прямоугольника. Пусть u - вектор, параллельный a и c, а v - перпендикулярный вектор. Пусть они плавно меняются по всему диапазону. В векторном выражении площадь становится равной ((AC).v) / |v| * ((BD).u) / |u|= {((AC).v) ((BD).u)} / {|u| |v|}. Выберем также, что u = (1,y). Тогда v = (y, -1). Если u является вертикальным, это создает небольшую проблему с ограничениями и бесконечностями, поэтому просто выберите u в этом случае горизонтально. Для численной устойчивости просто поверните на 90 ° каждый u, который находится вне (1,-1)..(1,1). Перевод области в декартовую форму, при желании, оставлен в качестве упражнения для читателя.

Ответ 2

Было показано, что минимальный прямоугольник области множества точек коллинеарен одному из краев многоугольника сборной выпуклой оболочки [ "Определение минимума -Area Encasing Rectangle для произвольной замкнутой кривой" [Freeman, Shapira 1975]

Решение O (nlogn) для этой проблемы было опубликовано в "О вычислении минимальных прямоугольников и заданных диаметров" [Allison, Noga, 1981]

Простое и элегантное решение O (n) было опубликовано в "Алгоритм линейного времени для минимального прямоугольника области, охватывающего выпуклый многоугольник" [ Arnon, Gieselmann 1983], когда вход представляет собой выпуклую оболочку (сложность построения выпуклой оболочки равна сложности сортировки входных точек), Решение основано на методе Вращающиеся суппорты, описанном в Shamos, 1978. Онлайн-демонстрация доступна здесь.

Ответ 3

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