Détection d'angle et de bord dans un graphique

Question

Je suis actuellement en train d'essayer de programmer un système de détection de coin et de bord qui devrait être capable de détecter les coins et les arêtes dans un graphique.

La structure de données de graphe est construite à partir d'un tableau de caractères 2d qui pourrait ressembler à ceci: La taille de cet exemple est de 10 lignes et de 9 colonnes. (Espaces blancs à remplir le reste des disparus, je ne pouvais pas ajouter des espaces aux frontières ...?)

 ... 
..Y..... 
..Y . 
    ZYZ.Z.Z 
    .Y .... 
    .M 
    .. 

Un nœud est créé pour chaque caractère dans le noeud et le graphe complet est stocké en tant que vector<Node> graph.

Chaque noeud est défini comme tel

struct Node 
{ 
    char character; 
    pair<int,int> position; 
    bool lock; 
    vector<Vertex> adjacent; 
}; 

struct Vertex 
{ 
    Node *current; 
    Node *nextTo; 

}; 

donc .. J'ai nœuds de beaucoup, mais certains d'entre eux est redondant dans mon cas d'utilisation, pour lequel chaque noeud a une bool lock => dire les systèmes que ceux-ci les nœuds devraient être ignorés.

Les nœuds que je veux ignorer sont ceux qui ont le caractère ., dans la carte et sont placés dans une position d'angle (le nœud lui-même a 2 voisin (le vecteur de taille == 2)), ou des nœuds avec caractère . qui est entre deux coins. Si un autre caractère apparaît entre deux coins, seuls les coins seront verrouillés. tout en traversant le nœud adjacent du coin (en recherchant le deuxième coin), et un nœud a 4 nœuds adjacents, seul le premier virage vu sera réglé pour être verrouillé.

Donc ... je l'ai écrit dans un code qui a fini par ressembler à ceci.

for(auto graph_it = begin(graph); graph_it != end(graph); graph_it++) 
    { 
     if(graph_it->adjacent.size() == 2 && graph_it->character == '.') 
     { 
      vector<Node*> trace; 
      cout << "corner found " <<"("<< graph_it->position.first <<","<< graph_it->position.second << ")" << endl; 
      graph_it->lock = true; 

      for (Vertex edge : graph_it->adjacent) 
      { 
       cout << "Check neighbour direction" << endl; 
       int changeX = 0; 
       int changeY = 0; 

       changeX = graph_it->position.first - edge.nextTo->position.first; 
       changeY = graph_it->position.second - edge.nextTo->position.second; 

       cout << "neighbour direction is first: " << changeX << changeY << endl; 
       auto start_position = edge.nextTo; 
       vector<Node*> trace; 
       bool endIsCorner = false; 
       bool conditionMet = false; 
       cout << endl; 
       while((start_position->adjacent.size() != 2|| start_position->adjacent.size() != 4) /*&& start_position->character =='.'*/) 
       { 
        for(Vertex traversing_edge : start_position->adjacent) 
        { 
         cout <<"position before: " << graph_it->position.first << graph_it->position.second << " now position: "<< start_position->position.first << start_position->position.second << " change is: " << (start_position->position.first - traversing_edge.nextTo->position.first) << " " << start_position->position.second - traversing_edge.nextTo->position.second << " character is: " << traversing_edge.nextTo->character << endl; 
         if (traversing_edge.nextTo->adjacent.size() == 2) 
         { 
          cout << "error found case 1" << endl; 
          cout << "position: " << traversing_edge.nextTo->character << traversing_edge.nextTo->position.first << traversing_edge.nextTo->position.second << endl; 
          start_position = traversing_edge.nextTo; 
          start_position->lock =true; 
          trace.push_back(start_position); 
          endIsCorner = true; 
          conditionMet = true; 
          break; 
         } 
         else if(traversing_edge.nextTo->adjacent.size() == 4) 
         { 
          cout << "error found case 2" << endl; 
          cout << "position: " << traversing_edge.nextTo->character << traversing_edge.nextTo->position.first << traversing_edge.nextTo->position.second << endl; 
          conditionMet = true; 
          break; 
         } 

         if (start_position->position.first - traversing_edge.nextTo->position.first == changeX && start_position->position.second - traversing_edge.nextTo->position.second == changeY) 
         { 
          if (traversing_edge.nextTo->adjacent.size() == 3) 
          { 
           start_position = traversing_edge.nextTo; 
           cout << "traversed to position: " << start_position->position.first << start_position->position.second <<" character: "<<start_position->character<< endl; 
           trace.push_back(start_position); 
          } 

          if (traversing_edge.nextTo->adjacent.size() == 2) 
          { 
           edge.nextTo->lock = true; 
           start_position = traversing_edge.nextTo; 
           cout << "traversed to position being corner: " << start_position->position.first << start_position->position.second <<" character: "<<start_position->character<< endl; 
           trace.push_back(start_position); 
           endIsCorner = true; 
          } 

          if (traversing_edge.nextTo->adjacent.size() == 4) 
          { 
           cout << "traversed something else: " << start_position->position.first << start_position->position.second <<" character: "<<start_position->character<< endl; 
           start_position = traversing_edge.nextTo; 
          } 
         } 
         cout << endl; 
        } 
        if (conditionMet) 
        { 
         break;/* code */ 
        } 

       } 
       if (endIsCorner == true) 
       { 
        for(auto traced: trace) 
        { 
         cout << "Traced for locking position: " <<traced->position.first << traced->position.second << traced->character<< endl; 
         if (traced->character == '.') 
         { 
          cout << "locking position: " <<traced->position.first << traced->position.second << traced->character<< endl; 
          traced->lock = true; 
         } 
        } 
       } 
       else 
       { 
        trace.empty(); 
        endIsCorner = false; 
       } 
       cout<<endl; 
      } 

     } 
     cout << endl; 
    } 

    cout << "Locks detected" << endl; 

