最容易实现的 Voronoi 图算法？

Question

Closed. This question is seeking recommendations for software libraries, tutorials, tools, books, or other off-site resources. It does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

我们不允许提出寻求软件库、教程、工具、书籍或其他场外资源推荐的问题。 您可以编辑问题，以便用事实和引文来回答。

5 年前已关闭。

社区在2年前审查了是否重新开放此问题，并将其关闭：

原始关闭原因未解决

Answer 1

计算点集 Delaunay 三角剖分的一种简单算法是翻转边< /a>. 由于 Delaunay 三角剖分是 Voronoi 图的对偶图，因此您可以在线性时间内根据三角剖分构造该图。

不幸的是，翻转方法的最坏情况运行时间是 O(n^2)。 存在更好的算法，例如 Fortune 的线扫描，它需要 O(n log n) 时间。 但这实施起来有些棘手。 如果您很懒（像我一样），我建议您寻找 Delaunay 三角剖分的现有实现，使用它，然后计算对偶图。

一般来说，关于该主题的一本好书是 de Berg 等人的计算几何 。

Answer 2

最简单？ 这是蛮力方法：对于输出中的每个像素，迭代所有点，计算距离，使用最近的点。 尽可能慢，但非常简单。 如果性能不重要，它就可以完成工作。 我自己一直在进行一项有趣的改进，但仍在寻找其他人是否有相同（相当明显）的想法。

Answer 3

Bowyer-Watson 算法非常容易理解。 这是一个实现：http://paulbourke.net/papers/triangulate/。 这是一组点的德劳内三角剖分，但您可以使用它来获得德劳内的对偶，即沃罗诺图。 顺便提一句。 最小生成树是 delaunay 三角剖分的子集。

Answer 4

构建 voronoi 图最有效的算法是 Fortune 算法。 它的运行时间为 O(n log n)。

以下是他的C 参考实现的链接。

就我个人而言，我真的很喜欢 python 实现由 Bill Simons 和 Carson Farmer 撰写，因为我发现它更容易扩展。

Answer 5

