Минимальный четырехугольник алгоритма площади

Question

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

Кто-нибудь знает об алгоритме нахождения ограничивающего четырехугольника минимальной площади (любого четырехугольника, а не только прямоугольников)?

Я искал в Интернете уже несколько часов, но хотя я нашел несколько теоретических работ по этому вопросу, я не нашел ни одной реализации ...

РЕДАКТИРОВАТЬ: Люди в Mathoverflow указали мне на статью с математическим решением ( мой пост ), но для которого я не нашел реальной реализации. Я решил пойти по методу Монте-Карло от Карла, но нырну в газету и доложу здесь, когда у меня будет время ...

Спасибо всем!

Answer 1

подход Монте-Карло

Спасибо за разъяснения по проблеме. Я забрал, что требуется не математически правильный результат, а «подгонка», которая лучше, чем любая сопоставимая подгонка для других форм.

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

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

---

Монте-Карло, улучшенный

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

• Для каждого испытания случайным образом выберите p отдельных вершин и q отдельных сторон многоугольника, так что p + q = 4 .
• Для каждой из сторон q построить линию, проходящую через конечные точки этой стороны.
• Для каждой из p вершин построить линию, проходящую через эту вершину и со случайно назначенным наклоном.
• Убедитесь, что 4 прямые действительно образуют четырехугольник и что этот четырехугольник содержит (и не пересекает!) Многоугольник. Если эти тесты не пройдены, не следует продолжать эту итерацию.
• Если площадь этого четырехугольника является минимальной из всех видимых областей, запомните область и координаты вершин четырехугольника.
• Повторите произвольное количество раз и верните "лучший" найденный четырехугольник.

В отличие от того, чтобы всегда требовать 8 случайных чисел (координаты x и y для каждой из 4 точек), это решение требует только (4 + p ) случайных чисел. Кроме того, полученные линии не слепо колеблются в плоскости, а каждая из них касается многоугольника. Это гарантирует, что четырехугольники с самого начала по крайней мере очень близки к многоугольнику.

Answer 2

Скупой алгоритм

Начните с вашего выпуклого многоугольника. Хотя их более 4, найдите пару соседних точек, которые дешевле всего объединить, и объедините их, сократив количество точек в вашем многоугольнике на 1.

Под «консолидацией» я подразумеваю только расширение двух ребер с обеих сторон до их соприкосновения в точке и взятие этой точки вместо двух.

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

Before:                       After consolidating P and Q:

                                    P'
                                   /\
   P____Q                         /  \
   /    \                        /    \
  /      \                      /      \
 /        \                    /        \

Работает в O (n log n). Но это дает только приближение, и я не совсем доволен этим. Чем лучше алгоритм создает хороший правильный пятиугольник, тем больше области должна съесть последняя консолидация.

Answer 3

Вот наблюдение, которое приводит к улучшению алгоритма Монте-Карло, а также может привести к прямому ответу.

Лемма. Если ребро оптимального четырехугольника касается многоугольника только в одной точке, оно касается середины этого ребра.

Доказательство: определите X и Y как длины двух сегментов по обе стороны от точки касания. Представьте, что вы поворачиваете ребро вокруг единственной точки касания на бесконечно малый угол A. Поворот влияет на размер четырехугольника, увеличивая его на XA / 2 и уменьшая на YA / 2, или наоборот. Если X! = Y, то одно из двух направлений вращения приводит к меньшему четырехугольнику. Поскольку четырехугольник минимален, мы должны иметь X = Y.

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

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

Answer 4

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

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

ОБНОВЛЕНО: предположение о том, что каждая сторона ограничивающего четырехугольника пройдет хотя бы 2 вершины, неверно, но связанный набор линий может служить основой для решения. По крайней мере, каждая сторона ограничивающего четырехугольника будет проходить через одну из вершин, используемых для определения уникального набора линий, которые определены двумя вершинами и не пересекают многоугольник.

Answer 5

Я думаю, что 2D OBB вокруг точек является хорошей отправной точкой. Это, вероятно, даст «хорошее» (но не лучшее) соответствие; если вам все еще нужна более жесткая граница, вы можете расширить подгонку до четырехугольников.

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

Я бы держался подальше от ковариантного метода, на который ссылаются в статье Готшалка в другом месте. Это не всегда дает наилучшее соответствие и может быть очень неправильным для очень простого ввода (например, квадрат).

В 2D подход "вращающихся штангенциркулей", описанный в http://cgm.cs.mcgill.ca/~orm/maer.html, должен дать точный наиболее подходящий OBB. Эту проблему также легко представить как проблему минимизации 1D:

1. Для заданного угла поверните оси x и y на этот угол. Это дает вам два ортогональных вектора.
2. Для каждой точки проецируйте на обе оси. Следите за минимальной и максимальной проекцией по каждой оси.
3. Площадь OBB равна (max1-min1) * (max2-min2), и вы можете легко вычислить точки OBB по углу, а также по минимальной и максимальной проекциям.
4. Повторите, выбирая интервал [0, pi / 2] настолько точно, насколько вы хотите, и отслеживая лучший угол.

В блоге Джона Рэтклиффа (http://codesuppository.blogspot.com/2006/06/best-fit-oriented-bounding-box.html) есть некоторый код, который использует этот подход сэмплирования в 3D; вы сможете адаптировать его к своему 2D-случаю, если застряли. Предупреждение : Джон иногда мягко размещает фотографии NSFW на своих постах в блоге, но эта конкретная ссылка в порядке.

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

1. Вместо выбора ортогональных осей, как указано выше, вы можете выбрать две неортогональные оси. Это даст вам самый подходящий ромб. Чтобы сделать это, вам необходимо выполнить двумерный поиск по [0, pi] x [0, pi].
2. Используйте наиболее подходящий OBB в качестве отправной точки для более детального поиска. Например, вы можете взять 4 точки с OBB, перемещать одну из них, пока линия не коснется точки, а затем повторить для других точек.

Надеюсь, это поможет. Извините, информационная перегрузка:)

Answer 6

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

Посмотрите на раздел 3 (Установка OBB).