Eu tenho dados de trajetória, onde cada trajetória consiste em uma sequência de coordenadas (pontos x, y) e cada trajetória é identificada por um ID exclusivo.

Essas trajetórias estão emx - yplano, e eu quero dividir o plano inteiro em grade de tamanho igual (grade quadrada). Essa grade é obviamente invisível, mas é usada para dividir trajetórias em sub-segmentos. Sempre que uma trajetória cruza com uma linha de grade, ésegmentado lá e se torna uma nova sub-trajetória comnew_id.

Incluí um gráfico artesanal simples para deixar claro o que estou esperando.

Pode-se ver como a trajetória é dividida nas interseções das linhas de grade e cada um desses segmentos possui um novo ID exclusivo.

Estou trabalhando no Python e procuro alguns links de implementação, sugestões, algoritmos ou até um pseudocódigo para o mesmo.

Informe-me se algo não estiver claro.

ATUALIZAR

Para dividir o plano em grade, a indexação de células é feita da seguinte maneira:

#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 

Como o avião agora está dividido em 25 células, cada uma com umcellid. Para encontrar interseções, talvez eu possa verificar a próxima coordenada na trajetória, se ocellid permanece o mesmo, então esse segmento da trajetória está na mesma célula e não tem interseção com a grade. Digamos, se x_cellid [2] for maior que x_cellid [0], o segmento cruzará as linhas de grade verticais. No entanto, ainda não tenho certeza de como encontrar as interseções com as linhas de grade e segmentar a trajetória nas interseções, dando-lhes um novo ID.