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

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

пример:

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

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

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

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

3 52
c++ algorithm

3 ответа:

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

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

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

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

для каждого направления ограничивающий прямоугольник определяется теми же четырьмя (не обязательно различными) точками для каждого угла в этом интервале. Для направления кандидата, вы будете иметь по крайней мере один произвольный выбор. Поиск этих точек может показаться задачей 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). Перевод области в декартову форму, при желании, оставляется как упражнение для читателя.

35

было показано, что минимальный прямоугольник области набора точек коллинеарен с одним из ребер выпуклого многоугольника корпуса коллекции ["определение прямоугольника с минимальной площадью для произвольной замкнутой кривой" [Freeman, Shapira 1975]

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

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

26

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

0