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
| lr = [ ('rect1', 10, 10, 20, 20), ('rect2',30,18,60,60), ('rect3',40,50,60,70),('rect4',23,40,48,80)]
print lr
# RÉFÉRENCEMENT PRÉALABLE DES RECTANGLES
##############################E#########
listex = [] # liste des limites des bandes verticales
listey = [] # liste des limites des bandes horizontales
# Création de ces deux listes
for r in lr:
if r[1] not in listex:
listex.append(r[1])
if r[2] not in listey:
listey.append(r[2])
if r[3] not in listex:
listex.append(r[3])
if r[4] not in listey:
listey.append(r[4])
listex.sort()
listey.sort()
print 'listex =',listex
print 'listey =',listey
# Création du dictionnaire dx de listes de rectangles dont les clés sont les bandes verticales
# et du dictionnaire dy de listes dont les clés sont les bandes horizontales.
# En réalité, chaque bande verticale est repérée par sa limite gauche listex[k],
# et chaque bande horizontale est repérée par sa limite inférieure listy[k].
dx = {}
dx[0] = []
dx[listex[-1]] = []
for k in range(0,len(listex)-1): # pour chaque bande verticale definie par k
print '\nk =',k,' intervalle en x : (',listex[k],',',listex[k+1],')'
li = []
for r in lr: # on passe en revue successivement tous les rectangles
print r[0],' : x =',r[1],'a',r[3],
if r[1]<=listex[k] and r[3]>=listex[k+1]: # on détermine si le rectangle intersecte la bande examinée
print r[0],'est dedans'
li.append(r[0]) # tout rectangle intersectant la bande est référenc dans une liste provisoire
else: # simplement pour l'organisation de l'affichage
print ''
dx[listex[k]] = li # la liste des rectangles intersectant la bande k est mise dans le dictionnaire dx
# sous la clé=limite gauche de la bande
dy = {}
dy[0] = []
dy[listey[-1]] = []
for k in range(0,len(listey)-1):
print '\nk =',k,' intervalle en y : (',listey[k],',',listey[k+1],')'
li = []
for r in lr:
print r[0],' : y =',r[2],'a',r[4],
if r[2]<=listey[k] and listey[k+1]<=r[4]:
print r[0],'est dedans'
li.append(r[0])
else: # simplement pour l'organisation de l'affichage
print ''
dy[listey[k]] = li
print 'dx =',dx
print 'dy =',dy
# UTILISER LE PROGRAMME
#######################
print ''
while 1:
a = input('\nEntrer abscisse : ')
b = input('Entrer ordonnee : ')
xt = 0
for x in listex:
if x<=a:
xt = x
else:
break
yt = 0
for y in listey:
if y<=b:
yt = y
else:
break
result = []
for r in dx[xt]:
if r in dy[yt]:
result.append(r)
if result!=[]:
print 'Le point (',a,',',b,') est dans les rectangles :',result
else:
print 'Le point est en dehors de tout rectangle.' |
