.

Inf 431 – Cours 16

Algorithmes
géométriques
[Link]
secrétariat de l’enseignement:
Catherine Bensoussan
cb@[Link]
Aile 00, LIX,
01 69 33 34 67

[Link]/informatique/IF
.

Plan
1. Graphique bitmap
2. Enveloppe convexe
3. Recherche de points dans des intervalles
4. Intersection de segments orthogonaux
5. Intersection de segments

Bibliographie

J.D. Foley, A. van Dam, S.K. Feiner, J.F. Hugues, Computer Graphics, Principle and Practice, Addison
Wesley, 1990.

D.E. Knuth, The Metafont book, Addison Wesley, 1986.

D.E. Knuth, Metafont : The Program, Addison Wesley, 1986.

.
Architecture de X-window

Utilisateur 1 Utilisateur 2

Ecran Serveur Emulateur Application

de terminal
fenêtres

X xterm sort
Clavier java
Souris javac

Driver Socket Pseudo−tty

d’événements

Système d’exploitation 1 Système d’exploitation 2

Machine 1 Réseau Machine 2

cf. Cours systèmes d’exploitation et réseaux en majeure 2

.

Graphique bitmap
• Ecran = matrice de pixels (1280 × 854 × 32).
• Ecran = zone mémoire (mémoire vidéo), directement accessible
par le processeur, et/ou par son co-processeur graphique.
• Tous les tracés sont digitalisés.

Par exemple pour un vecteur ou le dessin de la lettre ”a”

y+1

x x+1 x+2
.
Tracé de vecteur (1/4)
−−−→
• But : tracer le vecteur P0 P1 entre les points P0 et P1 de
coordonnées (x0 , y0 ) et (x1 , y1 ) (x0 ∈ N, y0 ∈ N, x1 ∈ N, y1 ∈ N)
• La méthode la plus simple consiste à calculer la pente m = dy/dx
où dy = y1 − y0 et dx = x1 − x0 , et en supposant 0 ≤ m ≤ 1 et 0 < dx.

static void vecteur (int x0, int y0, int x1, int y1) {
int dx = x1 - x0, dy = y1 - y0;
float m = ((float)dy) / dx;
for (int x = x0, float y = y0; x <= x1; ++x) {
setPixel(x, [Link](y));
y = y + m;
}
}
• Opérations flottantes. Calcul de l’arrondi. C’est un peu long.
• Exécution
.
Tracé de vecteur (2/4)
• L’équation de la droite passant par (x0 , y0 ) et (x1 , y1 ) est

−xdy + ydx + x0 dy − y0 dx = 0

où dy = y1 − y0 et dx = x1 − x0 .
• On maintient une erreur e entre le point (x, y) et la droite.

e = −xdy + ydx + x0 dy − y0 dx

• On suppose 0 ≤ dy/dx ≤ 1. Pour savoir si le pixel suivant sur la

droite y = x + 1 est à l’est ou au nord-est du point (x, y), on
regarde le signe de l’erreur pour le point (x + 1, y + 0.5)

em = −(x + 1)dy + (y + 0.5)dx + x0 dy − y0 dx

Soit
em = e − dy + dx/2
En multipliant par 2, on obtient

2em = 2e − 2dy + dx
.
Tracé de vecteur (3/4)
Si 2em ≤ 0, on positionne le pixel nord-est et 2e ← 2em − dx.
Sinon on positionne le pixel est ; l’erreur devient 2e ← 2em + dx.

D’où le programme quand la pente est positive et inférieure à 1.

static void vecteur (int x0, int y0, int x1, int y1) {
int dx = x1 - x0, dy = y1 - y0;
int e = 0;
for (int x = x0, y = y0; x <= x1; ++x) {
setPixel(x,y);
int em = e - 2*dy + dx;
if (em <= 0) {
++y;
e = em + dx;
} else
e = em - dx;
}
}

Si x0 , y0 , x1 , y1 sont entiers, toutes les opérations sont des additions

entières de constantes. [Bresenham]
.
Tracé de vecteur (4/4)
Exercice 1 Compléter le programme pour qu’il trace un vecteur de
pente arbitraire.

