Créer une liste de coordonnées à partir de formes

[Sephi-Chan]

L'image est bien bicolore et j'ai opacifié les pixels semi-transparents grâce à la commande :

Code :

convert shapes.png -background white -background white -channel A -threshold 75%  -alpha remove white.png

En revanche je ne comprends pas bien l'algorithme que tu décris.
Quelque questions pour être sûr de parler de la même chose :

• Pourquoi 121 sommets pour 100 pixels ?
  
• Qu'est-ce que tu entends (algorithmiquement parlant) par "lier" ?
  

Admettons qu'on prenne cette carte de 100*100 (désolé, j'étais pas très inspiré) :



En quoi consiste concrètement l'algo ?

[Xenos]

Il consiste à considérer les bords des pixels (carrés) au lieu des pixels eux-mêmes (généralement, on considère leur centre.
Un pixel n'est plus vu comme un point avec une couleur (comme c'est le cas avec les textures 3D par exemple) mais comme un aplat de couleur carré dont les bords constituent la frontière.
Je je prends cette image, l'algo considère la moitié de gauche (sans filtrage 3D donc) et non la partie de droite (filtrage, aka gradient progessif entre deux pixels).

Du coup, on a une grille constitué des bords des pixels. Chaque segment (bord de pixel) touche 2 pixels, donc il est facile de savoir si ce segment est une frontière ou non (on compare la couleur des deux pixels). On a donc, pour chaque segment de la grille, un boolean indiquant si ce segment est une frontière. On vire les segments non-frontaliers, et on a le contour des objets (à simplifier par le JS précédent).

Pour une image 10x10, on a donc une grille de 10x10 carrés en 10 colonnes et 10 lignes, donc 11 colonnes de bords (x10 segments par colonne) et 11 lignes de bords (x10 segments par ligne), soient 110+110 segments (220).

Autre exemple plus simple, pour une image de 3x3 pixels (9 carrés donc), on a 4x4=16 sommets et 4x3+4x3=24 segments, et ce sont eux que l'on considère pour calculer le contour des objets (plutôt que de considérer le centre des pixels).

Dans le cas d'exemple de 100x100, l'algo créerait donc une grille de 101x101 sommets (qui englobe l'image), et construirait les 101x100+101x100=20200 segments entre ces sommets pour créer la grille, puis l'algo ne garderait que les segments qui constituent une frontière entre deux pixels de couleur différente (en pratique, mieux vaut construire la grille de 101x101 sommets, puis pour chaque sommet, ne construire que les segments qui sont une frontière entre deux pixels de couleur différente; c'est nettement moins lourd en mémoire que de construire toute la grille pour ensuite supprimer les segments qui ne sont pas des frontières entre pixels de couleur différente).

[Thêta Tau Tau]

Ce que je ferrais :
-détection des bords (on ne garde que les points noirs en contact avec du blanc).
-"classement" des points, de façon à avoir un chemin.
-simplification du chemin (en fouillant un peu sur wikipédia je suis tombé sur ça , et il y a d'autres algos listés à la fin de l'article).

Il y a surement moyen de faire mieux avec des courbes de Bézier ou autre mais ça risque d'être plus compliqué.

[Xenos]

Theta Tau Tau, c'est exactement la démarche que l'on applique
• Détection des bords → Construction de la grille des bords des pixels qui sont de 2 couleurs différentes
• Classement des points → Parcours de la grille
• Simplification → Simplify.js

[Thêta Tau Tau]

Ok j'ai lu en diagonale et pas compris ça, désolé.