Задать вопрос

Как получить минимальную рамку кривого контура по границам контура?

6216a0dc442b3727198106.png
Вот есть контур, я легко могу составить прямоугольную вертикальную рамку.(вторая) но она не оптимальная может быть в многих случаях Площадь будет больше. Тогда как можно сделать повернутую с меньшей площадью. Есть алгоритмы оптимальные. На вход поступают вершины всех точек кривой.
  • Вопрос задан
  • 301 просмотр
Подписаться 6 Простой 1 комментарий
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Есть алгоритм за O(n log n), где n - количество точек в кривой.

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

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

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

Удобно это реализовывать, если взять углы наклона всех сторон оболочки, их же сдвинутые на 90, 180 и 270 градусов и отсортировать. Далее надо перебирать рамки с такими углами наклона певрой стороны (можно в пределах [0,90) градусов). Первую рамку найдите перебором, а дальше какие-то точки надо будет сдвигать.

Итак, весь алгоритм:
1) построить выпуклую оболочку
2) добавить в массив углы всех сторон и их копии повернутые на 90, 180 и 270 градусов и отсортировать, но не добавлять углы не в [0,90).
3) для первого угла в массиве найдите 4 точки касания рамки.
4) Для каждого отрезка углов в отсортированном массиве проверить, а надо ли сдвинуть точки касания вперед (каждую из четырех точек со своим углом), потом найти площадь рамки в известных точках с известным наклоном.

Вместо работы с углами, для чего нужны тригонометрические функции, можно работать с векторами на единичной окружности. На отрезке углов можно легко взять середину, просто сложив два вектора-границы и нормировав. Для тернарного поиска не обязательно брать 1/3 и 2/3 на отрезке, поэтому можно так же просто просуммировать вектора с коэффициентами 1 и 2 и опять нормировать (v1+2*v2). Сортировать по углу тоже можно сравнивая вектора через векторное произведение векторов (иногда его называют псевдоскалярным).

Чтобы найти рамку с заданным углом на точках не надо ничего пересекать (кроме ответа в конце, если вам надо координаты рамки вывести, а не только площадь найти). Надо представить прямые в виде cosa*x + sina*y + c = 0. Отсюда, зная точку (x, y) и угол прямой (a), можно найти c. cosa и sina считать не надо - это координаты вектора, перпендикулярного к известному вектору наклона прямой. Когда вы нашли два значения c для двух параллельных сторон, эти коэффициенты можно сложить - это и будет расстояние между сторонами (надо складывать, потому что cosa и sina в этих двух прямых будут с разными знаками, ведь у одной прямой угол на пол оборота больше). Остается подсчитать это два раза для перпендикулярных прямых и перемножить.

Код для пересечения прямых в конце можно посмотреть тут.
Ответ написан
Пригласить эксперта
Ответы на вопрос 2
@U235U235
Откройте исходники OpenCV и посмотрите как это сделано в функции minAreaRect. Все.
Ответ написан
profesor08
@profesor08
Найди самые дальние, друг от друга, точки, проведи между ними мнимую прямую. Потом найди еще две, чтоб мнимая прямая, между ними, была перпендикулярна первой. Перемножив длины прямых получишь свою площадь. А так как знаешь координаты своих точек, то сможешь посчитать координаты угловых точек площади, чтоб правильно нарисовать свои линии. Либо не считать, а рисовать линии через найденные точки, чтоб центр линии проходил через точку, но тогда надо будет посчитать угол, под которым линия будет проходить через точку.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы