Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

I have a big grid (indicated on the image in grey) that is divided in several blocks (each with a maximum width of 3 units). Now I would like to divide a region (indicated on the grid in red) by the corresponding blocks.

enter image description here

To give an example, I would like the 'block regions' (represented {X,Y,Width,Height}):

A: {2,3,2,1} B: {4,3,3,1} C: {7,3,1,1} D: {2,4,2,3} ... The only information that I have is the size of the blocks in the grid (in this case 3) and the dimensions of the region: {2,3,6,5} (= {X,Y, width, height})

Does anybody know how to do this in an efficient way? I thought about the use of mround to calculate the first boundaries of the blocks, but that lead to a dead end. Thanks in advance!

share|improve this question
    
What is mround? –  belisarius Apr 5 '13 at 16:36
    
mround is a function used in excel, it returns a number rounded to the desired multiple. i.e. mround(10,3) = 9 –  Consec Apr 5 '13 at 16:39
1  
Are you aware that this site is about a particular software product (Mathematica (TM))? –  belisarius Apr 5 '13 at 16:46
    
I think this is an interesting question. Even if it was not intended as a Mathematica question let's not close it but rather write it such that it is. –  Mr.Wizard Apr 5 '13 at 17:32
    
Cross-posted: math.stackexchange.com/q/352262 –  rm -rf Apr 6 '13 at 3:09
show 1 more comment

3 Answers

I thought it could be easier using IntegerPartitions[], but suddenly the code got convoluted.

part[r_] := 
   Module[{d},
     d = IntegerPartitions[#, All, Range@3, 1][[1]] & /@ r[[3 ;; 4]];
     Flatten/@Transpose@{Tuples[r[[#]]+Most@FoldList[Plus,0,d[[#]]] & /@ {1, 2}], Tuples@d}]

part[{2, 3, 6, 5}]
(*
{{2, 3, 3, 3}, {2, 6, 3, 2}, {5, 3, 3, 3}, {5, 6, 3, 2}}
*)
part[{2, 3, 7, 9}]
(*
{{2, 3, 3, 3}, {2, 6, 3, 3}, {2, 9, 3, 3}, {5, 3, 3, 3}, 
 {5, 6, 3, 3}, {5, 9, 3, 3}, {8, 3, 1, 3}, {8, 6, 1, 3}, {8, 9, 1, 3}}
*)

Edit

A plotting function, just for completeness:

rect[{x_, y_, w_, h_}] := Rectangle[{x, -y - h}, {x + w, -y}]
plotrects[{x_, y_, w_, h_}] := 
 Graphics[{FaceForm[White], EdgeForm[Black],  rect /@ part[{x, y, w, h}]}, Axes -> True, 
           PlotRange -> {{x - 3, x + w + 3}, {-y - h - 3, -y + 3}}]
plotrects[{2, 3, 6, 5}]
share|improve this answer
    
Where do we specify the block size in this code? –  Mr.Wizard Apr 6 '13 at 1:09
    
@Mr.Wizard I nailed it with Range@3. Do you think the OP wants it as a parameter? –  belisarius Apr 6 '13 at 1:43
    
Yes, because he said "in this case 3" but I was more interested comparing it myself. By the way I don't think your input and output format is the same as described in the question but that may not matter if it's not a Mathematica question anyway. –  Mr.Wizard Apr 6 '13 at 3:30
add comment

EDIT: Mr. Wizard's comment just made me realize that my blocks start at (0,0). The conversion to (1,1) blocks is obvious, but it only makes the calculations less readable. I've changed the graphics to show where the blocks are.

Not very pretty, but simple:

blockWidth = 3;
{x1, y1, x2, y2} = rect = {2, 3, 2 + 6, 3 + 5};

clippedRects = Table[
   {
    {
     Clip[x1, {x, x + blockWidth}],
     Clip[y1, {y, y + blockWidth}]
     },
    {
     Clip[x2, {x, x + blockWidth}],
     Clip[y2, {y, y + blockWidth}]
     }
    },
   {x, Floor[x1, blockWidth], Ceiling[x2, blockWidth] - 1, blockWidth},
   {y, Floor[y1, blockWidth], Ceiling[y2, blockWidth] - 1, 
    blockWidth}];

Displaying the results:

gridLines = {#, {Gray, If[Mod[#, 3] == 0, Dashed, Dotted]}} & /@ 
   Range[0, 9];
Graphics[{Transparent, EdgeForm[Red], 
  Rectangle[{x1, y1} - .1, {x2, y2} + .1], EdgeForm[Black], 
  Rectangle @@@ Flatten[clippedRects, 1],}, Axes -> True, 
 AxesOrigin -> {0, 0}, Ticks -> {Range[0, 9, 3], Range[0, 9, 3]}, 
 GridLines -> {gridLines, gridLines}]

enter image description here

share|improve this answer
    
This doesn't show the nine regions illustrated in the question. Why? –  Mr.Wizard Apr 6 '13 at 1:11
    
nikie, I'm not trying to be a pest, but I still see six regions in your output rather than nine. Am I missing something? –  Mr.Wizard Apr 6 '13 at 9:37
    
@Mr.Wizard I fail to understand you. What do you want to compare? There are a lot of ways to partition a rectangular area and the OP hasn't asked for a particular algorithm. I think I'm missing something ... –  belisarius Apr 6 '13 at 10:42
    
@belisarius I am expecting a function that takes the OP's data: "The only information that I have is the size of the blocks in the grid (in this case 3) and the dimensions of the region: {2,3,6,5} (= {X,Y, width, height})" and outputs the nine regions in the {X,Y,w,h} format. Yes, someone's missing something, but I don't have the audacity to suggest it's not me. :-) –  Mr.Wizard Apr 6 '13 at 13:06
    
@Mr.Wizard Oh, well. I think it's enough for an OT, underspecified and probably Excel related question. I'm not voting to close just because you requested it. –  belisarius Apr 6 '13 at 13:17
show 1 more comment

Not terribly efficient, but here's a start:

f1[b_] := SplitBy[Range@# + #2, Ceiling[#, b] &] &;

f2[p_List] := Join[p[[All, 1]], Length /@ p]

f3[block_, {x_, y_, w_, h_}] :=
 f2 /@ Tuples@MapThread[f1[block], {{w, h}, {x, y} - 1}]

f3[3, {2, 3, 6, 5}]
{{2, 3, 2, 1}, {2, 4, 2, 3}, {2, 7, 2, 1}, {4, 3, 3, 1}, {4, 4, 3, 3},
 {4, 7, 3, 1}, {7, 3, 1, 1}, {7, 4, 1, 3}, {7, 7, 1, 1}}

Here's a faster, if more opaque, f1 function:

f1[b_] := Partition[Range@# + #2, b, b, {Mod[#2, b] + 1, -b}, {}] &
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.