Comme je l'ai réalisé le code n'a pas fait que je veux faire, j'ai commencé le déboguer ..

La première chose bizarre je l'ai vu est cela. Le premier nœud détecté en tant que coin est celui situé à la rangée 2 et à la colonne 1, ce qui est correct.

Ensuite, il essaie de traverser dans la direction de la première direction nextTo node qui est celle en dessous (ligne 3, col 2) qui est aussi un coin, mais en quelque sorte il entre en boucle? ce que je ne comprends pas. Sa taille de vecteur adjacente est 2, ce que le débogueur dit aussi, mais en quelque sorte dans la boucle while il détecte la taille étant 2, et sort de la boucle while correctement et lui fixe ce noeud à verrouiller .... (Problème possible) Alors que je finis tout cela, je vérifie le graphique complet pour voir si les choses qui devraient être verrouillées sont également verrouillées ... ce qui n'est pas le cas.

for(auto node : graph) 
{  
    cout << "node position: " <<"(" << node.position.first << "," << node.position.second << ")" << " " << node.character << endl; 
    if (node.locked) 
    { 
     cout << node.position.first << node.position.second << endl; 
    } 
} 

Pour que j'obtenir cette sortie

node position: (2,1) . 
21 
node position: (3,1) . 
31 
node position: (2,2) . 
node position: (3,2) . 
node position: (4,2) Z 
node position: (5,2) . 
52 
node position: (6,2) . 
node position: (7,2) . 
72 
node position: (2,3) Y 
node position: (3,3) Y 
node position: (4,3) Y 
node position: (5,3) Y 
node position: (6,3) M 
node position: (7,3) . 
73 
node position: (2,4) . 
24 
node position: (4,4) Z 
node position: (2,5) . 
25 
node position: (4,5) . 
node position: (5,5) . 
55 
node position: (1,6) . 
16 
node position: (2,6) . 
node position: (4,6) Z 
node position: (5,6) . 
node position: (1,7) . 
node position: (2,7) . 
node position: (3,7) . 
37 
node position: (4,7) . 
node position: (5,7) . 
57 
node position: (1,8) . 
18 
node position: (2,8) . 
28 
node position: (4,8) Z 
48 
node position: (5,8) . 
58 

