图中的拐角和边缘检测

Question

我正在尝试编写角点和边缘检测方案,该方案应该能够检测图形中的角和边缘.

图形数据结构是从2d char数组构建的,它看起来像这个例子的大小是10行和9 col.(白色空间填补了其余的遗失,我无法在边界添加空格......？)

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

为节点中的每个字符创建一个节点,完整的图形存储为a vector<Node> graph.

每个节点都是这样定义的

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

struct Vertex
{
   Node *current;
   Node *nextTo;

};

所以..我有很多节点但是在我的用例中有些节点是冗余的,每个节点都有一个bool lock=>告诉系统应该忽略这些节点.

我想忽略的节点是那些.在地图中具有角色并放置在角落位置的节点(节点本身有2个邻居(大小矢量邻居== 2)),或者.是在两个角落之间具有角色的节点.如果在两个角之间出现其他角色,则仅将角设置为锁定.当遍历角落的相邻节点(寻找第二个角落),并且一个节点有4个相邻节点时,只有看到的第一个角落被设置为被锁定.

所以..我把它写成了一些代码,最终看起来像这样.

 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;

当我意识到代码没有像我想要的那样做时,我开始调试它..

所以我看到的第一个奇怪的事情就是这个.它检测到的第一个节点是位于第2行和第1列的节点,这是正确的.

然后它尝试遍历第一个nextTo节点方向的方向,该方向是它下面的那个方向(第3行,第2列),它也是一个角,但不知何故它进入循环？我没有得到.它的相邻向量大小是2,调试器也说,但是在while循环中,它检测到大小为2,并正确地离开while循环并将其设置为被锁定....(可能的问题)

当我完成所有这些时,我检查完整的图表以查看应该锁定的东西是否也被锁定......事实并非如此.

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

我得到了这个输出

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

这意味着它不仅锁定了我想要锁定的那些(.我放置在指定位置的角色),还锁定了我不想锁定的那些(除了以外的字符.).

(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

这里出了什么问题..我很确定它必须与我在调试器中发现的问题有关,但我不明白为什么甚至会发生这种情况？

--- Update--

我似乎在这里看到了另一个问题.

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

这是从while循环输出的.

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

我改变了循环start_position内部的值,for循环将如何对此作出反应？在我脑海里它应该从头开始,从头开始,而不是继续迭代第一个start_position向量.

它应该是while一个for吗？

Start_position通过作为放置在(7,2)的节点开始,然后它遍历到右边的节点(6,2),并且它成为新节点start_position.然后它再次向右移动(5,2)并start_position成为该节点.但变量traversing_edge成为放置在(7,2)的节点,从而不正确地结束.. traversing_edge变成一个不可能的值,因为与放置在(5,2)的节点相邻的节点只有邻居(4,2),(6) ,2),(5,3)......所以这里肯定是错的..

- 更新 -

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

没有节点具有大小为1的相邻向量,也创建具有空白字符的节点. D显示应锁定哪些节点.

--- Lamda更新---

它是推箱子地图,M是人,Y是钻石,Z是目标.这个想法是M在某个方向上推Y,但是为了防止钻石移动到无法再次检索的位置,这个方案会预先处理图形,以便忽略那些位置.

Answer 1

所以..我终于通过重写解决了我的问题..

新版本以不同的方式工作，对于人眼来说似乎更加结构化，但与上面发布的版本相比速度较慢。

我确信我也发现了上面代码中的错误。我过度使用基于范围的 for 循环，导致无法在对象的成员值上插入值，调试器向我展示了这一点。

解决这个问题和其他一些问题就可以让它发挥作用。

我要感谢大家尝试帮助解决我的问题，非常感谢您的帮助。我不认为人们会对这么长的帖子做出反应，但我觉得同时我必须提供所有给定的信息，这样如果有人敢于研究它，他们就有合理的机会理解它。

谢谢 ：）