优化自定义洪水填充算法 (Java)

Question

我完全没有使用任何类型的洪水填充算法的经验。但我尽力了。起初，我会在用户点击的地方用洋红色填充一个像素，然后通过一个循环在每个洋红色像素的顶部、左侧、底部和右侧绘制一个像素。这最多需要 8 秒才能完成特别大的区域的填充。所以我添加了另一个循环，向上、向下、向左和向右绘制直的洋红色线条。这将时间减半。我让电脑画了更多的线……左上、左上、左上、左下、左下……等等。现在缩短到 1 到 2 秒之间。我还能做些什么来减少完成填充所需的时间？

  for(Point p:shiftDownPoints)
  {
     //down
     for(int y = p.y+1; y<SCREEN_DIM.height; y++)
     {
        if(capture.getRGB(p.x,y)==Color.BLACK.getRGB())break;
        else capture.setRGB(p.x,y,Color.MAGENTA.getRGB());
     }
     //up
     for(int y = p.y-1; y>0; y--)
     {
        if(capture.getRGB(p.x,y)==Color.BLACK.getRGB())break;
        else capture.setRGB(p.x,y,Color.MAGENTA.getRGB());
     }
     //right
     for(int x = p.x+1; x<SCREEN_DIM.width; x++)
     {
        if(capture.getRGB(x,p.y)==Color.BLACK.getRGB())break;
        else capture.setRGB(x,p.y,Color.MAGENTA.getRGB());
     }
     //left
     for(int x = p.x-1; x>0; x--)
     {
        if(capture.getRGB(x,p.y)==Color.BLACK.getRGB())break;
        else capture.setRGB(x,p.y,Color.MAGENTA.getRGB());
     }
     //down-right
     for(int i = 1; i<Math.min(SCREEN_DIM.width,SCREEN_DIM.height); i++)
     {
        if(capture.getRGB(p.x+i,p.y+i)==Color.BLACK.getRGB())break;
        else capture.setRGB(p.x+i,p.y+i,Color.MAGENTA.getRGB());
     }
     //down-left
     for(int i = 1; i<Math.min(SCREEN_DIM.width,SCREEN_DIM.height); i++)
     {
        if(capture.getRGB(p.x-i,p.y+i)==Color.BLACK.getRGB())break;
        else capture.setRGB(p.x-i,p.y+i,Color.MAGENTA.getRGB());
     }
     //up-left
     for(int i = 1; i<Math.min(SCREEN_DIM.width,SCREEN_DIM.height); i++)
     {
        if(capture.getRGB(p.x-i,p.y-i)==Color.BLACK.getRGB())break;
        else capture.setRGB(p.x-i,p.y-i,Color.MAGENTA.getRGB());
     }
     //up-right
     for(int i = 1; i<Math.min(SCREEN_DIM.width,SCREEN_DIM.height); i++)
     {
        if(capture.getRGB(p.x+i,p.y-i)==Color.BLACK.getRGB())break;
        else capture.setRGB(p.x+i,p.y-i,Color.MAGENTA.getRGB());
     }
     //up-up-left
     for(int i = 1; i<Math.min(SCREEN_DIM.width,SCREEN_DIM.height); i++)
     {
        if(capture.getRGB(p.x-i,p.y-i*2)==Color.BLACK.getRGB())break;
        else capture.setRGB(p.x-i,p.y-i*2,Color.MAGENTA.getRGB());
     }
     //up-left-left
     for(int i = 1; i<Math.min(SCREEN_DIM.width,SCREEN_DIM.height); i++)
     {
        if(capture.getRGB(p.x-i*2,p.y-i)==Color.BLACK.getRGB())break;
        else capture.setRGB(p.x-i*2,p.y-i,Color.MAGENTA.getRGB());
     }
     //down-left-left
     for(int i = 1; i<Math.min(SCREEN_DIM.width,SCREEN_DIM.height); i++)
     {
        if(capture.getRGB(p.x-i*2,p.y+i)==Color.BLACK.getRGB())break;
        else capture.setRGB(p.x-i*2,p.y+i,Color.MAGENTA.getRGB());
     }
     //down-down-left
     for(int i = 1; i<Math.min(SCREEN_DIM.width,SCREEN_DIM.height); i++)
     {
        if(capture.getRGB(p.x-i,p.y+i*2)==Color.BLACK.getRGB())break;
        else capture.setRGB(p.x-i,p.y+i*2,Color.MAGENTA.getRGB());
     }
     //down-down-right
     for(int i = 1; i<Math.min(SCREEN_DIM.width,SCREEN_DIM.height); i++)
     {
        if(capture.getRGB(p.x+i,p.y+i*2)==Color.BLACK.getRGB())break;
        else capture.setRGB(p.x+i,p.y+i*2,Color.MAGENTA.getRGB());
     }
     //down-right-right
     for(int i = 1; i<Math.min(SCREEN_DIM.width,SCREEN_DIM.height); i++)
     {
        if(capture.getRGB(p.x+i*2,p.y+i)==Color.BLACK.getRGB())break;
        else capture.setRGB(p.x+i*2,p.y+i,Color.MAGENTA.getRGB());
     }
     //up-right-right
     for(int i = 1; i<Math.min(SCREEN_DIM.width,SCREEN_DIM.height); i++)
     {
        if(capture.getRGB(p.x+i*2,p.y-i)==Color.BLACK.getRGB())break;
        else capture.setRGB(p.x+i*2,p.y-i,Color.MAGENTA.getRGB());
     }
     //up-up-right
     for(int i = 1; i<Math.min(SCREEN_DIM.width,SCREEN_DIM.height); i++)
     {
        if(capture.getRGB(p.x+i,p.y-i*2)==Color.BLACK.getRGB())break;
        else capture.setRGB(p.x+i,p.y-i*2,Color.MAGENTA.getRGB());
     }
  }

  while(pixelsDrawn)
  {
     pixelsDrawn=false;
     for(int x = 0; x<SCREEN_DIM.width; x++)
        for(int y = 0; y<SCREEN_DIM.height; y++)
        {
           if(capture.getRGB(x,y)==Color.MAGENTA.getRGB())
           {
              if(capture.getRGB(x-1,y)!=Color.MAGENTA.getRGB()
              &&capture.getRGB(x-1,y)!=Color.BLACK.getRGB())
              {
                 capture.setRGB(x-1,y,Color.MAGENTA.getRGB());
                 pixelsDrawn = true;
              }
              if(capture.getRGB(x+1,y)!=Color.MAGENTA.getRGB()
              &&capture.getRGB(x+1,y)!=Color.BLACK.getRGB())
              {
                 capture.setRGB(x+1,y,Color.MAGENTA.getRGB());
                 pixelsDrawn = true;
              }
              if(capture.getRGB(x,y-1)!=Color.MAGENTA.getRGB()
              &&capture.getRGB(x,y-1)!=Color.BLACK.getRGB())
              {
                 capture.setRGB(x,y-1,Color.MAGENTA.getRGB());
                 pixelsDrawn = true;
              }
              if(capture.getRGB(x,y+1)!=Color.MAGENTA.getRGB()
              &&capture.getRGB(x,y+1)!=Color.BLACK.getRGB())
              {
                 capture.setRGB(x,y+1,Color.MAGENTA.getRGB());
                 pixelsDrawn = true;
              }
           }
        }
  }

