Coverage for src/ensae_teaching_cs/special/tsp_bresenham.py: 93%
95 statements
« prev ^ index » next coverage.py v7.1.0, created at 2023-04-28 06:23 +0200
« prev ^ index » next coverage.py v7.1.0, created at 2023-04-28 06:23 +0200
1# -*- coding: utf-8 -*-
2"""
3@file
4@brief Ce module contient la fonction trace_ligne qui retourne l'ensemble des pixels
5concernés par le tracé d'une ligne en 8-connexité entre deux pixels.
6"""
9def trace_ligne_simple(x1, y1, x2, y2):
10 """
11 Trace une ligne entre les points de coordonnées *(x1,y1)* et *(x2,y2)*,
12 on suppose que *x2 > x1*, *y2 >= y1*,
13 retourne la ligne sous la forme d'un ensemble de pixels *(x,y)*."""
15 if y2 - y1 <= x2 - x1: # droite en dessous de la première bissectrice
16 vx = x2 - x1
17 vy = y2 - y1
18 b = vx / 2
19 y = y1
20 x = x1
22 ligne = []
23 while x <= x2:
24 ligne.append((x, y))
25 b -= vy
26 x += 1
27 if b < 0:
28 b += vx
29 y += 1
30 return ligne
31 else: # droite au dessus de la première bissectrice
32 vx = x2 - x1
33 vy = y2 - y1
34 b = vy / 2
35 y = y1
36 x = x1
38 ligne = []
39 while y <= y2:
40 ligne.append((x, y))
41 b -= vx
42 y += 1
43 if b < 0:
44 b += vy
45 x += 1
46 return ligne
49def draw_line(x1, y1, x2, y2):
50 """
51 Trace une ligne entre les points de coordonnées *(x1,y1)* et *(x2,y2)*,
52 aucune contrainte sur les coordonnées,
53 retourne la ligne sous la forme d'un ensemble de pixels *(x,y)*.
54 Utilise l'algorithme de :epkg:`Bresenham`.
55 """
57 if x1 == x2:
58 if y1 <= y2:
59 return [(x1, i) for i in range(y1, y2 + 1)]
60 else:
61 return [(x1, i) for i in range(y2, y1 + 1)]
63 if y1 == y2:
64 if x1 <= x2:
65 return [(i, y1) for i in range(x1, x2 + 1)]
66 else:
67 return [(i, y1) for i in range(x2, x1 + 1)]
69 if x1 < x2:
70 if y1 < y2:
71 return trace_ligne_simple(x1, y1, x2, y2)
72 else:
73 ligne = trace_ligne_simple(x1, y2, x2, y1)
74 return [(x, y1 + y2 - y) for (x, y) in ligne]
76 if x2 < x1:
77 if y1 < y2:
78 ligne = trace_ligne_simple(x2, y1, x1, y2)
79 return [(x1 + x2 - x, y) for (x, y) in ligne]
80 else:
81 ligne = trace_ligne_simple(x2, y2, x1, y1)
82 return [(x1 + x2 - x, y1 + y2 - y) for (x, y) in ligne]
84 raise RuntimeError("All cases have already been processed.")
87def draw_ellipse(xc, yc, a, b):
88 """
89 Dessine une ellipse de centre *xc, yc*, de demi axe horizontal *a*,
90 de demi-axe vertical b, l'ellipse a pour équation x²/a² + y²/b² = 1
91 si l'origine est placée en *xc, yc*,
92 l'équation de la tangente au point *x0, y0* est :
93 :math:`\frac{x x_0}{a^2} + \frac{y y_0}{b^2}=0`,
94 ou :math:`x x_0 b^2 + y y_0 a^2 = 0`.
95 Utilise l'algorithme de :epkg:`Bresenham`.
96 """
98 # on évite les cas litigieux
99 if a == 0:
100 return [(xc, yc + y) for y in range(-b, b)]
101 if b == 0:
102 return [(xc + x, yc) for x in range(-a, a)]
104 bb = b * b
105 aa = a * a
107 # on trace l'ellipse de centre 0,0
108 ellipse = []
109 # premier huitième
110 vx = a * bb
111 vy = 0
112 x = a
113 y = 0
114 bl = vx / 2
116 while vx >= vy and x >= 0:
117 ellipse.append((x, y))
118 y += 1
119 vy += aa # vy = y * aa
120 bl -= vy
121 if bl < 0:
122 x -= 1
123 vx -= bb # vx = x * bb
124 bl += vx
126 # second huitième
127 while x >= 0:
128 ellipse.append((x, y))
129 x -= 1
130 vx -= bb # vx = x * bb
131 bl += vx
132 if bl > 0:
133 y += 1
134 vy += aa # vy = y * aa
135 bl -= vy
137 # second quart, symétrique par rapport à l'axe des ordonnées
138 ellipse2 = [(-x, y) for (x, y) in ellipse]
139 ellipse2.reverse()
140 ellipse.extend(ellipse2)
142 # troisième et quatrième quarts : symétrique par rapport à l'axe des
143 # abscisse
144 ellipse2 = [(x, -y) for (x, y) in ellipse]
145 ellipse2.reverse()
146 ellipse.extend(ellipse2)
148 return [(x + xc, y + yc) for (x, y) in ellipse]
151def display_line(ligne, screen, pygame):
152 """
153 Affiche une ligne à l'écran.
154 """
155 color = 0, 0, 0
156 for p in ligne:
157 pygame.draw.line(screen, color, p, p)
158 pygame.display.flip()