Каковы простые алгоритмы для реализации диаграммы Вороного?
Я не мог найти какой-либо алгоритм специально в псевдо форме. Пожалуйста, поделитесь некоторыми ссылками алгоритма диаграммы Вороного, учебника и т.д.
Самый простой алгоритм построения Вороного?
Ответ 1
Легкий алгоритм вычисления триангуляции Деланея точечного множества переворачивает края. Поскольку триангуляция Делоне является двойственным графом диаграммы Вороного, вы можете построить диаграмму из триангуляции в линейном времени.
К сожалению, наихудшее время работы подхода сбрасывания - O (n ^ 2). Существуют лучшие алгоритмы, такие как развертка линии Fortune, которые берут O (n log n). Это несколько сложно реализовать. Если вы ленивы (как и я), я бы предложил искать существующую реализацию триангуляции Delaunay, использовать ее, а затем вычислить двойной граф.
В целом, хорошая книга по теме Вычислительная геометрия от Berg и др.
Ответ 2
Самый простой? Это подход грубой силы: для каждого пикселя в вашем выходе, итерации по всем точкам, вычислите расстояние, используйте ближайший. Медленно, как может быть, но очень просто. Если производительность не важна, она выполняет эту работу. Я сам работаю над интересной утонченностью, но все еще ищу, чтобы увидеть, имеет ли кто-нибудь еще одну и ту же (довольно очевидную) идею.
Ответ 3
Алгоритм Бойера-Ватсона довольно легко понять. Вот реализация: http://paulbourke.net/papers/triangulate/. Это треугольная триангуляция для множества точек, но вы можете использовать ее, чтобы получить двойное от delaunay, т.е. voronoi-диаграмма. КСТАТИ. минимальное остовное дерево является подмножеством триангуляции delaunay.
Ответ 4
Страница Wikipedia (http://en.wikipedia.org/wiki/Voronoi_diagram) имеет раздел Алгоритмы со ссылками на алгоритмы для реализации диаграмм Вороного.
Ответ 5
Существует свободная реализация voronoi для 2-х графиков в C и С++ от Stephan Fortune/Shane O'Sullivan:
VoronoiDiagramGenerator.cpp
VoronoiDiagramGenerator.h
Вы найдете его во многих местах. То есть на http://www.skynet.ie/~sos/masters/
Ответ 6
Самый эффективный алгоритм построения диаграммы voronoi - Фортунный алгоритм. Он работает в O (n log n).
Вот ссылка на его ссылочную реализацию в C.
Лично мне очень нравится реализация python от Билла Саймонса и Карсона Фармера, так как мне стало легче распространяться.
Ответ 7
Вот реализация javascript, которая использует quat-tree и позволяет инкрементное построение.
Ответ 8
В то время как первоначальный вопрос спрашивает о том, как реализовать 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". Это выглядит очень многообещающе. Это происходит с эталонными тестами, чтобы доказать точность и отличную производительность. Библиотека имеет надлежащий интерфейс и документацию. Я удивлен, что раньше я не нашел эту библиотеку, поэтому я пишу об этом здесь. (Я прочитал этот пост в начале моего исследования.)
Ответ 9
Это самая быстрая возможность - это простая ворона, но она отлично выглядит. Он делит пространства на сетку, помещает точку в каждую ячейку сетки, помещенную случайным образом, и перемещается по сетке, проверяя ячейки 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 );
}
и здесь то же самое с чебычевским расстоянием. вы можете использовать random3f 2d float noise здесь:
https://www.shadertoy.com/view/Msl3DM
edit: Я преобразовал это в 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 );
}
Ответ 10
На самом деле существуют реализации для 25 различных языков, доступных на https://rosettacode.org/wiki/Voronoi_diagram
Например, для 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);
}
}
Ответ 11
Проверить решение грубой силы, представленное псевдокодом Ричардом Франком в его ответе на вопрос Как получить диаграмма Вороного с учетом ее точечного множества и триангуляции Делоне?
Ответ 12
Самый простой алгоритм исходит из определения диаграммы ворона: "Разбиение плоскости с n точек на выпуклые многоугольники, так что каждый многоугольник содержит ровно одну точку генерации, а каждая точка в заданном многоугольнике ближе к своей порождающей точке, чем к любому другому." определение из wolfram.
Важная часть здесь заключается в том, что каждая точка ближе к генерирующей точке, чем любая другая, отсюда алгоритм очень прост:
- Имейте массив генерирующих точек.
- Прокручивайте каждый пиксель на вашем холсте.
- Для каждого пикселя найдите ближайшую к нему точку генерации.
- В зависимости от диаграммы вы хотите получить цвет пикселя. Если вы хотите, чтобы диаграмма была отделена рамкой, проверьте вторую на ближайшую точку, затем проверьте их разницу и цвет с цветом границы, если она меньше некоторого значения.
Если вы хотите, чтобы цветная диаграмма имела цвет, связанный с каждой точкой генерации, и цвет каждого пикселя с его ближайшим цветом, связанным с точкой генерации. И что об этом, это не эффективно, но очень легко реализовать.
Ответ 13
Нашел эту отличную библиотеку С# в коде google, основанном на алгоритме Fortune/алгоритме линии развертки
https://code.google.com/p/fortune-voronoi/
Вам просто нужно создать список. Вектор может быть создан путем передачи в два числа (координаты) как float. Затем передайте список в Fortune.ComputeVoronoiGraph()
Вы можете понять концепцию алгоритма немного больше с этих страниц википедии:
http://en.wikipedia.org/wiki/Fortune%27s_algorithm
http://en.wikipedia.org/wiki/Sweep_line_algorithm
Хотя одна вещь, которую я не мог понять, - это создать линию для Частично бесконечных ребер (не знаю много о геометрии координат:-)). Если кто-то знает, сообщите мне об этом.
Ответ 14
существует несколько VoronoiDiagramGenerator.cpp/h вокруг
требуется всякая серьезная очистка памяти если вы планируете тяжелое приложение в реальном времени
как и все судьбы sweepline, имеют проблемы с очень близкими точками как минимум
-move от float до double
-remove "идентичная" точка в начале
- тогда попытайтесь справиться с проблемой точности в редком случае