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