如何找到与网格相交的直线？
我有轨迹数据，每个轨迹由一个坐标序列(x，y点)组成，每个轨迹都由一个唯一的ID识别。
这些轨迹在x-y平面上，我想把整个平面划分成等尺寸的网格(正方形网格)。这个网格显然是不可见的，但用于将轨迹划分成子段。当一个轨迹与网格线相交时，它就是分段，成为new_id的一个新的子轨道。
我已经包括了一个简单的手工制作的图表，以明确我的期望。
可以看到，在网格线的交叉口，轨迹是如何被划分的，并且每一段都有新的唯一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个细胞，每个细胞都有一个。为了找到交叉点，也许我可以检查轨迹中的下一个坐标，如果保持不变，那么这段轨迹就在同一个单元中，并且没有与网格的交集。如果x_cellid2大于x_cellid，则分段与垂直网格线相交。尽管如此，我仍然不确定如何找到与网格线的交叉口，并在交叉口上分割轨迹，为他们提供新的id。
回答 3
Stack Overflow用户
发布于 2017-07-22 11:27:10
这可以通过形象化的方式解决：
%matplotlib inline
import pylab as pl
from shapely.geometry import MultiLineString, LineString
import numpy as np
from matplotlib.collections import LineCollection
x0, y0, x1, y1 = -10, -10, 10, 10
n = 11
lines = []
for x in np.linspace(x0, x1, n):
lines.append(((x, y0), (x, y1)))
for y in np.linspace(y0, y1, n):
lines.append(((x0, y), (x1, y)))
grid = MultiLineString(lines)
x = np.linspace(-9, 9, 200)
y = np.sin(x)*x
line = LineString(np.c_[x, y])
fig, ax = pl.subplots()
for i, segment in enumerate(line.difference(grid)):
x, y = segment.xy
pl.plot(x, y)
pl.text(np.mean(x), np.mean(y), str(i))
lc = LineCollection(lines, color="gray", lw=1, alpha=0.5)
ax.add_collection(lc);结果：
不要用造型，自己去做：
import pylab as pl
import numpy as np
from matplotlib.collections import LineCollection
x0, y0, x1, y1 = -10, -10, 10, 10
n = 11
xgrid = np.linspace(x0, x1, n)
ygrid = np.linspace(y0, y1, n)
x = np.linspace(-9, 9, 200)
y = np.sin(x)*x
t = np.arange(len(x))
idx_grid, idx_t = np.where((xgrid[:, None] - x[None, :-1]) * (xgrid[:, None] - x[None, 1:]) <= 0)
tx = idx_t + (xgrid[idx_grid] - x[idx_t]) / (x[idx_t+1] - x[idx_t])
idx_grid, idx_t = np.where((ygrid[:, None] - y[None, :-1]) * (ygrid[:, None] - y[None, 1:]) <= 0)
ty = idx_t + (ygrid[idx_grid] - y[idx_t]) / (y[idx_t+1] - y[idx_t])
t2 = np.sort(np.r_[t, tx, tx, ty, ty])
x2 = np.interp(t2, t, x)
y2 = np.interp(t2, t, y)
loc = np.where(np.diff(t2) == 0)[0] + 1
xlist = np.split(x2, loc)
ylist = np.split(y2, loc)
fig, ax = pl.subplots()
for i, (xp, yp) in enumerate(zip(xlist, ylist)):
pl.plot(xp, yp)
pl.text(np.mean(xp), np.mean(yp), str(i))
lines = []
for x in np.linspace(x0, x1, n):
lines.append(((x, y0), (x, y1)))
for y in np.linspace(y0, y1, n):
lines.append(((x0, y), (x1, y)))
lc = LineCollection(lines, color="gray", lw=1, alpha=0.5)
ax.add_collection(lc);Stack Overflow用户
发布于 2017-07-19 21:09:55
你要求太多了。一旦你有了一个通用的方法，你就应该自己攻击大部分的设计和编码。算法识别是合理的堆栈溢出，要求设计和参考链接不是。
我建议你把点坐标放到一个列表中。使用NumPy和SciKit功能插入网格交叉口。您可以将段存储在列表中(任何定义数据设计中的段的部分)。考虑制作一个字典，允许您通过网格坐标检索这些段。例如，如果段仅由端点表示，而点是您的类，则可以使用每个正方形的左下角作为其定义点：
grid_seg = {
(0.5, 0.5): [p0, p1],
(1.0, 0.5): [p1, p2],
(1.0, 1.0): [p2, p3],
...
}其中p0、p1等是插值的交叉点。
Stack Overflow用户
发布于 2017-07-19 21:32:53
每条轨迹由一系列直线段组成。因此，您需要一个例程来将每个线段分解为完全位于网格单元格内的部分。这样一个例程的基础是数字微分分析仪(DDA)算法，但是您需要修改基本算法，因为您需要每个单元格内的行端点，而不仅仅是访问哪个单元格。
有几件事你必须小心：
1)如果使用浮点数，在计算步长值时要注意舍入错误，因为这会导致算法失败。由于这个原因，许多人选择转换为整数网格，显然是由于精度的损失。这很好地讨论了这些问题，使用了一些工作代码(虽然不是python)。
2)您需要决定围绕单元格的4条网格线中的哪一条属于该单元格。一种惯例是使用底部和左侧边缘。如果您考虑一个落在网格线上的水平线段--它的段属于上面的单元格还是下面的单元格，您可以看到这个问题。
干杯
https://stackoverflow.com/questions/45200428
复制相似问题
腾讯云开发者
