Moin,
ich habe wiedermal ein unnützes Problem und suche nützliche Kommentare
Es geht um den FloodFill Algorithmus in 4 Richtungen (also Pixel die durch eine "1px breite Diagonale" getrennt sind gehören NICHT zusammen).
Der Klassiker ist der einfache Rekursive Ansatz bei welchem man einfach Rekursiv mit x-1, x+1, y-1 und y+1 sich selbst aufruft und so jeden Pixel überprüft. Dabei geht die anzahl Rekursionsschritte aber sehr schnell durch die Decke, sodass diese Methode nicht nur relativ langsam, sondern auch nur für relativ kleine Anwendungen geeignet ist.
UEZ hat dazu schonmal vor einiger Zeit einen Thread gestartet (im EN-Forum) bei dem vorgeschlagen (und auch umgesetzt) wurde, dass man einen Stack benutzt um die Rekursion loszuwerden.
Das Problem ist aber villeicht nicht unbedingt der Stack, sondern die Methode ansich. Es gibt viele Wege um eine FloodFill Funktion zu realisieren und nur eine einzige davon ist es, für jeden Pixel (in 1 px Schritten) in alle 4 Richtungen zu suchen (Hier werden noch ein paar Methoden gezeigt). Im englischen Wikipedia ist z.B. noch eine Right-Hand Fill Method vermerkt (die im Deutschen fehlt). Im Deutschen Wiki ist dafür noch eine kurze Vermerkung zu einem gewissen Span Flood Fill.
Und hier kommt der Hilfegesuch:
Bevor ich jetzt 50 verschiedene Methoden (ich zähle eine Rekursive und eine Iterative Methode als EINE Methode, sofern sie gleich vorgeht) implementiere und gegeneinander antreten lasse möchte ich herumfragen ob jemand schonmal etwas in diese Richtung programmiert hat (vllt sogar in AutoIt) und dazu irgendein Statement hat welche Methode in AutoIt eventuell recht schnell arbeitet.
Im Beispielskript sind 3 FloodFill Methoden eingebaut.
- FloodFill1: Das erste was Wikipedia sagt muss auch zuerst implementiert werden.
- FloodFill2: Genau wie FF1 mit dem Unterschied, dass man keinen "Schritt zurück" gehen kann. (also wenn ich x+1 gehe kann man im nächsten Schritt nicht x-1 gehen)
- FloodFill3: Habe ich mir ausgedacht und später herausgefunden, dass das Ganze eine Variation des Recursive Scanline Flood Fill Algorithmus ist.
Natürlich kann jeder der Lust hat auch Eigenkreationen ausprobieren, die können villeicht besser als alles was es bereits gibt sein
#include <Array.au3>
; Einstellungen zum Ausprobieren
Global Const $n = 10 ; Anzahl Runden deren mittlere Zeit gemessen wird
Global Const $ArrayDisplay = False ; Will man die Arrays sehen ?
; Die "Bitmap" wird hier erstellt. Es wird angenommen, dass die FloodFill Algorithmen iW und iH kennen (global)
Global Const $iW = 24
Global Const $iH = 24
Global $aBitmap[$iH][$iW], $aReads[$iH][$iW], $aWrites[$iH][$iW], $iPixel = 0
Func Reset() ; Hier kann sich jeder eine "bitmap" basteln mit 2 Farben
$iPixel = 0
For $y = 0 To $iW - 1 Step 1
For $x = 0 To $iH - 1 Step 1
$aBitmap[$y][$x] = ($x - 8) ^ 2 + ($y - 8) ^ 2 < 6 ^ 2 ? 2 : 1
$aBitmap[$y][$x] = ($x - 16) ^ 2 + ($y - 16) ^ 2 < 6 ^ 2 ? 2 : $aBitmap[$y][$x]
If $aBitmap[$y][$x] = 2 Then $iPixel += 1
$aReads[$y][$x] = 0
$aWrites[$y][$x] = 0
Next
Next
$aBitmap[19][2] = 2
$aBitmap[18][2] = 2
$aBitmap[17][2] = 2
$aBitmap[15][2] = 2
$aBitmap[15][3] = 2
$aBitmap[16][4] = 2
$aBitmap[17][5] = 2
$aBitmap[18][4] = 2
$aBitmap[19][4] = 2
$aBitmap[16][1] = 2
$aBitmap[15][0] = 2
$aBitmap[17][0] = 2
$aBitmap[19][3] = 2
$aBitmap[7][7] = 1
EndFunc ;==>Reset
; ################################################################################
Global $iTimer, $iTime
Reset()
If $ArrayDisplay Then _ArrayDisplay($aBitmap)
ConsoleWrite('###############' & @CRLF)
$iTime = 0
For $i = 1 To $n Step 1
Reset()
$iTimer = TimerInit()
FloodFill1(18, 18, 123)
$iTime += TimerDiff($iTimer)
Next
ConsoleWrite('FF1: ' & StringFormat('%.3f', $iTime / $n) & ' ms' & @CRLF)
Info(True)
If $ArrayDisplay Then _ArrayDisplay($aBitmap)
ConsoleWrite('###############' & @CRLF)
$iTime = 0
For $i = 1 To $n Step 1
Reset()
$iTimer = TimerInit()
FloodFill2(18, 18, 123)
$iTime += TimerDiff($iTimer)
Next
ConsoleWrite('FF2: ' & StringFormat('%.3f', $iTime / $n) & ' ms' & @CRLF)
Info(True)
If $ArrayDisplay Then _ArrayDisplay($aBitmap)
ConsoleWrite('###############' & @CRLF)
$iTime = 0
For $i = 1 To $n Step 1
Reset()
$iTimer = TimerInit()
FloodFill3(18,18, 123)
$iTime += TimerDiff($iTimer)
Next
ConsoleWrite('FF3: ' & StringFormat('%.3f', $iTime / $n) & ' ms' & @CRLF)
Info(True)
If $ArrayDisplay Then _ArrayDisplay($aBitmap)
ConsoleWrite('###############' & @CRLF)
$iTime = 0
For $i = 1 To $n Step 1
Reset()
$iTimer = TimerInit()
FloodFill_Andy(18, 18, 123)
$iTime += TimerDiff($iTimer)
Next
ConsoleWrite('Andy: ' & StringFormat('%.3f', $iTime / $n) & ' ms' & @CRLF)
Info(True)
If $ArrayDisplay Then _ArrayDisplay($aBitmap)
ConsoleWrite('###############' & @CRLF)
$iTime = 0
For $i = 1 To $n Step 1
Reset()
$iTimer = TimerInit()
FloodFill_Andy2(18, 18, 123)
$iTime += TimerDiff($iTimer)
Next
ConsoleWrite('Andy2: ' & StringFormat('%.3f', $iTime / $n) & ' ms' & @CRLF)
Info(True)
If $ArrayDisplay Then _ArrayDisplay($aBitmap)
ConsoleWrite('###############' & @CRLF)
Func FloodFill_Andy($x, $y, $iColFill)
Dim $liste[$iW * $iH] ;maximaler Füllbereich, normalerweise eine "leere" Bitmap
Dim $bitmap_marker[$iW * $iH]
Local $iColRead = Read($x, $y)
$counter = 0 ;für Listenelement
$listcounter = 0 ;anzahl elemente in liste
$liste[$listcounter] = $y * $iW + $x ;position pixel in bitmap
Write($x, $y, $iColFill)
While 1 ;$listende_nicht_erreicht
;koordinate nächstes Element in der Liste, diese umrecherei ist in einer bitmap völlig unnötig.....
$x = Mod($liste[$counter], $iW)
$y = Int($liste[$counter] / $iH)
;4 Nachbarpunkte auf $iColRead testen
$xL = $x - 1 ;linker pixel
$yL = $y
$xR = $x + 1 ;rechter pixel
$yR = $y
$xO = $x ;oberer Pixel
$yO = $y - 1
$xU = $x ;unterer Pixel
$yU = $y + 1
If $xL >= 0 And $xL < $iW And $bitmap_marker[$yL * $iW + $xL] = 0 Then ;wenn im bereich und noch nicht in der Liste
If Read($xL, $yL) = $iColRead Then ;Pixel mit $iColRead gefunden
Write($xL, $yL, $iColFill)
$listcounter += 1
$liste[$listcounter] = $yL * $iW + $xL ;position pixel in bitmap
$bitmap_marker[$yL * $iW + $xL] = 1
EndIf
EndIf
If $xR >= 0 And $xR < $iW And $bitmap_marker[$yR * $iW + $xR] = 0 Then
If Read($xR, $yR) = $iColRead Then ;Pixel mit $iColRead gefunden
Write($xR, $yR, $iColFill)
$listcounter += 1
$liste[$listcounter] = $yR * $iW + $xR ;position pixel in bitmap
$bitmap_marker[$yR * $iW + $xR] = 1
EndIf
EndIf
If $yO >= 0 And $yO < $iH And $bitmap_marker[$yO * $iW + $xO] = 0 Then
If Read($xO, $yO) = $iColRead Then ;Pixel mit $iColRead gefunden
Write($xO, $yO, $iColFill)
$listcounter += 1
$liste[$listcounter] = $yO * $iW + $xO ;position pixel in bitmap
$bitmap_marker[$yO * $iW + $xO] = 1
EndIf
EndIf
If $yU >= 0 And $yU < $iH And $bitmap_marker[$yU * $iW + $xU] = 0 Then
If Read($xU, $yU) = $iColRead Then ;Pixel mit $iColRead gefunden
Write($xU, $yU, $iColFill)
$listcounter += 1
$liste[$listcounter] = $yU * $iW + $xU ;position pixel in bitmap
$bitmap_marker[$yU * $iW + $xU] = 1
EndIf
EndIf
If $listcounter = $counter Then ExitLoop
$counter = $counter + 1
; _arraydisplay($liste)
;~ If $ArrayDisplay Then _ArrayDisplay($aBitmap)
WEnd
;~ If $ArrayDisplay Then _ArrayDisplay($areads)
;~ If $ArrayDisplay Then _ArrayDisplay($bitmap_marker)
EndFunc ;==>FloodFill_Andy
Func FloodFill_Andy2($x, $y, $iColFill)
Dim $liste[$iW * $iH] ;maximaler Füllbereich, normalerweise eine "leere" Bitmap
Dim $bitmap_marker[$iW * $iH]
Local $iColRead = Read($x, $y)
$counter = 0 ;für Listenelement
$listcounter = 0 ;anzahl elemente in liste
$liste[$listcounter] = $y * $iW + $x ;position pixel in bitmap
Write($x, $y, $iColFill)
While 1 ;$listende_nicht_erreicht
;koordinate nächstes Element in der Liste, diese umrecherei ist in einer bitmap völlig unnötig.....
$x = Mod($liste[$counter], $iW)
$y = Int($liste[$counter] / $iH)
;4 Nachbarpunkte auf $iColRead testen
$xL = $x - 1 ;linker pixel
$xR = $x + 1 ;rechter pixel
$yO = $y - 1
$yU = $y + 1
$pos = $y * $iW + $xL
If $xL >= 0 And $bitmap_marker[$pos] = 0 Then ;wenn im bereich und noch nicht in der Liste
If Read($xL, $y) = $iColRead Then ;Pixel mit $iColRead gefunden
Write($xL, $y, $iColFill)
$listcounter += 1
$liste[$listcounter] = $pos ;position pixel in bitmap
$bitmap_marker[$pos] = 1
EndIf
EndIf
$pos = $y * $iW + $xR
If $xR < $iW And $bitmap_marker[$pos] = 0 Then
If Read($xR, $y) = $iColRead Then ;Pixel mit $iColRead gefunden
Write($xR, $y, $iColFill)
$listcounter += 1
$liste[$listcounter] = $pos ;position pixel in bitmap
$bitmap_marker[$pos] = 1
EndIf
EndIf
$pos = $yO * $iW + $x
If $yO >= 0 And $bitmap_marker[$pos] = 0 Then
If Read($x, $yO) = $iColRead Then ;Pixel mit $iColRead gefunden
Write($x, $yO, $iColFill)
$listcounter += 1
$liste[$listcounter] = $pos ;position pixel in bitmap
$bitmap_marker[$pos] = 1
EndIf
EndIf
$pos = $yU * $iW + $x
If $yU < $iH And $bitmap_marker[$pos] = 0 Then
If Read($x, $yU) = $iColRead Then ;Pixel mit $iColRead gefunden
Write($x, $yU, $iColFill)
$listcounter += 1
$liste[$listcounter] = $pos ;position pixel in bitmap
$bitmap_marker[$pos] = 1
EndIf
EndIf
If $listcounter = $counter Then ExitLoop
$counter = $counter + 1
; _arraydisplay($liste)
;~ If $ArrayDisplay Then _ArrayDisplay($aBitmap)
WEnd
;~ If $ArrayDisplay Then _ArrayDisplay($areads)
;~ If $ArrayDisplay Then _ArrayDisplay($bitmap_marker)
EndFunc ;==>FloodFill_Andy2
Func FloodFill1($x, $y, $iColFill, $iColArea = 0) ; Aus dem Bilderbuch bzw. Wikipedia.
Local $iColRead = Read($x, $y) ; Tempo : Bummelbahn mit angezogener Handbremse
If $iColArea = 0 Then $iColArea = $iColRead ; Rekursion: Sehr schnell sehr viele Rekursionen
If $iColArea <> $iColRead Then Return ; Reads : So viel wie möglich (schlecht)
If $iColFill = $iColRead Then Return
Write($x, $y, $iColFill)
If $x > 0 Then FloodFill1($x - 1, $y, $iColFill, $iColArea)
If $x < $iW - 1 Then FloodFill1($x + 1, $y, $iColFill, $iColArea)
If $y > 0 Then FloodFill1($x, $y - 1, $iColFill, $iColArea)
If $y < $iH - 1 Then FloodFill1($x, $y + 1, $iColFill, $iColArea)
EndFunc ;==>FloodFill1
Func FloodFill2($x, $y, $iColFill, $iColArea = 0, $iLast = -1) ; Genau das gleiche wie FloodFill1 nur, dass man nicht mehr dahingehen kann wo man herkommt.
Local $iColRead = Read($x, $y) ; Tempo : Bummelbahn
If $iColArea = 0 Then $iColArea = $iColRead ; Rekursion: Sehr schnell sehr viele Rekursionen
If $iColArea <> $iColRead Then Return ; Reads : Weniger als FloodFill1 und FloodFill3
If $iColFill = $iColRead Then Return
Write($x, $y, $iColFill)
If $iLast <> 0 And $x > 0 Then FloodFill2($x - 1, $y, $iColFill, $iColArea, 2)
If $iLast <> 2 And $x < $iW - 1 Then FloodFill2($x + 1, $y, $iColFill, $iColArea, 0)
If $iLast <> 3 And $y > 0 Then FloodFill2($x, $y - 1, $iColFill, $iColArea, 1)
If $iLast <> 1 And $y < $iH - 1 Then FloodFill2($x, $y + 1, $iColFill, $iColArea, 3)
EndFunc ;==>FloodFill2
Func FloodFill3($x, $y, $iColFill, $iColArea = 0) ; Spontan ausgedacht. Nachschlagen ergab, dass eine ähnliche Methode Scanline Flood Fill heißt.
If $iColArea = 0 Then $iColArea = Read($x, $y) ; Tempo : Mofa mit aufgebohrtem Zylinderkopf und zugepetztem Auspuff.
Write($x, $y, $iColFill) ; Rekursion: Eine für jede "Linie" in jeder Zeile. Also irgendwas wie die CONST * AREAHEIGHT (sollte nicht so schnell wachsen)
For $xMax = $x + 1 To $iW - 1 Step 1 ; Reads : Weniger als FloodFill1 und mehr als FloodFill3
$iColRead = Read($xMax, $y)
If $iColRead <> $iColArea Then ExitLoop
Write($xMax, $y, $iColFill)
Next
For $xMin = $x - 1 To 0 Step -1
$iColRead = Read($xMin, $y)
If $iColRead <> $iColArea Then ExitLoop
Write($xMin, $y, $iColFill)
Next
$xMin += 1
$xMax -= 1
;~ If $xMin = -1 Then $xMin = 0
;~ If $xMax = $iW Then $xMax = $iW - 1
If $y > 0 Then
For $i = $xMin To $xMax Step 1
If Read($i, $y - 1) = $iColArea Then FloodFill3($i, $y - 1, $iColFill, $iColArea)
Next
EndIf
If $y < $iH - 1 Then
For $i = $xMin To $xMax Step 1
If Read($i, $y + 1) = $iColArea Then FloodFill3($i, $y + 1, $iColFill, $iColArea)
Next
EndIf
EndFunc ;==>FloodFill3
Func Info($bPlot = False)
Local $iReads, $iWrites
If $bPlot Then ConsoleWrite('##################################### [ Reads | Writes ] ######################################' & @CRLF)
For $y = 0 To $iH - 1 Step 1
For $x = 0 To $iW - 1 Step 1
$iReads += $aReads[$y][$x]
$iWrites += $aWrites[$y][$x]
If $bPlot Then ConsoleWrite('[' & $aReads[$y][$x] & '|' & $aWrites[$y][$x] & '] ')
Next
If $bPlot Then ConsoleWrite(@CRLF)
Next
ConsoleWrite('Reads: ' & $iReads & @CRLF)
ConsoleWrite('Writes: ' & $iWrites & @CRLF)
If $bPlot Then ConsoleWrite('###############################################################################################' & @CRLF)
EndFunc ;==>Info
Func Read($x, $y)
$aReads[$y][$x] += 1
Return $aBitmap[$y][$x]
EndFunc ;==>Read
Func Write($x, $y, $iCol)
$aWrites[$y][$x] += 1
$aBitmap[$y][$x] = $iCol
EndFunc ;==>Write
Alles anzeigen
lg
M