0
$\begingroup$

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.

1 Answers 1

2

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

  • 0
    @EnviousPage: Thanks. Fixed.2012-09-04