Finding intersections of lines with grid

Question

I have trajectory data, where each trajectory consists of a sequence of coordinates and each trajectory is identified by a unique ID.

These trajectories are in x - y plane, and I want to divide the whole plane into equal sized cell grid (square grid). This grid is obviously invisible but is used to divide trajectories into sub-trajectories. Whenever a trajectory intersects with a grid line, it becomes a new sub-trajectory with "new_id", i.e a trajectory is divided at the intersections of the grid lines, and each of these segments has new unique id.

Finally, I am hoping to pick any random grid cell and retrieve all the sub-trajectories in that cell.

Please suggest me a way to divide the 2d plane into the grid, and how should the trajectories be segmented on encountering grid lines. I am working on Python, and seek some python implementation links, suggestions, algorithms, or even a pseudocode for the same.

Please let me know if anything is unclear.

Answer 1

Grid indexing is simple:

x_idx =  Floor(x / CellSize)  //rounding it integer down 

But finding intersections with grid depends on way - how trajectories are defined. If they are polylines - sequences of straight segments - just calculate intersections of line segments with grid lines

 X = k * CellSize
 Y = l * CellSize

in k,l intervals between starting and ending cells of segment

Example: polyline starts in point x[0], y[0]. This corresponds to cell with indexes

x_idx[0] =  Floor(x[0] / CellSize)
y_idx[0] =  Floor(y[0] / CellSize)

The find cell for the end of the first segment x[1], y[1]. If cell indexes remain the same, entire segment lies in a single cell and has no intersection with grid. If x_idx[1] is larger than x_idx[0], then segment intersects vertical grid lines

(x_idx[0] + 1) * CellSize   //right border of the initial cell
(x_idx[0] + 2) * CellSize   
...
(x_idx[1]) * CellSize       //left border of the final cell

How to find intersection point

P.S. If segments are long and usually intersect many cells, it is worth to use advanced algorithms for intersection calculation like Amanatides and Woo