title: How to find intersection of a line with a mesh?
body: <p>I have trajectory data, where each trajectory consists of a sequence of coordinates(x, y points) and each trajectory is identified by a unique ID.</p>
  
  <p>These trajectories are in <strong>x - y</strong> plane, and I want to divide the whole plane into equal sized grid (square grid). This grid is obviously invisible but is used to divide trajectories into sub-segments. Whenever a trajectory intersects with a grid line, it is <strong>segmented</strong> there and becomes a new sub-trajectory with <strong>new_id</strong>.</p>
  
  <p>I have included a simple handmade graph to make clear what I am expecting.</p>
  
  <p><a href="https://i.stack.imgur.com/7gLGi.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/7gLGi.jpg" alt="enter image description here"></a></p>
  
  <p>It can be seen how the trajectory is divided at the intersections of the grid lines, and each of these segments has new unique id.</p>
  
  <p>I am working on Python, and seek some python implementation links, suggestions, algorithms, or even a pseudocode for the same.</p>
  
  <p>Please let me know if anything is unclear.</p>
  
  <p><strong>UPDATE</strong></p>
  
  <p>In order to divide the plane into grid , cell indexing is done as following:</p>
  
  <pre><code>#finding cell id for each coordinate
  #cellid = (coord / cellSize).astype(int)
  cellid = (coord / 0.5).astype(int)
  cellid
  Out[] : array([[1, 1],
                [3, 1],
                [4, 2],
                [4, 4],
                [5, 5],
                [6, 5]])
  #Getting x-cell id and y-cell id separately 
  x_cellid = cellid[:,0]
  y_cellid = cellid[:,1]
  
  #finding total number of cells
  xmax = df.xcoord.max()
  xmin = df.xcoord.min()
  ymax = df.ycoord.max()
  ymin = df.ycoord.min()
  no_of_xcells = math.floor((xmax-xmin)/ 0.5)
  no_of_ycells = math.floor((ymax-ymin)/ 0.5)
  total_cells = no_of_xcells * no_of_ycells
  total_cells
  Out[] : 25 
  </code></pre>
  
  <p>Since the plane is now divided into 25 cells each with a <strong>cellid</strong>. In order to find intersections, maybe I could check the next coordinate in the trajectory, if the <strong>cellid</strong> remains the same, then that segment of the trajectory is in the same cell and has no intersection with grid. Say, if x_cellid[2] is greater than x_cellid[0], then segment intersects vertical grid lines. Though, I am still unsure how to find the intersections with the grid lines and segment the trajectory on intersections giving them new id. </p>