如何找到与网格线的交集？ [英] How to find intersection of a line with a mesh?

问题描述

我有轨迹数据，每个轨迹由一系列坐标（x，y点）组成，每个轨迹由一个唯一的ID标识。

这些轨迹都在 y 平面中，我想将整个平面划分成相等大小的网格（方形网格）。这个网格显然是不可见的，但用于将轨迹划分为子部分。每当轨迹与网格线相交时，它就会在中分段，并成为 new_id 的新子轨迹。

我已经加入了一个简单的手工图形来清楚我所期待的。

可以看出轨迹是如何在网格线的交点处分开的，并且每个段都有新的唯一ID。 >我正在研究Python，并寻求一些python实现链接，建议，算法，甚至是伪代码。

请让我知道是否有什么不清楚的地方。

UPDATE

为了将飞机划分成网格，完成如下：

 ＃为每个坐标#finding cell id 
 #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]]）
＃分别获取x-cell id和y-cell id 
 x_cellid = cellid [：，0] 
 y_cellid = cellid [：，1] 
 
 #finding总数单元
 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_cells * no_of_ycells 
 total_cells 
 Out []：25 
  

由于飞机现在被分成25个单元每个都带有 cellid 。为了找到相交点，也许我可以检查轨迹中的下一个坐标，如果 cellid 保持不变，那么该轨迹段将位于同一单元格中，并且与网格没有交点。假设，如果x_cellid [2]大于x_cellid [0]，则分段与垂直网格线相交。尽管如此，我仍然不确定如何找到与网格线的交点，并在交叉点上分割轨迹，从而为它们提供新的ID。

解决方案

这可以通过匀称的方式来解决：

 ％matplotlib inline 
从shapely.geometry中导入pylab作为pl 
 import MultiLineString，LineString 
将numpy导入为np 
 from matplotlib.collections import LineCollection 
 
 x0，y0，x1，y1 = -10，-10，10，10 
n = 11 
 
 lines = [] 
 for 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（）
为i，枚举段（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。 （（xgrid [:,无]  -  x [无，：-1]）*（xgrid [:,无]  -  x [无，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 [ （ygrid [:,无]  -  y [无，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）枚举（zip（xlist，ylist））：
 pl.plot（xp，yp）
 pl.text（np.mean（xp），np.mean（yp），str（i）） 
 
 
 lines = [] 
 for np.linspace（x0，x1，n）：
 lines.append（（（x，y0），（ （y0，y1，n）：
 lines.append（（（x0，y），（x1，y）））
 
 for y in np.linspace 
 
 lc = LineCollection（lines，color =gray，lw = 1，alpha = 0.5）
 ax.add_collection（lc）; 
  

I have trajectory data, where each trajectory consists of a sequence of coordinates(x, y points) and each trajectory is identified by a unique ID.

These trajectories are in x - y plane, and I want to divide the whole plane into equal sized grid (square grid). This grid is obviously invisible but is used to divide trajectories into sub-segments. Whenever a trajectory intersects with a grid line, it is segmented there and becomes a new sub-trajectory with new_id.

I have included a simple handmade graph to make clear what I am expecting.

It can be seen how the trajectory is divided at the intersections of the grid lines, and each of these segments has new unique id.

I am working on Python, and seek some python implementation links, suggestions, algorithms, or even a pseudocode for the same.

Please let me know if anything is unclear.

UPDATE

In order to divide the plane into grid , cell indexing is done as following:

#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 

Since the plane is now divided into 25 cells each with a cellid. In order to find intersections, maybe I could check the next coordinate in the trajectory, if the cellid remains the same, then that segment of the trajectory is in the same cell and has no intersection with grid. Say, if x_cellid[2] is greater than x_cellid[0], then segment intersects vertical grid lines. Though, I am still unsure how to find the intersections with the grid lines and segment the trajectory on intersections giving them new id.

解决方案

This can be solved by shapely:

%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);

The result:

To not use shapely, and do it yourself:

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);

这篇关于如何找到与网格线的交集？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！