Zusammenhängenden Bereich erkennen

[Campino]

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]

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

 

[Campino]

Ä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]

Nun ja...

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

 

[Wildcard]

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]

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]

ä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]

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]

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

Eben das ist ja mein Problem.