I am currently attempting to calculate a specific type of set of locations within a grid. The problem at hand is related to a 2D packing optimization problem.
When packing items, I need to select a position (i,j) in the grid for the item. Due to the item size, several other positions in the grid could also be covered. Therefore I am in need of a set Qijc, which is the set of squares were placing an item c may cover position (i,j). For example if item c is sizes 2x2 the Qijc contains {(i,j),(i-1,j-1),(i-1,j),(i,j-1)}. If item c is in any of these positions.. position (i,j) is also covered.
I have the current working code. However, it brute forces the calculation and is extremely slow when hitting grid sizes of 150x400. I have been trying to optimize the code, and I believe that I am missing something simple. Any suggestions would be appreciated.
Currently, I store the information in a dictionary in order to have a "one-to-many" relationship. Another caveat to the problem is that I only store positions for item c, that would cover position (i,j) if the position is available in the network for item c.
In the given example, if item c = 3, and we are looking at position (4,3) the positions that would cover is (4,2) and (4,3), however, position (5,3) would also usually cover (4,3), however, is not stored as item c cannot go to this position. ( I hope this makes sense)
I believe that I have several redundant loops, and that it could be done in a much faster fashion, however, I struggle to wrap my head around it.
function validpositions(UnusuableSpace::Matrix{Int64}, nCargoes::Int64, SquaresL::Vector{Int64}, SquaresW::Vector{Int64})
# This function should return all position that are valid in the layout for
# cargo c in C. This should be returned as a tuple e.g. pos = [(1,1),(4,3),..,(18,1)].
N = []
for c in 1:nCargoesM
pos = Vector{Tuple{Int64,Int64}}()
for i in SquaresL[c]:size(UnusuableSpace)[1] # skip some of the rows. If the cargo has dimensions > 1.
for j in 1:size(UnusuableSpace)[2]
# Check if position includes a pillar / object
if UnusuableSpace[i,j] != 1
# Check if these is space for the cargo in the position.
if (i-SquaresL[c]) >= 0 && (j+SquaresW[c]-1) <= size(UnusuableSpace)[2]
# Check if position i,j covers an are with pillars in due to cargo
# dimensions.
if sum(UnusuableSpace[i-SquaresL[c]+1:i,j:j+SquaresW[c]-1]) == 0
push!(pos,(i,j))
end
end
end
end
end
push!(N,pos)
end
# return all valid positions of the cargo c.
return N
end # end valid position function
nCargoesM = 3
SquaresL = [1,2,3]
SquaresW = [1,2,2]
UnusableSpace = [
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 1 1 1 0 1 0 0 0
0 0 1 1 1 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0]
N = validpositions(UnusableSpace, nCargoesM, SquaresL, SquaresW)
function coveringSet(UnusableSpace::Matrix{Int64}, nCargoes::Int64, SquaresL::Vector{Int64}, SquaresW::Vector{Int64}, N)
Qijc = Dict{}()
for c in 1:nCargoesM
for i in 1:size(UnusableSpace)[1]
for j in 1:size(UnusableSpace)[2]
tmpset = []
for (k, l) in N[c]
# Get the points/nodes of the areas to check
vec1 = [i, j]
vec2 = [k-SquaresL[c]+1:k, l:l+SquaresW[c]-1]
tmp = [[x, y] for x in vec1[1], y in vec1[2]]
tpm = [[x, y] for x in vec2[1], y in vec2[2]]
# Check for overlapping
if sum([tmp in tpm for tmp = tmp]) > 0
push!(tmpset, [k, l])
end
end
push!(Qijc, [i, j, c] => tmpset)
end
end
end
return Qijc
end
Qijc = coveringSet(UnusableSpace, nCargoesM, SquaresL, SquaresW, N)
I actually solved this problem myself after some time. You can precompute all the keys in the dictionary and thread the loop. Checking the positioning of the cargo and whether it is a spot that is allowable.
function coveringSet_new_threaded(UnusableSpace, nCargoesM::Int64, SquaresL::Vector{Int64}, SquaresW::Vector{Int64})
# Create dictionary
Qijc4 = Dict{}()
for c in 1:nCargoesM
for i in 1:size(UnusableSpace)[1]
for j in 1:size(UnusableSpace)[2]
push!(Qijc4, [i, j, c] => [])
end
end
end
# Finding the combinations of cargo size
combinationsCargo = Vector{Tuple{Int64,Int64}}()
for i in 1:length(SquaresL)
push!(combinationsCargo, (SquaresL[i], SquaresW[i]))
end
# The unique combinations available
CargoTypes = unique(combinationsCargo)
Threads.@threads for c in 1:length(CargoTypes)
typeindx = findall(x -> x == CargoTypes[c], combinationsCargo)
# Index to control where to find information regarding squaresL and squaresW
sizeidx = typeindx[1]
#Threads.@threads for c in 1:nCargoesM
for i in 1:size(UnusableSpace)[1]
for j in 1:size(UnusableSpace)[2]
tmpset = []
# Generate the range of positions to check. (h,m) check if it also covers (i,j)
# due to cargo size.
for h in i:i+SquaresW[sizeidx]-1
for m in j-SquaresL[sizeidx]+1:j
# Check that the position is actually within the layout of the ship
if (h > 0 && m > 0 && h <= size(UnusableSpace)[1] && h <= size(UnusableSpace)[2])
# Check that the position is not unusable.
if UnusableSpace[h, m] != 1
# Check that the position given cargo size is withon the layout of the ship.
if (h - SquaresW[sizeidx]) >= 0 && (m + SquaresL[sizeidx] - 1) <= size(UnusableSpace)[2]
# Check that the cargo, when in position (h,m) does not collide with any unusable space.
if sum(UnusableSpace[h-SquaresW[sizeidx]+1:h, m:m+SquaresL[sizeidx]-1]) == 0
# Only then is it a position for cargo c that covers (i,j).
push!(tmpset, [h, m])
end
end
end
end
end
end
# Push in set for that position. It may be empty.
for k in typeindx
Qijc4[[i, j, k]] = tmpset
end
end
end
end
return Qijc4
end