учитывая выпуклый полигон и число N, как найти наименьший многоугольник, который
- содержит каждую точку из исходного многоугольника
- имеет ровно N угловых точек
Например, предположим, что у меня есть набор точек и вычислим для них выпуклую оболочку (зеленый). Теперь я хочу найти наименьший четырехугольник, содержащий все точки (красный)
Легко видеть, что любой другой многоугольник с 4 углами будет либо больше, либо не содержать всех точек. Но как найти этот многоугольник в общем случае?
EDIT:
С наименьшим полигоном я имею в виду тот, который покрывает самую маленькую область, хотя я не уверен, что самая маленькая окружность даст разные результаты.
Я добавил еще два примера, которые, к сожалению, не работают с подходом "удалить края" в одном из ответов
Некоторая справочная информация:
Цель состоит в том, чтобы точно определить фигуры с распознаванием изображений. Например, возьмите фотографию кубоида. Все точки внутри коробки в 2D-фотографии будут содержаться в 6-угловом выпуклом многоугольнике. Однако, поскольку у реальных фигур нет идеальных углов, а камера добавляет некоторое размытие, края этого многоугольника будут закруглены. См. Прикрепленное изображение из вопроса Получение углов из выпуклых точек