维基百科页面 (http://en.wikipedia.org/wiki/Voronoi_diagram) 有一个算法部分包含用于实现 Voronoi 图的算法的链接。

Answer 6

Stephan Fortune / Shane O'Sullivan 提供了一个用 C 和 C++ 语言免费提供的用于二维图的 voronoi 实现：

VoronoiDiagramGenerator.cpp 

VoronoiDiagramGenerator.h 

您可以在很多地方找到它。 即位于 http://www.skynet.ie/~sos/masters/

Answer 7

这是一个使用 quat-tree 并允许增量构造的 JavaScript 实现。

http://code.google.com/p/javascript-voronoi/

Answer 8

虽然最初的问题询问如何实现 Voronoi，但如果我在搜索有关此主题的信息时发现一篇文章说以下内容，它会节省我很多时间：

有很多“几乎正确”的 C++ 代码用于实现 Voronoi 图的互联网。 当种子点变得非常密集时，大多数都很少触发失败。
我建议您在浪费太多时间之前，先对您在网上找到的任何代码进行广泛测试，并根据您希望在已完成的项目中使用的点数进行测试。

我在网上找到的最好的实现是从这里链接的 MapManager 程序的一部分：
http://www.skynet.ie/~sos/mapviewer/voronoi.php
它大部分工作正常，但在处理 10^6 点的订单时，我遇到间歇性图表损坏。
我一直无法弄清楚腐败是如何蔓延的。

昨晚我发现了这一点：
http://www.boost.org/doc/libs /1_53_0_beta1/libs/polygon/doc/voronoi_main.htm
“Boost.Polygon Voronoi 库”。
看起来很有前途。 它带有基准测试来证明其准确性并具有出色的性能。
该库有适当的界面和文档。
我很惊讶我之前没有找到这个库，因此我在这里写了关于它的文章。 （我在研究初期读过这篇文章。）

Answer 9

这是最快的 - 这是一个简单的 voronoi，但看起来很棒。 它将空间划分为网格，在随机放置的每个网格单元中放置一个点，并沿着网格移动检查 3x3 单元以找出它与相邻单元的关系。

没有渐变的话速度会更快。

您可能会问最简单的 3d voronoi 是什么。 如果知道的话会很有趣。 可能是 3x3x3 单元格并检查梯度。

http://www.iquilezles.org/www/articles/smoothvoronoi/smoothvoronoi。 htm

float voronoi( in vec2 x )
{
    ivec2 p = floor( x );
    vec2  f = fract( x );

    float res = 8.0;
    for( int j=-1; j<=1; j++ )
    for( int i=-1; i<=1; i++ )
    {
        ivec2 b = ivec2( i, j );
        vec2  r = vec2( b ) - f + random2f( p + b );
        float d = dot( r, r );

        res = min( res, d );
    }
    return sqrt( res );
}

这里与切比雪夫距离相同。 您可以从这里使用 random2f 2d 浮动噪声：

https://www.shadertoy.com/view/Msl3DM

编辑：我已将其转换为类似 C 的代码

这是不久前的事了，为了那些这样做的人的利益，我相信这很酷：

 function rndng ( n: float ): float
 {//random number -1, 1
     var e = ( n *321.9)%1;
     return  (e*e*111.0)%2-1;
 }

 function voronoi(  vtx: Vector3  )
 {
     var px = Mathf.Floor( vtx.x );
     var pz = Mathf.Floor( vtx.z );
     var fx = Mathf.Abs(vtx.x%1);
     var fz = Mathf.Abs(vtx.z%1);

     var res = 8.0;
     for( var j=-1; j<=1; j++ )
     for( var i=-1; i<=1; i++ )
     {
         var rx = i - fx + nz2d(px+i ,pz + j ) ;
         var rz = j - fz + nz2d(px+i ,pz + j ) ;
         var d = Vector2.Dot(Vector2(rx,rz),Vector2(rx,rz));
         res = Mathf.Min( res, d );
     }
     return Mathf.Sqrt( res );
 }

Answer 10

实际上，https://rosettacode.org/wiki/Voronoi_diagram 上提供了 25 种不同语言的实现，

例如爪哇：

import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.geom.Ellipse2D;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.util.Random;

import javax.imageio.ImageIO;
import javax.swing.JFrame;

public class Voronoi extends JFrame {
    static double p = 3;
    static BufferedImage I;
    static int px[], py[], color[], cells = 100, size = 1000;

    public Voronoi() {
        super("Voronoi Diagram");
        setBounds(0, 0, size, size);
        setDefaultCloseOperation(EXIT_ON_CLOSE);
        int n = 0;
        Random rand = new Random();
        I = new BufferedImage(size, size, BufferedImage.TYPE_INT_RGB);
        px = new int[cells];
        py = new int[cells];
        color = new int[cells];
        for (int i = 0; i < cells; i++) {
            px[i] = rand.nextInt(size);
            py[i] = rand.nextInt(size);
            color[i] = rand.nextInt(16777215);

        }
        for (int x = 0; x < size; x++) {
            for (int y = 0; y < size; y++) {
                n = 0;
                for (byte i = 0; i < cells; i++) {
                    if (distance(px[i], x, py[i], y) < distance(px[n], x, py[n], y)) {
                        n = i;

                    }
                }
                I.setRGB(x, y, color[n]);

            }
        }

        Graphics2D g = I.createGraphics();
        g.setColor(Color.BLACK);
        for (int i = 0; i < cells; i++) {
            g.fill(new Ellipse2D .Double(px[i] - 2.5, py[i] - 2.5, 5, 5));
        }

        try {
            ImageIO.write(I, "png", new File("voronoi.png"));
        } catch (IOException e) {

        }

    }

    public void paint(Graphics g) {
        g.drawImage(I, 0, 0, this);
    }

    static double distance(int x1, int x2, int y1, int y2) {
        double d;
        d = Math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)); // Euclidian
    //  d = Math.abs(x1 - x2) + Math.abs(y1 - y2); // Manhattan
    //  d = Math.pow(Math.pow(Math.abs(x1 - x2), p) + Math.pow(Math.abs(y1 - y2), p), (1 / p)); // Minkovski
        return d;
    }

    public static void main(String[] args) {
        new Voronoi().setVisible(true);
    }
}

