Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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).$

share|improve this answer
    
Your TeX messed up in the last line, forgot an ending dollar sign. –  Envious Page Aug 30 '12 at 5:22
    
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
    
Also, I'd love to hear your explanation to the second point if you get a chance to look at the linked image. –  Raheel Khan Aug 30 '12 at 5:33
1  
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
    
Ross, I'm not sure if it is appropriate to solicit professional consulting on Stack Exchange. If so, I would highly appreciate a private discussion to see if this would be of any interest to you. The context is, of course, related to the two questions you have answered. –  Raheel Khan Sep 4 '12 at 15:42

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.