Fast axis aligned cell traversal algorithm

Question

• Given an axis aligned square divided in four cells of equal size A, B, C and D.
• Given a line segment going from point s1 to point s2.

What is the fastest way to find the cells traversed by the segment (if any), sorted by traversal order ?

In the example above, the correct results are :

• Segment 1 : [D]
• Segment 2 : [A, B]
• Segment 3 : [C, D, B]
• Segment 4 : []
• Segment 5 : [C]

Answer 1

You can try "A Fast Voxel Traversal Algorithm for Ray Tracing" by Amanatides and Woo.

It is intended to deal with big grids, but the principle can be useful for your application too.

Answer 2

The following can be done using only a simple line intersect formula:

Observe that your grid consists of 6 line segments (3 horizontal, 3 vertical). If you were to extend each of these segments into infinity (making them lines, without start or end points), you have divided your 2D space into 16 areas.

Define a 4x4 array of areas. For each such area, store which line (if any) delimits it on the north side, on the east side, etc. This will be our traversal data structure.

Now, to find the cells traversed by a given query segment S, starting at u and ending at v, we will do a line walk from u to v using this traversal data structure to keep track of the area we're currently in and at which locations we're exiting that area.

• Determine Au as the area in which u is located, and Av as the area in which v is located. Because of the axis-aligned nature of the areas, this shouldn't take more than 4 comparisons per area (2 on x-coordinate, 2 on y).
  Also, define the current location as p and the current area as A; initially, these will be u and Au, respectively.

• First, report A as an area that is traversed by S. Determine the first intersection point between the segment* (p, v] and the delimiting lines at each of the 4 sides of A. If such an intersection point q is found, the side that contains q determines which neighbouring area will become our new A - in that case our new p will be the intersection point q. Using this new A and p, repeat this step.
  If no intersection point is found, p must lie in the same area as v and the walk is complete.

*(p, v] meaning: the segment between p and v, excluding p but including v.