CODEWITHSUNDEEP
algorithm
FearLeslie
FearLeslie

Reputation: 41

Calculate cell dimensions given the positions in a finite grid

I did a search on whether this has been asked before but I could not find any similar question. This is more of a algorithmic question and is not confined to any particular programming language. So, my question is as follows.

Data given:

  1. A rectangular grid, 'G' of fixed width and height: (W, H).
  2. An array, 'A1', of absolute positions of 'n' blocks in the grid: A1 = [(x0, y0), (x1, y1), ..., (xn-1, yn-1)].
  3. Each and every block in the array is a simple rectangle with 4 edges.
  4. The sum of areas of all the blocks in the array 'A1' = total area of the grid 'G', in other words, the array 'A1' has as many blocks as it takes to fill the entire grid 'G'.
  5. The positions in the array 'A1' are not arranged in any particular order.
  6. Position values represent upper-left corners of the blocks.
  7. None of the blocks overlap.

Problem: Calculate size(width and height) of each block. i.e., calculate (w0, h0), (w1, h1), ..., (wn-1, hn-1).

I feel this problem can be generalized to a space of any dimension.

Upvotes: 2

Views: 91

Answers (1)

j_random_hacker
j_random_hacker

Reputation: 51316

I see now that you are looking for a way to partition the grid into rectangular blocks having given upper-left corners. However, in general there is still more than one way to do this. E.g. given the 3 upper-left corners A, B and C in the 4x4 grid on the left below, either of the two sets of blocks to its right solves the problem:

A.B.    AaBb    AaBb
....    aabb    aabb
C...    Ccbb    Cccc
....    ccbb    cccc

You can make a larger grid from as many copies of this grid as you like. A grid made from k copies (and thus using 3k blocks) will have 2^k distinct solutions.

Also, a particular problem instance need not have any solution. For example, at least one grid square is left uncovered by the problem instance on the left:

A.      Aa      A.
.B      .B      aB

Upvotes: 1

Related Questions