Courbes de couverture de l'espace (SPACE-FILLING CURVE)


Une idée pour améliorer la performance des méthodes de tramage est d'utiliser une courbe de recouvrement de l'espace (space-filling curves) au lieu de faire un balayage de type vidéo. En 1890 Peano a découvert une courbe continue qui traverse chaque point d'une place fermée. C'était un des premiers exemples de ce qui s'appelle maintenant des courbes de couverture de l'espace. En général, une courbe continue qui traverse chaque point d'une cellule fermée s'appelle une courbe remplissante de l'espace. Une année après, Hilbert publia la description d'une autre courbe, connue comme courbe de Hilbert qui est l'exemple le plus simple graphiquement.

Il y a plusieurs courbes en plus de celles de Peano et Hilbert, comme les courbes de E.H. Moore, de Lebesgue, de Osgood, de Sierpinski-Knopp.
 
 
 
 


 
 

Référence des images: [7].
 
 

La figure suivante montre à Lena après avoir appliqué un dithering de Floyd & Steinberg avec un balayage vidéo et un balayage serpentine.
 
 




 





Néanmoins, ces courbes présentent quelques inconvénients:

Pour résoudre ces problèmes on peut utiliser une courbe de couverture de l'espace aléatoire, qui peut être utilisée même avec des treillis irréguliers. Ces courbes changent sa direction fréquemment, donc elles contiennent à peine des longs gaps. [7]