Самый простой алгоритм диаграммы Вороного для реализации? [закрыто]

Каковы простые алгоритмы реализации диаграммы Вороного?

Я не мог найти ни одного алгоритма специально в псевдо форме. Пожалуйста, поделитесь некоторыми ссылками на алгоритм диаграммы Вороного, учебник и т. Д.

Простой алгоритм вычисления триангуляции Делоне набора точек - это переворот ребер . Поскольку триангуляция Делоне - это двойственный график диаграммы Вороного, вы можете построить диаграмму из триангуляции за линейное время.

К сожалению, время работы с переворачиванием в худшем случае - O (n ^ 2). Существуют лучшие алгоритмы, такие как строчная развертка Fortune, которые занимают время O (n log n). Однако реализовать это довольно сложно. Если вы ленивы (как и я), я бы посоветовал найти существующую реализацию триангуляции Делоне, использовать ее, а затем вычислить двойной граф.

В общем, хорошая книга по этой теме - Computational Geometry by de Berg et al.

Самый простой? Это метод грубой силы: для каждого пикселя в выходных данных перебирайте все точки, вычисляйте расстояние, используйте ближайший. Медленно, но очень просто. Если производительность не важна, она делает свою работу. Я сам работал над интересным усовершенствованием, но все еще ищу, есть ли у кого-нибудь такая же (довольно очевидная) идея.

Алгоритм Бойера-Ватсона довольно легко понять. Вот реализация: http://paulbourke.net/papers/triangulate/ . Это триангуляция Делоне для набора точек, но вы можете использовать ее для получения двойника Делоне, то есть диаграммы Вороного. Кстати. минимальное остовное дерево - это подмножество триангуляции Делоне.

Наиболее эффективным алгоритмом построения диаграммы Вороного является алгоритм Фортуны . Он выполняется за O (n log n).

Вот ссылка на его эталонной реализации в C .

Лично мне очень нравится реализация python Билла Саймонса и Карсона Фармера, так как я обнаружил, что ее легче расширять.

На странице Википедии ( http://en.wikipedia.org/wiki/Voronoi_diagram ) есть раздел Алгоритмы со ссылками на алгоритмы для реализации диаграмм Вороного.

Существует свободно доступная реализация voronoi для двумерных графиков на C и C ++ от Стефана Форчун / Шейна О'Салливана:

VoronoiDiagramGenerator.cpp 

VoronoiDiagramGenerator.h 

Вы найдете его во многих местах. Т.е. на http://www.skynet.ie/~sos/masters/

Вот реализация javascript, которая использует дерево квадратов и допускает инкрементное построение.

http://code.google.com/p/javascript-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". Выглядит очень многообещающе. Он поставляется с тестовыми тестами, подтверждающими его точность и отличную производительность. У библиотеки хороший интерфейс и документация. Я удивлен, что не нашел эту библиотеку раньше, поэтому я пишу об этом здесь. (Я прочитал этот пост в начале своего исследования.)

На самом деле есть реализации для 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);
    }
}

Самый простой алгоритм исходит из определения диаграммы Вороного: «Разбиение плоскости с n точками на выпуклые многоугольники так, что каждый многоугольник содержит ровно одну производящую точку, и каждая точка в данном многоугольнике ближе к своей производящей точке, чем к любой другой. ... "определение из вольфрама.

Важной частью здесь является то, что каждая точка находится ближе к генерирующей точке, чем любая другая, отсюда алгоритм очень прост:

1. Имейте массив генерирующих точек.
2. Просматривайте каждый пиксель на холсте.
3. Для каждого пикселя ищите ближайшую к нему генерирующую точку.
4. В зависимости от того, на какой диаграмме вы хотите получить цвет пикселя. Если вы хотите, чтобы диаграмма была разделена рамкой, проверьте наличие второй ближайшей точки, а затем проверьте их разницу и цвет с помощью цвета границы, если он меньше некоторого значения.

Если вам нужна цветовая диаграмма, укажите цвет, связанный с каждой точкой генерации, и раскрасьте каждый пиксель цветом, соответствующим ближайшей точке генерации. И это все, это неэффективно, но очень легко реализовать.

Это самый быстрый из возможных - это простой вороной, но выглядит он великолепно. Он делит пробелы на сетку, помещает точку в каждую ячейку сетки, размещенную случайным образом, и перемещается по сетке, проверяя ячейки 3x3, чтобы определить, как они соотносятся с соседними ячейками.

Это быстрее без градиента.

Вы спросите, какой будет самый простой 3д вороной. Было бы интересно узнать. Наверное 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 );
}

и здесь то же самое с расстоянием Чебычева. вы можете использовать случайный 2f-шум с плавающей точкой отсюда:

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 );
 }

Проверьте решение методом перебора, представленное с помощью псевдокода Ричардом Фрэнксом в его ответе на вопрос « Как мне вывести диаграмму Вороного с учетом ее набора точек и ее триангуляции Делоне?»

Нашел эту отличную библиотеку C # в коде Google, основанном на алгоритме Fortune / алгоритме Sweep line.

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

Хотя одной вещи я не мог понять, это как создать линию для частично бесконечных ребер (мало что знаю о координатной геометрии :-)). Если кто-то знает, дайте мне знать и об этом.

Если вы пытаетесь нарисовать его на изображении, вы можете использовать алгоритм заполнения очереди на основе флуда.

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 пиксели обрабатываются в том порядке, в котором они помещаются. Результирующие изображения будут примерно одинаковыми независимо от того, используете ли вы стек или очередь, но большой О для очереди гораздо ближе к линейному (по отношению к количеству пикселей изображения), чем большой О алгоритма стека. Общая идея состоит в том, что регионы будут распространяться с одинаковой скоростью, и столкновения, как правило, будут происходить точно в точках, которые соответствуют границам регионов.