Wikipédia

Fichier:Construction voronoi shamos.svg

Fichier d’origine ‎(Fichier SVG, nominalement de 943 × 1 064 pixels, taille : 69 kio)

Ce fichier et sa description proviennent de Wikimedia Commons.

Accéder au fichier sur Commons

Description

Description
Français : Algorithme de Shamos pour la construction du diagramme de Voronoï (diviser pour régner).
  1. L'ensemble S est partitionné en deux sous-ensembles G (gauche, bleu) et D (droite, vert), pour lesquels on connaît le diagramme de Voronoï, resp. V(G) et V(D).
  2. On raccorde les enveloppes convexes C(G) et C(D), et on trace les médiatrices des segments de raccordement.
  3. On construit la ligne de soudure P.
  4. Les deux diagrammes sont raccordés.
English: Shamos algorithm to build the Voronoi diagram (divide-and-conquer).
  • The S set is divided int two subsets, G (left, blue) and D (right, green). Their respective Voronoi diagram is known: V(G) and V(D).
  • The convex hulls C(G) and C(D) are merged. We draw the bissectors of the lines linking the hulls.
  • The seam line P is built.
  • The diagrams are merged.
    		•
    Date
    Source Travail personnel. Data set from File:Smallest circle problem.svg. Algorithm from Shamos, M. I. and Hoey, D., Closest-point problems, in Proceeding of 16th Annual IEEE Symposium on Foundations of Computer Science, Los Angeles, IEEE Computer Society Press, 1975
    Auteur Cdang
     
    Cette image vectorielle non W3C-spécifiée a été créée avec Inkscape .

    Conditions d’utilisation

    Moi, en tant que détenteur des droits d’auteur sur cette œuvre, je la publie sous la licence suivante :
    w:fr:Creative Commons
    paternité partage à l’identique
    Ce fichier est disponible selon les termes de la licence Creative Commons Attribution – Partage dans les Mêmes Conditions 3.0 (non transposée).
    Vous êtes libre :
    • de partager – de copier, distribuer et transmettre cette œuvre
    • d’adapter – de modifier cette œuvre
    Sous les conditions suivantes :
    • paternité – Vous devez donner les informations appropriées concernant l'auteur, fournir un lien vers la licence et indiquer si des modifications ont été faites. Vous pouvez faire cela par tout moyen raisonnable, mais en aucune façon suggérant que l’auteur vous soutient ou approuve l’utilisation que vous en faites.
    • partage à l’identique – Si vous modifiez, transformez, ou vous basez sur cette œuvre, vous devez distribuer votre contribution sous la même licence ou une licence compatible avec celle de l’original.

    Légendes

    Ajoutez en une ligne la description de ce que représente ce fichier

    Éléments décrits dans ce fichier

    dépeint

    type MIME

    image/svg+xml

    somme de contrôle

    2ac2df8ecc8318e27d534b3ba9050fba877fd2b1

    méthode de détermination : SHA-1

    taille des données

    70 259 octet

    hauteur

    1 064 pixel

    largeur

    943 pixel

    Historique du fichier

    Cliquer sur une date et heure pour voir le fichier tel qu'il était à ce moment-là.

    Date et heureVignetteDimensionsUtilisateurCommentaire
    actuel9 janvier 2013 à 17:03Vignette pour la version du 9 janvier 2013 à 17:03943 × 1 064 (69 kio)Cdang{{Information |Description ={{en|1=one dashed line longer.}} |Source ={{own}} |Author =Cdang |Date = |Permission = |other_versions = }}
    9 janvier 2013 à 16:45Vignette pour la version du 9 janvier 2013 à 16:45943 × 1 064 (69 kio)CdangUser created page with UploadWizard

    La page suivante utilise ce fichier :

    Métadonnées

    Ce fichier contient des informations supplémentaires, probablement ajoutées par l'appareil photo numérique ou le numériseur utilisé pour le créer.

    Si le fichier a été modifié depuis son état original, certains détails peuvent ne pas refléter entièrement l'image modifiée.

    Ce document provient de « https://fr.wikipedia.org/wiki/Fichier:Construction_voronoi_shamos.svg ».