Answer 1

讨论洪水填充算法可能需要一个完整的 class session。我认为您应该参考 This Link，因为它解释了一切，pixel-by-pixel 如何（有效地）与算法一起绘制。希望这有帮助。

Answer 2

多亏了immibis的建议，我把flood-fill缩短到了半秒。在这个新代码中，我让计算机沿着轮廓的边缘创建一个多边形，然后只使用图形中的 fillPolygon。

  for(Point p:iterablePoints)
  {
     int dir = 2; //0:right, 1:down, 2:left, 3:up
     int xPos = p.x;
     int yPos = 0;
     Polygon poly = new Polygon();
     for(int y = p.y; y>0; y--)
     {
        if(capture.getRGB(p.x,y-1)==Color.BLACK.getRGB())
        {
           yPos = y;
           break;
        }
     }
     Vector<Point> tempRecord = new Vector<Point>();
     boolean run = true;
     while(run)
     {               
        if(dir==0&&capture.getRGB(xPos+1,yPos)==Color.BLACK.getRGB())dir--;
        else if(dir==1&&capture.getRGB(xPos,yPos+1)==Color.BLACK.getRGB())dir--;
        else if(dir==2&&capture.getRGB(xPos-1,yPos)==Color.BLACK.getRGB())dir--;
        else if(dir==3&&capture.getRGB(xPos,yPos-1)==Color.BLACK.getRGB())dir--;
        else 
        {
           if(dir==0)xPos++;
           if(dir==1)yPos++;
           if(dir==2)xPos--;
           if(dir==3)yPos--;

           dir++;

           tempRecord.add(new Point(xPos,yPos));
           if(tempRecord.size()>1)if(tempRecord.get(0)==tempRecord.get(1))tempRecord.remove(tempRecord.firstElement());
           else startPoint = tempRecord.get(0);
           if(startPoint!=null)if(startPoint.x==xPos&&startPoint.y==yPos) run=false;
           poly.addPoint(xPos,yPos);capture.setRGB(xPos,yPos,Color.MAGENTA.getRGB());
        }
        if(dir==4)dir=0;
        if(dir==-1)dir=3;
     }
     Graphics cg = capture.getGraphics();
     cg.setColor(Color.MAGENTA);
     cg.fillPolygon(poly);
     cg.dispose();
  }

优化自定义洪水填充算法 (Java)

Refining custom flood fill algorithm (Java)

java

graphics

flood-fill