Coloriage automatique d'images

Chaque zone blanche fermée d'une image noir et blanc reçoit sa propre couleur. Le programme C d'origine tourne ici dans votre navigateur, compilé en WebAssembly.

Comment ça marche : Union-Find

Chaque pixel blanc forme d'abord un ensemble à lui seul (MakeSet). On parcourt ensuite l'image : deux pixels blancs voisins sont fusionnés (Union). À la fin, tous les pixels d'une même zone ont le même représentant (FindSet), dont ils prennent la couleur.

Listes chaînées

Chaque élément pointe vers la tête de sa liste, qui est le représentant : FindSet est en O(1). Union rattache la plus petite liste à la plus grande et met à jour ses représentants, soit O(n log n) au total.

Arbres

Chaque nœud pointe vers son parent et la racine est le représentant : FindSet remonte jusqu'à elle. L'union par rang garde les arbres peu profonds : O(log n) par opération.

1. Image

Génération aléatoire

2. Structure

Entrée
Résultat