I need to find an algorithm to find a rectangle inside of a regular grid with missing points. so for example I have a grid which looks like this:
X X
+------------+
| X X X X |
| |
| X X X X | X
| |
X | X X X X |
+------------+
X
where I have 16 points, and they are all on a grid of 1x1. structured they look like this in the array:
[
{x:0, y:1},
{x:1, y:0},
{x:1, y:1},
{x:1, y:2},
{x:1, y:3},
{x:1, y:4},
{x:2, y:1},
{x:2, y:2},
{x:2, y:3},
{x:2, y:4},
{x:3, y:1},
{x:3, y:2},
{x:3, y:3},
{x:4, y:1},
{x:4, y:2},
{x:4, y:3},
{x:5, y:2},
]
how would I find the rectangle which is completely full? so I mean which has the most like the one shown in the ascii graphic?
I tried to do something like that, but it only gives me the length of each row, without knowing if there is one missing in the beginning or not. so I guess its not the right approach.
function calculateRowAndColumnLengths(array: { x: number, y: number }[]) {
let maxRow = -1;
let maxColumn = -1;
for (const item of array) {
if (item.x > maxRow) {
maxRow = item.x;
}
if (item.y > maxColumn) {
maxColumn = item.y;
}
}
const rowLengths: number[] = new Array(maxRow + 1).fill(0);
const columnLengths: number[] = new Array(maxColumn + 1).fill(0);
for (const item of array) {
rowLengths[item.x]++;
columnLengths[item.y]++;
}
return { rowLengths, columnLengths };
}
maybe there is a name for this problem? or how would I solve it? Thanks a lot for help!