[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/all2fr\/wiki1\/quickhull-wikipedia\/#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/all2fr\/wiki1\/quickhull-wikipedia\/","headline":"Quickhull – Wikipedia","name":"Quickhull – Wikipedia","description":"before-content-x4 Animation de l’algorithme QuickHull Foule est un algorithme pour calculer la coquille convexe de toute quantit\u00e9 finie de points","datePublished":"2022-10-28","dateModified":"2022-10-28","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/all2fr\/wiki1\/author\/lordneo\/#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/all2fr\/wiki1\/author\/lordneo\/","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/thumb\/4\/42\/Animation_depicting_the_quickhull_algorithm.gif\/220px-Animation_depicting_the_quickhull_algorithm.gif","url":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/thumb\/4\/42\/Animation_depicting_the_quickhull_algorithm.gif\/220px-Animation_depicting_the_quickhull_algorithm.gif","height":"220","width":"220"},"url":"https:\/\/wiki.edu.vn\/all2fr\/wiki1\/quickhull-wikipedia\/","wordCount":2386,"articleBody":"     (adsbygoogle = window.adsbygoogle || []).push({});before-content-x4 Animation de l’algorithme QuickHull Foule est un algorithme pour calculer la coquille convexe de toute quantit\u00e9 finie de points dans l’espace bidimensionnel ou tridimensionnel. La couverture convexe d’une quantit\u00e9 de points est d\u00e9crite par un train polygone ferm\u00e9, qui repr\u00e9sente la connexion de tous les points extr\u00eames de la foule, comprend ainsi tous les points de la foule. Une explication intuitive fr\u00e9quemment utilis\u00e9e de cette coque est une bande de caoutchouc qui couvre la quantit\u00e9 ponctuelle. S’il se trouve serr\u00e9 sur tous les points ext\u00e9rieurs, cela forme la couverture convexe de la file d’attente.        (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4Le nom Foule est d\u00e9riv\u00e9 de la similitude avec Quicksort, un algorithme pour trier n’importe quel montant. Il est mentionn\u00e9 pour la premi\u00e8re fois dans le livre G\u00e9om\u00e9trie informatique Par Franco Prepared et Michael Shamos, [d’abord] dans lequel les deux auteurs pr\u00e9sentent l’algorithme d\u00e9crit ici, qui ramasse les id\u00e9es d’autres auteurs. [2] [3] [4] L’id\u00e9e algorithmique pour Quickhull provient du principe de \u00abparties et dominantes\u00bb, qui est souvent utilis\u00e9e en informatique. Il d\u00e9crit la proc\u00e9dure pour diviser le probl\u00e8me en plusieurs petits probl\u00e8mes, puis le r\u00e9soudre de mani\u00e8re r\u00e9cursive en utilisant le m\u00eame algorithme. Dans ce contexte, des tentatives sont souvent faites pour choisir la division si intelligemment qu’un grand nombre de quantit\u00e9s de solutions non valides tombent. Ce type de structure peut souvent impl\u00e9menter des algorithmes qui ont \u00e9t\u00e9 con\u00e7us sur ce principe facilement et facilement lisibles car ils ont une structure r\u00e9cursive compr\u00e9hensible.        (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4Des noms : S Est le montant des points donn\u00e9s Skin Est la quantit\u00e9 de points d’un c\u00f4t\u00e9 du droit \u00e0 travers les points P et Q . [5] fonction QuickHull (s){ \/\/ d\u00e9termine la coquille convexe de la foule s Coque convexe: = {}    A: = point \u00e0 l'extr\u00eame gauche    B: = point \u00e0 l'extr\u00eame droite    Ajouter les points A et B de la coque convexe    \/\/ Celui divise simplement le n - 2 points restants dans les sous-quantit\u00e9s S1 et S2    S1: = quantit\u00e9 de points en s qui se trouvent sur le c\u00f4t\u00e9 droit de    S2: = quantit\u00e9 de points en s qui se trouvent sur le c\u00f4t\u00e9 gauche de    Findhull (S1, A, B)    Findhull (S2, B, A)    \u00c9dition: coque convexe} fonction Findhull (SK, P, Q){ \/\/ d\u00e9termine les points sur la coquille convexe de la foule s k qui sont sur le c\u00f4t\u00e9 droit du pq droit Si SK ne contient aucun point alors \u00c9dition: coque convexe    C: = le point de SK, qui a la plus grande distance du pq droit    Ajoutez le point C au couvercle convexe entre les points P et Q    \/\/ Les trois points P, Q et C divisent les points restants de SK dans les sous-quantit\u00e9s S0, S1 et S2    S0: = les points dans le triangle PCQ    S1: = les points sur le c\u00f4t\u00e9 droit du PC droit    S2: = les points sur le c\u00f4t\u00e9 droit du CQ droit    Findhull (S1, P, C)    Findhull (S2, C, Q)    \u00c9dition: coque convexe}  L’algorithme fonctionne sur n’importe quel nombre fini de points. Il n’y a aucune exigence particuli\u00e8re pour l’arrangement ou le nombre de points. Cependant, un arrangement sym\u00e9trique des points a une plus grande probabilit\u00e9 des meilleurs cas (meilleurs cas) Barri\u00e8re de temps d’ex\u00e9cution de O ( n \u22c5 enregistrer \u2061 ( n ) ) {DisplayStyle {Mathcal {o}} (ncdot log (n))} Partir et \u00eatre consid\u00e9rablement plus lent.         (adsbygoogle = window.adsbygoogle || []).push({});after-content-x42. Points extr\u00eames gauche et droit Pour d\u00e9terminer la premi\u00e8re division de la foule, les deux points extr\u00eames de l’axe X sont recherch\u00e9s. Donc, ces points qui sont les plus \u00e0 gauche et le plus \u00e0 droite. Ces points peuvent d\u00e9j\u00e0 \u00eatre ajout\u00e9s au train polygone de la coquille convexe, car ils sont garantis pour en faire partie comme des points extr\u00eames.  3. Distribution dans la quantit\u00e9 de point gauche et droit Les deux points trouv\u00e9s forment une ligne droite qui divise la quantit\u00e9 ponctuelle en deux zones. Tous points liens Beaucoup et tous les points repr\u00e9sentent de la ligne droite \u00c0 droite De l’autre. \u00c0 droite et liens Dans ce contexte, r\u00e9sulte de l’angle entre le vecteur directionnel de la s\u00e9paration droite et le vecteur d\u00e9fini par le point de d\u00e9part du droit et le point \u00e0 v\u00e9rifier. Si cet angle est inf\u00e9rieur \u00e0 180 \u00b0, le point est consid\u00e9r\u00e9 comme 180 \u00b0 comme \u00e0 gauche que celle de celui-ci. Les deux sont d\u00e9sormais trait\u00e9s r\u00e9cursivement avec l’algorithme QuickHull par ces points s\u00e9par\u00e9s. Dans cet exemple, seule la partie gauche de la quantit\u00e9 de points est prise en compte. Toutes les d\u00e9clarations faites s’appliquent \u00e9galement \u00e9quivalentes \u00e0 la bonne partie.  4. point avec une distance maximale de la droite Le point qui a la distance maximale de la ligne droite est d\u00e9termin\u00e9 dans le point de vue consid\u00e9r\u00e9. Cela fait \u00e9videmment partie du train polygone que vous recherchez. Un triangle est cr\u00e9\u00e9 avec le point de d\u00e9part et le point final des lignes droites.  5. Les points dans le triangle sont ignor\u00e9s Le triangle est compos\u00e9 de trois points, qui font tous partie des polygones du bo\u00eetier convexe. Pour cette raison, tous les points \u00e0 l’int\u00e9rieur de ce triangle ne peuvent pas faire partie de ce polygone, car ils sont d\u00e9j\u00e0 \u00e0 l’int\u00e9rieur. Tous les points de ce triangle peuvent donc \u00eatre ignor\u00e9s pour d’autres r\u00e9cursives de l’algorithme.  6. Division renouvel\u00e9e et appel r\u00e9cursif Les lignes droites r\u00e9sultant comme les c\u00f4t\u00e9s du triangle sont maintenant consid\u00e9r\u00e9es comme une ligne de s\u00e9paration renouvel\u00e9e de la quantit\u00e9 ponctuelle. Tous les points \u00e0 gauche du triangle repr\u00e9sentent beaucoup, tous les points \u00e0 droite du triangle l’autre.  7. Le polygone de couverture convexe fini Cette division r\u00e9cursive et la d\u00e9termination des autres points sont r\u00e9p\u00e9t\u00e9es jusqu’\u00e0 ce que le point de d\u00e9part et le point final de la s\u00e9paration droite fait partie des quantit\u00e9s \u00e0 consid\u00e9rer, car dans ce cas, il est clair qu’il s’agit actuellement d’un segment du train polygone que vous recherchez. \u2191  Franco P. Pr\u00e9paration, Michael Ian Shamos: G\u00e9om\u00e9trie informatique . Une introduction. 1\u00e8re \u00e9dition. Springer-Verlag, 1985, ISBN 0-387-96131-3.   \u2191  William F. Eddy: Un nouvel algorithme convexe de coque pour les ensembles planaires . Dans: Transactions ACM sur les logiciels math\u00e9matiques . 3e ann\u00e9e, 1977, S.  393\u2013403 .   \u2191  Alex Bykat: Coque convexe d’un ensemble fini de points en deux dimensions . Dans: Lettres de traitement de l’information . 7e ann\u00e9e, 1978, S.  296\u2013298 .   \u2191  P. J. Green, B.W. Silverman: Construire la coque convexe d’un ensemble de points dans le plan . Dans: Journal informatique . 22e ann\u00e9e, 1979, S.  262\u2013266 .   \u2191  OpenGenus IQ: Algorithme rapide de la coque pour trouver la coque convexe       (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4"},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/all2fr\/wiki1\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/all2fr\/wiki1\/quickhull-wikipedia\/#breadcrumbitem","name":"Quickhull – Wikipedia"}}]}]