Floodfillアルゴリズムが遅く動作していますが、どうすればこのアルゴリズムを高速化できますか？

Question

public void floodFill(Bitmap bitmap, Point point, int i, int j) { 
    int k = bitmap.getWidth(); 
    int l = bitmap.getHeight(); 
    if (i != j) { 
     LinkedList linkedlist = new LinkedList(); 
     do { 
      int i1 = point.x; 
      int j1; 
      for (j1 = point.y; i1 > 0 && !isBlack(bitmap.getPixel(i1 - 1, j1),j); i1--) { 
      } 
      boolean flag = false; 
      boolean flag1 = false; 
      while (i1 < k && !isBlack(bitmap.getPixel(i1, j1), j)) { 
       bitmap.setPixel(i1, j1, j); //main 

       if (!flag && j1 > 0 && !isBlack(bitmap.getPixel(i1, j1 - 1), j)) { 
        linkedlist.add(new Point(i1, j1 - 1)); 
        flag = true; 
       } else if (flag && j1 > 0 && isBlack(bitmap.getPixel(i1, j1 - 1), j)) { 
        flag = false; 
       } 

       if (!flag1 && j1 < l - 1 && !isBlack(bitmap.getPixel(i1, j1 + 1), j)) { 
        linkedlist.add(new Point(i1, j1 + 1)); 
        flag1 = true; 
       } else if (flag1 && j1 < l - 1 && isBlack(bitmap.getPixel(i1, j1 + 1), j)) { 
        flag1 = false; 
       } 

       i1++; 
      } 

      point = (Point) linkedlist.poll(); 
     } while (point != null); 
    } 
} 

private boolean isBlack(int i, int j) { 
    while (Color.red(i) == Color.green(i) && 
      Color.green(i) == Color.blue(i) && 
      Color.red(i) < 100 || i == j) { 
     return true; 
    } 
    return false; 
} 

私はこのコードを使用して、イメージの任意の部分をクリックするとそれぞれの色で図形を塗りつぶします。ボーダーに白い辺を残すことなく、まったく問題なく動作していますが、この問題はあまりにも遅いです。どうすればスピードアップできますか？

Answer 1

あなたがアップ薄く速度にさまざまな方法を試してみることができます。

1. 変更アルゴリズム自体
2. は、物事を少し速める可能性が少しoptiomizationsを作ります。

常に最適化のため： 各最適化の前後にコードをプロファイルして、何か入手したかどうかを確認します。 1.
に関連

あなたは大きな黒い部分を持っている場合は、あなたが試みることができる：あなたのイメージダウンスケール

1. をして（ただし国境まで）ダウンスケール画像を記入し、充填を適用大きな矩形で元の画像に戻します。

2. （境界とすべての詳細を土台に）次のステップ1に充填された大きな矩形の一つに原画像に2

   • 関連

を埋めます画像の周りに1ピクセルの黒い枠線を追加することができます。

public void floodFill(Bitmap bitmap, Point point, int i, int j) { 
int k = bitmap.getWidth(); 
int l = bitmap.getHeight(); 
if (i != j) { 
    LinkedList linkedlist = new LinkedList(); 
    do { 
     int i1 = point.x; 
     int j1; 
     for (j1 = point.y; i1 > 0 && !isBlack(bitmap.getPixel(i1 - 1, j1),j); i1--) { 
     } 
     boolean flag = false; 
     boolean flag1 = false; 
     while (i1 < k && !isBlack(bitmap.getPixel(i1, j1), j)) { 
      bitmap.setPixel(i1, j1, j); //main 

      if (!flag && !isBlack(bitmap.getPixel(i1, j1 - 1), j)) { 
       linkedlist.add(new Point(i1, j1 - 1)); 
       flag = true; 
      } else if (flag && isBlack(bitmap.getPixel(i1, j1 - 1), j)) { 
       flag = false; 
      } 

      if (!flag1 && !isBlack(bitmap.getPixel(i1, j1 + 1), j)) { 
       linkedlist.add(new Point(i1, j1 + 1)); 
       flag1 = true; 
      } else if (flag1 && j1 < l - 1 && isBlack(bitmap.getPixel(i1, j1 + 1), j)) { 
       flag1 = false; 
      } 
      i1++; 
     } 

     point = (Point) linkedlist.poll(); 
    } while (point != null); 
} 

// maybe even reorder the conditions: 
// If conditions are equal hard to compute: 
// for || always do the mostlikely satisfied condition to the front 
// for && always do the mostlikely to fail condition to the front 



private boolean isBlack(int i, int j) { 
    float r= Color.red(i); 
    float g= Color.green(i); 
    float b= Color.blue(i); 
    retrun (r == g && g == b && r < 100 || i == j) ; 
}