# Zusammenhängenden Bereich erkennen



## Campino (18. Dez 2007)

hi, 

ich möchte, dass mein Programm zusammenhängende Bildbereiche, also unregelmäßig geformte Flächen in einer Farbe einfärbt. Leider tritt, wenn ich einfach bei einem Pixel anfange und alle angrenzenden derselben Farbe fülle, eine StackOverflowException auf. Gibt es da einen Trick?

Danke schonmal, 
campino


----------



## Marco13 (18. Dez 2007)

Jo, das ganze nicht rekursiv machen, sondern iterativ....


----------



## Campino (18. Dez 2007)

Ähm...inwiefern hilft den das? Abgesehen davon, dass der Code wahnsinnig umständlich wird, weil ich ja theoretisch in der Mitte meines Bereiches geklickt haben könnte (bzw. der User das vermutlich getan haben wird), ich dann also in alle Richtungen gehen müsste sehe ich nicht, wie das Speicherplatz spart? 

Vielleicht bin ich gerade einfach zu blöd...


----------



## Illuvatar (18. Dez 2007)

Nun ja...

iterativ => keine wiederholten Methodenaufrufe => kein sich füllender Stack => keine StackOverflowException


----------



## Wildcard (18. Dez 2007)

Wenn die Anzahl der Pixel zwar groß, aber dennoch überschaubar groß ist, und ein bestimmtes Maximum nicht überschreitet, dann kannst du auch die Stackgröße erhöhen.


----------



## Marco13 (18. Dez 2007)

Naja, mit an Sicherheit grenzender Wahrscheinlichkeit hast du jetzt im Pesudocode sowas ähnliches (!) wie

```
fülle(x,y)
{
    if (schonGefülltOderAußerhalbDesBereiches(x,y)) return;
    fülle(x+1,y);
    fülle(x,y+1);
    ...
    fülle(x+1,y+1);
}
```
Das wird iterativ natürlich etwas komplizierter, aber u.U. _deutlich_ schneller und eben "sicherer", weil man keinen StackOverflow produzieren kann.

Ganz pragmatisch: Du kannst einen eigenen Stack bauen. Sehr Pseudocodig:

```
fülle(x,y)
{
    if (schonGefülltOderAußerhalbDesBereiches(x,y)) return;
    stack.push(x,y);
    while (!stack.isEmpty())
    {    
        current = stack.pop();
        setzePixel(current.x,current.y);
        stack.push(alleNachbarnDieUngefültSindUndImFüllbereichLiegen(x,y));
    }
}
```
Häm - ja, so etwa ... müßte passen (ist schon recht spät, und bin nicht ganz fit  :?


----------



## Campino (19. Dez 2007)

ähm...das Problem ist, dass ich den Bereich erst bestimmen muss, füllen ist dann okay. 

"schonGefülltOderAußerhalbDesBereiches" geht halt nur, wenn ich weiß, was eigentlich alles im Bereich ist, dass muss ich aber erst feststellen. Die Frage wäre also quasi: Ist es möglich von x, y eine Position x2, y2, von der bekannt ist, dass sie im Bereich liegt, zu erreichen ohne eine Bereichgrenze überqueren zu müssen?


----------



## Marco13 (19. Dez 2007)

Naja, wie sieht denn deine Methode im Moment (ggf. auch im Pseudocode) aus? Irgendwie mußt du ja bestimmen, welcher Punkt in diesem Bereich liegt, und das entscheidet entweder darüber, ob ein neuer rekursiver Aufruf gemacht wird, oder eben darüber, welche Punkte bei alleNachbarnDieUngefültSindUndImFüllbereichLiegen auf den Stack gelegt werden....


----------



## Campino (19. Dez 2007)

> Irgendwie mußt du ja bestimmen, welcher Punkt in diesem Bereich liegt


Eben das ist ja mein Problem.


----------

