trouver le plus petit polygone convexe contenant un nombre donné de points
avec un polgyon convexe et un nombre N, Comment trouver le plus petit polygone que
- contient chaque point du polygone d'origine
- a exactement N points d'angle
Par exemple, supposons que j'ai un ensemble de points et de calculer l'enveloppe convexe (en vert). Maintenant je veux trouver le plus petit quadrangle qui contient tous les points (rouge)
il est facile de voir que n'importe quel autre polygone avec 4 coins serait soit plus grand ou ne pas contenir tous les points. Mais comment trouver ce polygone dans le cas général?
EDIT:
avec le plus petit polygone je veux dire celui qui couvre la plus petite superficie, bien que je ne suis pas sûr que la plus petite circonférence donnerait des résultats différents.
I ajout de deux autres exemples d'images qui, malheureusement, ne semblent pas fonctionner avec l'approche "remove edges" dans l'une des réponses
Quelques informations de fond:
le but est de déterminer avec précision les formes avec la reconnaissance d'image. Par exemple, prenez une photo d'un cuboïde. Tous les points à l'intérieur de la boîte dans la photo 2D seront contenus dans un polygone convexe à 6 coins. Cependant, puisque les formes du monde réel n'ont pas des coins parfaits, et l'appareil ajoute un flou, les côtés de ce polygone sera arrondi. Voir l'image ci-jointe à la question prendre des coins à partir de points convexes
2 réponses
Vous devez définir la notion de "petit" dans votre question. Quelle que soit votre définition, cette question a été fortement étudiée dans la littérature de géométrie computationnelle. La phrase clé de recherche est contenant minimal k-gon :
- Mictchell et al.: "Minimum-Périmètre Englobant k-gone" de 2006 ( CiteSeer lien )
- Aggarwal et al.: "Superficie Minimale Délimitant Les Polygones" 1985 ( CiteSeer lien )
- O'Rourke et al.: "Un algorithme optimal pour fnding minimale joignant triangles" en 1986, Algorithmica ( ACM lien )
les algorithmes généraux ne sont pas simples (bien que les algorithmes pour les triangles de zone min ou les rectangles soient simples). Selon vos objectifs, vous pourriez avoir à abandonner toute notion mathématique de "plus petit" et la tête pour un heuristique.
While number of edges > N do
remove the shortest edge by replacing its endpoints
with the intersection point of the adjacent edges