用网格求直线交叉口
用网格求直线交叉口
提问于 2017-07-10 04:24:51
我有轨迹数据，每个轨迹由一个坐标序列组成，每个轨迹都由一个唯一的ID识别。
这些轨迹在x - y平面上，我想把整个平面划分成等尺寸的单元格网(正方形网格)。这个网格显然是看不见的，但是被用来把轨迹划分成子轨迹.当一条轨迹与网格线相交时，它就变成了"new_id“的一个新的子轨道，即在网格线的交叉口处划分一条轨迹，并且每一段都有新的唯一id。
最后，我希望选择任意的网格单元，并检索该单元中的所有子轨迹。
请建议我一种将2d平面划分为网格的方法，以及如何在遇到网格线时分割轨迹。我正在研究Python，并为其寻找一些python实现链接、建议、算法，甚至是伪代码。
如果有什么不清楚的地方请告诉我。
回答 1
Stack Overflow用户
发布于 2017-07-10 05:42:43
网格索引很简单：
x_idx = Floor(x / CellSize) //rounding it integer down 但是，寻找与网格的交叉点取决于路径--如何定义轨迹。如果它们是多边形--直线序列--只需计算线段与网格线的交点。
X = k * CellSize
Y = l * CellSize在k，l段的起始细胞和结束细胞之间的间隔
例如: polyline开始于点x，y。这对应于带有索引的单元格。
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 cellHow to find intersection point
如果段长且通常相交多个单元格，则值得使用高级算法(如Amanatides and Woo )进行相交计算。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/45003744
复制相关文章
相似问题
腾讯云开发者
