ÉCOLE POLYTECHNIQUE - ÉCOLES NORMALES SUPÉRIEURES
ÉCOLE SUPÉRIEURE DE PHYSIQUE ET DE CHIMIE INDUSTRIELLES
COMPOSITION D'INFORMATIQUE - B - (XECLR)
(Durée : 2 heures)
L'utilisation des calculatrices n'est pas autorisée pour cette épreuve.
Le langage de programmation choisi par le candidat doit être spécifié en tête de la copie.
Enveloppes convexes dans le plan
Ce sujet a pour objectif de calculer des enveloppes convexes de nuages de points dans le plan affine, un grand classique en géométrie algorithmique. On rappelle qu'un ensemble est convexe si et seulement si pour toute paire de points , le segment de droite est inclus dans . L'enveloppe convexe d'un ensemble , notée , est le plus petit convexe contenant . Dans le cas où est un ensemble fini (appelé nuage de points), le bord de est un polygône convexe dont les sommets appartiennent à , comme illustré dans la figure 1.
Figure 1 - Un nuage de points, numérotés de 0 à 11, et le bord de son enveloppe convexe.
Le calcul de l'enveloppe convexe d'un nuage de points est un problème fondamental en informatique, qui trouve des applications dans de nombreux domaines comme :
la robotique, par exemple pour l'accélération de la détection de collisions dans le cadre de la planification de trajectoire,
le traitement d'images et la vision, par exemple pour la détection d'objets convexes (comme des plaques minéralogiques de voiture) dans des scènes 2 d ,
l'informatique graphique, par exemple pour l'accélération du rendu de scènes 3d par lancer de rayons,
la théorie des jeux, par exemple pour déterminer l'existence d'équilibres de Nash,
la vérification formelle, par exemple pour déterminer si une variable risque de dépasser sa capacité de stockage ou d'atteindre un ensemble de valeurs interdites lors de l'exécution d'une boucle dans un programme,
et bien d'autres encore.
Dans ce sujet nous allons écrire deux algorithmes de calcul du bord de l'enveloppe convexe d'un nuage de points dans le plan affine. Le premier, dit algorithme du paquet cadeau, consiste à envelopper le nuage de points progressivement en faisant pivoter une droite tout autour. Le deuxième, dit de balayage, consiste à balayer le plan horizontalement avec une droite verticale, tout en maintenant au fur et à mesure l'enveloppe convexe de la partie du nuage située à gauche de cette droite verticale. Les deux algorithmes sont illustrés respectivement dans les figures 3 et 4 .
Le temps d'exécution du premier algorithme est majoré par une constante fois , celui du deuxième par une constante fois , où désigne le nombre total de points de et le nombre de points de appartenant au bord de . Rappelons que le temps d'exécution d'un programme (fonction ou procédure) est le nombre d'opérations élémentaires (comparaisons, additions, soustractions, multiplications, divisions, affectations, etc.) nécessaires à l'exécution de . Sauf mention contraire dans l'énoncé du sujet, le candidat n'aura pas à justifier des temps de calcul de ses programmes. Toutefois, il devra veiller à ce que ces derniers ne dépassent pas les bornes prescrites.
Dans toute la suite on supposera que le nuage de points est de taille et en position générale, c'est-à-dire qu'il ne contient pas 3 points distincts alignés.
Ces hypothèses vont permettre de simplifier les calculs en ignorant les cas pathologiques, comme par exemple la présence de 3 points alignés sur le bord de l'enveloppe convexe. Nos programmes prendront en entrée un nuage de points dont les coordonnées sont stockées dans un tableau tab à 2 dimensions, comme dans l'exemple ci-dessous qui contient les coordonnées du nuage de points de la figure 1 :
0
1
1
4
4
5
5
7
7
8
11
13
0
4
8
1
4
9
6
-1
2
5
6
1
Précisons que les coordonnées, supposées entières, sont données dans une base orthonormée du plan, orientée dans le sens direct. La première ligne du tableau contient les abscisses, tandis que la deuxième contient les ordonnées. Ainsi, la colonne d'indice contient les deux coordonnées du point d'indice . Ce dernier sera nommé dans la suite.
Partie I. Préliminaires
Question 1 Écrire une fonction plusBas qui prend en paramètre le tableau tab de taille et qui renvoie l'indice du point le plus bas (c'est-à-dire de plus petite ordonnée) parmi les points du nuage . En cas d'égalité, votre fonction devra renvoyer l'indice du point de plus petite abscisse parmi les points les plus bas.
Sur le tableau exemple précédent, le résultat de la fonction doit être l'indice 7.
Dans la suite nous aurons besoin d'effectuer un seul type de test géométrique : celui de l'orientation.
Définition 1 Étant donnés trois points du nuage , distincts ou non, le test d'orientation renvoie +1 si la séquence ( ) est orientée positivement, -1 si elle est orientée négativement, et 0 si les trois points sont alignés (c'est-à-dire si deux au moins sont égaux, d'après l'hypothèse de position générale).
Pour déterminer l'orientation de ( ), il suffit de calculer l'aire signée du triangle, comme illustré sur la figure 2 . Cette aire est la moitié du déterminant de la matrice formée par les coordonnées des vecteurs et .
Figure 2 - Test d'orientation sur la séquence ( ) : positif à gauche, nul au centre, négatif à droite.
Question 2 Sur le tableau exemple précédent, donner le résultat du test d'orientation pour les choix d'indices suivants : , .
Question 3 Écrire une fonction orient qui prend en paramètres le tableau tab et trois indices de colonnes, potentiellement égaux, et qui renvoie le résultat ( ou +1 ) du test d'orientation sur la séquence ( ) de points de .
Partie II. Algorithme du paquet cadeau
Cet algorithme a été proposé par R. Jarvis en 1973. Il consiste à envelopper peu à peu le nuage de points dans une sorte de paquet cadeau, qui à la fin du processus est exactement le bord de . On commence par insérer le point de plus petite ordonnée (celui d'indice 7 dans l'exemple de la figure 1) dans le paquet cadeau, puis à chaque étape de la procédure on sélectionne le prochain point du nuage à insérer.
La procédure de sélection fonctionne comme suit. Soit le dernier point inséré dans le paquet cadeau à cet instant. Par exemple, dans l'exemple de la figure 3 . Considérons la
Figure 3 - Mise à jour du paquet cadeau après insertion du point .
relation binaire définie sur l'ensemble par :
Question 4 Justifier brièvement le fait que est une relation d'ordre total sur l'ensemble , c'est-à-dire :
(réflexivité) pour tout ,
(antisymétrie) pour tous et implique ,
(transitivité) pour tous et implique ,
(totalité) pour tous ou .
Ainsi, le prochain point à insérer (le point d'indice 5 dans la figure 3) est l'élément maximum pour la relation d'ordre . Il peut se calculer en temps linéaire (c'est-à-dire majoré par une constante fois ) par une simple itération sur les points de .
Question 5 Décrire une réalisation en Python de la procédure. Elle prendra la forme d'une fonction prochainPoint , qui prend en paramètre le tableau tab de taille ainsi que l'indice du point inséré en dernier dans le paquet cadeau, et qui renvoie l'indice du prochain point à insérer. Le temps d'exécution de votre fonction doit être majoré par une constante fois , pour tous et . La constante doit être indépendante de et , et on ne demande pas de la préciser.
Question 6 Décrire à la main le déroulement de la procédure prochainPoint sur l'exemple de la figure 3. Plus précisément, indiquer la séquence des points de considérés et la valeur de l'indice du maximum à chaque itération.
On peut maintenant combiner la fonction prochainPoint avec la fonction plusBas de la question 1 pour calculer le bord de l'enveloppe convexe de . On commence par insérer le point d'ordonnée la plus basse, puis on itère le processus de mise à jour du paquet cadeau jusqu'à ce que le prochain point à insérer soit de nouveau . À ce moment-là on renvoie le paquet cadeau comme résultat sans insérer une seconde fois.
Un détail technique : comme la taille du paquet cadeau augmente peu à peu lors du processus, et qu'à la fin elle peut être petite par rapport au nombre de points de , nous stockerons les
indices des points du paquet cadeau dans une liste. Par exemple, sur le nuage de la figure 1, le résultat sera la liste .
Question 7 Écrire une fonction convJarvis qui prend en paramètre le tableau tab de taille représentant le nuage , et qui renvoie une liste contenant les indices des sommets du bord de l'enveloppe convexe de , sans doublon. Le temps d'exécution de votre fonction doit être majoré par une constante fois , où est le nombre de points de situés sur le bord de .
Question 8 Justifier brièvement le temps d'exécution de l'algorithme du paquet cadeau.
Intermède : piles d'entiers
Dans la suite nous aurons besoin d'utiliser des piles d'entiers, dont on rappelle la définition ci-dessous :
Définition 2 Une pile d'entiers est une structure de données permettant de stocker des entiers et d'effectuer les opérations suivantes en temps constant (indépendant de la taille de la pile) :
créer une nouvelle pile vide,
déterminer si la pile est vide,
insérer un entier au sommet de la pile,
déterminer la valeur de l'entier au sommet de la pile,
retirer l'entier au sommet de la pile.
Nous supposerons fournies les fonctions suivantes, qui réalisent les opérations ci-dessus et s'executent chacune en temps constant :
newStack(), qui ne prend pas d'argument et renvoie une pile vide,
isEmpty( ), qui prend une pile en argument et renvoie True ou False suivant que est vide ou non,
push , qui prend un entier et une pile en argument, insère au sommet de (c'est-à-dire à la fin de la liste), et ne renvoie rien,
, qui prend une pile (supposée non vide) en argument et renvoie la valeur de l'entier au sommet de (c'est-à-dire à la fin de la liste),
pop , qui prend une pile (supposée non vide) en argument, supprime l'entier au sommet de (c'est-à-dire à la fin de la liste) et renvoie sa valeur.
Dans la suite il est demandé aux candidats de manipuler les piles uniquement au travers de ces fonctions, sans aucune hypothèse sur la représentation effective des piles en mémoire.
Partie III. Algorithme de balayage
Cet algorithme a été proposé par R. Graham en 1972. Nous allons écrire la variante (plus simple) proposée par A. Andrew quelques années plus tard.
La première étape consiste à trier les points du nuage par ordre croissant d'abscisse, en conservant tous les points de même abscisse dans un ordre arbitraire.
Question 9 Parmi les algorithmes de tri que vous connaissez, mentionnez-en un qui a un temps d'exécution majoré par une constante fois sur les entrées de taille .
À partir de maintenant, on supposera que les points fournis en entrée sont triés par abscisse croissante, comme c'est le cas dans l'exemple du tableau tab donné au début du sujet.
L'idée de l'algorithme est de balayer le nuage de points horizontalement de gauche à droite par une droite verticale, tout en mettant à jour l'enveloppe convexe des points de situés à gauche de cette droite, comme illustré dans la figure 4.
Figure 4 - Diverses étapes dans la procédure de balayage. La droite de balayage est en tirets.
Plus précisément, l'algorithme visite chaque point de une fois, par ordre croissant d'abscisse (donc par ordre croissant d'indice de colonne dans le tableau tab car celui-ci est trié). À chaque nouveau point visité, il met à jour le bord de l'enveloppe convexe du sous-nuage situé à gauche de . On remarque que les points et sont sur ce bord, et on appelle enveloppe supérieure la partie du bord de située au-dessus de la droite passant par et ( et compris), et enveloppe inférieure la partie du bord de située au-dessous ( et compris). Le bord de est donc constitué de l'union de ces deux enveloppes, après suppression des doublons de et .
Par exemple, dans le cas du nuage de la figure 4 gauche, le sous-nuage a pour enveloppe supérieure la séquence et pour enveloppe inférieure la séquence , le bord de son enveloppe convexe étant donné par la séquence ( ).
Informatiquement, les indices des sommets des enveloppes inférieure et supérieure seront stockés dans deux piles d'entiers séparées, ei (pour enveloppe inférieure) et es (pour enveloppe supérieure).
La mise à jour de l'enveloppe supérieure est illustrée dans la figure 5 : tant que le point visité ( dans ce cas) et les deux points dont les indices sont situés au sommet de la pile es (dans l'ordre: et ) forme une séquence ( ) d'orientation négative (voir la définition 1 pour rappel de l'orientation), on dépile l'indice situé au sommet de ( 8 dans ce cas). On poursuit ce processus d'élimination jusqu'à ce que l'orientation devienne positive ou qu'il ne reste plus qu'un seul indice dans la pile. L'indice du point visité ( dans ce cas) est alors inséré au sommet de es. La mise à jour de l'enveloppe inférieure s'opère de manière symétrique.
Figure 5 - Mise à jour de l'enveloppe supérieure lors de la visite du point .
Question 10 Écrire une fonction majES( ) qui prend en paramètre le tableau ainsi que la pile et l'indice du point à visiter, et qui met à jour l'enveloppe supérieure du sousnuage. Le temps d'exécution de votre fonction doit être majoré par une constante fois .
Question 11 Écrire une fonction majEI qui effectue la mise à jour de l'enveloppe inférieure, avec le même temps d'exécution.
Question 12 Écrire maintenant une fonction convGraham qui prend en paramètre le tableau tab de taille représentant le nuage , et qui effectue le balayage des points de comme décrit précédemment. On supposera les colonnes du tableau tab déjà triées par ordre croissant d'abscisse. La fonction doit renvoyer une pile contenant les indices des sommets du bord de triés dans l'ordre positif d'orientation, à commencer par le point .
Par exemple, sur le nuage de la figure 1, le résultat de la fonction convGraham doit être la pile contenant la suite d'incides dans cet ordre, l'indice 0 se trouvant au fond de la pile et l'indice 2 au sommet de .
Question 13 Analyser brièvement le temps d'exécution de l'algorithme de balayage décrit précédemment, en supposant une fois encore que les points du nuage fourni en entrée sont déjà triés par abscisse croissante. En déduire que le temps d'exécution total de l'algorithme de Graham-Andrew est bien majoré par une constante fois .
X ENS Informatique Commune MP PC 2015 - Version Web LaTeX | WikiPrépa | WikiPrépa
