Как найти произвольно ориентированный минимальный ограничивающий прямоугольник в C ++

Question

Допустим, у меня есть список из N пар положительных длинных координат (точек).
Как найти наименьший прямоугольник, содержащий все их?
Прямоугольник также может иметь плавающие координаты и вращаться впод любым углом и дальше сжимается ... Не только X, Y, Ширина и Высота!

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

Answer 1

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

Answer 2

См. http://www.geometrictools.com/Source/ComputationalGeometry.html

В разделе «Поле минимальной площади» приведены различные примеры.

Answer 3

Может быть, эта статья может помочь: Наименьшая точка k, включающая прямоугольник произвольной ориентации

Answer 4

Может быть, это работает для вас:

• найти центральную точку всех ваших точек (сумма всех x / количество x, то же самое для y)
• взять самую дальнюю точкуот центра в качестве угловой точки
• проецируйте линию через 2-ю самую дальнюю точку под углом 90 ° к угловой точке
• итерируйте по точкам другой стороны центральной точки и найдите минимум

Answer 5

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

Вам понадобятся функции для определения ваших «самых угловых» точек (в вашем примере 2 левых и 2 правых пункта). Учитывая эти 4 точки, соедините их линиями.

(Обратите внимание, что в вашем примере изображения верхняя точка не будет содержаться в сгенерированном прямоугольнике, поэтому ...) Затем вам понадобится функция, чтобы определить, содержит ли созданный прямоугольник все заданные точки; если нет, увеличьте конечные точки (в данном случае верхние 2 точки сгенерированного прямоугольника) на N (что является либо одной мерой ... скажем, пикселем, либо, если вы умны, расстоянием до точки, которая находится вне границ плюс / минус один в зависимости от направления) и переоценить.