# Calculating which $(2^x,2^y)$ coordinates intersect diagonally ($45^{\circ}$) with an arbitrary rectangle in 2D space.

Calculating which $(2^x,2^y)$ coordinates intersect diagonally ($45^{\circ}$) with an arbitrary rectangle in 2D space. The rectangle in this case is your computer monitor.

Consider navigating a 2D space on your computer monitor (the arbitrary rectangle). Let's call the 2D space the $\mathrm{world}$ and your monitor the $\mathrm{viewport}$ where the coordinate system of both the $\mathrm{world}$ and $\mathrm{viewport}$ start at $(1,1)$ at the top left. The $\mathrm{world}$ goes on to infinity.

Let $(ox,oy)$ be the offset between the two such that if $(ox,oy) = (0,0)$, then you would be looking at the top-left of the $\mathrm{world}$ through your $\mathrm{viewport}$. The width and height of the $\mathrm{viewport}$ would determine how much of the world you can see at a given time.

If we want to calculate whether an arbitrary point $(2^x,2^y)$ intersects the $\mathrm{viewport}$ diagonally ($45^{\circ}$), we could do so easily. I want to do the opposite: calculate EACH $(2^x,2^y)$ that intersects diagonally with our viewport.

There are two distinct questions here:

• How can we calculate all intersecting points without the overhead of calculating misses?
• All $(2^x,2^y)$ points above and left of $(ox,oy)$ are easy to conceptualize since our $\mathrm{world}$ starts at $(1,1)$. How can get a mental grasp of points that are below or right of $(ox,oy)$ since the $\mathrm{world}$ is infinitely large?

UPDATE: To help understand the second point, I generated a high resolution rendering of a $\mathrm{world}$ with a width and height of $10,000$ with diagonals crossing each $(2^x,2^y)$ point. The image can be downloaded here and is essentially a snapshot of your $\mathrm{viewport}$. Due to the size of the image (2MB zipped, 300MB unzipped), I would recommend using Google Picasa as the image viewer.

Sure enough it shows some very interesting patterns but I could not tell if I am missing an infinite number of diagonals that should be intersecting from the right or below.

-

The critical information is already in the equations of the lines given in this earlier answer. Let the two corners of your rectangle be $(ox,oy)$ and $(fx,fy)$. The lines going diagonally up and to the right are lines of constant $x+y$. The minimum value of $x+y$ in your rectangle is $ox+oy$ and the maximum is $fx+fy$. So you want all values of $2^x+2^y$ that are in that range. Similarly, the lines going down to the right are lines of constant $x-y$. Your minimum $x-y$ is $ox-fy$ and your maximum is $fx-oy$. You want all values of $2^x-2^y$ that are in that range (which may be negative if $y \gt x).$
Thank you Ross. I do understand your answer and will be able to use it after a few reads but I have a silly somewhat unrelated question. When I think of lines as a lay man, the only thing that comes to mind is slope. So when you say 'lines of constant $x+y$', I find that hard to visualize. How would you explain this representation to say a child? – Raheel Khan Aug 30 '12 at 5:30
Lines of constant $x+y$ are those sets of points with a common value. For example, $(0,10), (1,9), (2,8), \ldots (10,0)$ are on a line of constant $x+y$, in this case $10$. The constants for your lines are of the form $2^x \pm 2^y$, which is why the lines pack together near $x=\pm y$, because the powers of $2$ are closer together near $0$. – Ross Millikan Aug 30 '12 at 14:36