Tengo datos de trayectoria, donde cada trayectoria consiste en una secuencia de coordenadas (puntos x, y) y cada trayectoria se identifica con una ID única.

Estas trayectorias están enx - yplano, y quiero dividir todo el plano en una cuadrícula de igual tamaño (cuadrícula cuadrada). Esta cuadrícula es obviamente invisible pero se usa para dividir trayectorias en subsegmentos. Cada vez que una trayectoria se cruza con una línea de cuadrícula, essegmentario allí y se convierte en una nueva subtrayectoria connuevo_id.

He incluido un gráfico simple hecho a mano para aclarar lo que estoy esperando.

Se puede ver cómo se divide la trayectoria en las intersecciones de las líneas de la cuadrícula, y cada uno de estos segmentos tiene una nueva identificación única.

Estoy trabajando en Python y busco algunos enlaces de implementación de Python, sugerencias, algoritmos o incluso un pseudocódigo para el mismo.

Avíseme si algo no está claro.

ACTUALIZAR

Para dividir el plano en cuadrícula, la indexación de la celda se realiza de la siguiente manera:

#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 

Dado que el avión ahora está dividido en 25 celdas cada una con uncelid. Para encontrar intersecciones, tal vez podría verificar la siguiente coordenada en la trayectoria, si elcelid permanece igual, entonces ese segmento de la trayectoria está en la misma celda y no tiene intersección con la cuadrícula. Digamos, si x_cellid [2] es mayor que x_cellid [0], entonces el segmento interseca las líneas verticales de la cuadrícula. Sin embargo, todavía no estoy seguro de cómo encontrar las intersecciones con las líneas de cuadrícula y segmentar la trayectoria en las intersecciones dándoles una nueva identificación.