Найти наименьший содержащий выпуклый многоугольник с заданным числом точек

учитывая выпуклый полигон и число N, как найти наименьший многоугольник, который

  • содержит каждую точку из исходного многоугольника
  • имеет ровно N угловых точек

Например, предположим, что у меня есть набор точек и вычислим для них выпуклую оболочку (зеленый). Теперь я хочу найти наименьший четырехугольник, содержащий все точки (красный)

smallest quadrangle             enter image description here

Легко видеть, что любой другой многоугольник с 4 углами будет либо больше, либо не содержать всех точек. Но как найти этот многоугольник в общем случае?

EDIT:

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

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

Некоторая справочная информация:

Цель состоит в том, чтобы точно определить фигуры с распознаванием изображений. Например, возьмите фотографию кубоида. Все точки внутри коробки в 2D-фотографии будут содержаться в 6-угловом выпуклом многоугольнике. Однако, поскольку у реальных фигур нет идеальных углов, а камера добавляет некоторое размытие, края этого многоугольника будут закруглены. См. Прикрепленное изображение из вопроса Получение углов из выпуклых точек

blurred corners

Ответы

Ответ 1

Вам нужно определить понятие "наименьшее" в вашем вопросе. Независимо от вашего определения, этот вопрос был широко изучен в литературе по вычислительной геометрии. Ключевая фраза поиска минимальна: k-gon:

  • Mictchell и др. "Ограничение минимального периметра k-gon" 2006 (ссылка CiteSeer)
  • Aggarwal и др.: "Минимальные площади обложки полигонов" 1985 (ссылка CiteSeer)
  • O'Rourke et al.: "Оптимальный алгоритм для минимальных охватывающих треугольников" 1986, Алгоритмика (ссылка ACM)

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

Ответ 2

While number of edges > N do
  remove the shortest edge by replacing its endpoints 
  with the intersection point of the adjacent edges