Getting cells in a 2D grid between two angles

Question

I've implemented a basic raycasting algorithm successfully, but I want to expand it to work with "angle ranges".

Knowing grid cell size, number of columns and rows, starting ray position, angle a and angle b, how can I get all the cells that fall between the two rays?

Answer 1

If both rays lie in the same quadrant or in neighbour quadrants:

You can use slightly modified Bresenham algorithm to walk both rays together in parallel and get whole column or row of cells between them. Example pseudocode for the case of your example and for (mostly) horizontal sector:

 initialisation for deltaerr1, deltaerr2
 for x from 0 to EndXCoord
         get all cells in column (x,y1)-(x,y2)

         error1 := error1 + deltaerr1
         if error1 ≥ 0.5 then
             y1 := y1 + 1
             error1 := error1 - 1.0

         error2 := error2 + deltaerr2
         if error2 ≥ 0.5 then
             y2 := y2 + 1
             error2 := error2 - 1.0

If the rays are in opposite quadrants, then walk them apart (and take all intermediate quadrant)

Some cases:

1st and 2nd quadrants: make steps in y-direction, get rows

1st and 4th quadrants: make steps in x-direction ,get columns (as in pseudocode)

start in the 1st and end angle in 3rd quadrants: make steps in y-direction in each quadrant, get all needed cells in the 2nd quadrant

special cases:

some angle is n*90 - it may be necessary to change direction

rays make a 180° angle: do Bresenham steps along the line in needed range, get rows or columns in selected semi-plane