Exercice 2 Trouver un algorithme genre Bresenham pour les tracés

de cercles, ou d’ellipses.

Si on dessine le vecteur dans une fenêtre, on peut avoir à l’intersecter

avec un rectangle (clipping). Par exemple avec le bord gauche x = xmin
d’un rectangle. On calcule
dy
y = y0 + b(xmin − x0 ) + 0.5c
dx
et on démarre le tracé avec une erreur non nulle

2e = −2xmin dy + 2ydx + 2x0 dy − 2y0 dx

.

Remplissage de polygones
• Deux manières pour définir l’intérieur d’un polygone.
• pair-impair : on compte la parité des intersections d’une
droite intersectant le polygone.
• la règle de l’enroulement : les bords sont des vecteurs
orientés. L’intérieur est toujours à gauche du vecteur bord.

0 1 0 1 0
0 1 2 3 4

• on balaie par une ligne horizontale, et on adapte le Bresenham de

vecteurs en gérant une file de priorité pour l’arrivée de nouveaux
segments.
.
Bitblt
• Pour afficher du texte, chaque lettre est un petit rectangle de
pixels qu’on recopie à l’endroit voulu sur l’écran.
• Pour le défilement du texte dans une fenêtre, on recopie un
rectangle de quelques lignes vers le haut (scrolling).
• ⇒ opérations rapides pour recopier des rectangles de pixels. Bit
Block Transfer (bitblt) ou encore paquetage Raster-op, réalisées
par des processeurs vidéo spécialisés (avec beaucoup de mémoire
pour stocker les polices de caractères).
• Autrefois, ces opérations étaient réalisées par des processeurs
normaux, avec plein d’optimisations [Pike, Locanthi, Reiser, 84].
• Les opérations biblt viennent du premier écran bitmap : l’Alto de
Xerox PARC, [Lampson, McCreight, Thacker, 74]
• pixels pour chaque lettre, on part d’une description de chaque
caractère dans une police par des cubiques. Polices de
Postscript/PDF [Warnock] ou de Metafont [Knuth].
.

