get("#121") -- compareTables

get("#348") -- bright and rgb

maxSize = {width=100, height=50}

minSize = {width=4, height=4}

threshold = 0.5

wandSize = 2 -- 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 seen(x, y)

  for r, _ in pairs(rectangles) do

    if contains(r, x, y) then

      return true

    end

  end

return false

end

-- returns rectangle

function magicWand(image, x, y)

  if image ~= img then

    img, rectangles = image, {}

  end

  if seen(x, y) then return nil end

  local r = newRectangle(x, y, 1, 1)

  while true do

    local last = cloneRectangle(r)

    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

        rectangles[r] = true

        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 = magicWand(image, x, y)

      if r then

        allrects[recttostring(r)] = true

      end

    end

  end

  return allrects

end