Group rectangles in a grid

Question

I have a randomly-sliced rectangular grid - width is 80 unit.

I already have the free spaces of each row of my grid stored in an array like this below:

[
    {pX:1,sX:15},
    {pX:30,sX:13},
    {pX:43,sX:1},
    {pX:44,sX:17}
],
[
    {pX:1,sX:15},
    {pX:16,sX:14},
    {pX:30,sX:13},
    {pX:43,sX:1},
    {pX:44,sX:17}
]

where pX is the starting point and sX represent the width of each rectangle.

Some of the array entries are adjacent, i.e. pX[i]+sX[i] = pX[i+1]. How can i group these array entries together and get the resulting rectangles with the maximum adjacent width?

Can you post desired output? – Nenad Vracar Jul 19 '16 at 15:06 — Nenad Vracar, Jul 19 '16 at 15:06
@NenadVracar: `[{pX:1,sX:15},{pX:30,sX:31}],[{pX:1,sX:60}]` – deblocker Jul 19 '16 at 16:44 — deblocker, Jul 19 '16 at 16:44

score 0 · Accepted Answer · answered Jul 19 '16 at 15:56

You need to tighten arrays, joining adjacent segments. This code (Delphi, consider it as pseudocode) shrinks arrays in needed manner:

var
  pX, sX: TArray<Integer>;
  i, removed: Integer;
begin
  pX := [1, 30, 43, 44, 64, 66, 69, 72];
  sX := [15, 13, 1, 17, 2, 2, 3, 5];


  removed := 0;
  for i := 1 to High(pX) do begin
    if (pX[i - removed - 1] + sX[i - removed - 1] = pX[i]) then
    begin                ////join neighbors
      sX[i - removed - 1] := sX[i - removed - 1] + sX[i];
      Inc(removed);    ////removed++
    end
    else
    if (removed > 0) then
    begin                 ////copy to new place
      pX[i - removed] := pX[i];
      sX[i - removed] := sX[i];
    end;
  end;

  ////shorten array, remove tail
  SetLength(px, Length(pX) - removed);
  SetLength(sX, Length(sX) - removed);

  ////output result
  Memo1.Lines.Add(ArrayToString(pX));
  Memo1.Lines.Add(ArrayToString(sX));

output

1 30 64 69 
15 31 4 8

Yes!!! "Tighten", not "joining" is the right way here! Many thanks for the pitch to the TurboPascal-time. — deblocker, Jul 19 '16 at 16:57

Group rectangles in a grid

1 Answers1

Linked