无法找出无限循环背后的原因

Question

我目前正在开发一个程序，它可以从形成轮廓的文件中读取一组坐标，然后使用 flood fill 算法填充它。

下面的代码似乎在无限循环中运行，但我似乎无法找出原因。

非常感谢您的帮助或建议:-)

    /* Flood fill */
    TargetColour = 0.0;
    NewColour = 2.0;
    starting_point = 0+slice;

    //Create queue
    queue < int > MyQue;
    //Insert first point into the queue
    MyQue.push(starting_point);

    //While loop for iterating over the nodes.
    while (!MyQue.empty()){
        //Take out the front element
        Node = MyQue.front();
        MyQue.pop();
        tmpSlice[Node] = NewColour;

        //Define the Node directions
        WestNode = Node-1;
        EastNode = Node+1;
        NorthNode = Node-sizes[1];
        SouthNode = Node+sizes[2];


        //East Node
        if (slab[EastNode] == TargetColour && floor((Node-sizes[1]*sizes[2]*floor(Node/(sizes[1]*sizes[2])))/sizes[1]) == floor((EastNode-sizes[1]*sizes[2]*floor(EastNode/(sizes[1]*sizes[2])))/sizes[1])){
            MyQue.push(EastNode);
        }
        //West Node
        if (slab[WestNode] == TargetColour && floor((Node-sizes[1]*sizes[2]*floor(Node/(sizes[1]*sizes[2])))/sizes[1]) == floor((WestNode-sizes[1]*sizes[2]*floor(WestNode/(sizes[1]*sizes[2])))/sizes[1])){
            MyQue.push(WestNode);
        }
        //North Node
        if (slab[NorthNode] == TargetColour && floor(Node / (sizes[1]*sizes[2])) == floor(NorthNode / (sizes[1]*sizes[2]))){
            MyQue.push(NorthNode);
        }
        //South Node
        if (slab[SouthNode] == TargetColour && floor(Node / (sizes[1]*sizes[2])) == floor(SouthNode / (sizes[1]*sizes[2]))){
            MyQue.push(SouthNode);
        }
    }

Answer 1

我部分确定您的算法实际上正在终止，但只是在很长一段时间后（假设队列有足够的内存）。我需要有关 sizes 值的更多详细信息才能完全确定。

让我们玩一个 3x3 的小示例字段，并假设整个 floor((Node-sizes[1]*sizes[2]*floor(Node/(sizes[1]*sizes[2])))/sizes[1]) 只是一个边界检查（它是什么？）。

字段（数字为职位名称）：

1 2 3
4 5 6
7 8 9

假设starting_point = 1

MyQue = { 1 }
- 访问 1，将 2 和 4 添加到 MyQue
MyQue = { 2, 4 }
- 访问 2，将 3 和 5 添加到 MyQue
MyQue = { 4, 3, 5 }
- 访问 4，将 5 和 7 添加到 MyQue
MyQue = { 3, 5, 5, 7 }
- 访问 3，将 6 添加到 MyQue
MyQue = { 5, 5, 7, 6 }
- 访问 5，将 6 和 8 添加到 MyQue
MyQue = { 5, 7, 6, 6, 8 }
- 访问 5，将 6 和 8 添加到 MyQue
MyQue = { 7, 6, 6, 8, 6, 8 }
- 访问 7，将 8 添加到 MyQue
MyQue = { 6, 6, 8, 6, 8, 8 }
- 访问6，添加9到MyQue
MyQue = { 6, 8, 6, 8, 8, 9 }
- 访问6，添加9到MyQue
MyQue = { 8, 6, 8, 8, 9, 9 }
- 访问8，将9添加到MyQue
MyQue = { 6, 8, 8, 9, 9, 9 }
- 访问6，添加9到MyQue
MyQue = { 8, 8, 9, 9, 9, 9 }
- 访问8，将9添加到MyQue
MyQue = { 8, 9, 9, 9, 9, 9 }
- 访问8，将9添加到MyQue
MyQue = { 9, 9, 9, 9, 9, 9 }
- 访问 9
MyQue = { 9, 9, 9, 9, 9 }
- 访问 9
MyQue = { 9, 9, 9, 9 }
- 访问 9
MyQue = { 9, 9, 9 }
- 访问 9
MyQue = { 9, 9 }
- 访问 9
MyQue = { 9 }
- 访问 9

我希望这说明算法将如何经常重复相同的事情，即使对于一个小字段 - 这种效果会随着字段大小的增加而增加。

所以你能做的就是确保每个节点只排队一次。我认为评估顺序并不重要，因此您可以使用 set 来代替 queue 来存储工作集。这样可以保证每个号码同时只排队一次

您还可以组合队列和设置，以便保持评估顺序。

set < int > marker;
queue < int > MyQue;

// ... replace later in code
// MyQue.push(SomeNode);
// by
if (marker.insert(SomeNode).second) {
    MyQue.push(SomeNode);
}

编辑：稍微更改了 if 条件。如果插入 SomeNode，marker.insert(SomeNode).second 将是 true，如果 SomeNode 已经是集合的一部分，则 false。

无法找出无限循环背后的原因

Can't spot the reason behind infinite loop

c++

flood-fill