Création d'ensembles d'éléments similaires dans un tableau 2D

Dans votre situation, je vous fierais au moins sur deux tableaux différents:

private bool isSurroundingPoint(Point point1, Point point2)
{
    bool isSurrounding = false;
    if (point1.X == point2.X || point1.X == point2.X + 1 || point1.X == point2.X - 1)
    {
        if (point1.Y == point2.Y || point1.Y == point2.Y + 1 || point1.Y == point2.Y - 1)
        {
            isSurrounding = true;
        }
    }
    return isSurrounding;
}

[modifier le 5/8/2013: complexité du temps fixe. (O (A (n)) est essentiellement une période constante!)]

Dans ce qui suit, par "composant connecté", je veux dire l'ensemble de toutes les positions accessibles par un chemin qui ne permet que des déplacements horizontaux, verticaux ou diagonaux entre les positions voisines ayant le même type d'élément. Par exemple. Votre exemple {(0,1), (1,1), (2,2), (2,3), (1,4)} est un composant connecté dans votre exemple d'entrée. Chaque position appartient exactement à un composant connecté.

Nous construirons un Structure de données Union / Recherche qui sera utilisée pour donner chaque Position (x, Y) une "étiquette" numérique ayant la propriété que si et seulement si deux positions (x, y) et (x, y ') appartiennent au même composant alors ils ont la même étiquette. En particulier, cette structure de données prend en charge trois opérations:

• SET (x, y, i) définira l'étiquette de position (x, y) vers i.
• Recherche (x, y) retournera l'étiquette attribuée à la position (x, y).
• Union (z) , pour certains étiquettes Z, combinera toutes les étiquettes de Z dans une seule étiquette K, dans le sens des appels futurs vers Rechercher (x, Y) sur n'importe quelle position (x, y) qui avait précédemment eu une étiquette dans Z renverra maintenant k. (En général, K sera l'une des étiquettes déjà dans Z, bien que cela ne soit pas vraiment important.) Union (z) renvoie également la nouvelle étiquette "maître", k.

  S'il y a n = la largeur * Positions de hauteur au total, cela peut être effectué dans O (N * A (N)), où A () est la fonction d'Ackermann inverse extrêmement lente. pour toutes les tailles d'entrée pratiques, c'est la même chose que O (n).

  Notez que chaque fois que deux sommets sont adjacents les uns aux autres, il y a quatre cas possibles:

  1. L'un est au-dessus de l'autre (relié par un bord vertical)
  2. l'un est à gauche de l'autre (relié par un bord horizontal)
  3. L'un est au-dessus et à gauche de l'autre (connecté par un \ bord diagonal)
  4. L'un est au-dessus et à droite de l'autre (connecté par un / bord diagonal)

     Nous pouvons utiliser la passe suivante pour déterminer les étiquettes pour chaque position (x, y):

     • Ensemble NextLabel à 0.
     • pour chaque rangée y dans l'ordre croissant:
       • pour chaque colonne x dans l'ordre croissant:
         • examinez les voisins W, NW, N et NE de (x, y). Soit Z le sous-ensemble de ces 4 voisins qui sont de même nature que (x, y).
         • Si z est l'ensemble vide, nous supposons que nous supposons provisoirement que (x, y) démarre un nouveau composant, donc appelé (X, Y, NextLabel) et Incrément NextLabel.
         • Sinon, appelez (z [i]) sur chaque élément de Z pour trouver leurs étiquettes et appelez Union () sur cet ensemble d'étiquettes pour les combiner ensemble. Attribuez la nouvelle étiquette (le résultat de cet appel de l'Union ()) à K, puis d'appeler également défini (x, y, k) pour ajouter (x, y) à ce composant.

           Après cela, appeler trouver (x, y) sur n'importe quelle position (x, y) vous indique efficacement quel composant il appartient. Si vous souhaitez être capable de répondre rapidement à des requêtes du formulaire "Quels positions appartiennent au composant connecté contenant position (x, y)?" Ensuite, créez une haquetable de listes postincomp et créez une deuxième passe sur le tableau d'entrée, ajoute chacun (x, y) à la liste postincomp [Rechercher (x, y)] . Cela peut tous être fait en temps et à l'espace linéaire. Maintenant, pour répondre à une requête pour une position donnée (x, y), appelez simplement lab = rechercher (x, y) pour trouver l'étiquette de cette position, puis répertoriez les positions dans Posincomp [Lab ] .

           Pour faire face à des composants "trop ​​petits", il suffit de regarder la taille de postincomp [laboratoire] . Si c'est 1 ou 2, alors (x, y) n'appartient à aucun composant "assez gros".

           Enfin, tout ce travail prend effectivement du temps linéaire, il sera donc rapide que votre matrice d'entrée soit énorme. Il est donc parfaitement raisonnable de la recomposer à partir de zéro après la modification du tableau d'entrée.