Самый простой алгоритм реализации диаграммы Вороного?
Какие простые алгоритмы для реализации диаграммы Вороного?
Я не смог найти алгоритм специально в псевдо-форме. Пожалуйста, поделитесь некоторыми ссылками алгоритма диаграммы Вороного, учебника и т. Д.
14 ответов
Простой алгоритм вычисления триангуляции Делоне для набора точек - это переворот ребер. Поскольку триангуляция Делоне является двойственным графом диаграммы Вороного, вы можете построить диаграмму из триангуляции за линейное время.
К сожалению, наихудшее время прогона подхода переворота - O(n^2). Существуют лучшие алгоритмы, такие как развертка линии Fortune, которые занимают O(n log n) времени. Это несколько сложно реализовать, хотя. Если вы ленивы (как и я), я бы предложил поискать существующую реализацию триангуляции Делоне, использовать ее, а затем вычислить двойной граф.
В целом, хорошая книга по этой теме - " Вычислительная геометрия " де Берга и соавт.
Самый простой? Это подход грубой силы: для каждого пикселя в выходных данных итерируйте по всем точкам, вычисляйте расстояние, используйте ближайший. Медленно, как может быть, но очень просто. Если производительность не важна, она делает работу. Я сам работал над интересным уточнением, но все еще искал, чтобы узнать, была ли у кого-то еще такая же (довольно очевидная) идея.
Алгоритм Бойера-Ватсона довольно прост для понимания. Вот реализация: http://paulbourke.net/papers/triangulate/. Это триангуляция Делоне для набора точек, но вы можете использовать ее, чтобы получить двойник Делоне, то есть диаграмму Вороного. КСТАТИ. минимальное остовное дерево является подмножеством триангуляции Делоне.
Наиболее эффективным алгоритмом построения диаграммы вороного является алгоритм Фортуны. Он работает в O(N журнала N).
Вот ссылка на его справочную реализацию на С.
Лично мне очень нравится реализация Python Биллом Саймонсом и Карсоном Фармером, так как мне было проще расширять.
На странице Википедии ( http://en.wikipedia.org/wiki/Voronoi_diagram) есть раздел "Алгоритмы" со ссылками на алгоритмы для реализации диаграмм Вороного.
Существует свободно доступная реализация вороной для двумерных графов на С и С ++ от Стефана Фортуни / Шейна О'Салливана:
VoronoiDiagramGenerator.cpp
VoronoiDiagramGenerator.h
Вы найдете это во многих местах. То есть на http://www.skynet.ie/~sos/masters/
Вот реализация javascript, которая использует quat-tree и допускает пошаговое построение.
Это самый быстрый вариант - это простой вороной, но выглядит великолепно. Он делит пробелы на сетку, размещает точку в каждой ячейке сетки случайным образом и перемещается вдоль сетки, проверяя ячейки 3х3, чтобы найти, как она связана с соседними ячейками.
Это быстрее без градиента.
Вы можете спросить, какой будет самая простая 3d вороной. Было бы интересно узнать. Вероятно, 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 );
}
и тут то же самое с чебычевым расстоянием. отсюда вы можете использовать случайный 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 );
}
На самом деле на 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);
}
}
Хотя первоначальный вопрос спрашивает о том, как реализовать Вороного, если бы я искал сообщение, в котором говорилось бы следующее, когда я искал информацию по этому вопросу, это сэкономило бы мне много времени:
В Интернете много "почти правильного" кода 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 Вороного". Это выглядит очень многообещающе. Это идет с тестами, чтобы доказать его точность и отличную производительность. Библиотека имеет соответствующий интерфейс и документацию. Я удивлен, что не нашел эту библиотеку до сих пор, поэтому я написал об этом здесь. (Я прочитал этот пост в начале моего исследования.)
Простейший алгоритм исходит из определения диаграммы Вороного: "Разбиение плоскости с n точками на выпуклые многоугольники так, что каждый многоугольник содержит ровно одну порождающую точку, и каждая точка в данном многоугольнике ближе к своей порождающей точке, чем к любой другой определение от вольфрама.
Важной частью здесь является то, что каждая точка находится ближе к точке генерации, чем любая другая, отсюда алгоритм очень прост:
- Иметь массив генерирующих точек.
- Переберите каждый пиксель на вашем холсте.
- Для каждого пикселя ищите ближайшую к нему точку генерации.
- В зависимости от того, на какой диаграмме вы хотите получить цвет пикселя. Если вы хотите, чтобы диаграмма была отделена рамкой, проверьте, находится ли вторая и ближайшая точки, а затем проверьте их разницу и цвет с цветом рамки, если он меньше некоторого значения.
Если вы хотите цветовую диаграмму, то укажите цвет, связанный с каждой точкой генерации, и раскрасьте каждый пиксель цветом, связанным с ближайшей точкой генерации. И это все, это не эффективно, но очень легко реализовать.
Проверьте решение грубой силы, представленное Alexandra Franks с псевдокодом в своем ответе на вопрос " Как получить диаграмму Вороного, учитывая ее набор точек и триангуляцию Делоне?"
Если вы пытаетесь нарисовать его на изображении, вы можете использовать основанный на очереди алгоритм заполнения.
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 алгоритма стека. Общая идея заключается в том, что регионы будут распространяться с одинаковой скоростью, и столкновения, как правило, будут происходить точно в точках, которые соответствуют границам регионов.
Нашел эту превосходную библиотеку C# в коде Google на основе алгоритма Fortune / алгоритма Sweep Line
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
Хотя одна вещь, которую я не смог понять, это как создать линию для частично бесконечных ребер (не знаю много о координатной геометрии:-)). Если кто-то знает, пожалуйста, дайте мне знать это тоже.
Вокруг есть несколько VoronoiDiagramGenerator.cpp/h
требующие серьезной очистки памяти, если вы планируете тяжелое приложение в реальном времени
как и все фортуны, есть проблемы с очень близкими точками, по крайней мере
движение от поплавка к двойному
убрать "одинаковую" точку при старте
- тогда попробуй разобраться с точностью вопроса в редком случае