December 04, 2020, 10:54:46 AM

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

#### 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
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
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
57.                          If CColL=BCol
58.                               Image.WritePixel Lx,Fp.y,RCol
59.                               If Fp.y>0
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
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
136.                          If CColR=BCol
137.                               Image.WritePixel Rx,Fp.y,RCol
138.                               If Fp.y>0
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
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

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