Answer 11

最简单的算法来自 voronoi 图的定义：
“将具有 n 个点的平面划分为凸多边形，使得每个多边形恰好包含一个生成点，并且给定多边形中的每个点比任何其他点都更接近其生成点。”来自 Wolfram 的定义。

这里重要的部分是每个点都比其他点更接近生成点，从这里开始算法非常简单：

1. 有一个生成点数组。
2. 循环遍历画布上的每个像素。
3. 对于每个像素寻找距离它最近的生成点。
4. 根据您希望为像素着色的图表。
   如果您想要一个用边框分隔的图表，请检查第二个最接近的点，然后检查它们与边框颜色的差异和颜色（如果它小于某个值）。

如果您想要一个颜色图，那么有一个与每个生成点关联的颜色，并使用与它最接近的生成点关联的颜色为每个像素着色。
就是这样，它效率不高，但很容易实现。

Answer 12

检查 Richard Franks 在他对问题 我该怎么办给定点集和 Delaunay 三角剖分，导出 Voronoi 图？

Answer 13

在 google code 上找到了这个基于 Fortune 算法/扫线算法的优秀 C# 库

https://code。 google.com/p/fortune-voronoi/

您只需创建一个列表。 可以通过传入两个数字（坐标）作为浮点数来创建向量。 然后将列表传递到 Fortune.ComputeVoronoiGraph()

您可以从这些维基百科页面进一步了解算法的概念：

http://en.wikipedia.org/wiki/Fortune%27s_algorithm

http:/ /en.wikipedia.org/wiki/Sweep_line_algorithm

虽然我无法理解的一件事是如何为部分无限边缘创建一条线（对坐标几何不太了解:-)）。 如果有人知道，也请告诉我。

Answer 14

如果您尝试将其绘制到图像中，可以使用基于队列的洪水填充算法。

Voronoi::draw(){
    // define colors for each point in the diagram;
    // make a structure to hold {pixelCoords,sourcePoint} queue objects
    // initialize a struct of two closest points for each pixel on the map
    // initialize an empty queue;

    // for each point in diagram:
        // for the push object, first set the pixelCoords to pixel coordinates of point;
        // set the sourcePoint of the push object to the current point;
        // push the queue object;

    // while queue is not empty:
        // dequeue a queue object;
        // step through cardinal neighbors n,s,e,w:
            // if the current dequeued source point is closer to the neighboring pixel than either of the two closest:
                // set a boolean doSortAndPush to false;
                // if only one close neighbor is set:
                    // add sourcePoint to closestNeighbors for pixel;
                    // set doSortAndPush to true;
                // elif sourcePoint is closer to pixel than it's current close neighbor points:
                    // replace the furthest neighbor point with sourcePoint;
                    // set doSortAndPush to true;
                // if flag doSortAndPush is true:
                    // re-sort closest neighbors; 
                    // enqueue object made of neighbor pixel coordinates and sourcePoint;

    // for each pixel location:
        // if distance to closest point within a radius for point drawing:
            // color pixel the point color;
        // elif distances to the two closest neighbors are roughly equal:
            // color the pixel to your border color;
        // else 
            // color the pixel the color of the point's region; 

}

使用队列将确保区域并行传播，从而最大限度地减少像素访问总数。 如果使用堆栈，第一个点将填充整个图像，然后第二个点将填充比第一个点更靠近它的任何像素。 这种情况将继续下去，从而大大增加访问次数。 使用 FIFO 队列按照像素被推送的顺序处理像素。 无论使用堆栈还是队列，生成的图像都大致相同，但队列的 big-O 比堆栈算法的 big-O 更接近线性（与图像像素数相关）。 一般的想法是，区域将以相同的速率扩散，并且碰撞通常恰好发生在与区域边界相对应的点处。