biorąc pod uwagę wypukły polgyon i liczbę N, jak znaleźć najmniejszy wielokąt

zawiera każdy punkt z oryginalnego wielokątama dokładnie N punktów narożnych

Załóżmy na przykład, że mam zestaw punktów i obliczę dla nich wypukły kadłub (zielony). Teraz chcę znaleźć najmniejszy czworokąt, który zawiera wszystkie punkty (czerwony)

Łatwo zauważyć, że każdy inny wielokąt z 4 rogami byłby większy lub nie zawierał wszystkich punktów. Ale jak znaleźć ten wielokąt w ogólnym przypadku?

EDYTOWAĆ:

Przy najmniejszym wielokącie mam na myśli ten, który pokrywa najmniejszy obszar, chociaż nie jestem pewien, czy najmniejszy obwód dawałby różne wyniki.

Dodałem jeszcze dwa przykładowe zdjęcia, które niestety nie działają z podejściem „usuń krawędzie” w jednej z odpowiedzi

Niektóre podstawowe informacje:

Celem jest dokładne określenie kształtów za pomocą rozpoznawania obrazu. Na przykład zrób zdjęcie prostopadłościanu. Wszystkie punkty wewnątrz ramki na zdjęciu 2D będą zawarte w 6-narożnym wypukłym wielokącie. Ponieważ jednak kształty w rzeczywistym świecie nie mają idealnych rogów, a kamera dodaje trochę rozmycia, krawędzie tego wielokąta zostaną zaokrąglone. Zobacz załączony obraz z pytaniaZdobywanie narożników z wypukłych punktów