# Shading in squares crossed by a diagonal

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}
]


Any help would be appreciated.

-
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
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

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}
]


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.

-
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

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


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
*)

-
Thanks , that is really cool!! I'll add that to my folder with the original. – Tom De Vries Apr 20 '12 at 2:36

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}]


-

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}},