get("#349") -- table functions
get("#121") -- compareTables
get("#348") -- bright and rgb

maxSize = {width=100, height=50}
minSize = {width=4, height=4}
threshold = 0.5
wandSize = 3 -- magic wand size

local rectangles, _img

function cloneRectangle(r)
  return newRectangle(r.x, r.y, r.width, r.height)
end

function newRectangle(x, y, w, h)
  return {x=x, y=y, width=w, height=h}
end

function contains(r, x, y)
  return x >= r.x and y >= r.y and x < r.x+r.width and y < r.y+r.width
end

function nextX(x, y)
  for r, _ in pairs(rectangles) do
    pTests = pTests+1
    if contains(r, x, y) then
      return r.x+r.width
    end
  end
  return nil
end

pDuplicate, pNew, pSeen, pNotSeen, pTests = 0, 0, 0, 0, 0

-- returns rectangle
function magicWand(image, x, y)
  if image ~= _img then
    _img, rectangles = image, {}
  end
  local nx = nextX(x, y)
  if nx ~= nil then
    pSeen = pSeen+1
    return nil, nx
  end
  pNotSeen = pNotSeen+1
  local r = newRectangle(x, y, 1, 1)
  
  while true do
    local last = cloneRectangle(r)
    expandLeft(image, r)
    if tooLarge(r) then return nil end
    expandTop(image, r)
    if tooLarge(r) then return nil end
    expandRight(image, r)
    if tooLarge(r) then return nil end
    expandBottom(image, r)
    if tooLarge(r) then return nil end    
    if compareTables(last, r) then
      if r.width >= minSize.width and r.height >= minSize.width then
        if rectangles[r] then
          pDuplicate = pDuplicate+1
        else
          pNew = pNew+1
          rectangles[r] = true
        end
        return r
      else
        return nil
      end
    end
  end
end

function tooLarge(r)
  return maxSize ~= nil and (r.width > maxSize.width or r.height > maxSize.height)
end

function expandLeft(image, r)
  local newX = math.max(r.x - wandSize, 0)
  if newX == r.x then return end
  newX = searchFromLeft(image, newRectangle(newX, r.y, r.x-newX, r.height))
  r.width = r.width+r.x-newX
  r.x = newX
end

function searchFromLeft(image, r)
  for x = r.x, r.x+r.width-1 do
    if regionNotEmpty(image, newRectangle(x, r.y, 1, r.height)) then
      return x
    end
  end
  return r.x+r.width
end

function expandRight(image, r)
  local newX = math.min(r.x + r.width + wandSize, image.width)
  if newX == r.x+r.width then return end
  newX = searchFromRight(image, newRectangle(r.x+r.width, r.y, newX-(r.x+r.width), r.height))
  r.width = newX-r.x
end

function searchFromRight(image, r)
  for x = r.x+r.width-1, r.x, -1 do
    if regionNotEmpty(image, newRectangle(x, r.y, 1, r.height)) then
      return x+1
    end
  end
  return r.x
end

function expandTop(image, r)
  local newY = math.max(r.y - wandSize, 0)
  if newY == r.y then return end
  newY = searchFromTop(image, newRectangle(r.x, newY, r.width, r.y-newY))
  r.height = r.height+r.y-newY
  r.y = newY
end

function searchFromTop(image, r)
  for y = r.y, r.y+r.height-1 do
    if regionNotEmpty(image, newRectangle(r.x, y, r.width, 1)) then
      return y
    end
  end
  return r.y+r.height
end

function expandBottom(image, r)
  local newY = math.min(r.y + r.height + wandSize, image.height)
  if newY == r.y+r.height then return end
  newY = searchFromBottom(image, newRectangle(r.x, r.y + r.height, r.width, newY-(r.y+r.height)))
  r.height = newY-r.y
end

function searchFromBottom(image, r)
  for y = r.y+r.height-1, r.y, -1 do
    if regionNotEmpty(image, newRectangle(r.x, y, r.width, 1)) then
      return y+1
    end
  end
  return r.y
end

-- we're looking for dark pixels this time
function regionNotEmpty(image, r)
  --return image.clip(rectangle).anyPixelBrighterThan(threshold)
  for y=r.y, r.y+r.height-1 do
    for x=r.x, r.x+r.width-1 do
      if bright(rgb(image.getInt(x, y))) < threshold then
        return true
      end
    end
  end
  return false
end


function recttostring(r)
  return r.x..", "..r.y..", "..r.x+r.width..", "..r.y+r.height
end

function magicWandAll(image)
  local allrects = {}

  for y = 0, image.height-1, 2 do
    for x = 0, image.width-1, 2 do
      local r, nx = magicWand(image, x, y)
      
      if r then
        allrects[recttostring(r)] = true
      elseif nx ~= nil then
        x = nx
        if x%2 == 1 then x=x+1 end -- get to 2-boundary
        x=x-2 -- counteract loop increment
      end
    end
  end
  
  return allrects
end

allrects = magicWandAll(img)

result = table.concat(keystolist(allrects), "|")
if result ~= '' then
  return "Magic Wand All (optimizing): "..result
end

Began life as a copy of #400