Минимальный ограничивающий прямоугольник многоугольника

Question

Допустим, у нас есть класс / структура Point

class Point
{
 int x;
int y;
}

и класс Polygon, который содержит список точек

class Polygon
{
  List<Point> points;

  Path(List<Point> points)
  {
  //some implementation
  }
}

Мне интересно найти точки минимального ограничивающего прямоугольника Многоугольник (https://en.wikipedia.org/wiki/Minimum_bounding_rectangle). Найденные минимальные стороны ограничивающего прямоугольника могут быть не параллельны обеим осям, поэтому я пытаюсь найти алгоритм, написанный на Java, C#, C ++. Кто-нибудь может предложить или связать такое решение, спасибо!

Answer 1

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

Описание можно найти на этой странице архива обратного пути

Прямоугольник минимальной площади, охватывающий выпуклый многоугольник P, имеет сторону, коллинеарную краю многоугольника.

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

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

Простым алгоритмом было бы вычислить для каждого края соответствующий прямоугольник, коллинеарный ему. Но построение этого прямоугольника предполагает вычисление крайних точек многоугольника для каждого ребра, процесс, который занимает O (n) времени (для n ребер). Тогда весь алгоритм будет иметь квадратичную c временную сложность.

Можно найти гораздо более эффективный алгоритм. Вместо того, чтобы пересчитывать крайние точки, их можно обновлять за постоянное время с помощью поворотных суппортов. Действительно, рассмотрим выпуклый многоугольник с двумя парами опорных линий, проходящих через все четыре обычные крайние точки в направлениях x и y. Четыре линии уже определяют прямоугольник, охватывающий многоугольник. Но если многоугольник не имеет горизонтального или вертикального края, этот прямоугольник не может претендовать на минимальную площадь. Однако линии можно вращать, пока не будет выполнено указанное выше условие. Эта процедура лежит в основе следующего алгоритма. Предполагается, что входные данные представляют собой выпуклый многоугольник с n вершинами, заданными в порядке по часовой стрелке.

Вычислите все четыре крайние точки для многоугольника и назовите их xminP, xmaxP, yminP ymaxP.

Постройте четыре линии поддержки P через все четыре точки. Они определяют два набора «измерителей».

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

Поворачивайте линии по часовой стрелке, пока одна из них не совпадет с краем его многоугольника.

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

Повторяйте шаги 4 и 5, пока линии не будут повернуты на угол больше 90 градусов. Выведите минимальную площадь, охватывающую прямоугольник. Поскольку две пары «измерителей» определяют охватывающий прямоугольник, этот алгоритм рассматривает все возможные прямоугольники, которые могут иметь минимальную площадь. Кроме того, помимо инициализации, в главном l oop алгоритма столько шагов, сколько вершин. Таким образом, алгоритм имеет линейную временную сложность.

Answer 2

Вы можете сделать это следующим образом:

1. Найдите выпуклую оболочку точек многоугольника. Популярным методом является сканирование Грэма .

2. Для каждого края выпуклой оболочки найдите минимальный ограничивающий прямоугольник, у которого одна сторона должна перекрываться с этим краем, поэтому край выпуклой оболочки является частью стороны этого прямоугольника.

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

3. Рассчитайте размер этих прямоугольников и оставьте минимальный.

Сложность этого алгоритма определяется первым step, который равен O (nlogn) . Второй шаг - O (n) , так как у вас есть выбор из одного ребра и 3 вершин, которые вращаются вокруг выпуклой оболочки, посещая каждое ребро один раз и каждую вершину 3 раза.