8連結境界塗りの範囲外の座標

Question

8連結境界塗りを使用してポリゴンを塗りたい。 4連結境界塗りのコードは動作します。ただし、8連結境界フィルの対角位置をテストするための4つの追加ステートメントを追加すると、ArrayIndexOutOfBoundsExceptionが発生します。境界外の座標！エラー。問題は何ですか？解決する方法は？

private void bfill(int x, int y, Color fillColour, Color borderColour){ 
    Stack<Point> points = new Stack<>(); 
    points.add(new Point(x, y)); 
    while(!points.isEmpty()) { 
     Point currentPoint = points.pop(); 
     x = currentPoint.x; 
     y = currentPoint.y; 
     Color interiorColour = new Color(bi.getRGB(x, y)); 
     if (!interiorColour.equals(borderColour) && !interiorColour.equals(fillColour)){ 
      setPixel(x, y); //draw pixel 
      points.push(new Point(x+1, y)); 
      points.push(new Point(x-1, y)); 
      points.push(new Point(x, y+1)); 
      points.push(new Point(x, y-1)); 
      //Error occurs when the next four lines are uncommented for 8-connected boundary fill 
      /*points.push(new Point(x+1, y+1)); 
      points.push(new Point(x+1, y-1)); 
      points.push(new Point(x-1, y-1)); 
      points.push(new Point(x-1, y+1));*/ 
     } 
    } 
} 

編集：gpaschの答えの後、私は境界チェックが含まれています。しかし、プログラムは無限に実行されます。境界チェックで何が問題になっていますか？

if (!interiorColour.equals(borderColour) && !interiorColour.equals(fillColour)){ 
    if (x > -1 && y > -1 && x < getWidth() && y < getHeight()){ 
     setPixel(x, y); //draw pixel 
     if (x+1 < getWidth()) points.push(new Point(x+1, y)); 
     if (x-1 > -1)   points.push(new Point(x-1, y)); 
     if (y+1 < getHeight()) points.push(new Point(x, y+1)); 
     if (y-1 > -1)   points.push(new Point(x, y-1)); 

     if (x+1 < getWidth() && y+1 < getHeight()) points.push(new Point(x+1, y+1)); 
     if (x+1 < getWidth() && y-1 > -1)   points.push(new Point(x+1, y-1)); 
     if (x-1 > -1 && y-1 > -1)     points.push(new Point(x-1, y-1)); 
     if (x-1 > -1 && y+1 > getHeight())   points.push(new Point(x-1, y+1)); 
     } 
    } 
} 

Answer 1

（x、y）が外れています。

あなたがチェックする必要がある場合は

(X>-1 && x<width) && (y>-1 && y<height) 

（後でトラブルを避けたい場合は）ポイントを追加するときに同じ。

任意の（x + 1、y）、....などが範囲外になる場合は、追加しないでください。

- あなたは次のように境界チェックを拘束する必要があり

：

Color interiorColour = null; 
if (x > -1 && y > -1 && x < getWidth() && y < getHeight()) { 
    interiorColour=new Color(bi.getRGB(x, y)); 
    if (!interiorColour.equals(borderColour) && !interiorColour.equals(fillColour)){ 
     setPixel(x, y); //draw pixel 
     if (x+1 < getWidth()) points.push(new Point(x+1, y)); 
     if (x-1 > -1)   points.push(new Point(x-1, y)); 
     if (y+1 < getHeight()) points.push(new Point(x, y+1)); 
     if (y-1 > -1)   points.push(new Point(x, y-1)); 

     if (x+1 < getWidth() && y+1 < getHeight()) points.push(new Point(x+1, y+1)); 
     if (x+1 < getWidth() && y-1 > -1)   points.push(new Point(x+1, y-1)); 
     if (x-1 > -1 && y-1 > -1)     points.push(new Point(x-1, y-1)); 
     if (x-1 > -1 && y+1 < getHeight())   points.push(new Point(x-1, y+1)); 
    } 
} 

-

さらに検討にあなたのソリューションは、次のような問題に苦しんでいる：訪問されるポイントではありません彼らが何度も何度も訪問されて潜在的に終わりのないプログラムにつながることができるようにする。私はあなたのアルゴリズムの完全な意味を理解しないが、私は次のことをお勧め：

a）の配列を定義：あなたはループに入り、点（x、y）を持っているとき

boolean[] visited=new boolean[width*height]; 
for(i=0; i<visited.length; i++) visited[i]=false; 

Bを） - の後を飛び出る：

if(visited[x+y*width]) continue;   
    visited[x+y*width]=true; 

c）に次のようにチェックを調整します。他の4つについて

if (x+1 < width) if(!visited[x+1+y*width]) points.push(new Point(x+1, y)); 
    if (x-1 > -1)  if(!visited[x-1+y*width])  points.push(new Point(x-1, y)); 
    if (y+1 < height) if(!visited[x+(y+1)*width]) points.push(new Point(x, y+1)); 
    if (y-1 > -1) if(!visited[x+(y-1)*width])  points.push(new Point(x, y-1)); 

同様チェック。

スタックは最大で幅の大きさ*高さに到達することができ、それはまた、0

注意誤差y + 1>のgetHeight（）に減少する、のgetHeight（）< 1 + Yであるべきです。

Answer 2

gpaschさんの更新された回答に続いて、visited配列を境界チェックに含めました。プログラムは終了します。ただし、ウィンドウ全体が塗りつぶされます。

各ポイントがポップされると、xとyの値がテストされました。それらはポリゴンの境界を超えます。ポリゴンの外側の点は、ポリゴンの内側の点と同じ色です。どちらも境界色でも塗りつぶし色でもありません。したがって、それらはスタックに押し込まれ、ポップされると塗りつぶし色で着色されます。

境界チェックは必要ですが、ポリゴンの境界に限定し、ウィンドウの境界には限定しないでください。したがって、ポップ後にポイント（x、y）を取得すると、Polygonオブジェクトのcontainsメソッドを使用して、ポリゴン内にあるかどうかを確認します。