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.

You have a rectangle and it is diagonal. How many squares will be crossed by the diagonal (I guess assuming the side length of the rectangle are nice whole numbers)

I've seen an implementation in Geogebra to shade in the squares that are crossed by the diagonal of a rectangle. I'd really be happy to see how to do this using Mathematica, it would help me learn a lot. But it's beyond me right now.

Here is my "start"....

Manipulate[ Module[{length, width},

    length = Round[p[[1]]];
    width = Round[p[[2]]];

    Graphics[{

    {GrayLevel[0.8], 
     Line /@ Table[{{i, 0}, {i, 20}}, {i, 0, 20}],
     Line /@ Table[{{0, i}, {20, i}}, {i, 0, 20}]},

    (*rectangle to mark off area*)
    {Line[{{0, 0}, {Round[p[[1]]], 
        0} , Round[p], {0, Round[p[[2]]]}, {0, 0}}]},

    (*point to control rectangle*)
    {Blue, AbsolutePointSize[8], 
     Point[Round[p]]},

    (*diagonal*)
    Line[{{0, 0}, Round[p]}]

    },

   PlotRange -> {{-0.1, 20.1}, {-0.1, 20.1}},
   ImageSize -> {800, 640}]],
 {{p, {1, 1}}, {0, 0}, {20, 20}, Locator, Appearance -> None}
]

Mathematica graphics

Any help would be appreciated.

share|improve this question
    
NOTE, the actual number of squares crossed by the diagonal can be found (pretty sure...!) using length + width - GCD [length, width] but I am sure there are other ways... –  Tom De Vries Apr 18 '12 at 23:13
1  
I created a Demonstration with Stephen a long time ago. It will be useful. It handles both discreet and anti-aliasing (weighted) cases. –  Yu-Sung Chang Apr 19 '12 at 2:57
add comment

4 Answers

up vote 8 down vote accepted

You could do something like this

