I am unable to figure out how I could solve the following problem.
Assume I have a discrete grid, and each cell (or pixel) can either only be occupied or unoccupied. Additionally, I have a starting cell location $(x1, y1)$. Then, given a line originating from $(x1, y1)$ making an angle $\alpha$ with the $x$-axis, how could I find the first unoccupied cell along this line?
The problem is that this line could be touching many pixels along the way, and I have no way of finding which pixels I should be checking? If I already had an endpoint, Bresenham's algorithm could have been used to find the pixels that are being touched. But the endpoint is what I want.
Motivation behind this: I have a 2D occupancy grid map and a known robot pose. I want to be able to generate an expected laser scan. So for each ray originating from the given grid cell, I want a range value that I should expect to observe. Then the ideal range is the distance between these two pixel times the cell size.
Any tips to help me go in a direction would be much appreciated.
Edit: After some more searching around, I came to the realisation that what I am looking for is provided by rayIntersection implementation from MATLAB. Unfortunately I cannot get the robotics toolbox that is needed. Neither does it give any indications how to solve this problem.