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
    $\begingroup$ Related questions, so people can see what's already been done: math.stackexchange.com/questions/175347/…; math.stackexchange.com/questions/179078/…; math.stackexchange.com/questions/180460/… $\endgroup$ – Gerry Myerson Aug 19 '12 at 0:09
  • $\begingroup$ 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. $\endgroup$ – joriki Aug 19 '12 at 1:50
  • $\begingroup$ @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. $\endgroup$ – Raheel Khan Aug 19 '12 at 2:27
  • $\begingroup$ @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. $\endgroup$ – Raheel Khan Aug 19 '12 at 2:31
  • $\begingroup$ You can never provide too much context. And you shouldn't hide it when discussions of one question might shed light on another. $\endgroup$ – Gerry Myerson Aug 19 '12 at 6:24

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:





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$






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

  • $\begingroup$ 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. $\endgroup$ – Raheel Khan Aug 18 '12 at 23:07
  • $\begingroup$ 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? $\endgroup$ – Raheel Khan Aug 18 '12 at 23:10
  • 1
    $\begingroup$ @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$ $\endgroup$ – Ross Millikan Aug 18 '12 at 23:13
  • 1
    $\begingroup$ @RaheelKhan: for binary representation you could start at en.wikipedia.org/wiki/Positional_notation or en.wikipedia.org/wiki/Binary_notation. For linear equations 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. $\endgroup$ – Ross Millikan Aug 18 '12 at 23:17
  • 1
    $\begingroup$ @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. $\endgroup$ – Ross Millikan Aug 19 '12 at 14:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.