Manipulate[
 DynamicModule[{ptlst, height, length},
  {length, height} = Round[pt];
  ptlst = 
   Floor[1 + {height, length} #] & /@ 
    MovingAverage[
     Union@Join[Range[0, 1, 1/length], Range[0, 1, 1/height]], 2];
  Show[ArrayPlot[SparseArray[Thread[ptlst -> 1]], Mesh -> True, 
    MeshStyle -> Gray, DataReversed -> True],
   Graphics[{Red, Line[{{0, height}, {length, 0}}]}],
   PlotRange -> {{-1, 21}, {-1, 21}},
   GridLines -> {Range[0, 21], Range[0, 21]},
   GridLinesStyle -> LightGray]],
 {{pt, {10, 10}}, {1, 1}, {20, 20}, {1, 1}, Locator}
 ]

screenshot

Explanation of the code

We're representing the squares in the rectangle by an array of 0's and 1's. We're assuming that the rectangle has dimensions {length, height} and is aligned with the origin. The array is such that the unit square with lower left corner {k,l} corresponds to the element at index {l + 1, k + 1} in the array (the reversal of indices is because ArrayPlot plots an m by n array as a n by m rectangle).

The diagonal from {0,0} to {length, height} can be parameterized by {length, height} t where 0<=t<=1. To find all squares that are intersected by this diagonal, we first calculate the intersection points of the diagonal with the grid, i.e. we find a list of values for t such that either length t or height t is an integer. For two consecutive elements in this list, t0 and t1, the line segment from {length, height} t0 to {length, height} t1 will lie completely within one unit square. The coordinates of the lower left corner of this square are equal to Floor[{height, length} (t0+t1)/2] which corresponds to the element at index 1 + Floor[{length, height} (t0+t1)/2] in the array.

share|improve this answer
    
So much better than what I was writing –  Rojo Apr 18 '12 at 22:42
    
Thanks so much, that's exactly what I needed. I see so many things that will help my attempt to be better. I don't follow how you formed the pt list, but I'll try to break that down. Thanks for answering my question!! –  Tom De Vries Apr 18 '12 at 22:45
    
@TomDeVries I've added a bit of explanation about how I'm calculating the indices of the squares. –  Heike Apr 19 '12 at 9:13
    
Thanks for taking the extra time to do that. I learn the most when I can see an approach for a problem I actually wanted to solve... –  Tom De Vries Apr 20 '12 at 2:38
add comment

I was trying to answer this question, and i came up with the following related thing.

I was in doubt to post it, but I think is a "curious" way to count the squares that have been split by the diagonal by using image processing:

c[x_, y_] :=
 Module[{d = .03}, 
  MorphologicalComponents@ColorNegate@Rasterize@
     Graphics[{Black, Table[Rectangle[(1 + d) {i,j}],{i, 0, x - 1}, {j, 0, y - 1}], 
               White, Thickness[d/4], Line[{{0, 0}, {x + (x - 1) d, y + (y - 1) d}}]}]]

So

c[4, 5] // Colorize

enter image description here

hence you can define:

countDividedSquares[x_, y_] := Max@
  Module[{d = .03}, 
    MorphologicalComponents@ColorNegate@Rasterize@
    Graphics[{Black, Table[Rectangle[(1 + d) {i,j}], {i, 0, x - 1}, {j, 0, y - 1}],
              White, Thickness[d/4], Line[{{0, 0}, {x + (x - 1) d, y + (y - 1) d}}]}] 
    - x y];

countDividedSquares[4, 5]
(*
-> 8
*)
share|improve this answer
    
Thanks , that is really cool!! I'll add that to my folder with the original. –  Tom De Vries Apr 20 '12 at 2:36
add comment

Here's a simple approach. For each vertex in the $x$-direction, we find the range of $y$-values that the line passes through, and draw the corresponding rectangles. This assumes that you're using an integer grid, and that the line goes through (0,0).

Manipulate[Module[{length, width, slope},
   length = Round[p[[1]]];
   width = Round[p[[2]]];

   (* don't divide by zero *)
   slope = If[length > 0, width/length, 0];

   Graphics[{
      (* grid *)
      {GrayLevel[0.8], 
       Line[Table[{{i, 0}, {i, 20}}, {i, 0, 20}]], 
       Line[Table[{{0, i}, {20, i}}, {i, 0, 20}]]}, 

      (* squares "hit" by the line *)
      {FaceForm[Directive[LightGray, Opacity[0.5]]], EdgeForm[Black], 
       Table[Table[
          Rectangle[{i, j}, {i + 1, j + 1}], 
          {j, Floor[slope i], Ceiling[slope (i + 1)] - 1}], {i, 0, length - 1}]},

      (*point to control rectangle*)
      {Blue, AbsolutePointSize[8], Point[Round[p]]},

      (*diagonal*)
      Line[{{0, 0}, Round[p]}]
      }, 
      PlotRange -> {{-0.1, 20.1}, {-0.1, 20.1}}]], 
   {{p, {1, 1}}, {0, 0}, {20, 20}, Locator, Appearance -> None}]

enter image description here

share|improve this answer
add comment

ListPlot with Filling and InterpolationOrder options:

 Manipulate[{length, width} = Round[p];
 lctr = Graphics[{Green, PointSize -> .025, Point[{length, width}]}];
 rectangle ={Green,Thick,Line[{{0, 0}, {0, width}, {length, width}, {length, 0}, {0, 0}}]};
 lst = Transpose[{#, (width/length) #} &@Range[0, length, 1]];
 data = {lst, lst /. {x_, y_} :> {x,Floor[y]}, 
 ((lst /. {x_Integer, y_} :> {Max[0, x - 1], Ceiling[y]}) // Append[#, Last@lst] &)};
 ListPlot[data, InterpolationOrder -> {1, 0, 0},
 Joined -> True, AspectRatio -> 1, Axes -> False, 
 PlotStyle -> {{Thick, Red}, White, White},
 Filling -> {3 -> {{1}, {Black, Black}}, 1 -> {{2}, {Black, Black}}},
 GridLines -> {Table[i, {i, 0, 20}], Table[i, {i, 0, 20}]},
 Method -> {"GridLinesInFront" -> True},
 Epilog -> rectangle, PlotRange -> {{0, 20}, {0, 20}}, 
 PlotRangePadding -> .2],
 {{p, {2, 3}}, {1, 1}, {20, 20}, {1, 1}, Locator, Appearance -> lctr}]

enter image description here

Snapshots:

enter image description here

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.