python - 带有跳跃泛洪算法的 Voronoi 图 : performance issue

Question

我正在尝试实现 Jump Flooding 算法以从一组点绘制 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 中实现了。