algorithm - 多边形边缘梯度算法

我正在尝试创建一个使用不常见多边形渐变填充的应用程序。这个想法是多边形的每条边都有一种颜色，这些边颜色用于以平滑的渐变填充多边形的其余像素。

我有一个工作程序，它通过为每个像素确定它与所有多边形边缘的距离并根据到它们的距离对所有边缘的颜色进行加权平均来执行此渐变。这是一个示例输出:

问题是当多边形有很多边时，算法非常慢，即因为对于每个像素，它必须计算到每条边的距离。关于如何加快速度的任何想法？

当前算法:

for pixel in polygon: # predetermined using a basic scan-line polygon-fill algorithm
    edge_distances = {}
    for edge in polygon:
        distance = calc_point_to_line_distance(pixel, edge) # simple formula, constant time
        edge_distances[edge] = distance
    colour = calc_pixel_colour(edge_distances)  # runs in O(num_edges) time
    set_pixel_colour(pixel, colour)

我省略了细节，因为我正在寻找如何更好地做到这一点的大局想法(即比 O(num_pixels*num_edges) 更好)。欢迎所有想法。

谢谢!

最佳答案

感谢@SirRaffleBuffle 为我指出答案(对不起，我没有足够的“声誉点”来给你投票)。

我最后采用的是一种颜色扩散算法，结合多网格求解器来获得巨大的性能提升(用数学描述 here 、 here 和 here ；警告，大量不透明的数学术语和希腊字母)。

扩散算法相当简单。您从像素 Canvas 开始，其中一些像素具有指定的颜色(例如由您指定)。然后，通过对每个像素平均四个相邻(非对角线)像素，开始将颜色散布到 Canvas 的其余部分。然后你一遍又一遍地重复这个过程，直到所有的像素都被填满并且它们的颜色稳定了。

这个过程本身非常缓慢，但可以通过“多网格求解器”显着加快。在这里，您最初在一个非常小的 Canvas (即低分辨率)上运行扩散，然后将输出颜色映射到具有两倍分辨率的第二个 Canvas ，并在该 Canvas 上运行扩散。这个过程可以以越来越高的分辨率重复，直到你得到你想要的。这个想法是用接近最终输出的像素颜色来初始化扩散过程，从而切断算法的大部分工作。

这是一个非常粗略的解释；如果您想了解更多详情，请告诉我。

关于algorithm - 多边形边缘梯度算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/46996012/