查找线条与网格的交点

Question

我有轨迹数据，其中每个轨迹由一系列坐标组成，每个轨迹由唯一ID标识。

这些轨迹在x - y平面上，我想将整个平面划分成相等大小的单元网格（方形网格）。这个网格显然是不可见的，但用于将轨迹划分为子轨迹。每当轨迹与网格线相交时，它就变成一个新的子轨迹，其具有“new_id”，即轨迹在网格线的交点处被分开，并且这些段中的每一个具有新的唯一ID。

最后，我希望能够选取任意随机网格单元并检索该单元格中的所有子轨迹。

请给我一种将2d平面划分成网格的方法，以及如何在遇到网格线时分割轨迹。我正在研究Python，并寻求一些python实现链接，建议，算法，甚至是伪代码。

请让我知道，如果有什么不清楚。

Answer 1

电网索引很简单：

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

但要找到与网格交叉依赖的方式 - 轨迹是如何定义的。如果它们是折线 - 直线段序列 - 只是计算线段的交叉点与网格线在K

X = k * CellSize 
Y = l * CellSize 

，起始之间升间隔和段的结束细胞

实施例：折线开始在点x [ 0]，y [0]。与此对应的指标

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

了第一部分x[1], y[1]末的发现细胞对细胞。如果单元格索引保持不变，则整个片段位于单个单元格中并且与网格没有交集。如果x_idx[1]比x_idx[0]大，则段相交的垂直网格线

(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.如果分段很长并且通常与许多单元格相交，则值得使用高级算法进行交点计算，如Amanatides and Woo