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.

  • 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
    @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