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

Question

В настоящее время я получаю ограничивающий прямоугольник для моего многоугольника, получая минимальные / максимальные x и минимальные / максимальные значения y точек, но при вращении многоугольника ограничивающий прямоугольник слишком мал, чтобы соответствовать повернутому многоугольнику. Смотрите иллюстрацию для уточнения:

Это:

Превращается в это:

Как бы получить ограничивающую рамку, которая достаточно велика, чтобы содержать любое повернутое состояние?

Answer 1

Если я правильно понимаю проблему, это действительно тривиально.

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

1. Найдите вершину, наиболее удаленную от центра, и пусть d обозначает ее расстояние от центра.
2. Многоугольник всегда будет помещаться в поле 2d × 2d.