Fixed-size squares packing on a grid with obstacles
I'm searching for an algorithm that would find all non-overlapping squares of given size in a grid with obstacles. All squares must have the same size, which would be given as one of the inputs.
Example grid with black cells representing empty space and red cells representing obstacles. Next is an example solution with multiple 5x5 yellow squares found in the grid:
What I have so far is an algorithm that finds biggest square using dynamic programming, but I don't know if it will be useful for the above problem. Maybe it could be modified to find multiple squares.
var width = 10, height = 10;
var grid = new Array(width * height);
var sizes = new Array(width * height);
function findBiggestSquare() {
var bestSize = -1, bestLocation = -1;
for (var i = grid.length - 1; i >= 0; i--) {
var size = 0;
if (grid[i] === 0) {
size = 1 + Math.min(sizes[i+1], sizes[i+width], sizes[i+1+width]);
if (size > bestSize) {
bestSize = size;
bestLocation = i;
}
}
sizes[i] = size;
}
if (bestLocation !== -1)
return {'size': bestSize, 'location': bestLocation};
else
return null;
}
algorithm matrix language-agnostic dynamic-programming
asked Nov 26 '18 at 11:29
HankMoodyHankMoody
2,1811029
add a comment |
I'm searching for an algorithm that would find all non-overlapping squares of given size in a grid with obstacles. All squares must have the same size, which would be given as one of the inputs.
Example grid with black cells representing empty space and red cells representing obstacles. Next is an example solution with multiple 5x5 yellow squares found in the grid:
What I have so far is an algorithm that finds biggest square using dynamic programming, but I don't know if it will be useful for the above problem. Maybe it could be modified to find multiple squares.
var width = 10, height = 10;
var grid = new Array(width * height);
var sizes = new Array(width * height);
function findBiggestSquare() {
var bestSize = -1, bestLocation = -1;
for (var i = grid.length - 1; i >= 0; i--) {
var size = 0;
if (grid[i] === 0) {
size = 1 + Math.min(sizes[i+1], sizes[i+width], sizes[i+1+width]);
if (size > bestSize) {
bestSize = size;
bestLocation = i;
}
}
sizes[i] = size;
}
if (bestLocation !== -1)
return {'size': bestSize, 'location': bestLocation};
else
return null;
}
algorithm matrix language-agnostic dynamic-programming
asked Nov 26 '18 at 11:29
HankMoodyHankMoody
2,1811029
add a comment |
I'm searching for an algorithm that would find all non-overlapping squares of given size in a grid with obstacles. All squares must have the same size, which would be given as one of the inputs.
Example grid with black cells representing empty space and red cells representing obstacles. Next is an example solution with multiple 5x5 yellow squares found in the grid:
What I have so far is an algorithm that finds biggest square using dynamic programming, but I don't know if it will be useful for the above problem. Maybe it could be modified to find multiple squares.
var width = 10, height = 10;
var grid = new Array(width * height);
var sizes = new Array(width * height);
function findBiggestSquare() {
var bestSize = -1, bestLocation = -1;
for (var i = grid.length - 1; i >= 0; i--) {
var size = 0;
if (grid[i] === 0) {
size = 1 + Math.min(sizes[i+1], sizes[i+width], sizes[i+1+width]);
if (size > bestSize) {
bestSize = size;
bestLocation = i;
}
}
sizes[i] = size;
}
if (bestLocation !== -1)
return {'size': bestSize, 'location': bestLocation};
else
return null;
}
algorithm matrix language-agnostic dynamic-programming
asked Nov 26 '18 at 11:29
HankMoodyHankMoody
2,1811029
I'm searching for an algorithm that would find all non-overlapping squares of given size in a grid with obstacles. All squares must have the same size, which would be given as one of the inputs.
Example grid with black cells representing empty space and red cells representing obstacles. Next is an example solution with multiple 5x5 yellow squares found in the grid:
What I have so far is an algorithm that finds biggest square using dynamic programming, but I don't know if it will be useful for the above problem. Maybe it could be modified to find multiple squares.
var width = 10, height = 10;
var grid = new Array(width * height);
var sizes = new Array(width * height);
function findBiggestSquare() {
var bestSize = -1, bestLocation = -1;
for (var i = grid.length - 1; i >= 0; i--) {
var size = 0;
if (grid[i] === 0) {
size = 1 + Math.min(sizes[i+1], sizes[i+width], sizes[i+1+width]);
if (size > bestSize) {
bestSize = size;
bestLocation = i;
}
}
sizes[i] = size;
}
if (bestLocation !== -1)
return {'size': bestSize, 'location': bestLocation};
else
return null;
}
algorithm matrix language-agnostic dynamic-programming
algorithm matrix language-agnostic dynamic-programming
asked Nov 26 '18 at 11:29
HankMoodyHankMoody
2,1811029
asked Nov 26 '18 at 11:29
HankMoodyHankMoody
2,1811029
edited Nov 26 '18 at 11:41
HankMoody
asked Nov 26 '18 at 11:29
HankMoodyHankMoody
2,1811029
asked Nov 26 '18 at 11:29
HankMoodyHankMoody
2,1811029
asked Nov 26 '18 at 11:29
HankMoodyHankMoody
2,1811029
2,1811029
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
You can easily find all the potential centers of such squares by checking for obstacles in each NxN portions of the grid. Some straightforward optimizations can be done. Here is your example with the potential centers in orange:
Although picking the central cell is easier to visualize, you may want to work with a corner. That way, you don't have to worry about the parity of N, and the rest might be more straightforward.
Once you have these highlighted cells, assign a number to each one equal to the number of other highlighted cells that would be unavailable if you put a square there. For example, if you have the list of potential top-left corners, the number assigned to one of them is the number of potential top-left corners in a 2*N-1 square centered on it.
Then, pick the cell with the lowest number to put a square on, and update the grid accordingly. Repeat until your list is empty.
answered Nov 26 '18 at 13:13
NelfealNelfeal
5,2221825
Create graph of cells with edges between intersecting cells and find maximum independant set.
– Ante
Nov 28 '18 at 20:18
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53480163%2ffixed-size-squares-packing-on-a-grid-with-obstacles%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
You can easily find all the potential centers of such squares by checking for obstacles in each NxN portions of the grid. Some straightforward optimizations can be done. Here is your example with the potential centers in orange:
Although picking the central cell is easier to visualize, you may want to work with a corner. That way, you don't have to worry about the parity of N, and the rest might be more straightforward.
Once you have these highlighted cells, assign a number to each one equal to the number of other highlighted cells that would be unavailable if you put a square there. For example, if you have the list of potential top-left corners, the number assigned to one of them is the number of potential top-left corners in a 2*N-1 square centered on it.
Then, pick the cell with the lowest number to put a square on, and update the grid accordingly. Repeat until your list is empty.
answered Nov 26 '18 at 13:13
NelfealNelfeal
5,2221825
Create graph of cells with edges between intersecting cells and find maximum independant set.
– Ante
Nov 28 '18 at 20:18
add a comment |
You can easily find all the potential centers of such squares by checking for obstacles in each NxN portions of the grid. Some straightforward optimizations can be done. Here is your example with the potential centers in orange:
Although picking the central cell is easier to visualize, you may want to work with a corner. That way, you don't have to worry about the parity of N, and the rest might be more straightforward.
Once you have these highlighted cells, assign a number to each one equal to the number of other highlighted cells that would be unavailable if you put a square there. For example, if you have the list of potential top-left corners, the number assigned to one of them is the number of potential top-left corners in a 2*N-1 square centered on it.
Then, pick the cell with the lowest number to put a square on, and update the grid accordingly. Repeat until your list is empty.
answered Nov 26 '18 at 13:13
NelfealNelfeal
5,2221825
Create graph of cells with edges between intersecting cells and find maximum independant set.
– Ante
Nov 28 '18 at 20:18
add a comment |
You can easily find all the potential centers of such squares by checking for obstacles in each NxN portions of the grid. Some straightforward optimizations can be done. Here is your example with the potential centers in orange:
Although picking the central cell is easier to visualize, you may want to work with a corner. That way, you don't have to worry about the parity of N, and the rest might be more straightforward.
Once you have these highlighted cells, assign a number to each one equal to the number of other highlighted cells that would be unavailable if you put a square there. For example, if you have the list of potential top-left corners, the number assigned to one of them is the number of potential top-left corners in a 2*N-1 square centered on it.
Then, pick the cell with the lowest number to put a square on, and update the grid accordingly. Repeat until your list is empty.
answered Nov 26 '18 at 13:13
NelfealNelfeal
5,2221825
You can easily find all the potential centers of such squares by checking for obstacles in each NxN portions of the grid. Some straightforward optimizations can be done. Here is your example with the potential centers in orange:
Although picking the central cell is easier to visualize, you may want to work with a corner. That way, you don't have to worry about the parity of N, and the rest might be more straightforward.
Once you have these highlighted cells, assign a number to each one equal to the number of other highlighted cells that would be unavailable if you put a square there. For example, if you have the list of potential top-left corners, the number assigned to one of them is the number of potential top-left corners in a 2*N-1 square centered on it.
Then, pick the cell with the lowest number to put a square on, and update the grid accordingly. Repeat until your list is empty.
answered Nov 26 '18 at 13:13
NelfealNelfeal
5,2221825
answered Nov 26 '18 at 13:13
NelfealNelfeal
5,2221825
answered Nov 26 '18 at 13:13
NelfealNelfeal
5,2221825
answered Nov 26 '18 at 13:13
NelfealNelfeal
5,2221825
5,2221825
Create graph of cells with edges between intersecting cells and find maximum independant set.
– Ante
Nov 28 '18 at 20:18
add a comment |
Create graph of cells with edges between intersecting cells and find maximum independant set.
– Ante
Nov 28 '18 at 20:18
Create graph of cells with edges between intersecting cells and find maximum independant set.
– Ante
Nov 28 '18 at 20:18
Create graph of cells with edges between intersecting cells and find maximum independant set.
– Ante
Nov 28 '18 at 20:18
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53480163%2ffixed-size-squares-packing-on-a-grid-with-obstacles%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
