2
$\begingroup$

Calculating closest and furthest possible diagonal intersections.

Please refer to the image attached. It represents a $2D$ grid with the following properties:

  • The grid origin is $(1,1)$ at the top-left.
  • The x coordinates are $1, 2, 3... infinity$.
  • The y coordinates are $1, 2, 3... infinity$.
  • The highlighted cells with red dots represent all coordinates whose x and y values are powers of 2.
  • Each power of 2 cell has horizontal and vertical lines going through them. These are just visual aids and can be ignored for any calculations.
  • Each power of 2 cell has diagonal and anti-diagonal lines going through them. These are important because we want to intersect with them from a given $(x,y)$.
  • There is an arbitrary given position $(x,y)$ which does not lie on a power of 2 cell or any diagonals. In this example the values are $(969,512)$ but this could be any value.

The question:

  • Given a coordinate $(x,y)$, I want to calculate coordinate $(ix,iy)$ that is an intersection point (towards the North only) between $(x,y)$ and $(px, py)$ where both $px$ and $py$ are powers of two.

The attached image shows $(x,y)$ to be $(969,551)$ and various surrounding power of 2 cells. The closest and furthest possible diagonal intersections are marked in the image.

Open this image in a new tab to see full view.
Illustration 1

What we already know:

  • Given $(x,y)$, we could calculate surrounding power of 2 cells by $flooring$ or $ceiling$ the $base 2 log$ of both $x$ and $y$. As an example $(100,100)$ can be represented as (2^6.64,2^6.64). So the nearest power of 2 cell to the top-left would be $(2^6,2^6)=(64,64)$.

What I cannot figure out is which power of 2 cell to consider when trying to find the closest or furthest intersections.

EDIT: I am convinced that the answer lies in elementary geometry but cannot seem to get a grip on it.

  • 1
    Related questions, so people can see what's already been done: http://math.stackexchange.com/questions/175347/tracing-diagonal-numbers-on-a-2d-grid-or-matrix; http://math.stackexchange.com/questions/179078/calculating-powers-of-2-on-a-2d-grid-without-factoring; http://math.stackexchange.com/questions/180460/structures-in-the-multiplication-table-involving-powers-of-22012-08-19
  • 0
    Where you say "random", I think you mean "arbitrary". If you really mean "random", you should say something about the distribution and how it enters into the question.2012-08-19
  • 0
    @joriki: Noted. Changed to arbitrary. In other words, we have NO control over the (x,y). All we know is that the given position will not be a power of 2 or one of its diagonals.2012-08-19
  • 0
    @GerryMyerson: Thanks for the links. I'm sure you already know those are my own questions. I did not want to complicate the question by providing too much context. Those two questions pose VERY different sub-objectives.2012-08-19
  • 0
    You can never provide too much context. And you shouldn't hide it when discussions of one question might shed light on another.2012-08-19

1 Answers 1

2

The lines going downward to the right are of the form $x-y=2^m-2^n$ for some $m,n$. The ones going up to the right are of the form $x+y=2^m+2^n$ for some $m,n$. Given an input $x,y$ you are asking for the maximum $y' \lt y$ such that either $x-y'=2^m-2^n$ or $x+y'=2^m+2^n$. To find the second: Let $z=x+y$, then set all the low order bits of $z$ to $0$ until you only have two $1$ bits left. This will be the value of $x+y'$. Some pseudocode that will get you there:
z=x+y

m=int(log2(z))

z'=z-2^m

n=int(log2(z'))

y'2=2^m+2^n-x

For the first, you can round $x-y$ up to the next higher power of $2$ to get $m$, then find the lowest $n$ such that $2^m-2^n \gt x-y$

z=x-y

m=int(log2(z))+1

z'=2^m-z

n=int(log2(z'))+1

y'1=x-2^m+2^n

and take the greater of the two y's. Is $x$ always greater than $y$?

  • 0
    Thank you for the answer and +1 for the pseudocode. I came across similar logic in a related question but failed to understand the relationship of $x \pm y=2^m \pm 2^n$. Could you please explain the math logic behind that? That would not only help me understand your answer but help in deducing other areas of the overall application. As you can probably tell, I don't process notation very well.2012-08-18
  • 0
    I suspect I am missing a fundamental concept of relationships between powers, sums and binary representation. If that is the case, where/how could I read up on it?2012-08-18
  • 1
    @RaheelKhan: Lines in the plane represent equations of the form $y=mx+b$, where $m$ is the slope and $b$ is the intercept (the $y$ value at $x=0$) The $2^m\pm2^n$ comes because you started with points $(2^m,2^n)$ and either the sum or difference is constant along your lines because the slope is $\pm1$2012-08-18
  • 1
    @RaheelKhan: for binary representation you could start at http://en.wikipedia.org/wiki/Positional_notation or http://en.wikipedia.org/wiki/Binary_notation. For linear equations http://en.wikipedia.org/wiki/Linear_equation Computer graphics people orient their axes differently from mathematicians so there is some confusion. In math, $x$ is positive to the right, $y$ is positive upward.2012-08-18
  • 0
    Thanks. Ross, I understand the sum and difference remaining constant since slope of $\pm 1$ due to 45 degree diagonals. What I'm trying to figure out is what that has to do with the number of high/low order bits set. [joriki] used a similar approach in his [answer here](http://math.stackexchange.com/a/179144/31055) to determine whether a given $(x,y)$ is diagonal to a power of 2 cell.2012-08-19
  • 1
    @RaheelKhan: In binary, each bit represents a particular power of $2$. A number of the form $2^m+2^n$ has two bits set. For example, $68=2^6+2^2=100100_2$. A number of the form $2^n-2^m$ will have a whole string of bits set due to the borrows. $60=2^4-2^4=11100_2$. You will have all the bits from $2^{n-1}$ through $2^m$ set.2012-08-19
  • 0
    Thanks. That clarifies quite a bit for both questions. Regarding your question `Is x always greater than y?`, not always. Our arbitrary point could be anywhere (even x = y). What happens in this case? More importantly what would I have to do to adapt your answer for the west direction instead of north?2012-08-19
  • 0
    @RaheelKhan: If $x \lt y$ which do you want to change and in which direction? If you want to go west, you are decreasing $x$ and should be able to just interchange $x$ and $y$ in the above, but I haven't thought too hard on it so there may be some details that need cleanup (signs, for example).2012-08-19
  • 0
    I'm looking to understand in concept what I need to consider when $x, $x=y$, and $x>y$. On top of that, we have four possible directions (north, south, east, west). And lastly, in each direction we can go to the furthest possible intersection or the closest. For this purpose, let's assume the width and height of the 2D space to be $finite$. With a few words of guidance, I'm sure I'll be able to adapt your answer to every which combination. I'm marking your answer as correct since this extended discussion is clearly due to my lack of exposure.2012-08-19
  • 0
    Thank you for all your help. If you can spare a moment, please have a look at my last comment above about directions. I would gladly start a bounty but don' have enough rep on this site :).2012-08-23
  • 0
    @RaheelKhan: the equations of the lines don't change if $x \lt y$ or if you move in a different direction. If you move east or west, you are changing x. If you move south, you are increasing y instead of decreasing, so now you want the minimum y' such that... Just some of the signs change.2012-08-24