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

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

Just an image I found on the web...

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

Ответы

Ответ 2

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

Ответ 4

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

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

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

Ответ 5

Возможно, это работает для вас:

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