December 04, 2020, 10:54:46 AM

Author Topic: [bmx] Non Recursive FloodFill by klepto2 [ 1+ years ago ]  (Read 458 times)

Offline BlitzBot

  • Jr. Member
  • **
  • Posts: 1
[bmx] Non Recursive FloodFill by klepto2 [ 1+ years ago ]
« on: June 29, 2017, 12:28:40 AM »
Title : Non Recursive FloodFill
Author : klepto2
Posted : 1+ years ago

Description : After trying some recursive Functions without success, I found this BB code from Snarty and converted it to Bmax.

It is fully non recursive so no chance of these Overflow errors.


Code :
Code: BlitzMax
  1. 'Fill Routines
  2. ' Written By Paul Snart (Snarty) - Converted to BMax by klepto2 in Oct 2005
  3. ' Oct 2001
  4.  
  5. ' RCol = RGB Color To Fill with
  6. ' Ax = X Start on Image To Fill
  7. ' Ay = Y Start on Image To Fill
  8. ' Image = Image To fill on
  9.  
  10. Strict
  11.  
  12.  
  13. Type Point
  14.         Global Point_List:TList
  15.      Field x
  16.      Field y
  17.  
  18.         Method New()
  19.                 If Point.Point_List = Null Then Point.Point_List = New TList
  20.                 Point.Point_List.AddLast(Self)
  21.         End Method
  22.        
  23. End Type
  24.  
  25. Function FloodFill(RCol,ax,ay,Image:TPixmap)
  26.  
  27.          Local timeit=MilliSecs()
  28.          Local y:Int
  29.                  Local BCol=Image.ReadPixel(ax,ay)
  30.          Local ImW=Image.width
  31.          Local ImH=Image.Height
  32.      
  33.       If BCol<>RCol
  34.      
  35.         Local   Hlt=-1
  36.         Local   Hlb=-1
  37.     Local   Hrt=-1
  38.         Local   Hrb=-1
  39.     Local   Entrys=1
  40.         Local   FP:Point = New Point
  41.             Fp.x=ax
  42.             Fp.y=ay  
  43.            
  44.           Repeat
  45.                FP:Point=Point(Point.Point_List.First())
  46.         Local  Lx=Fp.x
  47.         Local  Rx=Fp.x+1
  48.         Local  HitL=False
  49.                 Local  HitR=False
  50.                Hlt=-1
  51.                            Hlb=-1
  52.                Hrt=-1
  53.                            Hrb=-1
  54.                Repeat
  55.                     If Lx=>0 and HitL=False
  56.         Local           CColL=Image.ReadPixel(Lx,Fp.y)
  57.                          If CColL=BCol
  58.                               Image.WritePixel Lx,Fp.y,RCol
  59.                               If Fp.y>0
  60.                                    CColL=Image.ReadPixel(Lx,Fp.y-1)
  61.                                    If CColL=BCol
  62.                                         Hlt=Lx
  63.                                    Else
  64.                                         If Hlt<>-1
  65.                                              y=Fp.y-1
  66.                                              FP:Point = New Point
  67.                                              Fp.y=y
  68.                                                                             Fp.x=Hlt
  69.                                              Hlt=-1
  70.                                              FP:Point = Point(Point.Point_List.First())
  71.                                              Entrys=Entrys+1
  72.                                         EndIf
  73.                                    EndIf
  74.                               EndIf
  75.                               If Fp.y<ImH-1
  76.                                    CColL=Image.ReadPixel(Lx,Fp.y+1)
  77.                                    If CColL=BCol
  78.                                         Hlb=Lx
  79.                                    Else
  80.                                         If Hlb<>-1
  81.                                              y=Fp.y+1
  82.                                              FP:Point = New Point
  83.                                              Fp.y=y
  84.                                                                             Fp.x=Hlb
  85.                                              Hlb=-1
  86.                                              FP:Point = Point(Point.Point_List.First())
  87.                                              Entrys=Entrys+1
  88.                                         EndIf
  89.                                    EndIf
  90.                               EndIf
  91.                               Lx=Lx-1
  92.                          Else
  93.                               HitL=True
  94.                               If Hlt<>-1
  95.                                    y=Fp.y-1
  96.                                    FP:Point = New Point
  97.                                    Fp.y=y
  98.                                                            Fp.x=Hlt
  99.                                    Hlt=-1
  100.                                    FP:Point = Point(Point.Point_List.First())
  101.                                    Entrys=Entrys+1
  102.                               EndIf
  103.                               If Hlb<>-1
  104.                                    y=Fp.y+1
  105.                                    FP:Point = New Point
  106.                                    Fp.y=y
  107.                                                            Fp.x=Hlb
  108.                                    Hlb=-1
  109.                                    FP:Point = Point(Point.Point_List.First())
  110.                                    Entrys=Entrys+1
  111.                               EndIf
  112.                          EndIf
  113.                     Else
  114.                          HitL=True
  115.                          If Hlt<>-1
  116.                               y=Fp.y-1
  117.                               FP:Point = New Point
  118.                               Fp.y=y
  119.                                                    Fp.x=Hlt
  120.                               Hlt=-1
  121.                               FP:Point = Point(Point.Point_List.First())
  122.                               Entrys=Entrys+1
  123.                          EndIf
  124.                          If Hlb<>-1
  125.                               y=Fp.y+1
  126.                               FP:Point = New Point
  127.                               Fp.y=y
  128.                                                    Fp.x=Hlb
  129.                               Hlb=-1
  130.                               FP:Point = Point(Point.Point_List.First())
  131.                               Entrys=Entrys+1
  132.                          EndIf
  133.                     EndIf
  134.                     If Rx<=ImW-1 and HitR=False
  135.         Local           CColR=Image.ReadPixel(Rx,Fp.y)
  136.                          If CColR=BCol
  137.                               Image.WritePixel Rx,Fp.y,RCol
  138.                               If Fp.y>0
  139.                                    CColR=Image.ReadPixel(Rx,Fp.y-1)
  140.                                    If CColR=BCol
  141.                                         Hrt=Rx
  142.                                    Else
  143.                                         If Hrt<>-1
  144.                                              y=Fp.y-1
  145.                                              FP:Point = New Point
  146.                                              Fp.y=y
  147.                                                                             Fp.x=Hrt
  148.                                              Hrt=-1
  149.                                              FP:Point = Point(Point.Point_List.First())
  150.                                              Entrys=Entrys+1
  151.                                         EndIf
  152.                                    EndIf
  153.                               EndIf
  154.                               If Fp.y<ImH-1
  155.                                    CColR=Image.ReadPixel(Rx,Fp.y+1)
  156.                                    If CColR=BCol
  157.                                         Hrb=Rx
  158.                                    Else
  159.                                         If Hrb<>-1
  160.                                              y=Fp.y+1
  161.                                              FP:Point = New Point
  162.                                              Fp.y=y
  163.                                                                             Fp.x=Hrb
  164.                                              Hrb=-1
  165.                                              FP:Point = Point(Point.Point_List.First())
  166.                                              Entrys=Entrys+1
  167.                                         EndIf
  168.                                    EndIf
  169.                               EndIf
  170.                               Rx=Rx+1
  171.                          Else
  172.                               HitR=True
  173.                               If Hrt<>-1
  174.                                    y=Fp.y-1
  175.                                    FP:Point = New Point
  176.                                    Fp.y=y
  177.                                                            Fp.x=Hrt
  178.                                    Hrt=-1
  179.                                    FP:Point = Point(Point.Point_List.First())
  180.                                    Entrys=Entrys+1
  181.                               EndIf
  182.                               If Hrb<>-1
  183.                                    y=Fp.y+1
  184.                                    FP:Point = New Point
  185.                                    Fp.y=y
  186.                                                            Fp.x=Hrb
  187.                                    Hrb=-1
  188.                                    FP:Point = Point(Point.Point_List.First())
  189.                                    Entrys=Entrys+1
  190.                               EndIf
  191.                          EndIf
  192.                     Else
  193.                          HitR=True
  194.                          If Hrt<>-1
  195.                               y=Fp.y-1
  196.                               FP:Point = New Point
  197.                               Fp.y=y
  198.                                                    Fp.x=Hrt
  199.                               Hrt=-1
  200.                               FP:Point = Point(Point.Point_List.First())
  201.                               Entrys=Entrys+1
  202.                          EndIf
  203.                          If Hrb<>-1
  204.                               y=Fp.y+1
  205.                               FP:Point = New Point
  206.                               Fp.y=y
  207.                                                  Fp.x=Hrb
  208.                               Hrb=-1
  209.                               FP:Point = Point(Point.Point_List.First())
  210.                               Entrys=Entrys+1
  211.                          EndIf
  212.                     EndIf
  213.                    
  214.                Until (HitR=True And HitL=True) or KeyHit(1)
  215.                FP:Point=Point(Point.Point_List.First())
  216.                Point.Point_List.Remove(FP)
  217.                Entrys=Entrys-1  
  218.              
  219.                
  220.           Until Entrys=False or KeyHit(1)
  221.      EndIf
  222.                
  223.         Local     mhit=False
  224.                   DebugLog (Float(MilliSecs()-TimeIt)/1000)+" seconds"
  225.  
  226. End Function
  227.  
  228. Graphics 800,600,0,-1
  229.  
  230.  
  231.  
  232. SetColor 255,0,255
  233.  
  234. DrawOutline(200,100,400,200)
  235.  
  236. Local Test:TPixmap = GrabPixmap(0,0,800,600)
  237.  
  238. FloodFill($FFff00ff,0,599,Test)
  239.  
  240. DrawPixmap (Test,0,0)
  241.  
  242. Flip
  243.  
  244. WaitKey()
  245.  
  246. Function DrawOutline(x1:Int, y1:Int, w1:Int, h1:Int,_b:Int = 1)
  247.         DrawRect x1, y1, w1 - _B, _B
  248.         DrawRect x1, y1, _B, h1
  249.         DrawRect x1 + w1 - _B, y1, _B, h1
  250.         DrawRect x1, y1 + h1, w1 , _B
  251. End Function


Comments :


mulawa1(Posted 1+ years ago)

 Great work - just what I needed - thanks for sharing!Peter


big10p(Posted 1+ years ago)

 The 'non recursive' part of the title is somewhat redundant since flood fill algo's should never be recursive. :)


Sonic(Posted 1+ years ago)

 i need help speeding this up, it is too slow for a paint package i'm writing. my only thought is to preallocate all points (up to the maximum size of the canvas)?  any thoughts?


 

SimplePortal 2.3.6 © 2008-2014, SimplePortal