У меня есть рисунок, представленный через матрицу байтов (растровую матрицу). Пример рисунка показан на Picture 1.
Цель состоит в том, чтобы найти лучший угол поворота некоторого данного рисунка . Когда рисунок поворачивается на лучший угол, прямоугольник, параллельный осям X и Y и вписывающий рисунок, имеет наименьшую площадь.
Прямоугольники, которые вписывают фигуру, показаны на изображениях светло-серым цветом. В Picture 2, вы можете увидеть , что идеальный поворот рисунка составляет около 30 градусов по часовой стрелке.
Теперь я знаю алгоритм, как найти этот угол, но мне кажется, что это очень неэффективно. Это выглядит так:
- Проход по углам от 0 до 45.
- Для текущего угла, для каждой точки фигуры рассчитайте новое, повернутое местоположение
- Найдите границы прямоугольника, который содержит фигуру (минимальное и максимальное значения x, y), и зарегистрируйте ее, если на данный момент наилучшее совпадение
- Следующий угол
Это своего рода метод грубой силы, который работает хорошо и достаточно быстро для маленьких фигур. Однако мне нужно работать с фигурами, которые содержат до 10 миллионов точек, и мой алгоритм становится медленным.
Какой будет хороший алгоритм для этой проблемы?
источник
Первый шаг вашего подхода ошибочен - существует бесконечное количество реальных значений от 0 до 45, поэтому нет смысла «проходить через них». Тем не менее, ваш алгоритм может быть восстановлен:
найти выпуклую оболочку многоугольника
пройти через конечное (!) число углов, заданных внешними краями выпуклой оболочки
Теперь примените шаги с 2 по 4, используя эти углы.
Это работает, потому что можно показать, что минимальный охватывающий прямоугольник должен касаться одного из внешних краев выпуклой оболочки.
источник