я есть данные о траектории, где каждая траектория состоит из последовательности координат (x, y точек), и каждая траектория идентифицируется уникальным идентификатором.

Эти траектории находятся вх - уплоскость, и я хочу разделить всю плоскость на сетку одинакового размера (квадратная сетка). Эта сетка, очевидно, невидима, но используется для разделения траекторий на подсегменты. Всякий раз, когда траектория пересекается с линией сетки, этосегментированный там и становится новой суб-траектории сnew_id.

Я включил простой график ручной работы, чтобы прояснить, чего я ожидаю.

Можно увидеть, как траектория делится на пересечениях линий сетки, и каждый из этих сегментов имеет новый уникальный идентификатор.

Я работаю над Python и ищу ссылки на реализацию Python, предложения, алгоритмы или даже псевдокод для того же самого.

Пожалуйста, дайте мне знать, если что-то неясно.

ОБНОВИТЬ

Чтобы разделить плоскость на сетку, индексация ячейки выполняется следующим образом:

#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 

Поскольку самолет теперь разделен на 25 ячеек, каждая сCellID, Чтобы найти пересечения, возможно, я мог бы проверить следующую координату в траектории, еслиCellID остается тем же, то этот отрезок траектории находится в той же ячейке и не имеет пересечения с сеткой. Скажем, если x_cellid [2] больше, чем x_cellid [0], то сегмент пересекает вертикальные линии сетки. Тем не менее, я все еще не уверен, как найти пересечения с линиями сетки и сегментировать траекторию на пересечениях, давая им новый идентификатор.