Минимальный квадратичный алгоритм

Ответ 1

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

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

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

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

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

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

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

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

Ответ 2

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

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

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

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

Before:                       After consolidating P and Q:

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

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

Ответ 3

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

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

Ответ 4

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

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

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

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

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

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

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

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

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

Ответ 5

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

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

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

Ответ 6

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

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

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

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

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