Aller au contenu

Visualisation des cellules de Voronoï☘

Représentation graphique en python☘

On donne ci-dessous quelques éléments de code python pour représenter des points dans un repère.

On utilise pour cela la bibliothèque matplotlib.

Exemple 1☘

# import de la bibliothèque pour nos figures
import matplotlib.pyplot as plt 

# dessin d'un point de coordonnées (2,3),
# représenté par un carré ( 's' pour square)
# de couleur noir (k)
# de taille 10
plt.plot(2,3, marker='s', color='k', markersize=10)

# pour lancer la construction de la figure à l'écran
plt.show()
Liste des formes et couleurs

Vous trouverez la liste des markers (forme des points) ici ou là.
Et la liste des couleurs ici ou là.

Image obtenue

On obtient:

A vous.☘

Modifier forme, couleur, taille et position du point pour bien comprendre le fonctionnement.

Exemple 2☘

On représente maintenant une série de points.

Pour cela, on crée la liste X des abscisses de ces points et la liste Y des ordonnées de ces points.
Les points placés ci-dessous sont donc les points (0,0), (1,1), (2,4), (3,9) et (4,16).

import matplotlib.pyplot as plt

X = [0, 1, 2, 3, 4]
Y = [0, 1, 4, 9, 16]

# points de couleur cyan (c), de forme hexagonale (h)
# on ne relie pas les points (linestyle = '')
plt.plot(X,Y, marker='h', color='c', markersize=20, linestyle='')
plt.show()
Valeurs de linestyle

Les valeurs pour linestyle (ou ls en abrégé):

  • ‘solid’
  • ‘dashed’
  • ‘dashdot’
  • ‘dotted’
  • '-'
  • '--'
  • '-.'
  • ':'
  • 'None'
  • ' '
  • '' (chaîne vide)
Image obtenue

On obtient:

A vous.☘

Modifier forme, couleur, taille, liste des points et linestyle pour bien comprendre le fonctionnement.

Exercice 1☘

Compléter le script ci-dessous en écrivant un corps possible pour la fonction representation dont la spécification est donnée en docstring.

from random import randint
from math import sqrt, inf
import matplotlib.pyplot as plt

xmin, xmax = -20, 20
ymin, ymax = -20, 20


def genereListePoints(nbmin, nbmax):
    """
    nbmin -- entier
    nbmax -- entier
    précondition: nbmin < nbmax

    Renvoie une liste de couples d'entiers, le premier élément du couple
    est compris entre xmin et xmax (au sens large), le second élément entre 
    ymin et ymax (au sens large).
    Les couples (x, y) sont générés au hasard.
    Le nombre de couples est généré au hasard, entre nbmin et nbmax.
    """
    assert nbmin < nbmax, "Attention, on doit avoir nbmin < nbmax"
    nbPoints = randint(nbmin, nbmax)
    return [(randint(xmin, xmax), randint(ymin, ymax)) for _ in range(nbPoints)]

def distance(x,y,a,b):
    """
    Renvoie la distance euclidienne entre A(a,b) et M(x,y)
    """
    dx, dy = x-a, y-b
    return sqrt(dx**2 + dy**2)



def plusProcheVoisin(listePoints, x, y):
    """
    listePoints -- liste de points à coordonnées entières 
    x -- entier entre xmin et xmax
    y -- entier entre ymin et ymax

    Renvoie le point de la liste listePoints le plus proche de (x,y)
    """
    distance_min = inf # initialisation à +infini
    for point in listePoints:
        d = distance(x, y, point[0], point[1])
        if d < distance_min:
            distance_min = d
            pointPlusProche = point
    return pointPlusProche


def representation(nvPoint, listePoints):
    """
    nvPoint -- couple (x,y) des coordonnées d'un point, 
    précondition:  xmin <= x <= xmax, ymin <= y <=  ymax
    listePoints -- liste de points à coordonnées dans [xmin, xmax]*[ymin,ymax]

    Affiche nvPoint en rouge forme carrée.
    Affiche les points de listePoints en bleu, forme ronde.
    Affiche le point de listePoints le plus proche de nvPoint avec un diamètre plus grand.
    """

    ## CORPS A DEFINIR ##


points = genereListePoints(8, 20)
point = (2,3)
representation(point, points)
Un code possible
from random import randint
from math import sqrt, inf
import matplotlib.pyplot as plt

xmin, xmax = -20, 20
ymin, ymax = -20, 20


def genereListePoints(nbmin, nbmax):
    """
    nbmin -- entier
    nbmax -- entier
    précondition: nbmin < nbmax

    Renvoie une liste de couples d'entiers, le premier élément du couple
    est compris entre xmin et xmax (au sens large), le second élément entre 
    ymin et ymax (au sens large).
    Les couples (x, y) sont générés au hasard.
    Le nombre de couples est généré au hasard, entre nbmin et nbmax.
    """
    assert nbmin < nbmax, "Attention, on doit avoir nbmin < nbmax"
    nbPoints = randint(nbmin, nbmax)
    return [(randint(xmin, xmax), randint(ymin, ymax)) for _ in range(nbPoints)]

def distance(x,y,a,b):
    """
    Renvoie la distance euclidienne entre A(a,b) et M(x,y)
    """
    dx, dy = x-a, y-b
    return sqrt(dx**2 + dy**2)



