vector_extras/adammil_flood_fill.lua

117 lines
1.9 KiB
Lua
Raw Permalink Normal View History

-- http://www.adammil.net/blog/v126_A_More_Efficient_Flood_Fill.html
local can_go
local marked_places
local function calc_2d_index(x, y)
return (y + 32768) * 65536 + x + 32768
end
local function mark(x, y)
marked_places[calc_2d_index(x, y)] = true
end
local _fill
local function fill(x, y)
if can_go(x, y) then
_fill(x, y)
end
end
local corefill
function _fill(x, y)
while true do
local ox = x
local oy = y
while can_go(x, y-1) do
y = y-1
end
while can_go(x-1, y) do
x = x-1
end
if x == ox
and y == oy then
break
end
end
corefill(x, y)
end
function corefill(x, y)
local lastcnt = 0
repeat
local cnt = 0
local sx = x
if lastcnt ~= 0
and not can_go(y, x) then
-- go right to find the x start
repeat
lastcnt = lastcnt-1
if lastcnt == 0 then
return
end
x = x+1
until can_go(x, y)
sx = x
else
-- go left if possible, and mark and _fill above
while can_go(x-1, y) do
x = x-1
mark(x, y)
if can_go(x, y-1) then
_fill(x, y-1)
end
cnt = cnt+1
lastcnt = lastcnt+1
end
end
-- go right if possible, and mark
while can_go(sx, y) do
mark(sx, y)
cnt = cnt+1
sx = sx+1
end
if cnt < lastcnt then
local e = x + lastcnt
sx = sx+1
while sx < e do
if can_go(sx, y) then
corefill(sx, y)
end
sx = sx+1
end
elseif cnt > lastcnt then
local ux = x + lastcnt + 1
while ux < sx do
if can_go(ux, y-1) then
_fill(ux, y-1)
end
ux = ux+1
end
end
lastcnt = cnt
y = y+1
until lastcnt == 0
end
local function apply_fill(go_test, x0, y0, allow_revisit)
if allow_revisit then
can_go = go_test
else
local visited = {}
can_go = function(x, y)
local vi = calc_2d_index(x, y)
if visited[vi] then
return false
end
visited[vi] = true
return go_test(x, y)
end
end
marked_places = {}
fill(x0, y0)
return marked_places
end
return apply_fill