Koordinaten außerhalb der Grenze in 8-zusammenhängender Grenzfüllung

Question

Ich möchte ein Polygon mit 8-verbundener Grenzfüllung füllen. Der Code für die 4-verknüpfte Grenzfüllung funktioniert. Wenn ich jedoch die vier zusätzlichen Anweisungen hinzufüge, um diagonale Positionen für die 8-verbundene Grenzfüllung zu testen, bekomme ich ArrayIndexOutOfBoundsException: Coordinate out of bounds! Fehler. Was ist das Problem und wie löst man es?

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));*/ 
     } 
    } 
} 

bearbeiten: gpasch Antwort Folgen, I der Grenzen zu überprüfen. Das Programm läuft jedoch endlos. Was stimmt nicht mit der Überprüfung der Grenzen?

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) geht außerhalb der Grenzen.

Sie benötigen, wenn

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

Das gleiche gilt für überprüfen, wenn die erhaltenen Punkte (wenn Sie später Probleme vermeiden möchten).

Wenn eines (x + 1, y), ... usw. außerhalb der Grenzen liegt, fügen Sie es nicht hinzu.

-

Sie haben die Überprüfung der Grenzen zu beschränken, wie folgt:

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)); 
    } 
} 

-

Bei näherer Betrachtung Ihre Lösung aus folgendem Problem leidet: Punkte, die besucht werden, sind nicht ausgeschlossen, so dass sie immer wieder besucht werden können, was möglicherweise zu einem nie endenden Programm führt. Ich habe nicht die vollen Auswirkungen des Algorithmus verstehen, aber ich schlage vor, die folgenden:

a) definieren ein Array:

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

b), wenn Sie geben Sie die Schleife und haben einen Punkt (x, y) - nach popping:

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

c) die Überprüfung wie folgt anpassen: für die anderen vier

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)); 

Ähnliche Kontrollen.

Der Stapel kann höchstens erreicht dann eine Größe der Breite * Höhe wird es auf 0 gesetzt

Hinweis auch der Fehler y + 1> getHeight() zu verringern, sollte y + 1 < getHeight() sein.

Answer 2

Nach gpaschs aktualisierter Antwort habe ich das besuchte Array in die Überprüfung der Grenzen einbezogen. Das Programm wird beendet. Es füllt jedoch das ganze Fenster aus.

Ich testete die x-und y-Werte, wie jeder Punkt geknallt wird. Sie gehen über die Grenzen des Polygons hinaus. Punkte außerhalb des Polygons haben die gleiche Farbe wie Punkte innerhalb des Polygons. Beide sind weder Randfarbe noch Füllfarbe. Daher werden sie auf den Stapel geschoben und beim Auffüllen mit der Füllfarbe eingefärbt.

Die Überprüfung der Grenzen ist erforderlich, sollte jedoch auf die Grenzen des Polygons und nicht auf die Grenzen des Fensters beschränkt sein. Sobald ich also einen Punkt (x, y) nach dem Popping habe, überprüfe ich mit der Methode contains des Polygon-Objekts, ob es sich im Polygon befindet.