Comment vérifier si les points d’une grid sont connectés verticalement / horizontalement? (1 loin les uns des autres)

Utilisons simplement 1 car il y a un point et 0 si rien.

Par exemple, la grid:

0 0 0 0 0

1 1 1 1 1

0 0 0 0 0

1 1 1 1 1

ne seraient pas connectés ensemble, alors que

0 0 1 0 0

0 1 1 0 0

0 0 1 1 0

0 0 0 1 1

est.

J’ai le sentiment qu’utiliser quelque chose comme BFS serait terriblement inefficace pour quelque chose qui devrait probablement être assez simple; y a-t-il une autre option?

La meilleure complexité asymptotique pour ce type de problème provient de l’algorithme de recherche d’union utilisant la compression de rang et de chemin.

Union find associe chaque nouveau point à un nom de groupe unique, issu du voisin de gauche ou du sumt supérieur, ou unifie les groupes (en établissant un lien entre les groupes).

En fin de compte, tous les parents de tous les groupes initialement uniques pointent vers le même élément, auquel cas l’ensemble est connecté.

Lectures supplémentaires avec le code source c ++

Lectures complémentaires pour le traitement d’images

#include "catch.hpp" #include  template  T parent(std::vector &links, T item) { if (item == 0) return item; while (links[(size_t)item - 1] != item) item = links[(size_t)item - 1]; // Should implement path compression return item; } template  bool is_connected(T(&array)[N][M]) { // Assumption is that the type T is large enough to hold N*M/2 distinct ensortinges // Thus we can use/modify the array itself to record (roots) of distinct labels // Of course we could copy the array into a vector of type size_t std::vector parents; for (auto j = 0; j < N; j++) { for (auto i = 0; i < M; i++) { T &current = array[j][i]; if (!current) continue; T left = i ? parent(parents, array[j][i - 1]) : 0; T above = j ? parent(parents, array[j - 1][i]) : 0; if (left == 0) { if (above) current = above; else parents.emplace_back(current = (T)(parents.size() + 1)); } else { // Todo: implement rank based selection of joining the sets current = left; if (above != 0 && above != left) parents[(size_t)above - 1] = left; } } } // Check that all intermediate disjoint sets have now a single root if (parents.size() == 0) return false; // is empty set connected or not? auto last_item = parents.back(); auto root = parent(parents, last_item); parents.pop_back(); for (auto &group : parents) { if (root != parent(parents, group)) return false; } return true; } SCENARIO("Is connected") { int arr[4][4] = { { 1, 0, 1, 0 }, { 1, 0, 1, 0 }, { 1, 0, 1, 0 }, { 1, 1, 1, 1 } }; auto foo = is_connected(arr); CHECK(foo == true); arr[3][1] = 0; CHECK(is_connected(arr) == false); } 

BFS ou DFS est en effet la solution appropriée. Le rest consiste simplement à tirer parti des propriétés de la grid rectiligne (raster) pour mettre en œuvre de tels algorithmes de recherche de manière plus efficace, de préférence plus efficace qu’une implémentation “simple”. Par exemple, certains algorithmes classiques d’ inondation de lignes de balayage masortingcielles à 4 voies constituent une bonne approche pour rechercher des composants connectés dans votre grid (voir la section «Remplissage de lignes de balayage »).