1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
|
# -*- coding: cp1252 -*-
import random # pour tirer aléatoirement des nombres
import Matrix as mat # pour les matrices
import UserArray as ua # pour les matrices
import math # fonction sqrt
import PIL.Image as Im # pour les images
import PIL.ImageDraw as Id # pour dessiner
def construit_noeud(n, x =500, y = 500):
l=[]
for i in range(0,n):
xx = x * random.random ()
yy = y * random.random ()
l.append ((xx,yy))
return l
def distance_noeud (l,i,j):
"""calcule la distance entre deux villes i et j de la liste l"""
x = l [i][0] - l [j][0]
y = l [i][1] - l [j][1]
d=math.sqrt (float (x*x+y*y))
return d
def construit_arete (l,part = 0.15,r=20):
"""tire aléatoirement part * len (l) arêtes et construit la matrice
d'adjacence"""
nb = len (l)
m = mat.Matrix ( [ 0 for i in range(0,nb) ]) # crée un vecteur de nb zéros
m = ua.transpose (m) * m # effectue une multiplication du vecteur
# précédent avec son vecteur transposé
# pour obtenir une matrice carrée nulle
are = int (part * nb * nb)
while are > 0:
i = random.randint (0,nb-1)
j = random.randint (0,nb-1)
if (distance_ville (l,i,j)-r )>0
m [i,j] =0
else m[i][j]=1
are -= 1
return m
def dessin_noeud_arete (l,m,chemin):
"""dessine la ville et les routes dans une image"""
mx, my = 0,0
for i in l:
mx = max (mx, i [0])
my = max (my, i [1])
mx += 25
my += 25
mx, my = int (mx), int (my)
im = Im.new ("RGB", (mx, my), (255,255,255)) # création d'une image blanche
draw = Id.Draw(im)
# dessin des noeuds
for i in l:
j = (int (i [0]), int (i[1]))
j2 = (j [0] + 10, j [1] + 10)
draw.ellipse ((j,j2), fill = (0,0,0))
# dessin des arêtes
for i in range (0,len(l)):
for j in range (0,len(l)):
if m [i,j] > 0:
a = (int (l [i][0]+5), int (l [i][1]+5))
b = (int (l [j][0]+5), int (l [j][1]+5))
draw.line ((a,b),fill=(255,0,0))
# dessin des noeuds de départ et d'arrivée
v1 = chemin [0]
v2 = chemin [ len (chemin)-1]
a = (int (l [v1][0]), int (l [v1][1]))
b = (int (l [v1][0]+10), int (l [v1][1]+10))
draw.ellipse ((a,b), fill = (0,255,0))
a = (int (l [v2][0]), int (l [v2][1]))
b = (int (l [v2][0]+10), int (l [v2][1]+10))
draw.ellipse ((a,b), fill = (0,255,0))
# dessin du chemin
for c in range (0,len(chemin)-1):
i = chemin [c]
j = chemin [c+1]
print i,j
if m [i,j] > 0:
a = (int (l [i][0]+5), int (l [i][1]+5))
b = (int (l [j][0]+5), int (l [j][1]+5))
draw.line ((a,b),fill=(0,0,255))
else:
a = (int (l [i][0]+5), int (l [i][1]+5))
b = (int (l [j][0]+5), int (l [j][1]+5))
draw.line ((a,b),fill=(0,0,50))
# programme principal
# construction des noeuds
l = construit_ville (10)
print l
# construction des arêtes
m = construit_arete (l)
print m
41
# choix de noeud de départ de d'arrivée
a,b = 0,0
while a == b:
a = random.randint (0,len(l)-1)
b = random.randint (0,len(l)-1)
print "noeud de départ et d'arrivée : ",a,b
# construction de l'image du résultat
im = dessin_ville_arete(l,m,[a,b]) |
Partager