trovare il poligono convesso più piccolo che contiene con un determinato numero di punti

Question

dato un polgyon convessa e un numero N, come faccio a trovare il poligono più piccolo che

1. contiene ogni punto dal poligono originale
2. ha esattamente N punti d'angolo

Ad esempio, supponiamo di avere un set di punti e di calcolare lo scafo convesso per loro (verde). Ora voglio trovare il quadrilatero più piccolo che contiene tutti i punti (rosso)

E 'facile vedere che qualsiasi altro poligono con 4 angoli sarebbe o essere più grande o non riescono a contenere tutti i punti . Ma come trovo questo poligono nel caso generale?

---

EDIT:

Con più piccolo poligono intendo il quello che copre l'area più piccola, anche se non sono sicuro se la circonferenza più piccola avrebbe dato risultati diversi.

ho aggiunto altre due immagini di esempio che purtroppo non sembrano lavorare con l'approccio dei 'rimuovere i bordi' in una delle risposte

---

Alcune informazioni di base:

L'obiettivo è quello di determinare con precisione forme con riconoscimento dell'immagine. Ad esempio, scatta una foto di un cuboide. Tutti i punti all'interno della scatola nella foto 2D saranno contenuti in un poligono convesso di 6 angoli. Tuttavia, poiché le forme del mondo reale non hanno angoli perfetti e la fotocamera aggiunge un po 'di sfocatura, i bordi di questo poligono saranno arrotondati. Vedere l'immagine allegata dalla questione Getting corners from convex points

Answer 1

è necessario definire la nozione di "più piccolo" nella sua interrogazione. Qualunque sia la tua definizione, questa domanda è stata pesantemente studiata nella letteratura sulla geometria computazionale. La ricerca frase chiave è racchiude minimo k-gon:

• Mictchell et al .: "Minimum-perimetrale Enclosing k-gon" 2006 (CiteSeer link)
• Aggarwal et al .: "minima Area circoscrivendo poligoni" 1985 (CiteSeer link)
• O'Rourke et al .: "Un algoritmo ottimale per fnding triangoli muraria minime" 1986, Algorithmica (ACM link)

Gli algoritmi generali non sono semplici (sebbene gli algoritmi per triangoli o rettangoli di area minima siano semplici). A seconda dei tuoi obiettivi, potresti dover abbandonare qualsiasi nozione matematica di "il più piccolo" e andare verso un'euristica.

Answer 2

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