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