增量邻域法迭代生成圆形像素绘制Voronoi图问题求解

问题描述 #

我正尝试使用增量邻域法在图像中生成Voronoi图，方案逻辑为：给定n个随机点（每个点对应一个像素），为每个点绘制其邻域，再对这些新邻域点继续向外扩展，直到整图被填满。目前遇到的问题是生成的区域完全错乱。我猜测原因是：如果检查给定点的全部邻域，最终扩展出的形状是正方形而非圆形，因此任意点的距离计算不符合欧氏距离。我不想通过计算每个像素到所有随机点的距离实现需求，该方案运行速度过慢，想知道如何正确筛选生成邻域，保证按欧氏距离正确扩展。

我尝试过仅在奇数次迭代时检查像素的对角线邻域，得到的圆形效果略有提升，但仍不符合要求。

当前运行效果 #

当前代码运行效果如下：

以下分别是迭代50次和75次的效果示例：

现有代码 #

区域生成代码 #

def createVoronoiIncremental(im, numPoints, param):
    y, x, z = im.shape
    points = []

    count = 0
    while count < numPoints:
        px = np.random.randint(0,x)
        py = np.random.randint(0,y)
        if not inPoints(np.array([px,py]), points):
            points.append(np.array([px,py]))
            count += 1

    points = np.array(points)

    mapPoint = {}
    mapDist = {}

    for i, col in enumerate(im):
            for j, row in enumerate(col):
                mapPoint[(j, i)] = -1 # 空白像素
                mapDist[(j, i)] = y*x # 空白像素


    groups = {}
    groups[-1] = (0,0,0)
    outer = {}
    count = 0
    for point in points:
        i = point[1]
        j = point[0]
        mapPoint[(j, i)] = count # 按组着色的像素
        mapDist[(j, i)] = 0
        outer[(j, i)] = [np.array([j, i])]
        groups[count] = (np.random.randint(0,255),np.random.randint(0,255),np.random.randint(0,255))
        count += 1

    isNeighbour = True
    count = 0
    while isNeighbour:
        isNeighbour = False
        for point in points:
            outerPoints = outer[(point[0], point[1])].copy()
            newOuterPoints = []
            for p in outerPoints:
                n, mapPoint = neightbours(p, mapPoint, mapDist, (x,y), count)
                for neighbour in n:
                    newOuterPoints.append(neighbour)
            outer[(point[0], point[1])] = newOuterPoints
            if len(newOuterPoints) != 0:
                isNeighbour = True
        count += 1
        if count > param:
            break

    return mapPoint

邻域定义代码 #

def neightbours(points, mapPoint, size, count):
    neightbours = []
    potentialNeighbours = []

    if type(points) != 'numpy.ndarray':
        x = points[0]
        y = points[1]

        # 上侧邻域
        if x-1 >= 0 and y+1 < size[1]:
            potentialNeighbours.append(np.array([x-1,y+1]))
        if y+1 < size[1]:
            potentialNeighbours.append(np.array([x  ,y+1]))
        if x+1 < size[0] and y+1 < size[1]:
            potentialNeighbours.append(np.array([x+1,y+1]))

        # 侧边邻域
        if x-1 >= 0:
            potentialNeighbours.append(np.array([x-1,y]))
        if x+1 < size[0]:
            potentialNeighbours.append(np.array([x+1,y]))

        # 下侧邻域
        if x-1 >= 0 and y-1 >= 0:
            potentialNeighbours.append(np.array([x-1,y-1]))
        if y-1 >= 0:
            potentialNeighbours.append(np.array([x  ,y-1]))
        if x+1 < size[0] and y-1 >= 0:
            potentialNeighbours.append(np.array([x+1,y-1]))

        for potentialNeighbour in potentialNeighbours:
            if mapPoint[(potentialNeighbour[0], potentialNeighbour[1])] == -1: #空白像素
                mapPoint[(potentialNeighbour[0], potentialNeighbour[1])] = mapPoint[(x,y)]
                neightbours.append(potentialNeighbour)
    else:
        for point in points:
            x = point[0]
            y = point[1]

            # 上侧邻域
            if x-1 >= 0 and y+1 < size[1]:
                potentialNeighbours.append(np.array([x-1,y+1]))
            if y+1 < size[1]:
                potentialNeighbours.append(np.array([x  ,y+1]))
            if x+1 < size[0] and y+1 < size[1]:
                potentialNeighbours.append(np.array([x+1,y+1]))

            # 侧边邻域
            if x-1 >= 0:
                potentialNeighbours.append(np.array([x-1,y]))
            if x+1 < size[0]:
                potentialNeighbours.append(np.array([x+1,y]))

            # 下侧邻域
            if x-1 >= 0 and y-1 >= 0:
                potentialNeighbours.append(np.array([x-1,y-1]))
            if y-1 >= 0:
                potentialNeighbours.append(np.array([x  ,y-1]))
            if x+1 < size[0] and y-1 >= 0:
                potentialNeighbours.append(np.array([x+1,y-1]))

            for potentialNeighbour in potentialNeighbours:
                if mapPoint[(potentialNeighbour[0], potentialNeighbour[1])] == -1: #空白像素
                    mapPoint[(potentialNeighbour[0], potentialNeighbour[1])] = mapPoint[(x,y)]
                    neightbours.append(potentialNeighbour)
                    
    return neightbours, mapPoint

解决方案 #

使用布雷森汉姆圆绘制算法（Bresenham’s circle drawing algorithm），逐次增大圆半径，检查对应点是否已被绘制，即可生成符合欧氏距离要求的Voronoi图，效果如下：

内容的提问来源于stack exchange，提问作者Hugofac