Summed Area Table Implementation

Bulletin Board
, ,
#1

Not a question, but just some help for whoever sees this down the line, as no Lua implementation of this algorithm exists to my knowledge.

Links describing what summed area is and some ideas of where to implement:

  1. https://stackoverflow.com/questions/45670761/algorithm-for-placing-rectangle-with-certain-size-into-free-area-in-matrix

  2. https://www.geeksforgeeks.org/submatrix-sum-queries/

Lua Implementation

function createSummedAreaTable( inputTable ) -- O( m * n )

	-- Reduce values in the input to boolean 0 or 1's if they are not integers
	local summableTable = {}
	for rowIndex, row in ipairs( inputTable ) do
		summableTable[rowIndex] = {}
		for colIndex, cell in ipairs( row ) do
			if type( cell ) == "number" then
				summableTable[rowIndex][colIndex] = cell
			else 
				summableTable[rowIndex][colIndex] = cell and 1 or 0
			end
		end
	end
	
	-- Make an auxiliary table the size of the summableTable to hold calculated sums
	local auxTable = {} 
	for i = 1, #summableTable, 1 do
		auxTable[i] = {}
	end
	
	-- Copy first row of summableTable to the auxTable
	for i = 1, #summableTable[1], 1 do
		auxTable[1][i] = matrixTable[1][i]
	end
	
	-- Column wise sum
	for i = 2, #matrixTable, 1 do
		for j = 1, #matrixTable[1], 1 do
			auxTable[i][j] = matrixTable[i][j] + auxTable[i-1][j]
		end
	end
	
	-- Row wise sum
	for i = 1, #matrixTable, 1 do
		for j = 2, #matrixTable[1], 1 do
			auxTable[i][j] = auxTable[i][j] + auxTable[i][j-1]
		end
	end
	
	return auxTable
end

function computeSummedArea( auxTable, topLeftX, topLeftY, botRightX, botRightY ) -- O( 1 )
	-- result equals sum of elements between (1, 1) and (botRightX, botRightY)
	local result = auxTable[botRightY][botRightX]
	
	-- Remove value between (1, 1) and (botRightX, topLeftY - 1)
	if topLeftY > 1 then
		result = result - auxTable[topLeftY - 1][botRightX]
	end
	
	-- Remove value between (1, 1) and (botRightY, topLeftX - 1)
	if topLeftX > 1 then
		result = result - auxTable[botRightY][topLeftX - 1]
	end
	
	-- Add aux[topLeftY -1][topLeftX - 1] as elements between (0, 0) and (topLeftX - 1, topLeftY - 1) are subtracted twice
	if topLeftX > 1 and topLeftY > 1 then
		result = result + auxTable[topLeftY - 1][topLeftX - 1]
	end
	
	-- Final value of rectangle in area between inputed coordinates
	return result
end

How to Use

local exampleTable = { -- An object[3][4] array
	{1, 0, 1, 1},
	{0, 1, 2, -9},
	{true, false, {object = ""}, nil}, -- Values reduced to {1, 0, 1, 0} in sum value calculation
}

local summedAreaTable = createSummedAreaTable( exampleTable )

-- Using summedAreaTable you can call
computeSummedArea( summedAreaTable, 1, 1, 4, 3 )
-- With any value between (1, 1) and (4, 3)
1 Like
#2

Not sure when anybody would use this but thanks. Also I recommend maybe putting this in #bulletin-board or #resources:community-resources ources or #resources:community-tutorials.