python - 采用跳跃洪泛算法的 Voronoi 图 : performance issue

Question

我正在尝试实现跳跃洪泛算法，以从点数组中绘制 Voronoi 图。下面的代码工作正常，但对于大 N 来说速度非常慢。速度慢的原因是有一个循环将新信息添加到正在迭代的数组中。该数组列出了邻近点。如果我不包含此附加内容，则 Voronoi 图是无意义的，算法无法达到大多数点。我不明白为什么对原始邻居搜索中识别的邻居进行简单扫描不会击中网格上的所有点。你能建议我的代码有什么问题吗？是否有一个高性能的替代方案可以将所有找到的邻居附加到一个巨大的数组中？或者这可能只是一个 python 问题，用 C/C++ 等重写可以解决性能问题？

import matplotlib.pyplot as plt
import numpy as np

from time import time

# array = np.zeros((5, 5))
# originalSeeds = {1: [2, 2], 2: [4, 1], 3: [0, 4]}

array = np.zeros((10, 10))
originalSeeds = {1: [2, 2], 2: [4, 1], 3: [0, 4]}
# array = np.zeros((200, 200))
# originalSeeds = {1: [20, 20], 2: [40, 10], 3: [0, 40]}
for key, value in originalSeeds.items():
    array[value[0], value[1]] = key

seeds = {1: [], 2: [], 3: []}
# this is constantly updated list of neighbors

colors = [1, 2, 3]
colorvalues = {1: 1, 2: 2, 3: 3}

# plt.imshow(array)
# plt.show()

start = time()

step = 2**(int(np.log2(array.shape[0])))


def distance(crd1, crd2):
    return np.linalg.norm(crd1 - crd2)


while step >= 1:
    for color in colors:
        originalSeedCoords = originalSeeds[color]
        # neighbor displacments
        disp = step * np.array([[1, 1], [0, 1], [-1, 1], [1, -1], [1, 0], [-1, -1], [0, -1], [-1, 0]])
        for element in disp:
            center = originalSeeds[color]
            idx = center + np.array(element)

            if idx[0] > array.shape[0] - 1 or idx[1] > array.shape[1] - 1 or idx[0] < 0 or idx[1] < 0:
                continue
            else:

                if array[idx[0], idx[1]] == color:
                    continue
                elif array[idx[0], idx[1]] == 0:
                    array[idx[0], idx[1]] = colorvalues[color]
                    seeds[color].append(list(idx))
                else:
                    currColor = array[idx[0], idx[1]]

                    if distance(idx, originalSeeds[color]) < distance(idx, originalSeeds[currColor]):
                        array[idx[0], idx[1]] = colorvalues[color]
                        seeds[color].append(list(idx))
                    else:
                        array[idx[0], idx[1]] = colorvalues[currColor]
                        seeds[currColor].append(list(idx))

    for color in colors:
        for seed in seeds[color]:  # this list may grov during iteration, filling in uncharted points
            for element in disp:
                center = seed

                idx = center + np.array(element)

                if idx[0] > array.shape[0] - 1 or idx[1] > array.shape[1] - 1 or idx[0] < 0 or idx[1] < 0:
                    continue
                else:
                    if array[idx[0], idx[1]] == color:
                        continue
                    elif array[idx[0], idx[1]] == 0:
                        array[idx[0], idx[1]] = colorvalues[color]
                        if list(idx) not in seeds[color]:
                            seeds[color].append(list(idx))
                    else:
                        currColor = array[idx[0], idx[1]]

                        if distance(idx, originalSeeds[color]) < distance(idx, originalSeeds[currColor]):
                            array[idx[0], idx[1]] = colorvalues[color]
                            if list(idx) not in seeds[color]:
                                seeds[color].append(list(idx))
                        else:
                            array[idx[0], idx[1]] = colorvalues[currColor]
                            if list(idx) not in seeds[currColor]:
                                seeds[currColor].append(list(idx))

    step = step // 2
    # step -= 1

Answer 1

跳跃泛洪算法是为 GPU 设计的，该函数在所有像素上并行执行，并使用乒乓缓冲区来存储最后一次的结果。它不应该以顺序方式使用，更不用说在 Python 中实现。