我有轨迹数据，其中每条轨迹都由一系列坐标组成，并且每条轨迹都由唯一的 ID 标识。
这些轨迹在x - y 平面内，我想将整个平面划分为大小相等的单元格(方格)。该网格显然是不可见的，但用于将轨迹划分为子轨迹。每当一条轨迹与一条网格线相交时，它就成为一个带有“new_id”的新子轨迹，即一条轨迹在网格线的交点处被分割，并且这些段中的每一个都有新的唯一id .
最后，我希望选择任意一个随机网格单元并检索该单元中的所有子轨迹。
请建议我一种将 2d 平面划分为网格的方法，以及如何在遇到网格线时分割轨迹。我正在研究 Python，并寻求一些 Python 实现链接、建议、算法，甚至是相同的伪代码。
如果有什么不清楚的地方请告诉我。
最佳答案
网格索引很简单:
x_idx = Floor(x / CellSize) //rounding it integer down
但是找到与网格的交点取决于方式——轨迹是如何定义的。如果它们是折线 - 直线段序列 - 只需计算线段与网格线的交点
X = k * CellSize
Y = l * CellSize
在段的起始和结束单元格之间的 k,l 间隔内
示例:折线从点 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
附言如果线段很长并且通常与许多单元格相交，则值得使用高级算法进行相交计算，例如 Amanatides and Woo
关于python - 查找线与网格的交点，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/45003744/