qui signifie qu'elle bloque non seulement ceux que je veux verrouiller (être le caractère . que je placé à l'emplacement spécifié), mais aussi ceux que je n » Je veux verrouiller (caractères autres que .).

(5,2) should not be locked 
(2,4) should not be locked 
(2,5) should not be locked 
(1,7) should be locked 
(4,7) should be locked 

Qu'est-ce qui ne va pas ici .. Je suis assez sûr qu'il doit avoir à voir avec la question que j'ai trouvé dans mon débogueur, mais je ne comprends pas pourquoi cela se produit même pas du tout?

--- Update--

Je semble avoir trouvé une autre question comme on le voit ici.

corner found (7,2) 
Check neighbour direction 
neighbour direction is first: 10 

position before: 72 now position: 62 change is: 1 0 Element is: . 
traversed in right direction . 
traversed to position: 52 Element: . 

position before: 72 now position: 52 change is: -2 0 Element is: . 
error found case 1 
position: .72 

Ceci est généré à partir de la boucle while.

while((start_position->adjacent.size() != 2|| start_position->adjacent.size() != 4) /*&& start_position->character =='.'*/) 
        { 
         for(Vertex traversing_edge : start_position->adjacent) 
         { .. } 

je change la valeur de la start_position dans la boucle for, comment la boucle réagir à ce sujet? .. Dans ma tête, il faut tout recommencer, et recommencer depuis le début, au lieu de continuer itérer le premier vecteur start_position.

Devrait-il s'agir d'un while au lieu d'un for? Commence par être le nœud placé à (7,2), puis il traverse le nœud vers la droite (6,2), et cela devient le nouveau start_position. Puis il traverse de nouveau à droite (5,2) et start_position devient ce noeud. Mais la variable traversing_edge devient le noeud placé en (7,2) et se termine ainsi de façon incorrecte. traversing_edge devient une valeur impossible, car les noeuds voisins du noeud placé en (5,2) n'a que les voisins (4,2), (6,2), (5,3) ... donc, quelque chose ne va pas ici vraiment ..

--update -

 DDD 
D.Y....D 
D.Y . 
    ZYZ.Z.Z 
    .Y DDDD 
    .M 
    DD 

Aucun noeud a un vecteur adjacent de taille 1, des nœuds avec des espaces chars est également créé. D montre quels nœuds doivent être verrouillés.

--- --- Lamda update

Son plan Sokoban, et M est la personne, et Y est le diamant et Z sont des objectifs. L'idée est que M pousse Y dans une certaine direction, mais pour éviter de déplacer le diamant dans une position où il ne peut plus être récupéré, ce schéma prétraitera-t-il le graphe de telle sorte que ces positions seront ignorées.

Answer 1

donc .. J'ai finalement réussi à résoudre mon problème, en le réécrivant ..

Le travail nouvelle version d'une manière différente, et semblent un peu plus structuré pour l'oeil humain, mais par rapport celui affiché plus lent au dessus.

Je suis certain que j'ai également trouvé l'erreur dans mon code ci-dessus. Mon surutilisation de la gamme basée sur les boucles, a rendu impossible l'insertion d'une valeur sur la valeur membre de l'objet, que le débogueur m'a montré.

Fixer cela et d'autres choses l'auraient fait fonctionner.

Je tiens à remercier tout le monde pour avoir essayé d'aider à résoudre mon problème, votre aide a été très appréciée. Je ne pensais pas que les gens réagiraient sur un si long post, mais je sentais en même temps que je devais fournir toutes les informations données, donc si quelqu'un osait y jeter un coup d'œil, il aurait une chance raisonnable de le comprendre ..

merci :)