
\def\Th{\mathcal{T}_{h}}
\def\Sh{\mathcal{S}_{h}}
\section{Sujet: Recherche rapide d'un triangle contenant un point dans un maillage}

Un maillage conforme formé d'un ensemble de $n_{T}$ triangles $\Th$ telle
que l'intersection de 2 triangles distincts soit une arête commune, un sommet commun ou
rien, où les l'ensemble des $n_{S}$ sommets de $\Th$ est noté $\Sh$.

\begin{figure}[hbt]
%    \centerline{\includegraphics[height=7cm,bb=64 135 379 393]{squareb}}
    \centerline{\includegraphics[height=5cm]{cercle}}
    \caption{ exemple de maillage}
\end{figure}

\bigskip

Le but est d'écrire un algorithme de recherche d'un triangle $K$ dans un 
maillage  convexe $\Th$
contenant un point $(x,y)$ en $O(log_{2}(n_{T}))$.




\subsection{Projet 1 (promenade) }

\begin{Algo}  \label{algo rr}

  Partant du  triangle $K$,
  
   Pour les 3 arêtes $(a_{i},b_{i}), i=0,1,2$ du triangle $K$, tournant dans le
   sens trigonométrique, calculer l'aire des 3 triangles $(a_{i},b_{i},p)$. Si les
   trois aires sont positives alors $p \in K$ (stop), sinon nous choisirons
   comme nouveau triangle $K$ l'un des triangles adjacents à l'une des arête
   associée à une aire négative (les ambiguïtés sont levées aléatoirement).
\end{Algo}


 
\begin{enumerate}
   \item Construire une classe maillage formée d'un tableau de sommets et d'un tableau
   de triangles, qui lit le fichier maillage. 

   \item Construire  une méthode dans la classe maillage  donnant le  triangle $K'$  adjacent 
 d'un triangle $K$ opposé à son sommet $i \in \{ 0,1,2 \}$. La complexité de cette
fonction doit être constante après bien sur une unique initialisation en $O(n_{T})$ ou 
 $O(n_{T}log_2(n_{T}))$.

    Pour cela vous pourrez utiliser le chapitre chaîne et chaînage.

  \item Programmez  l'algorithme \ref{algo rr} en partant d'un triangle quelconque
(ajoutez une nouvelle méthode de la classe maillage).

  \item Puis trouver pour chaque sommet d'un autre maillage donné du même domaine,
  le triangle le contenant. Afin de briser la complexité
  algorithmique, il faut utiliser l'assertion suivante:  les sommets d'un triangle sont proche
  car les triangles sont petits.
  \end{enumerate}
 \subsection{Projet 2}
 
 Programmation d'une méthode pour trouver, rapidement un triangle 
 proche d'un point donné en $O(log(n))$
 
 Pour cela nous utiliserons,
un arbre quaternaire pour stocker les sommets dans maillages  comme suit:

\begin{Algo}  

  Soit $B_0$ une boite carre contenant tous les points du maillage.
  On applique la procédure récursive suivante à $B_0$.
  
  Soit $B_\alpha$ la boite indexée par $\alpha$ qui est une chaîne de $0$,$1$,$2$ ou $3$ (exemple $\alpha=011231$) 
  la longueur de la chaîne est note $l(\alpha)$.

  procedure appliqué à la boite $B_\alpha$: 
  \begin{itemize}
  \item la boite $B_\alpha$ contient moins de 5 points, on les stockes dans la boite et on a fini,
   \item sinon on découpe la boite $B_\alpha$ en 4 sous boites égale noté $B_{\alpha0},B_{\alpha1},B_{\alpha2}, B_{\alpha3}$ (on stocke les 4 pointeurs 
   vers ces boites dans la boite), et on applique la procédure 
   au 4 nouvelles boites. 
 \end{itemize}
\end{Algo}

Remarque: pour simplifier la programmation de l'arbre quaternaire, on peut construire
une application qui transforme le point de $\R^2$ en points  à coordonnées entières
en construisant une application affine $A$ qui transforme par exemple $B_{0}$ en $ [0,2^{31}[^2$. Dans ce cas, les coordonnées entières permettent de limiter la profondeur
de l'arbre à $32$ niveaux, et d'utiliser les opérateurs entiers en nombre binaire du $C$ comme 
\verb. & , | , ^ ..  

Quelque remarque:
\begin{itemize}
\item décomposition binaire, soit $i$ un nombre entier il peut s'écrire comme
$\sum b^i_k 2^k$, avec $b^i_k\in\{0,1\}$ et $b^i_k$ est appelé le $k$ ieme  bit de $i$.
\item \verb!( 1 << n) !  est égal à $2^n$  pour $n = 0,..., 31$
\item \verb!( i & ( 1 << n))! est vrai  si le $n$  ieme   bit de $i$ est égal à $1$ pour $n=0,...,31$
\item \verb!(( i >> n) & 1)!  est  égal à $b^i_n$ le n ieme bit de $i$. 
\item  La numérotation du découpage en   $4$ boites  d'un niveau $k$ sera numéroté  par $N_d$:
$$(b_i,b_j) \in \{0,1\} ^2 \mapsto \{0,1,2,3\} : \qquad N_d(b_i,b_j)= b_i + 2  b_j .$$
\item   La boite $b_\alpha$ (si elle existe) de niveau  $n$  contenant un point  de coordonnées $(x,y)$
 aura pour 
 $\alpha =  c_1...c_n$  avec   $c_k = N_d(b^i_{32-k},b^j_{32-k})$ pour $k=1,..,n$ où  les coordonnées entières  associées sont  $(i,j)=A(x,y)$   et où
 $b^i_{32-k}$ (resp.  $b^j_{32-k}$) est le (32-k) ieme bit de $i$ (resp j).
\end{itemize}

 \bigskip
 L'algorithme est : 
\begin{enumerate}
   \item Construire une classe maillage formé d'un tableau de sommets et d'un tableau
   de triangle, qui lit le fichier maillage. 


   
    \item Construire l'arbre quaternaire contenant les barycentres des triangles du maillage.
   
    \item Trouver la boite non vide la plus petit  $B_{\alpha(p)}$ de l'arbre contenant un point $p$.
 
    \item  
     Nous choisirons comme triangle de départ  $K$ , l'un des triangles associées l'un 
     des barycentres de la boite $B_{\alpha(p)}$.
    
    
   \item Construire  une méthode dans la classe maillage  donnant le  triangle $K'$  adjacent 
 d'un triangle $K$ opposé à son sommet $i \in \{ 0,1,2 \}$. La complexité de cette
fonction doit être constante après bien sur une unique initialisation en $O(n_{T})$ ou 
 $O(n_{T}log_2(n_{T}))$.

    Pour cela vous pourrez utiliser le chapitre chaîne et chaînage.

  \item Programmez l'algorithme \ref{algo rr} en partant du  triangle $K_{s}$.
      
  \end{enumerate}
 

 
  
