Génération aléatoire des points et structures des données

Télécharger le code source pour commencer. Modifier la méthode d'initialisation des points de la classe Vue pour générer des points sur un disque de centre le centre de la fenêtre et de rayon r. La méthode d'initialisation prend alors pour arguments:

• n : nb points,
• width: largeur et hauteur de la fenêtre, et
• r: rayon du disque compris entre 0 et width.

NB: pour les tests initiaux, vous pouvez prendre n = 20, width = 800, r = 250.

Tris d'un ensemble fini de points du plan

Pour cet exercice, vous pouvez implémenter les différents ordres à envisager dans des classes de comparateurs qui héritent de Comparator pour ensuite utiliser la méthode statique sort de la classe Collections pour obtenir le tri optimisé d'une liste de points selon vos comparateurs.

• Pour un ensemble fini de points noté V, effectuer les tris suivants:
1. tri x,y, appelé tri lexicographique. Ce tri utilise la relation définie à la question précédente: il ordonne les points selon leur abscisse (x) croissante et en cas d'égalité sur l'abscisse, la comparaison se fait sur ordonnée (y) croissante.
2. le tri y,x est une variante de ce tri qui s'obtient en inversant les rôles respectifs de x et y.
3. tri θ,ρ, appelé tri angulaire (ou polaire) de centre O, de direction $\overrightarrow{u}$ , ordonne les points selon leurs coordonnées polaires pour (O, $\overrightarrow{u}$) en inversant l'ordre pour ρ. C'est-à-dire, P ≤ M ⇔ P.θ < M.θ ou (P.θ = M.θ et P.ρ ≥ M.ρ)}.

Tester vos tris sur les points donnés dans des ensembles de points simples et sur des ensembles de points générés aléatoirement.

• Les relations définies ci-dessous, sont-elles des relations d'ordre?
  • R1 = {(P, M) | P.x < M.x ou (P.x = M.x et P.y ≤ M.y)}
  • R2 = {(P, M)_O | P ≼_O M} avec la relation de précédence notée ≼_O, définie par P ≼_O M ⇔ {0< α < Π ou ((α = 0 ou Π) et OP ≤ OM)} avec α = mesure de l'angle orienté ( $\overrightarrow{\mathrm{OP}},\overrightarrow{\mathrm{OM}}$)

• A quelle(s) condition(s), la relation R2 peut-elle devenir une relation d'ordre pour V?
• En déduire le calcul d'un ordre polaire de V n'utilisant ni les fonctions trigonométriques, ni leurs inverses.

Algorithme des demi-plans

En partant de l'algorithme des demi-plans, écrire les méthodes utiles au calcul de l'enveloppe convexe d'un ensemble de points et afficher les points et l'enveloppe convexe des points ainsi calculée.

Tester l'algorithme sur les points donnés dans des ensembles de points simples et sur des ensembles de points générés aléatoirement.

Algorithme de Jarvis

Ecrire la méthode jarvis qui part d'un ensemble de points du plan et qui construit la liste envConv contenant la liste cyclique des points formants les sommets de l'enveloppe convexe en utilisant l'algorithme de Jarvis. La liste cyclique des points de l'enveloppe convexe est la liste des points de l'enveloppe dans l'ordre de calcul de l'algorithme de Jarvis avec la répétition du dernier point qui est aussi le premier.

Tester l'algorithme sur les points donnés dans des ensembles de points simples et sur des ensembles de points générés aléatoirement.

Algorithme de Graham

Cet exercice consiste à implémenter l'algorithme de Graham vu en cours.

Tester l'algorithme sur les points donnés dans des ensembles de points simples et sur des ensembles de points générés aléatoirement.

Mise à jour dynamique de l'enveloppe convexe

Dans cet exercice, on suppose qu'un ensemble de points V est donné avec son enveloppe convexe EC et l'objectif est d'envisager l'ajout et la suppression de points de l'ensemble V après la construction initiale de l'EC.

Donner un algorithme qui permet d'ajouter un point à l'ensemble initial de points et à mettre à jour l'enveloppe convexe associée en O(k), où k représente le nombre de points dans EC.

Ecrire une méthode qui permet de supprimer un point de EC et de mettre à jour EC en O(n) où n représente le nombre de points de V.

Mesures empiriques

Ecrire les méthodes utiles à la mesure du temps mis pour calculer l'enveloppe convexe par chaque implémentation.

Faire la mesure du temps pour des ensembles de points de 10 à 10 000 pour tester empiriquement les implémentations des trois algorithmes et les comparer aux complexités théoriques.

Union et intersection d'enveloppes convexes

Dans cet exercice, on considère plusieurs ensembles de points pour lesquels les enveloppes convexes sont données.

1. Proposer une méthode qui calcule l'intersection des enveloppes convexes de ces ensembles de points.
2. Proposer une méthode qui calcule l'union des enveloppes convexes de ces ensembles de points.
3. Déduire de la question précédente un algorithme permettant de calculer l'enveloppe convexe d'un ensemble de points en procédant par dichotomie.