¿El algoritmo más fácil de implementar del diagrama de Voronoi? [cerrado]

¿Cuáles son los algoritmos fáciles de implementar en el diagrama de Voronoi?

No pude encontrar ningún algoritmo especialmente en forma pseudo. Comparta algunos enlaces del algoritmo de diagrama de Voronoi, tutorial, etc.

Un algoritmo sencillo para calcular la triangulación de Delaunay de un conjunto de puntos es invertir los bordes . Dado que una triangulación de Delaunay es el gráfico dual de un diagrama de Voronoi, puede construir el diagrama a partir de la triangulación en tiempo lineal.

Desafortunadamente, el peor tiempo de ejecución del enfoque de inversión es O (n ^ 2). Existen mejores algoritmos, como el barrido de línea de Fortune, que toma O (n log n) tiempo. Sin embargo, esto es algo complicado de implementar. Si eres vago (como yo), te sugiero que busques una implementación existente de una triangulación de Delaunay, la utilices y luego calcules el gráfico dual.

En general, un buen libro sobre el tema es Computational Geometry de de Berg et al.

¿Más fácil? Ese es el enfoque de fuerza bruta: para cada píxel en su salida, iterar a través de todos los puntos, calcular la distancia, utilizar el más cercano. Lento como puede ser, pero muy simple. Si el rendimiento no es importante, funciona. Yo mismo he estado trabajando en un refinamiento interesante, pero sigo buscando para ver si alguien más ha tenido la misma idea (bastante obvia).

El algoritmo Bowyer-Watson es bastante fácil de entender. Aquí hay una implementación: http://paulbourke.net/papers/triangulate/ . Es una triangulación de delaunay para un conjunto de puntos, pero puede usarla para obtener el dual del delaunay, es decir, un diagrama de voronoi. Por cierto. el árbol de expansión mínimo es un subconjunto de la triangulación delaunay.

El algoritmo más eficiente para construir un diagrama de voronoi es el algoritmo de Fortune . Se ejecuta en O (n log n).

Aquí hay un enlace a su implementación de referencia en C .

Personalmente, me gusta mucho la implementación de Python de Bill Simons y Carson Farmer, ya que me pareció más fácil de extender.

La página de Wikipedia ( http://en.wikipedia.org/wiki/Voronoi_diagram ) tiene una sección de Algoritmos con enlaces a algoritmos para implementar diagramas de Voronoi.

Hay una implementación de voronoi disponible gratuitamente para gráficos 2-d en C y en C ++ de Stephan Fortune / Shane O'Sullivan:

VoronoiDiagramGenerator.cpp 

VoronoiDiagramGenerator.h 

Lo encontrará en muchos lugares. Es decir, en http://www.skynet.ie/~sos/masters/

Aquí hay una implementación de javascript que usa quat-tree y permite la construcción incremental.

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

Si bien la pregunta original es sobre cómo implementar Voronoi, si hubiera encontrado una publicación que dijera lo siguiente cuando estaba buscando información sobre este tema, me habría ahorrado mucho tiempo:

Hay mucho código C ++ "casi correcto" en Internet para implementar diagramas de Voronoi. La mayoría rara vez ha provocado fallas cuando los puntos de semilla se vuelven muy densos. Recomendaría probar ampliamente cualquier código que encuentre en línea con la cantidad de puntos que espera usar en su proyecto terminado antes de perder demasiado tiempo en él.

La mejor de las implementaciones que encontré en línea fue parte del programa MapManager vinculado desde aquí: http://www.skynet.ie/~sos/mapviewer/voronoi.php En su mayoría funciona, pero obtengo una corrupción de diagrama intermitente cuando trato con Ordene 10 ^ 6 puntos. No he podido averiguar exactamente cómo se está infiltrando la corrupción.

Anoche encontré esto: http://www.boost.org/doc/libs/1_53_0_beta1/libs/polygon/doc/voronoi_main.htm "La biblioteca Boost.Polygon Voronoi". Parece muy prometedor. Esto viene con pruebas de referencia para demostrar su precisión y un gran rendimiento. La biblioteca tiene una interfaz y documentación adecuadas. Me sorprende no haber encontrado esta biblioteca antes, de ahí que escribo sobre ella aquí. (Leí esta publicación al principio de mi investigación).

En realidad, hay implementaciones para 25 idiomas diferentes disponibles en https://rosettacode.org/wiki/Voronoi_diagram

Por ejemplo, para 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);
    }
}

