Algorithme d\'emballage de cadeau
L'algorithme d'emballage de cadeau de est un algorithme simple pour calculer la coque convexe d'un ensemble donné de points.
Cas planaire
Dans le cas bidimensionnel l'algorithme est également connu en tant que marche de Jarvis de , après R. Jarvis, qui l'a éditée en 1973 ; il a la complexité de temps de du O ( NH ), où le n est le nombre de points et le h est le nombre de points sur la coque convexe. Son exécution réelle comparée à d'autres algorithmes convexes de coque est favorable quand n est petit ou on s'attend à ce que h soit très petit en ce qui concerne le N. Enferme en général l'algorithme est surpassé par beaucoup d'autres.
Algorithme
Pour la simplicité, la description ci-dessous suppose que les points sont en position générale , c., aucun trois points ne sont le situé sur la même droite. L'algorithme peut être facilement modifié pour traiter le collinearity, y compris le choix s'il devrait rapporter seulement à les points extrêmes (sommets de la coque convexe) ou tous points qui se trouvent sur la coque convexe. En outre, l'exécution complète doit traiter les cas dégénérés quand la coque convexe a seulement des 1 ou 2 sommets, aussi bien qu'avec les questions de la précision arithmétique limité, des calculs d'ordinateur et des données d'entrée. L'algorithme d'emballage de cadeau commence par le i =0 et un p0 de point connu pour être sur la coque convexe, par exemple, le point extrême gauche, et choisit le pi+1 de point tels que tous les points sont à la droite de la ligne le pi pi+1 . Ce point peut être trouvé le temps d'O ( n ) en comparant les angles polaires de tous les points en ce qui concerne le p0 de point pris pour le centre des coordonnées polaires . Laissant le i = i +1, et le répétant avec jusqu'à ce qu'on atteigne le ph = p0 rapporte encore la coque convexe dans des étapes du h . L'algorithme d'emballage de cadeau est exactement analogue au processus d'enrouler une corde (ou le papier d'emballage) autour de l'ensemble de points.
jarvis de def (P) i = 0 p = point extrême gauche de P faire p = point tels que tous autres points dans P sont au à droite la ligne pp i = I + 1 tandis que p ! = p p de retour
L'approche est extensible à des dimensions plus élevées.
| Random links: | Ignatius Bonomi | Prüm | ORP Orzeł | Fleuve Ver | Chiffon M42 | Algoritmo_del_embalaje_de_regalo |