Définition : une image 2d est représentée par une grille d'affichage I(x,y) telle que I(x,y) définit la couleur d'un pixel de coordonnées (x,y) avec x,y \in \mathbb{N}, 0\leq x \leq x_{max},0\leq y \leq y_{max}

pixel(x,y) = centre du carré de coté égal à l'unité.

Soit p\left(x,y\right)\in\mathbb{Z}^2 un point entier ou pixel

Les quatre points N,S,E,O/W sont dits 4-voisins de p. On rajoute NE, NW, SE, et SW pour avoir les huit points dits 8-voisins de p.

• Avec le maillage triangulaire (triangles équilatéraux) les pavés ont des 3-voisins (ceux avec lesquels sont partagés des côtés ou bords) et des 12-voisins avec le rajout des neuf autres qui partagent juste un sommet (trois par sommet).
• Avec le maillage hexagonal (seul autre pavage du plan avec une figure régulière) il n'y a que des 6-voisins : les six qui partagent un coté sont aussi les seuls voisins aux sommets.
• En 3-d on trouve les 6-voisins (comme les 4-voisins de 2-d: \left(x\pm 1,y,z\right), \left(x,y\pm 1, z\right), \left(x,y,z\pm 1\right) ), des 26-voisins (toutes les cellules partageant au moins un sommet avec p), mais aussi des 18-voisins, qui partagent un côté avec p. On peu aussi concevoir les 18-voisins comme l'ensemble des 26-voisins moins les 8 “coins” ou voisins purement diagonaux, ou encore \left\{ \left(x\pm 1,y,z\right), \left(x,y\pm 1, z\right), \left(x,y,z\pm 1\right)\right\}\cup \left\{\left(x\pm 1,y \pm 1, z\right), \left(x,y\pm 1, z \pm 1\right), \left(x \pm 1,y,z\pm 1\right)\right\} )

La relation de 4-voisinage (resp. 8-voisinage) est symétrique.

La relation de 4-voisinage (resp. 8-voisinage) définit un graphe dit de 4-connectivité (resp. 8-connectivité).

Soit un ensemble Z de points entiers dit une zone ou une région. Elle est 4-connexe (8-connexe) si le graphe correspondant de la 4-connectivité (8-connectivité) est connexe.

Une composante connexe d'une région Z pour la 4-connexité (8-connexité) est une partie maximale 4-connexe (8-connexe).

Soient P,Q \in \mathbb{Z}^2 des pixels. Un chemin 4-connexe (8-connexe) de P à Q est une suite P_0, P_1, \ldots P_n telle que P_0 = P, P_n = Q, P_i\in V_4\left(P_{i+1}\right) \left[P_i\in V_8\left(P_{i+1} \right)\right]\;\forall i=0,\ldots ,n-1

Une région Z est 4-connexe (8-connexe) \Leftrightarrow \; \forall P,Q\in Z \; : \exists un chemin 4-connexe (8-connexe) de P à Q dans Z.

Algorithmes de tracé de segments de droites – Connexité (suite)