El algoritmo más simple proviene de la definición de un diagrama de voronoi: "La división de un plano con n puntos en polígonos convexos de manera que cada polígono contiene exactamente un punto generador y cada punto en un polígono dado está más cerca de su punto generador que de cualquier otro . "definición de wolfram.

Lo importante aquí es que cada punto esté más cerca del punto de generación que cualquier otro, desde aquí el algoritmo es muy simple:

1. Tenga una variedad de puntos generadores.
2. Recorra cada píxel de su lienzo.
3. Para cada píxel, busque el punto de generación más cercano a él.
4. Dependiendo del diagrama que desees darle color al pixel. Si desea un diagrama separado con un borde, busque el segundo punto más cercano, luego verifique su diferencia y color con el color del borde si es más pequeño que algún valor.

Si desea un diagrama de color, tenga un color asociado con cada punto de generación y coloree cada píxel con su color asociado al punto de generación más cercano. Y eso es todo, no es eficiente pero muy fácil de implementar.

Este es el más rápido posible: es un voronoi simple pero se ve genial. Divide espacios en una cuadrícula, coloca un punto en cada celda de la cuadrícula colocada al azar y se mueve a lo largo de la cuadrícula verificando celdas de 3x3 para encontrar cómo se relaciona con las celdas adyacentes.

Es más rápido sin el degradado.

Puede preguntar cuál sería el voronoi 3d más fácil. Sería fascinante saberlo. Probablemente celdas de 3x3x3 y comprobando el gradiente.

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

y aquí sucede lo mismo con la distancia chebychev. puede usar un ruido flotante 2d random2f desde aquí:

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

editar: he convertido esto a C como código

Esto fue hace un tiempo, para el beneficio de aquellos que lo hacen, creo que esto es genial:

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

Compruebe la solución de fuerza bruta presentada con pseudocódigo por Richard Franks en su respuesta a la pregunta ¿Cómo puedo derivar un diagrama de Voronoi dado su conjunto de puntos y su triangulación de Delaunay?

Encontré esta excelente biblioteca C # en código de Google basada en el algoritmo de Fortune / algoritmo de línea de barrido

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

Solo necesita crear una lista. Se puede crear un vector pasando dos números (coordenadas) como flotante. Luego, pase la lista a Fortune.ComputeVoronoiGraph ()

Puede comprender un poco más el concepto del algoritmo en estas páginas de wikipedia:

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

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

Aunque una cosa que no pude entender es cómo crear una línea para bordes Parcialmente Infinitos (no sé mucho sobre geometría de coordenadas :-)). Si alguien lo sabe, hágamelo saber también.

Si está intentando dibujarlo en una imagen, puede utilizar un algoritmo de llenado de inundaciones basado en colas.

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; 

}

El uso de una cola asegurará que las regiones se extiendan en paralelo, minimizando el número total de visitas de píxeles. Si usa una pila, el primer punto llenará toda la imagen, luego el segundo llenará los píxeles más cercanos que el primer punto. Esto continuará aumentando considerablemente el número de visitas. El uso de una cola FIFO procesa los píxeles en el orden en que se insertan. Las imágenes resultantes serán aproximadamente las mismas ya sea que use la pila o la cola, pero el big-O para la cola está mucho más cerca de lineal (en relación con el número de píxeles de la imagen) que el big-O del algoritmo de pila. La idea general es que las regiones se extenderán al mismo ritmo y las colisiones ocurrirán generalmente exactamente en los puntos que corresponden a los límites de la región.