python - 在二进制网格中扩展 block ( dilation )

Question

对于 A* 实现(为“汽车”机器人生成路径)，我需要调整我的模型以考虑汽车的“宽度”，从而避开障碍物。

我的一个想法是将所有障碍物扩大汽车的宽度，这样所有太靠近障碍物的单元格也会被标记为障碍物。

我尝试使用两种朴素的算法来做到这一点，但它仍然太慢(尤其是在大网格上)，因为它多次经过相同的单元格:

    unreachable = set()
    # I first add all the unreachables to a set to avoid 'propagation'
    for line in self.grid:
        for cell in line:
            if not cell.reachable:
                unreachable.add(cell)

    for cell in unreachable:
        # I set as unreachable all the cell's neighbours in a certain radius
        for nCell in self.neighbours( cell, int(radius/division) ):
            nCell.reachable = False

这里是邻居的定义:

def neighbours(self, cell, radius = 1, unreachables = False):
    neighbours = set()
    for i in xrange(-radius, radius + 1):
        for j in xrange(-radius, radius + 1):
            x = cell.x + j
            y = cell.y + i
            if 0 <= y < self.height and 0 <= x < self.width and (self.grid[y][x].reachable or unreachables )) :
                neighbours.add(self.grid[y][x])

    return neighbours

是否有任何顺序算法(或 O(n.log(n)))可以做同样的事情？

Answer 1

您正在寻找的是所谓的Minkowski sum。 ，如果你的障碍物和汽车是凸的，有一个线性算法来计算它。