0

我一直在尝试编写一个可以在 Unity 中工作的洪水填充算法。这个想法是根据用户选择的颜色为黑白线条图的部分着色。我已经尝试了几种洪水填充算法的实现，但是当它们被调用时，它们都会导致统一挂起。

非常感谢对此的任何帮助，这是重要项目的一部分。任何有关修改代码、算法设计或任何替代方法的建议都将不胜感激:)

代码：

// FloodFill function
void FloodFill()
{
    // TEST - colour the clicked pixel
    //_tex.SetPixel( (int)_pixelUV.x, (int)_pixelUV.y, m_fillColour );
    //_tex.SetPixel( _pixelX, _pixelY, m_fillColour );


    // FLOOD FILL 
    // ----------

    // Create WestEast
    List<Point> m_WestEast;

    //get the pixel's colour
    Color PC = new Color(_tex.GetPixel(m_StartNode.X, m_StartNode.Y).r, _tex.GetPixel(m_StartNode.X, m_StartNode.Y).g, _tex.GetPixel(m_StartNode.X, m_StartNode.Y).b);

    //Record clicked pixel as point
    Point node = new Point(m_StartNode.X, m_StartNode.Y);

    //if the pixel's colour is boundary colour (black), return.
    if(PC == Color.black)
    {
        return;
    }

    //else continue

    // Create a list Q[]
    m_List = new List<Point>();

    //add clicked pixel to Q[]
    m_List.Add(node);

    //for each element in Q[]
    for(int i=0; i<m_List.Count; i++)
    {
        //create new WE[] and add Q[n] to it
        m_WestEast = new List<Point>();
        m_WestEast.Add(node);

        //get pixel 1 to left (w) of Q[n]
        Point w = new Point(node.X + 1, node.Y);
        //get colour of w
        Color wCol = new Color(_tex.GetPixel(w.X, w.Y).r, _tex.GetPixel(w.X, w.Y).g, _tex.GetPixel(w.X, w.Y).b);    

        while(wCol != Color.black)
        {        
            //add pixel to WE[] and repeat
            m_WestEast.Add(w);

            //get new w
            w = new Point(w.X + 1, w.Y);

            //get colour of w
            wCol = new Color(_tex.GetPixel(w.X, w.Y).r, _tex.GetPixel(w.X, w.Y).g, _tex.GetPixel(w.X, w.Y).b);    

            //else if colour is boundary colour
                //go to next step
        }

        //get pixel 1 to right (e) of Q[n]
        Point e = new Point(node.X - 1, node.Y);
        //get colour of w
        Color eCol = new Color(_tex.GetPixel(e.X, e.Y).r, _tex.GetPixel(e.X, e.Y).g, _tex.GetPixel(e.X, e.Y).b);    

        while(eCol != Color.black)
        {        
            //add pixel to WE[] and repeat
            m_WestEast.Add(e);

            //get new e
            e = new Point(e.X - 1, e.Y);

            //get colour of e
            eCol = new Color(_tex.GetPixel(e.X, e.Y).r, _tex.GetPixel(e.X, e.Y).g, _tex.GetPixel(e.X, e.Y).b);    

            //else if colour is boundary colour
                //go to next step
        }

        //for each pixel in WE[]
        for(int j=0; j<m_WestEast.Count; j++)
        {
            //set the pixel to replacement colour
            _tex.SetPixel(m_WestEast[j].X, m_WestEast[j].Y, m_fillColour);

            //get pixel 1 to north (n) of Q[n]
            Point n = new Point(m_WestEast[j].X, m_WestEast[j].Y - 1);    

            //get colour of n
            Color nCol = new Color(_tex.GetPixel(n.X, n.Y).r, _tex.GetPixel(n.X, n.Y).g, _tex.GetPixel(n.X, n.Y).b);

            //if colour is not boundary colour
            if(nCol != Color.black)
            {
                //add pixel to Q[]
                m_List.Add(n);
            }

            //get pixel 1 to south (s) of Q[n]
            Point s = new Point(m_WestEast[j].X, m_WestEast[j].Y + 1);    

            //get colour of s
            Color sCol = new Color(_tex.GetPixel(s.X, s.Y).r, _tex.GetPixel(s.X, s.Y).g, _tex.GetPixel(s.X, s.Y).b);

            //if colour is not boundary colour
            if(sCol != Color.black)
            {
                //add pixel to Q[]
                m_List.Add(s);
            }
        }

    }

    // ----------

}
4

1 回答 1

1

您的算法会一遍又一遍地添加相同的像素。它还有其他各种问题，但这就是让它永远运行并耗尽你所有记忆的原因。我认为您正在尝试在这里实现第三个算法：http ://en.wikipedia.org/wiki/Flood_fill

您所拥有的明显区别是 Wikipedia 算法具有：

11. 如果 n 以北的节点的颜色是 target-color，则将该节点添加到 Q。
12. 如果 n 以南的节点的颜色是 target-color，则将该节点添加到 Q。

...但是，您正在测试边界颜色，而不是目标颜色。您的算法将一遍又一遍地检测相同的像素，每次都注意到它们与边界颜色不同。

您还有其他一些问题：

  1. 您正在尝试通过在末尾附加来将列表用作队列。这意味着它一直在增长，并且会无缘无故地消耗大量内存。Wikipedia 中的算法假设您使用队列，并且循环每次将一个项目出列。这不应阻止您的算法工作，但您可能希望在大量使用它之前对其进行修复。
  2. 你有很多代码重复，这使得你的算法不必要地难以阅读，并且当你后来在一个地方进行更改而忘记在其他地方复制它时会带来麻烦。
于 2012-03-03T13:54:34.730 回答