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