Dessin des lettres

     
$.$#/0 1"2,33
%.%
'.' - /0
/0,2
)1,
'4'
, 3
-
(.(#/0 1
, 4
, 2
$33
*.*#/0 ,2
214
,4'
+.+#/0 ,2,3 3
",.",#/0
"$."$#/0 +4
&'',
2 , 33
% - "%."%#/0 1&4' 2,
F6:9;!<:GH:I567J:8"9:!JK:JKL;::!98:75"#%#DC CA EFGMN=OP=Q<RD;CSJ:TU9:JJ87:6:5F:G=<:;:9:865:98
: ; < = > ?@ AB B CD D D! D "$-.$#/0
.$#/0 11
$
$24
,
,
332
N$#
PRVDCSW W W WSCDVRPN &#NRJI!JJJJJ &JJJJ
! ! 6F;&- -
(+-.(#/0 1
, 2
, % 3
= =G G?E A BC C D 5
D V5 5
V V5
R 5
R 6
R 6
RI J JJJJ
! - .+#/0 ,2
2,4
3 3
HI5J6 7 8
JW 9S:
CDV;RQ;<
P O N I J (#
JJJJ ", .' /0% ' "' "
HJ5789JJJS:;<=GF DRQONM M +#
G<I79J;<FJJJJQ IIJJ!JJJJ !
JJJJ ! ' - ! 7
HJ !
7 J7!"%# ""
"$
-
- -
.""/0
."$#/0,4
2'
+
1
2
&
4
,
33 4
)-PV!CWHIJ)!JJJ!)# GM ;=F'#
6
I: S
C! V IJ JJJ
! ! ! JJC! !"$# - 1
"%-."%#/01+2,32
:865 56789",# 8
5 58
MNOPQRVDCSWJMJJN O OFPG=<P;Q:9Q8QR7R7*6*# R6R!-6R6R7Q 7Q8P 9O:N;<M=?ESCDVRQPOM MPR""# VCSWHJNOJJP Q QF=<Q;:QP!:PO:;""
M!M N<=FHWSCDVRPN
.

Tracé d’une cubique de Bézier

Par Bresenham ou par dichotomie :
P2
P21
P1
P32
P22
P33
P31

P11

P3
P0
.

Ordre trigonométrique
On cherche à savoir si l’angle 0 ≤ P\
1 P0 P2 < π ?
Dans le cas où P\
1 P0 P2 = 0, on exige alors P0 P1 < P0 P2 .
−−−→ −−−→
En calculant le produit vectoriel P0 P1 ∧ P0 P2 . Si l’angle est nul, par
convention on compare les normes.

static int ordreTrigo (Point p0, Point p1, Point p2) {

int dx1 = p1.x - p0.x; int dy1 = p1.y - p0.y;
int dx2 = p2.x - p0.x; int dy2 = p2.y - p0.y;
if (dx1 * dy2 > dy1 * dx2) return 1;
else if (dx1 * dy2 < dy1 * dx2) return -1;
else {
if (dx1 * dx2 < 0 || dy1 * dy2 < 0) return -1;
else if (dx1*dx1 + dy1*dy1 < dx2*dx2 + dy2*dy2) return 1;
else if (dx1*dx1 + dy1*dy1 == dx2*dx2 + dy2*dy2) return 0;
else return -1;
}
}
.

Intersection de segments
static boolean intersection (Line l1, Line l2) {
return ordreTrigo (l1.p1, l1.p2, l2.p1)
* ordreTrigo (l1.p1, l1.p2, l2.p2) <= 0
&& ordreTrigo (l2.p1, l2.p2, l1.p1)
* ordreTrigo (l2.p1, l2.p2, l1.p2) <= 0;
}

l2.p2
l1.p2

l1.p1
l2.p1
.

Pente d’un vecteur

static float theta (Point p1, Point p2) {
float t; int dx = p2.x - p1.x; int dy = p2.y - p1.y;
if (dx == 0 && dy == 0) t = 0;
else t = (float) dy / ([Link](dx) + [Link](dy));
if (dx < 0) t = 2 - t;
else if (dy < 0) t = 4 + t;
return t * 90.f;
}

Cette fonction évite le long calcul de [Link](dy/dx).

p2

p1

theta
O x
.

Enveloppe convexe (1/4)

[Jarvis]
• Chercher un point avec y minimum.
• Chercher les points successifs de l’enveloppe dans l’ordre
trigonométrique.
−−−→
• Un point Pm+1 sur l’enveloppe est le Pi tel que Pm Pi fait un angle
−
→
θ minimal et positif avec l’axe 0x.

O x
.

Enveloppe convexe (2/4)

static int enveloppe (Point[ ] p) {
int m = 0, n = [Link];
if (n > 0) {
int iMin = 0;
for (int i = 1; i < n; ++i) if (p[i].y < p[iMin].y) iMin = i;
float angleMin = 400;
do {
Point t = p[m]; p[m] = p[iMin]; p[iMin] = t;
++m; iMin = 0;
for (int i = m; i < n; ++i) {
float alpha = theta(p[m-1], p[i]);
if (alpha < angleMin) { iMin = i; angleMin = alpha; }
}
angleMin = theta(p[iMin], p[0]);
} while (iMin != 0);
}
return m;
}
0 m n−1

Complexité = O(n2 )
.

Enveloppe convexe (3/4)

[Graham]

• Chercher un point P0 avec y minimum.

• Trier les points Pi sur l’angle formé avec P0 .
• Partir de ce point en tournant toujours à gauche.

O x
P0
.

Enveloppe convexe (3/4)

static int enveloppe (Point[ ] p) {
int n = [Link]; if (n <= 2) return n;
else {
int iMin = 0;
for (int i = 1; i < n; ++i)
if (p[i].y < p[iMin].y || p[i].y == p[iMin].y && p[i].x > p[iMin].x)
iMin = i;
Point t = p[0]; p[0] = p[iMin]; p[iMin] = t;
trier(p); int m = 2;
for (int i = 3; i < n; ++i) {
while (ordreTrigo(p[m], p[m-1], p[i]) >= 0)
--m;
++m;
t = p[m]; p[m] = p[i]; p[i] = t;
}
return m+1;
}
}

Exercice 3 Complexité = O(n log n)

.

Recherche dans des intervalles (1/3)

En dimension 1, représenter les points avec un arbre de recherche.

static void rechercher (Arbre a, intervalle i) {

if (a != null) {
boolean bg = i.x1 <= a.x, bd = a.x <= i.x2;
if (bg) rechercher ([Link], i);
if (bg && bd) [Link] (a.x + " ");
if (bd) rechercher ([Link], i);
}
}

Exercice 4 Complexité ?
i.x1 i.x2

O x
.

Recherche dans des intervalles (2/3)

En dimension 2, arbre de recherche en alternant le rangement sur x et y.

static void rechercher (Arbre a, Rect r, boolean d) {

boolean b1, b2;
if (a != null) {
boolean bx1 = r.x1 <= a.p.x, bx2 = a.p.x <= r.x2;
boolean by1 = r.y1 <= a.p.y, by2 = a.p.y <= r.y2;
if (d) { b1 = bx1; b2 = bx2; }
else { b1 = by1; b2 = by2; }
if (b1)
rechercher ([Link], r, !d);
if (dansRect (a.p, r))
[Link] (a.p + " ");
if (b2)
rechercher ([Link], r, !d);
}
}

Exercice 5 Complexité ?
.

Recherche dans des intervalles (3/3)

Graphiquement

B
A
D

A
B E

G
E
F
I
C D F I

G H
.
Intersection de segments orthogonaux
• On balaie le plan avec une ligne horizontale de bas en haut
(scanline). Il faut trier les extrémités des segments sur y.
• A chaque point début de segment vertical, on rajoute dans l’arbre
de recherche sa coordonnée x.
• A chaque segment horizontal, on fait une recherche des points
dans l’intervalle correspondant au segment.
• A chaque fin de segment vertical, on retire de l’arbre de recherche
la coordonnée x.
• O(k + n log n).
A

D
G
F
H

I
.
Intersection de segments (1/3)
[Shamos-Hoey]

Recherche d’une intersection :

• On balaie le plan avec une ligne horizontale de bas en haut

(scanline). Il faut donc trier les extrémités des segments. Soit Q
cet ensemble. Au début, R = ∅.
• A chaque point p dans Q dans l’ordre des y croissants,

1. si p est le début du segment s. On insère s dans R. On teste si

s intersecte le segment de gauche ou de droite dans R, et on
retourne cette intersection.
2. si p est la fin du segment s. On teste si les segments à gauche
de s et à droite de s dans R s’intersectent, et on retourne
cette intersection. On enlève s de R.

• O(n log n).

.
Intersection de segments (2/3)
[Bentley-Ottmann, 79]

• On balaie le plan avec une ligne horizontale de bas en haut

(scanline). Il faut donc trier les extrémités des segments. Soit Q
cet ensemble. Au début, R = ∅.
• A chaque point p dans Q dans l’ordre des y croissants,

1. si p est le début du segment s. On insère s dans R. Si s

intersecte le segment de gauche ou de droite t dans R, on
rajoute le point d’intersection de s et t dans Q (en respectant
l’ordre des y croissants).
2. si p est la fin du segment s. Si l’intersection des segments à
gauche de s et à droite de s dans R n’est pas dans Q, on teste
l’intersection et on l’ajoute à Q. On enlève s de R.
3. si p est l’intersection de s et t, on écrit p et on échange s et t
dans R. (Remarque: ils sont alors adjacents). On teste si le
segment de gauche s s’intersecte avec le segment à gauche de
lui dans R, et le segment à droite de t, et on rajoute cette
intersection à Q.
.
Intersection de segments (3/3)
[Bentley-Ottmann, 79] (cf. l’appliquette)
• O(n log n + k log n), en utilisant des arbres équilibrés pour R et Q
comme une file de priorité.
A
B

D
E

F
G

H
I

La vision et la synthèse d’images sont enseignées en Majeure 1 et 2.