Python:非凸网格的边界点

Question

我遇到如下图所示的情况:

我想找出红点周围的网格点。红点是移动代理的轨迹。所以在很多情况下，我们有一堆点，因此解决方案应该尽可能快。

网格被绘制为点。

• 第一步，我设法减少了网格点的数量，如下所示(绘制为 x):

这是我的代码:

step = .5
gridX, gridY = np.meshgrid(np.arange(xmin-step, xmax+step, step), np.arange(ymin-step, ymax+step, step))
mask = False * np.empty_like(gridX, dtype=bool)
threshold = 0.5
for (x,y) in  zip(df_traj['X'], df_traj['Y']):
    pX = x * np.ones_like(gridX)
    pY = y * np.ones_like(gridY)
    distX = (pX - gridX)**2
    distY = (pY - gridY)**2
    dist = np.sqrt(distX + distY)
    condition = (dist < threshold)
    mask = mask | condition

gX = gridX*mask
gY = gridY*mask

• 第二步，这是我需要一点帮助的地方:

如何有效过滤掉网格内部的点，只保留“红色区域”之外的“x点”？

编辑

在这种特殊情况下，我有 92450 个红点。

Answer 1

我认为如果你只是绕着边缘走一圈，因为它是一个均匀分布的网格，它应该可以工作。不需要复杂得多的非凸壳来处理可以在任何地方的 pnt。这不适合您的代码，我使用我的数据结构作弊以使代码变得简单，因此您必须处理它，但它认为伪代码应该可以工作。

pnts = <<lists of points>>
edge_pnts = []
fpnt = pnt_with_min_x_then_min_y
cpnt = fpnt
npnt = None 

while npnt != fpnt:

    if   (cpnt[0] + 1, cpnt[1]    ) in pnts: npnt = (cpnt[0] + 1, cpnt[1]    )
    elif (cpnt[0] + 1, cpnt[1] + 1) in pnts: npnt = (cpnt[0] + 1, cpnt[1] + 1)
    elif (cpnt[0],     cpnt[1] + 1) in pnts: npnt = (cpnt[0]    , cpnt[1] + 1)
    elif (cpnt[0] - 1, cpnt[1] + 1) in pnts: npnt = (cpnt[0] - 1, cpnt[1] + 1)
    elif (cpnt[0] - 1, cpnt[1]    ) in pnts: npnt = (cpnt[0] - 1, cpnt[1]    )
    elif (cpnt[0] - 1, cpnt[1] - 1) in pnts: npnt = (cpnt[0] - 1, cpnt[1] - 1)
    elif (cpnt[0]    , cpnt[1] - 1) in pnts: npnt = (cpnt[0]    , cpnt[1] - 1)
    elif (cpnt[0] + 1, cpnt[1] - 1) in pnts: npnt = (cpnt[0] + 1, cpnt[1] - 1)
    else: raise ValueError("Oh no!")

    edge_pnts.append(npnt)
    cpnt = npnt