Мне нужно рассчитать минимальный прямоугольник области (наименьший возможный прямоугольник) вокруг многоугольника.Вычислить минимальный прямоугольник области для многоугольника
Единственный вход, который у меня есть, - это количество точек в многоугольнике.
У меня также есть координаты точек.
Используйте алгоритм rotating calipers для выпуклого многоугольника, иначе выпуклый корпус. Конечно, вам понадобятся координаты точек в многоугольнике, а не только количество точек.
Очевидно, что для получения ответа понадобятся координаты точек. Если прямоугольник выровнен по осям X и Y, то решение тривиально. Если вы хотите наименьший возможный прямоугольник под любым углом, вам нужно будет сделать какой-то процесс оптимизации.
спасибо за ур комментарий Да, мне нужна пряжка под любым углом. Не могли бы вы спроектировать процесс оптимизации – Samra
Несколько человек уже упомянули алгоритм вращающихся суппортов. Это в основном, как это делается.Вы выполняете эквивалент основного ограничивающего прямоугольника min/max, но с системой координат, повернутой под углом каждой из сторон. –
Это называется Minimum Bounding Box, это самый простой алгоритм, используемый в пакетах OCR. Вы можете найти реализацию с помощью вращающихся суппортов из пакета OpenCV. После того, как вы получите исходный код, проверить этот файл,
cv/src/cvrotcalipers.cpp
метод вам нужно, это cvMinAreaRect2().
Я не могу найти этот метод. Можете ли вы дать мне точные данные для этого спасибо – Samra
Это здесь http://www.google.com/codesearch/p?hl=ru&sa=N&cd=1&ct=rc#WMkTvnMDpLM/cv/src/cvrotcalipers.cpp&q=cvMinAreaRect2 –
Сначала сделайте grahm-scan и получите convex hull из множества точек. Затем вы можете использовать что-то вроде minimum rectangle discussed here
Выполните следующий алгоритм
для более подробно проверки связи Minimum-Area-Rectangle
только количество точек? или у вас есть координаты? – Naveen
Это обычная форма? – nickf
Является ли многоугольник произвольной ориентацией или прямоугольник должен быть ортогонален системе координат? –