-
Notifications
You must be signed in to change notification settings - Fork 2
/
floodfill90.f90
executable file
·296 lines (242 loc) · 7.07 KB
/
floodfill90.f90
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
module floodfill90
private
public :: flood_fill
integer :: CON, NX, NY
logical :: SAVE_PIX
integer :: npix, npixmax, ncall
integer, dimension(:), allocatable :: X_PIX,Y_PIX
integer, dimension(:), allocatable :: xstack, ystack
integer :: nstack=-1, nstackmax=-1
contains
logical function pushpix(x,y)
implicit none
integer, intent(in) :: x,y
integer, dimension(:), allocatable :: wj
integer status
if (npix.eq.npixmax) then
npixmax = npixmax + 10000
allocate (wj(npixmax),stat=status)
if (status.ne.0) then
pushpix = .false.
return
endif
wj(1:npix)=X_PIX
call move_alloc(wj,X_PIX)
allocate (wj(npixmax),stat=status)
if (status.ne.0) then
pushpix = .false.
return
endif
wj(1:npix)=Y_PIX
call move_alloc(wj,Y_PIX)
endif
npix=npix+1
X_PIX(npix)=x
Y_PIX(npix)=y
pushpix = .true.
end function pushpix
logical function pop(x,y)
implicit none
integer, intent(out) :: x,y
if (nstack.le.0) then
pop = .false.
return
endif
x=xstack(nstack)
y=ystack(nstack)
nstack = nstack - 1
pop = .true.
return
end function pop
logical function push(x,y)
implicit none
integer, intent(in) :: x,y
integer, dimension(:), allocatable :: wj
integer status
if (nstack.lt.0) then ! this means we haven't allocated memory
nstack = 0
nstackmax = 10000
allocate(xstack(nstackmax),ystack(nstackmax))
endif
if (nstack.eq.nstackmax) then ! allocate more memory
nstackmax = nstackmax + 10000
allocate(wj(nstackmax),stat=status)
if (status.ne.0) then
push = .false.
return
endif
wj(1:nstack) = xstack
call move_alloc (wj,xstack)
allocate(wj(nstackmax),stat=status)
if (status.ne.0) then
push = .false.
return
endif
wj(1:nstack) = ystack
call move_alloc (wj,ystack)
endif
nstack = nstack + 1
xstack(nstack)=x
ystack(nstack)=y
push = .true.
return
end function push
subroutine clear_stack
if (allocated(xstack)) deallocate(xstack)
if (allocated(ystack)) deallocate(ystack)
nstack = -1
nstackmax = 0
end subroutine clear_stack
subroutine flood_fill_4 (mask,i,j,newval,val)
! http://lodev.org/cgtutor/floodfill.html
implicit none
integer, dimension(:,:), intent(inout) :: mask
integer, intent(in) :: i,j, newval, val
integer :: x,y,y1
logical :: spanLeft, spanRight
if(newval.eq.val) return ! avoid infinite loop
call clear_stack
if (mask(i,j).ne.val) return
x=i
y=j
if(.not.push(x, y)) then
return
endif
do while (pop(x,y))
y1 = y
do while (y1.ge.1 .and. mask(x,y1).eq.val)
y1 = y1 - 1
end do
y1 = y1 + 1
spanLeft = .false.
spanRight = .false.
do while (y1.le.NY .and. mask(x,y1).eq.val)
mask(x,y1) = newval
if (SAVE_PIX) then
if (.not.pushpix(x,y1)) then
return
endif
endif
if (.not.spanLeft .and. x.gt.1 .and. mask(x-1,y1) .eq.val) then
if (.not.push(x-1,y1)) return
spanLeft = .true.
else
if (spanLeft .and. x.gt.1 .and. mask(x-1,y1).ne.val) then
spanLeft = .false.
endif
endif
if(.not.spanRight .and. x.lt.NX .and. mask(x+1,y1) .eq. val) then
if(.not.push(x+1,y1)) return
spanRight = .true.
else
if (spanRight .and. x.lt.NX .and. mask(x+1,y1).ne.val) then
spanRight = .false.
endif
endif
y1=y1+1
enddo
enddo
call clear_stack
end subroutine flood_fill_4
subroutine flood_fill (mask, i0,j0, newval, val, connect,xpix,ypix)
integer, dimension(:,:), intent(inout) :: mask
integer, intent(in) :: i0,j0, newval, val
integer, intent(in), optional :: connect
integer, allocatable, dimension(:), intent(inout), optional :: xpix,ypix
NX = size(mask,1)
NY = size(mask,2)
if (present(connect)) then
CON = connect
else
CON = 4
endif
if (present(xpix).and.present(ypix)) then
npix=0
npixmax = 10000
allocate (X_PIX(npixmax),Y_PIX(npixmax))
SAVE_PIX = .true.
else
SAVE_PIX = .false.
endif
! write (0,*) i0,j0,newval,val,CON
! write (0,*) 'SAVE_PIX=',SAVE_PIX, present(xpix), present(ypix)
ncall = 0
if (CON.eq.4) then
call flood_fill_4 (mask,i0,j0,newval,val)
else
call floodfill_w_recursive (mask,i0,j0,newval,val)
endif
if (SAVE_PIX) then
if (allocated(xpix)) deallocate(xpix)
if (allocated(ypix)) deallocate(ypix)
allocate (xpix(npix),ypix(npix))
xpix=X_PIX(1:npix)
ypix=Y_PIX(1:npix)
deallocate (X_PIX,Y_PIX)
endif
end subroutine flood_fill
recursive subroutine floodfill_w_recursive (mask,i0,j0,newval,val)
implicit none
integer, dimension(:,:), intent(inout) :: mask
integer, intent(in) :: i0,j0, newval, val
integer :: color,x,y
integer, dimension(:), allocatable :: wj
ncall = ncall + 1
if (i0.lt.1.or.i0.gt.NX.or.j0.lt.1.or.j0.gt.NY) return
color = mask(i0,j0)
x = i0
y = j0
if (color.eq.val) then
do ! while (color == original_color) {
mask(x,y)=newval
if (SAVE_PIX) then
if (.not.pushpix(x,y)) return
endif
call floodfill_w_recursive (mask,x,y+1,newval,val)
call floodfill_w_recursive (mask,x,y-1,newval,val)
if (CON.eq.8) then
call floodfill_w_recursive (mask,x+1,y+1,newval,val)
call floodfill_w_recursive (mask,x+1,y-1,newval,val)
call floodfill_w_recursive (mask,x-1,y+1,newval,val)
call floodfill_w_recursive (mask,x-1,y-1,newval,val)
endif
x = x - 1
if (x.lt.1) exit
color = mask(x,y)
if (color.ne.val) exit
end do
x = i0 + 1
y = j0
if (x.le.NX) then
color = mask(x,y)
do
mask(x,y)=newval
if (SAVE_PIX) then
if (.not.pushpix(x,y)) return
endif
call floodfill_w_recursive (mask,x,y+1,newval,val)
call floodfill_w_recursive (mask,x,y-1,newval,val)
if (CON.eq.8) then
call floodfill_w_recursive (mask,x+1,y+1,newval,val)
call floodfill_w_recursive (mask,x+1,y-1,newval,val)
call floodfill_w_recursive (mask,x-1,y+1,newval,val)
call floodfill_w_recursive (mask,x-1,y-1,newval,val)
endif
x = x+1
if (x.gt.NX) exit
color = mask(x,y)
if (color.ne.val) exit
end do
end if
end if
end subroutine floodfill_w_recursive
end module floodfill90
subroutine flood_fill_77 (mask,nx,ny,i0,j0,newval,val)
use floodfill90
implicit none
integer, intent(in) :: nx,ny
integer, dimension(nx,ny), intent(inout) :: mask
integer, intent(in) :: i0,j0, newval, val
call flood_fill (mask,i0,j0,newval,val)
return
end subroutine flood_fill_77