def plusProcheVoisin(listePoints, x, y):
    """
    listePoints -- liste de points à coordonnées entières 
    x -- entier entre xmin et xmax
    y -- entier entre ymin et ymax

    Renvoie le point de la liste listePoints le plus proche de (x,y)
    """
    distance_min = inf # initialisation à +infini
    for point in listePoints:
        d = distance(x, y, point[0], point[1])
        if d < distance_min:
            distance_min = d
            pointPlusProche = point
    return pointPlusProche


def representation(nvPoint, listePoints):
    """
    nvPoint -- couple (x,y) des coordonnées d'un point, xmin <= x <= xmax, ymin <= y <=  ymax
    listePoints -- liste de points à coordonnées dans [xmin, xmax]*[ymin,ymax]

    Affiche nvPoint en rouge forme carrée.
    Affiche les points de listePoints en bleu, forme ronde.
    Affiche le point de listePoints le plus proche de nvPoint avec un diamètre plus grand.
    """
    lePlusProche = plusProcheVoisin(listePoints, nvPoint[0], nvPoint[1])
    #liste des abscisses
    X = [point[0] for point in listePoints]
    #liste des ordonnées
    Y = [point[1] for point in listePoints] 
    plt.plot(X,Y, marker='o', color='b', markersize=4, linestyle='')
    plt.plot(nvPoint[0],nvPoint[1], marker='s', color='r', markersize=6)
    plt.plot(lePlusProche[0],lePlusProche[1], marker='o', color='b', markersize=10)
    plt.show()


points = genereListePoints(8, 20)
point = (2,3)
representation(point, points)

Exemple de graphique obtenu:

Dessiner les cellules de Voronoi☘

À partir des scripts précédents, on peut définir une fonction qui nous permettra de visualiser les différentes cellules de Voronoï.

Étudier et tester le script suivant:

from random import randint, random
from math import sqrt, inf
import matplotlib.pyplot as plt

xmin, xmax = -20, 20
ymin, ymax = -20, 20


def genereListePoints(nbmin, nbmax):
    """
    nbmin -- entier
    nbmax -- entier
    précondition: nbmin < nbmax

    Renvoie une liste de couples d'entiers, le premier élément du couple
    est compris entre xmin et xmax (au sens large), 
    le second élément entre 
    ymin et ymax (au sens large).
    Les couples (x, y) sont générés au hasard.
    Le nombre de couples est généré au hasard, entre nbmin et nbmax.
    """
    nbPoints = randint(nbmin, nbmax)
    return [(randint(xmin, xmax), randint(ymin, ymax)) for _ in range(nbPoints)]




def distance(x,y,a,b):
    """
    Renvoie la distance euclidienne entre A(a,b) et M(x,y)
    """
    dx, dy = x-a, y-b
    return sqrt(dx**2 + dy**2)





def indicePlusProcheVoisin(listePoints, x, y):
    """
    listePoints -- liste de points à coordonnées entières 
    x -- entier entre xmin et xmax
    y -- entier entre ymin et ymax

    Renvoie l'indice du point de la liste listePoints le plus proche de (x,y)
    """
    distance_min = inf # initialisation à +infini

    for indice, point in enumerate(listePoints):
        d = distance(x, y, point[0], point[1])
        if d < distance_min:
            distance_min = d
            pointPlusProche = point
            indiceDuMin = indice
    return indiceDuMin





def couleurAuHasard():
    """
    renvoie une couleur au hasard
    On pourra l'utiliser ainsi: plt.plot(..., color = couleurAuHasard(),...) 
    Voir
    https://matplotlib.org/3.1.0/gallery/color/color_demo.html#sphx-glr-gallery-color-color-demo-py
    """
    return (random(), random(), random())


def coloreCellules(listePoints):
    """
    listePoints -- liste de points dans [xmin,xmax]*[ymin,ymax] 
    (abris à rejoindre).

    Colore par une couleur au hasard chaque cellule de Voronoi définie par listePoints
    dans [xmin,xmax]*[ymin,ymax],
    c'est à dire colore la "zone de proximité" d'un abri.
    """

    # couleurs: liste de couleurs 
    # couleurs[0] sera la couleur de la zone de proximité
    # de l'abri listePoints[0]
    # couleurs[1] sera la couleur de la zone de proximité
    # de l'abri listePoints[1], etc...
    couleurs = [couleurAuHasard() for _ in range(len(listePoints))]


    # on parcourt le plan (en se limitant aux points à coord entières)
    # et on colore chaque point par la couleur correspondant 
    # à l'abri le plus proche
    for x in range(xmin, xmax+1):
        for y in range(ymin, ymax+1):
            indiceAbriPlusProche = indicePlusProcheVoisin(listePoints, x, y)
            plt.plot(x,y, marker='.', color= couleurs[indiceAbriPlusProche])

    # on dessine en noir les abris
    X = [point[0] for point in listePoints]
    Y = [point[1] for point in listePoints] 
    plt.plot(X,Y, marker='s', color='k', markersize=8, linestyle='')
    plt.show()


points = genereListePoints(8, 20)
coloreCellules(points)

Exemple de résultat: