You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

264 lines
16 KiB

  1. \documentclass[11pt]{scrartcl}
  2. % French
  3. \usepackage[utf8]{inputenc}
  4. \usepackage[T1]{fontenc}
  5. \usepackage[frenchb]{babel}
  6. \usepackage{hyperref}
  7. \hypersetup{
  8. colorlinks,
  9. linkcolor={red!50!black},
  10. citecolor={blue!50!black},
  11. urlcolor={blue!30!black}
  12. }
  13. \usepackage{dirtree}
  14. \usepackage{graphicx}
  15. \graphicspath{{images/}}
  16. % Specifying the outputdir option else a bug prevents from compiling a document that contains in-doc minted code.
  17. \usepackage[outputdir=/tmp]{minted}
  18. \usepackage[usenames,dvipsnames]{xcolor}
  19. \definecolor{darkblue}{HTML}{123C73}
  20. \definecolor{darkbrown}{HTML}{A16516}
  21. \newcommand{\funname}[1]{\texttt{\textcolor{darkblue}{#1}}}
  22. \newcommand{\filename}[1]{\texttt{\textcolor{darkbrown}{#1}}}
  23. \newcommand{\code}[1]{\mintinline{ocaml}{#1}}
  24. %% This code substitutes underscore.sty
  25. \begingroup\lccode`~=`_
  26. \lowercase{\endgroup
  27. \protected\def~{\ifmmode\sb\else\textunderscore\fi}
  28. }
  29. \AtBeginDocument{\catcode`_=\active}
  30. %% end
  31. \usepackage{fancyhdr}
  32. \pagestyle{fancy}
  33. \fancyhf{}
  34. \fancyhead[LE,RO]{Quentin Barrand}
  35. \fancyhead[RE,LO]{ENSIIE \\ IPRF - « QuadTree »}
  36. \fancyfoot[LE,CO]{\thepage}
  37. \areaset[5mm]{412pt}{657pt}
  38. \begin{document}
  39. \title{\textbf{IPRF - « QuadTree »}}
  40. \subtitle{Rapport}
  41. \author{Quentin Barrand\\
  42. \href{mailto:quentin@quba.fr}{\texttt{quentin@quba.fr}}}
  43. \date{\today}
  44. \maketitle
  45. \begin{abstract}
  46. Ce document a été réalisé dans le cadre du projet final du module IPRF \mbox{« Programmation fonctionnelle »} de la formation FIPA de l'ENSIIE.\\
  47. Dans ce projet, nous étudions l'opportunité d'utiliser une structure de données de type arbre 4-aire (« QuadTree ») pour stocker des points appartenant à un repère orthonormé; le but est de détecter des collisions entre un disque en déplacement et des obstacles matérialisés par ces points.\\
  48. Le QuadTree étudié dans ce projet n'est pas extensible (les bornes du plan donné à l'initialisation sont fixes et positives) et possède une taille de panier égale à 1, ce qui signifie qu'un seul objet peut être stocké par nœud terminal.\\
  49. Ce projet est l'occasion d'étudier plusieurs stratégies de stockage d'objets en mémoire et d'approfondir l'utilisation de la bibliothèque standard d'OCaml pour des usages graphiques.
  50. \end{abstract}
  51. \vspace{11mm}
  52. \begin{figure}[h]
  53. \centering
  54. \fbox{\includegraphics[scale=0.55]{q23.png}}
  55. \end{figure}
  56. \break
  57. \section*{Organisation du projet}
  58. Pour chaque section, les fonctions à écrire sont dans les fichiers \filename{partX.ml} et le code interactif (tel que les tests graphiques) dans les fichiers \filename{partX.test.ml}. Cette organisation permet d'importer le code des sections précédentes à l'aide de directives \mintinline{ocaml}{#use} sans provoquer des appels de fonction inattendus.
  59. \\
  60. Le rendu est donc constitué des fichiers suivants :
  61. \dirtree{%
  62. .1 /.
  63. .2 bonus.ml\DTcomment{Bonus}.
  64. .2 coord.ml\DTcomment{Partie 1}.
  65. .2 display.ml\DTcomment{Fourni par le sujet}.
  66. .2 part1.test.ml\DTcomment{Partie 1 - tests}.
  67. .2 part2.test.ml\DTcomment{Partie 2 - tests}.
  68. .2 part3.ml\DTcomment{Partie 3}.
  69. .2 part3.test.ml\DTcomment{Partie 3 - tests}.
  70. .2 part4.ml\DTcomment{Partie 4}.
  71. .2 part4.test.ml\DTcomment{Partie 4 - tests}.
  72. .2 part5.ml\DTcomment{Partie 5}.
  73. .2 part5.test.ml\DTcomment{Partie 5 - tests}.
  74. .2 quadtree.ml\DTcomment{Partie 2}.
  75. .2 rect.ml\DTcomment{Partie 1}.
  76. .2 report.pdf\DTcomment{Le présent rapport au format PDF}.
  77. .2 report.tex\DTcomment{Le présent rapport au format \LaTeX}.
  78. .2 simulation1.ml\DTcomment{Fourni par le sujet}.
  79. .2 simulation2.ml\DTcomment{Fourni par le sujet}.
  80. }
  81. \section{Échauffement sur les rectangles}
  82. \begin{description}
  83. \item[Question 1.] Voir \filename{rect.ml}.
  84. \item[Question 2.] Voir \filename{rect.ml}.
  85. \item[Question 3.] Voir \filename{rect.ml}.
  86. \item[Question 4.] Voir \filename{rect.ml}.
  87. \item[Question 5.] Voir \filename{rect.ml}.
  88. \item[Question 6.] Voir \filename{rect.ml}.
  89. \end{description}
  90. \section{La structure de données QuadTree}
  91. \begin{description}
  92. \item[Question 7.] Pour stocker une collection de points, on pourrait utiliser quatre grandes familles de structures de données :
  93. \begin{description}
  94. \item[Ensembles ou listes] On stocke les points les uns à la suite des autres dans une liste.\\
  95. Occupation mémoire : minimale ($n \times taille(n)$).\\
  96. Algorithmes d'accès : très peu efficaces (parcours de la liste - $\mathcal{O}(n)$).
  97. \item[Dictionnaires] On stocke les points dans un dictionnaire dont les clés sont les coordonnées des points.\\
  98. Occupation mémoire : modérée (on considère que pour éviter la plupart des collisions sur la fonction de hachage, il est nécessaire de d'utiliser un ensemble environ 5 fois plus grand que le nombre d'éléments à stocker -- $5 \times n \times taille(n)$).\\
  99. Algorithmes d'accès : très efficaces lorsque l'on connaît les coordonnées exactes du point (temps quasi-constant qui dépend de la fonction de hachage choisie et du nombre d'éléments possédant la même clé), peu efficaces dans les autres cas (recherche de tous les points contenus dans une restriction du plan initial par exemple) puisqu'il est nécessaire de parcourir tout le dictionnaire ($\mathcal{O}(n)$).
  100. \item[Matrices] On stocke un tableau à deux dimensions en mémoire, et on stocke le point à ses coordonnées dans le tableau.\\
  101. %Toutefois, cette structure de données peut se révéler inadaptée aux stockage de points aux coordonnées représentées par des nombres flottants, en raison de la façon dont ils sont représentés en mémoire.\\
  102. Occupation mémoire : très importante (de l'ordre de $((Abs_{max} - Abs_{min}) \times (Ord_{max} - Ord_{min})) \times taille(n)$).\\
  103. Algorithmes d'accès : très efficaces (temps quasi-constant qui dépend seulement du nombre d'éléments possédant la même clé).
  104. \item[Arbres n-aires] Les arbres permettent de combiner une utilisation mémoire modérée et une recherche efficace. L'emploi du QuadTree, arbre 4-aire, est particulèrement justifié pour travailler avec des points 2D, puisqu'il découpe si nécessaire le plan en rectangles successifs et que tout point est logiquement contenu dans un rectangle. Ainsi, la recherche de tous les points contenus dans une restriction du plan initial est très rapide.\\
  105. Occupation mémoire : modérée ($\leq 4 \times n \times taille(n)$).\\
  106. Algorithmes d'accès : efficaces ($\mathcal{O}(\log{}n)$).
  107. \end{description}
  108. \item[Question 8.] Voir \filename{quadtree.ml}.
  109. \item[Question 9.] Voir \filename{quadtree.ml}.
  110. \item[Question 10.] Voir \filename{quadtree.ml}.
  111. \item[Question 11.] Voir \filename{quadtree.ml}.
  112. \item[Question 12.] Voir \filename{quadtree.ml}.
  113. \item[Question 13.] Voir \filename{quadtree.ml}.\\
  114. Intuitivement, on pourrait être tenté d'utiliser \funname{list_of_quadtree}, puis de supprimer l'élément choisi dans la liste, puis de faire appel à \funname{quadtree_of_list} pour reconstruire un QuadTree à partir de cette nouvelle liste; la fonction \funname{list_remove} implémente cette méthode.\\
  115. Pour éviter l'opération en $\mathcal{O}(n)$ qui consiste à reconstruire le QuadTree après avoir supprimé un objet dans la liste, on peut écrire une fonction \funname{clean_qt} qui devrait permettre d'avoir une simplification plus performante du QuadTree que si l'on utilisait la méthode décrite plus haut. Malgré de nombreux tests, nous n'avons pas trouvé de cas dans lesquels cette fonction produirait des résultats incorrects.
  116. \end{description}
  117. \section{Représentation graphique d'un QuadTree et tests}
  118. \begin{description}
  119. \item[Question 14.] Fonctions de \filename{display.ml} :
  120. \begin{description}
  121. \item[\funname{draw_data}] Dessine une donnée stockée dans une feuille \code{Leaf of coord * 'a} d'un QuadTree. La fonction de conversion de \code{'a} vers \code{String} ainsi que la couleur de dessin doivent être passées en paramètres.
  122. \item[\funname{draw_quadtree}] Dessine récursivement un QuadTree. Commence par dessiner en bleu le rectangle dans lequel est contenu le QuadTree, puis, en fonction de la nature de l'élement \code{cell} :
  123. \begin{itemize}
  124. \item ne fait rien si l'élément est \code{Empty};
  125. \item fait appel à \funname{draw_data} si l'élément est \code{Leaf};
  126. \item s'appelle récursivement pour chaque sous-QuadTree si l'élément est \code{Node}.
  127. \end{itemize}
  128. \item[\funname{wait_and_quit}] Attend un appui sur une touche du clavier puis ferme la fenêtre de dessin.
  129. \item[\funname{init}] Initialise un environnement de dessin en fonction de la taille du rectangle passé en paramètre et ouvre la fenêtre. Retourne un triplet de \code{Float} nommé \code{dparams} dans le reste du projet et utilisé par toutes les fonctions de dessin.
  130. \item[\funname{simple_test}] Appelle la fonction \funname{draw_quadtree} à l'aide du triplet \code{dparams} (obtenu par un précédent appel à la fonction \funname{init}) et d'une fonction de conversion vers le type \code{String} pour dessiner le QuadTree passé en paramètre.
  131. \end{description}
  132. \item[Question 15.] Voir \filename{part3.ml}.\\
  133. La fonction \funname{new_simple_test} prend en paramètre deux coordonnées \code{c} et \code{c'} et un entier \code{n}. Elle insère dans un QuadTree vide délimité par le rectangle formé par \code{c} et \code{c'} \code{n} objets dont les coordonnées sont obtenues aléatoirement à l'aide du module \code{Random}. Elle affiche le QuadTree ainsi complété, puis lors de l'appui sur une touche, le vide et l'affiche de nouveau. De cette façon, on peut vérifier que tous les objets sont bien supprimés.\\
  134. Un appel à cette fonction avec l'insertion d'une centaine d'objets est disponible dans le fichier \filename{part3.test.ml}.
  135. \item[Question 16.] Voir \filename{part3.ml}.\\
  136. En utilisant \code{rect_length} et \code{rect_height}, dans la fonction \funname{bad_draw_quadtree}, on observe que certains segments délimitant les bordures du QuadTree sont plus épais que d'autres (voir Fig.~\ref{q16goodquadtree} et \ref{q16badquadtree}). Le problème peut être lié à plusieurs conversions de nombres flottants en entiers :
  137. \begin{itemize}
  138. \item Lorsque l'on utilise la fonction \funname{draw_quadtree}, la conversion de nombre flottant en nombre entier a lieu une fois que le calcul sur les composantes flottantes \code{sx} / \code{sy}, \code{rect_left r} / \code{rect_right r} / \code{rect_top r} / \code{rect_bottom r} et \code{z} est terminé; on a donc un seul arrondi.
  139. \item Lorsque l'on utilise la fonction \funname{bad_draw_quadtree}, on ajoute le résultat arrondi en entier du calcul sur les deux composantes flottantes \code{z} et \code{rect_length r} / \code{rect_height r} à la composante entière déjà arrondie \code{x1} ou \code{x2}; on fait alors deux arrondis, qui peuvent provoquer le dessin de traits non superposés lorsque l'on dessine plusieurs fois le même QuadTree.
  140. Ces traits proches mais non superposés apparaissent dans la fenêtre graphique comme des traits plus épais.
  141. \end{itemize}
  142. \begin{figure}[!h]
  143. \centering
  144. \fbox{\includegraphics[scale=0.6]{q16goodquadtree.png}}
  145. \caption{\label{q16goodquadtree} Un exemple de dessin d'un QuadTree \code{q} en utilisant la fonction \funname{simple_test} fournie par le sujet.}
  146. \end{figure}
  147. \begin{figure}[!h]
  148. \centering
  149. \fbox{\includegraphics[scale=0.6]{q16badquadtree.png}}
  150. \caption{\label{q16badquadtree} Un exemple de dessin du même QuadTree \code{q} que dans la Fig.~\ref{q16goodquadtree}, en utilisant cette fois la fonction buggée \funname{bad_simple_test}.}
  151. \end{figure}
  152. \clearpage
  153. \end{description}
  154. \section{Placement du disque}
  155. \begin{description}
  156. \item[Question 17.] Voir \filename{part4.ml}.
  157. \item[Question 18.] Voir \filename{part4.ml}.
  158. \item[Question 19.] Voir \filename{part4.ml}.
  159. \item[Question 20.] Fonctions de \filename{simulation1.ml} :
  160. \begin{description}
  161. \item[\funname{get_point}] Retourne les coordonnées du point sur lequel se trouve le pointeur de la souris lors du déclenchement du clic.
  162. \item[\funname{get_disk}] Retourne les coordonnées du centre et la longueur du rayon du cercle désigné par une action « clic - glisser » (début du clic - déplacement du pointeur - relâchement du pointeur).
  163. \item[\funname{draw_disk}] Dessine à disque d'une couleur spécifiée à des coordonnées spécifiées, plein ou non.
  164. \item[\funname{draw_disk_with_collisions}] Dessine un disque :
  165. \begin{itemize}
  166. \item de couleur jaune s'il recouvre des points du QuadTree (obtenus grâce à \funname{collision_disk} de \filename{part4.ml}), et fait appel à \funname{draw_data} de \filename{display.ml} pour dessiner ces points en rouge le cas échéant;
  167. \item de couleur verte sinon.
  168. \end{itemize}
  169. \item[\funname{simulation_placement}] Fait appel aux fonctions \funname{init} et \funname{draw_quadtree} de \\ \filename{display.ml} et aux fonctions \funname{get_disk} et \funname{draw_disk_with_collisions} pour dessiner un cercle défini à la souris par l'utilisateur et ses éventuelles collisions avec les points du QuadTree.
  170. \end{description}
  171. \end{description}
  172. \section{Déplacement du disque et détection de collision}
  173. \begin{description}
  174. \item[Question 21.] Voir \filename{part5.ml}.
  175. \item[Question 22.] Voir \filename{part5.ml}.
  176. \item[Question 23.] Voir \filename{part5.test.ml}.\\
  177. Fonctions de \filename{simulation2.ml} :
  178. \begin{description}
  179. \item[\funname{draw_trail_with_collisions}] Dessine la zone survolée pendant le cercle pendant son déplacement depuis son point de départ vers son point d'arrivée. Fait appel à \funname{collision_trail} pour obtenir une liste tous les points survolés. Redessine ensuite tous ces points en cyan.
  180. \item[\funname{simulation_move}] Idem que \funname{simulation_placement} de \filename{simulation1.ml}, sauf \\ qu'après avoir défini un cercle, un second clic de souris utilise la fonction \funname{draw_trail_with_collisions} pour déplacer le cercle vers cette seconde position. Un exemple de fonctionnement de cette fonction est disponible plus bas (voir Fig.~\ref{q23}).
  181. \end{description}
  182. Dans \filename{part5.ml}, on trouvera également les fonctions \funname{get_new_destination} et \\ \funname{new_simulation_move} qui implémentent le bonus de la question. Une illustration du fonctionnement de ces fonctions est disponible plus bas (voir Fig.~\ref{q23bonus}).
  183. \begin{figure}[h]
  184. \centering
  185. \fbox{\includegraphics[scale=0.6]{q23.png}}
  186. \caption{\label{q23} Illustration du fonctionnement de la fonction \funname{simulation_move}.}
  187. \end{figure}
  188. \begin{figure}[h]
  189. \centering
  190. \fbox{\includegraphics[scale=0.6]{q23bonus.png}}
  191. \caption{\label{q23bonus} Illustration du fonctionnement de la fonction bonus \funname{new_simulation_move}.}
  192. \end{figure}
  193. \clearpage
  194. \end{description}
  195. \section*{Bonus}
  196. A l'origine écrite pour débugger \funname{clip}, la fonction \funname{graphical_clip} du fichier \filename{bonus.ml} doit permettre de réaliser de façon graphique une restriction du plan, comme suggéré dans la Fig.~2 du sujet. Elle prend en paramètre un QuadTree et une fonction d'affichage des données du QuadTree; cependant, bien qu'elle semble produire un QuadTree correct, il est impossible de l'afficher correctement.
  197. \section*{Conclusion}
  198. L'arbre 4-aire (« QuadTree ») possède des propriétés très intéressantes pour le stockage de données géographiques dans un plan. D'une part, les algorithmes d'accès à une donnée en particulier sont raisonnablement rapides ($\mathcal{O}(\log{}n)$); d'autre part, l'empreinte mémoire est faible en comparaison avec d'autres structures de données de performance comparable. Les QuadTrees permettent également de restreindre assez facilement l'espace de recherche à une sous-partie du plan initial (voir la fonction \funname{clip} dans la partie 4), et la visualisation de leur contenu pour le débuggage est assez intuitive.
  199. \\
  200. Dans ce projet, nous avons vu un cas d'utilisation typique des QuadTrees : la détection de collisions. Les algorithmes développés plus haut sont couramment utilisés dans le monde des jeux vidéos par exemple puisqu'ils permettent de ne tester la collision de l'objet en mouvement qu'avec une partie des points du plan du plan complet, ce qui réduit considérablement les calculs.
  201. \\
  202. Il est également possible de généraliser cette structure de données pour gérer des objets en trois dimensions dans l'espace, en utilisant des arbres 8-aires (« OcTrees »).
  203. \end{document}