Wykrywanie narożników i krawędzi na wykresie

Question

W tej chwili próbuję zaprogramować schemat wykrywania narożników i krawędzi, który powinien być w stanie wykryć narożniki i krawędzie na wykresie.

Struktura danych wykresu zbudowana jest z tablicy char 2d, która może wyglądać tak, jak w tym przykładzie. Rozmiar tego przykładu to 10 wierszy i 9 kol. (Wypełnić białe przestrzenie w pozostałej części brakujące, nie mogłem dodać spacje na granicach ...?)

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

Węzeł jest tworzony dla każdego znaku w węźle, a graf pełny jest przechowywana jako vector<Node> graph.

Każdy węzeł jest zdefiniowany jako taki

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

struct Vertex 
{ 
    Node *current; 
    Node *nextTo; 

}; 

Więc .. Mam wiele węzłów, ale niektóre z nich są zbędne w moim przypadku użycia, do której każdy węzeł ma bool lock => mówi, że te systemy węzły powinny być ignorowane.

Węzły, które chcę zignorować, to te, które mają znak ., na mapie i są umieszczone w pozycji narożnej (sam węzeł ma 2 sąsiada (sąsiad wektora rozmiaru == 2)) lub węzły z charakterem ., który znajduje się między dwoma rogami. Jeśli pomiędzy dwoma rogami pojawi się inna postać, tylko narożniki zostaną zablokowane. podczas przechodzenia przez sąsiedni węzeł narożnika (patrząc na drugi narożnik), a węzeł ma 4 sąsiednie węzły, tylko pierwszy widoczny narożnik zostanie zablokowany.

Więc ... napisałem to do jakiegoś kodu, który skończył się tak.

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; 

Jak sobie sprawę, że kod nie robić, jak chcę to robić, zacząłem debugowanie go ..

Tak więc pierwszą rzeczą, jaką zobaczyłem dziwne jest to. Pierwszy węzeł, który wykrywa jako narożnik, znajduje się w wierszu 2 i kol 1, co jest poprawne.

Następnie próbuje przejść w kierunku pierwszego następnego kierunku węzła, który jest pod nim (wiersz 3, kol. 2), który jest również narożnikiem, ale jakoś wchodzi w pętli? czego nie dostaję. Jego sąsiadujący rozmiar wektora to 2, co również mówi debugger, ale w jakiś sposób w pętli while wykrywa rozmiar wynoszący 2 i wychodzi z pętli while poprawnie i ustawia go, aby węzeł był zablokowany .... (Możliwe problem)

Po tym wszystkim sprawdzam pełny wykres, aby sprawdzić, czy rzeczy, które powinny być zablokowane, są również zablokowane ... co nie jest prawdą.

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; 
    } 
} 

za co dostać to wyjście

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 

sposób, że blokuje nie tylko tych, chcę go zablokować (jako postać . które umieściłem w określonej lokalizacji), ale również tych, i don” t chcesz zablokować (znaki inne niż .).

(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 

Co tu jest nie tak .. Jestem pewien, że to musi mieć do czynienia z emisją znalazłem w moim debugera, ale nie rozumiem, dlaczego to występuje nawet w ogóle?

--- Update--

wydaje mi się, że znalazłem inny problem, jak widać tutaj.

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 

Jest to wyprowadzane z pętli while.

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

zmienić wartość start_position wewnątrz pętli for, jak będzie pętla reagują na to? .. W głowie powinien zacząć wszystko i zacząć od początku, zamiast kontynuować iteracji pierwszy wektor start_position.

Czy powinien to być while zamiast for?

Start_position rozpoczyna się od położenia węzła na (7,2), następnie przechodzi do węzła po prawej stronie (6,2), a to staje się nowym start_position. Następnie przechodzi ponownie w prawo (5,2) i start_position staje się tym węzłem. Ale zmienna traversing_edge staje się węzłem umieszczonym w (7,2), a tym samym kończy się niepoprawnie. traversing_edge staje się niemożliwą wartością, ponieważ węzły sąsiadujące z węzłem umieszczonym w punkcie (5,2) mają tylko sąsiadów (4,2), (6,2), (5,3) ... Więc coś zdecydowanie źle tutaj ..

--update -

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

Nie węzły ma sąsiadujący wektor wielkości 1, węzły ze spacjami tworzy się również znaki. D pokazuje, które węzły powinny być zablokowane.

--- Aktualizacja Lambda ---

Jego Sokoban map, a M jest osobą, a Y jest diament i Z są cele. Pomysł polega na tym, że M popycha Y w określonym kierunku, ale aby zapobiec przesunięciu diamentu do pozycji, w której nie można go odzyskać ponownie, schemat ten będzie wstępnie przetwarzał wykres w taki sposób, że pozycja ta zostanie zignorowana.

Answer 1

Więc .. I w końcu udało się rozwiązać mój problem, przepisując go ..

Nowa wersja praca w inny sposób, i wydaje się nieco bardziej zorganizowany dla ludzkiego oka, ale wolniej niż jeden pisał powyżej.

Jestem pewien, że znalazłem błąd w powyższym kodzie. Moje nadmierne użycie zakresu opartego na pętlach, uniemożliwiło wstawienie wartości do wartości elementu obiektu, którą pokazał mi debugger.

Naprawienie tego i kilka innych rzeczy spowodowałoby, że to zadziałało.

Chciałbym podziękować wszystkim za próbę pomocy w rozwiązaniu mojego problemu. Twoja pomoc została bardzo doceniona. Nie sądziłem, że ludzie zareagują na tak długi post, ale czułem jednocześnie, że muszę podać wszystkie podane informacje, więc jeśli ktokolwiek odważy się na to spojrzeć, będą mieli uzasadnioną szansę na zrozumienie ..

dzięki :)