Find cells in array that are crossed by a given line segment

Question

I have got a 2D array of cells with size 10x10, and many points that are pairs of floating point values, like: (1.6, 1.54), (4.53, 3.23). The pairs (x,y) are such that x<10 and y<10

Each cell takes points whose coordinates have the same integer part as the cell coordinates. So arr[3][7] will take points with x={3...3.99(9)} and y={7... 7.99(9)}, for example (3.5, 7.1) or (3.2, 7.6). Similarly (1.6, 1.54) is in arr[1][1] , (4.53, 3.23) is in arr[4][3], etc.

Each point has got a designated place in the array that is easy to find, because I just have to cast x and y to int to get rid of the decimal points.

But I would like to find which cells in the array are crossed by the line segment between two points A(x,y) and B(x,y).

For example: A(1.5, 2.5) and B(4.3, 3.2) crosses cells in array with indexes [1][2], [2][2], [3,3] and [3,4]

Is there any algorithm for that?

It is a similar problem to that one: Cells in grid crossed by a line ( PHP )

Answer 1

Let your points be A and B, with respective coordinates (xA,yA) and (xB,yB).

A parametric equation for the line segment between both points is given by:
A + t * (B-A) = (xA + t * (xB - xA), yA + t * (yB - yA)) where ttakes all valuers between 0 and 1.

You need to consider all the integral values of either coordinate, along the line segment. This will give you the point of intersection of your line and a cell's side, so you can mark both cells adjacent to this side as "traversed".

Here is the outline of an algorithm to do this, sorting intersection points along the line:

• start at cell A
• while you're not at cell B:
  • find the next intersection of your segment with an x axis
  • find the next intersection of your segment with a y axis
  • take the closest one, mark the adjacent cell, and move to it

There are some special cases, like cells that are only touched at one corner. To treat those specially in the previous algorithm, you can recognize the that both potential future intersections are the same.

---

Here is a quick python demo, where I scaled (multiplied) all t values of the parametric equation by dx * dy so you don't have to divide by dx or dy, except if you want the exact intersection coordinates.

from math import floor
def sign(n):
    return (n > 0) - (n < 0)

def raytrace(A, B):
    """ Return all cells of the unit grid crossed by the line segment between
        A and B.
    """

    (xA, yA) = A
    (xB, yB) = B
    (dx, dy) = (xB - xA, yB - yA)
    (sx, sy) = (sign(dx), sign(dy))

    grid_A = (floor(A[0]), floor(A[1]))
    grid_B = (floor(B[0]), floor(B[1]))
    (x, y) = grid_A
    traversed=[grid_A]

    tIx = dy * (x + sx - xA) if dx != 0 else float("+inf")
    tIy = dx * (y + sy - yA) if dy != 0 else float("+inf")

    while (x,y) != grid_B:
        # NB if tIx == tIy we increment both x and y
        (movx, movy) = (tIx <= tIy, tIy <= tIx)

        if movx:
            # intersection is at (x + sx, yA + tIx / dx^2)
            x += sx
            tIx = dy * (x + sx - xA)

        if movy:
            # intersection is at (xA + tIy / dy^2, y + sy)
            y += sy
            tIy = dx * (y + sy - yA)

        traversed.append( (x,y) )

    return traversed

---

If your cell width is w and the cell with coordinates 0, 0 starts at (x0, y0) (that is [x0 , x0 + w] * [y0, y0 + w]) then normalize for that when calling the function, i.e. instead of

raytrace( (1,1.5) , (5,2.5) )

use

raytrace( ((1 - x0) / w, (1.5 - y0) / w) , ((4 - x0) / w, (1.5 - y0) / w) )