найти наименьший содержащий выпуклый многоугольник с заданным количеством точек
учитывая выпуклый полигон и число N, как мне найти самый маленький многоугольник, который
contains every point from the original polygon has exactly N corner pointsНапример, предположим, что у меня есть набор точек и вычислим для них выпуклую оболочку (зеленая). Теперь я хочу найти самый маленький четырехугольник, который содержит все точки (красный)
Легко видеть, что любой другой многоугольник с четырьмя углами будет либо больше, либо не будет содержать все точки. Но как мне найти этот многоугольник в общем случае?
РЕДАКТИРОВАТЬ:
Под наименьшим полигоном я подразумеваю тот, который покрывает наименьшую площадь, хотя я не уверен, что наименьшая окружность даст другие результаты.
Я добавил еще два примера изображений, которые, к сожалению, не работают с «удалить края». подход в одном из ответов
Некоторая справочная информация:
Цель состоит в том, чтобы точно определить формы с помощью распознавания изображений. Например, возьмите фотографию кубоида. Все точки внутри рамки на 2D-фотографии будут содержаться в 6-угольном выпуклом многоугольнике. Однако, поскольку реальные фигуры не имеют идеальных углов, а камера добавляет некоторое размытие, края этого многоугольника будут округлены. Смотрите прикрепленное изображение из вопросаПолучение углов из выпуклых точек