Considérons un point (x,y) du carré unité. On divise le carré en 4 petits carrés égaux et on teste dans lequel est le point (x,y). S'il est dans celui de gauche en bas on assigne au point le couple (0,0), s'il est en haut à droite on assigne (1,1), s'il est en haut à gauche (0,1) et sinon (1,0). On redivise le petit carré en 4 et on fait la même opération. On obtient ainsi 2 couples de nombres binaires associés au point et on les concatènent. Si le point est en haut à droite dans la première division et en haut à gauche dans la deuxième il aura alors l'étiquette (10,11). Et ainsi de suite jusqu'a ce qu'on arrive à la précision maximal des entiers. On a construit ce qu'on appelle un arbre quaternaire (quadtree), produit de 2 arbres binaires.
Supposons qu'on ait un triangle (q0,q1,q2) dans le carré unité et qu'on veuille savoir si un point q apartient au triangle. On peut dégrossir fortement le problème en utilisant un représentation des points par quadtree. On cherche le carre quadtree qui contient les 3 sommets. Pour cela il suffit de comparer bit à bit la repréntation quadtree des points et de garder la partie commune. On cherche enfin si q est dans ce carré. S'il ne l'est pas q ne peut être dans le triangle. Pour savoir si le point est dans ce carré il suffit de vérifier que le début de sa représentation quadtree est bien celle du carré.
Dans le cas général, il faut donc changer les échelles pour se ramener au cas du carré unité. On aura aussi intérêt à convertir toutes les coordonnées en cordonnées entières (par changement d'échelle) de mainière à supprimer les indécisions dues à la limite de précision des représentations flottantes.
Inversement, si la question est dans l'autre sens: soit un point q dans un domaine triangulé, dans quel triangle est t'il? avec le quadtree, on va trouver tres rapidement une cellule, l'un des sommets du maillage le proche du point q, puis après on se promene par adjacence dans le maillage comme suit: calcule des 3 aires signées dans une triangles t de sommet s1,s2,s3:
a12=aire (s1,s2,q) arête 12,
a13=aire (s1,q,s3) arête 13,
a23=aire (q,s2,s3) arête 23,
si les 3 aires sont positives on a gagné. si l'une est négative on prend le triangle adjacent à l'arête si 2 sont négatives on prend le triangle adjacent al'arête au hasard qui a une aire négative ; si les 3 sont négatives alors bug.