实现 Voronoi 图的简单算法有哪些？
我找不到任何特别以伪形式存在的算法。请分享一些Voronoi图算法、教程等的链接。
问问题
91221 次
14 回答
33
计算点集的 Delaunay 三角剖分的一种简单算法是翻转边缘。由于 Delaunay 三角剖分是 Voronoi 图的对偶图，因此您可以在线性时间内从三角剖分构建图。
不幸的是，翻转方法的最坏情况运行时间是 O(n^2)。存在更好的算法，例如 Fortune 的线扫描，需要 O(n log n) 时间。不过，这实施起来有些棘手。如果您很懒惰（就像我一样），我建议您寻找 Delaunay 三角剖分的现有实现，使用它，然后计算对偶图。
一般来说，关于这个主题的一本好书是de Berg 等人的Computational Geometry 。
于 2009-06-10T00:18:30.973 回答
22
最简单？这就是蛮力方法：对于输出中的每个像素，遍历所有点，计算距离，使用最近的。尽可能慢，但非常简单。如果性能不重要，它就可以完成工作。我自己一直在进行有趣的改进，但仍在寻找其他人是否有相同（相当明显）的想法。
于 2012-06-01T10:19:33.047 回答
14
Bowyer-Watson 算法很容易理解。这是一个实现： http: //paulbourke.net/papers/triangulate/。这是一组点的 delaunay 三角剖分，但您可以使用它来获得 delaunay 的对偶，即 voronoi 图。顺便提一句。最小生成树是 delaunay 三角剖分的子集。
于 2013-08-06T15:23:00.853 回答
12
构建 voronoi 图最有效的算法是 Fortune 算法。它在 O(n log n) 中运行。
这是他在 C 中的参考实现的链接。
我个人非常喜欢 Bill Simons 和 Carson Farmer 的python 实现，因为我发现它更容易扩展。
于 2013-04-15T20:33:56.477 回答
10
维基百科页面 ( http://en.wikipedia.org/wiki/Voronoi_diagram ) 有一个算法部分，其中包含实现 Voronoi 图的算法的链接。
于 2009-06-10T00:10:31.330 回答
9
Stephan Fortune / Shane O'Sullivan 为 C 和 C++ 中的二维图提供了一个免费的 voronoi 实现：
VoronoiDiagramGenerator.cpp
VoronoiDiagramGenerator.h
你会在很多地方找到它。即在http://www.skynet.ie/~sos/masters/
于 2009-06-10T08:55:32.237 回答
8
这是一个使用 quat-tree 并允许增量构造的 javascript 实现。
于 2011-12-20T15:31:44.353 回答
6
这是最快的 - 这是一个简单的 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 );
}
于 2014-02-11T09:45:12.630 回答
6
虽然最初的问题是关于如何实现 Voronoi，但如果我在搜索有关此主题的信息时发现了一篇说以下内容的帖子，它会为我节省很多时间：
互联网上有很多用于实现 Voronoi 图的“几乎正确”的 C++ 代码。当种子点变得非常密集时，大多数很少触发故障。我建议在你浪费太多时间之前，用你希望在完成的项目中使用的点数来广泛地测试你在网上找到的任何代码。
我在网上找到的最好的实现是从这里链接的 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 库”。它看起来很有希望。这带有基准测试以证明其准确性并具有出色的性能。该库具有适当的界面和文档。我很惊讶我之前没有找到这个库，因此我在这里写了这篇文章。（我在研究的早期就读过这篇文章。）
于 2014-02-18T10:45:07.220 回答
5
实际上，https: //rosettacode.org/wiki/Voronoi_diagram 上有 25 种不同语言的实现
例如对于 Java：
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);
}
}
于 2017-02-18T21:48:24.770 回答
3
最简单的算法来自 voronoi 图的定义：“将具有 n 个点的平面划分为凸多边形，使得每个多边形恰好包含一个生成点，并且给定多边形中的每个点都比任何其他点更靠近其生成点. " 来自 wolfram 的定义。
这里的重要部分是每个点都比其他点更接近生成点，从这里算法非常简单：
- 有一组生成点。
- 循环遍历画布上的每个像素。
- 对于每个像素，寻找离它最近的生成点。
- 根据您希望为像素着色的图表。如果您想要一个用边框分隔的图表，请检查第二个最接近的点，然后使用边框颜色检查它们的差异和颜色（如果它小于某个值）。
如果你想要一个颜色图，那么就有一个与每个生成点相关联的颜色，并用它最接近的生成点相关颜色为每个像素着色。就是这样，它效率不高，但很容易实现。
于 2016-09-20T08:46:56.460 回答
1
检查理查德·弗兰克斯（ Richard Franks）在他对问题的回答中使用伪代码提供的蛮力解决方案如何根据其点集及其 Delaunay 三角剖分推导出 Voronoi 图？
于 2011-10-27T13:12:03.540 回答
0
在基于财富算法/扫描线算法的谷歌代码上找到了这个优秀的 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
虽然我无法理解的一件事是如何为部分无限边缘创建一条线（对坐标几何不太了解:-)）。如果有人知道，也请告诉我。
于 2015-06-03T15:01:40.767 回答
0
如果您尝试将其绘制到图像上，则可以使用基于队列的洪水填充算法。
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 队列按照它们被推送的顺序处理像素。无论您使用堆栈还是队列，生成的图像都将大致相同，但队列的大 O 比堆栈算法的大 O 更接近线性（相对于图像像素的数量）。一般的想法是，区域将以相同的速率传播，并且碰撞通常会恰好发生在与区域边界相对应的点上。
于 2018-07-06T00:56:38.520 回答