0

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!

Jason Aller
  • 3,541
  • 28
  • 38
  • 38
Hannes F
  • 339
  • 2
  • 11

0 Answers0