L'algorithme le plus facile du diagramme de Voronoi à mettre en œuvre?

un algorithme simple pour calculer la triangulation Delaunay d'un jeu de points est retournant les bords . Comme une triangulation Delaunay est le double graphe D'un diagramme de Voronoi, vous pouvez construire le diagramme à partir de la triangulation en temps linéaire.

malheureusement, la durée la plus mauvaise de l'approche de retournement est O(N^2). De meilleurs algorithmes tels que le balayage de ligne de Fortune existent, qui prennent O (N log n) Le temps. C'est quelque peu délicat à mettre en œuvre bien. Si vous êtes paresseux (comme je le suis), je suggère de chercher une implémentation existante d'une triangulation Delaunay, utilisez-la, puis calculez le graphe double.

en général, un bon livre sur le sujet est géométrie computationnelle par de Berg et al.

facile? C'est l'approche de la force brute: pour chaque pixel de votre sortie, itérez tous les points, calculez la distance, Utilisez la plus proche. Aussi lent que possible, mais très simple. Si le rendement n'est pas important, il fait le travail. J'ai moi-même travaillé sur un raffinement intéressant, mais je cherche toujours à savoir si quelqu'un d'autre a eu la même idée (plutôt évidente).

L'algorithme de Bowyer-Watson est assez facile à comprendre. Voici une implémentation: http://paulbourke.net/papers/triangulate / . C'est une triangulation delaunay pour un ensemble de points mais vous pouvez l'utiliser pour obtenir le dual du delaunay,i.e. un voronoi-diagramme. BTW. l'arbre couvrant minimum est un sous-ensemble de la triangulation delaunay.

la page Wikipedia ( http://en.wikipedia.org/wiki/Voronoi_diagram ) comporte une section algorithmes avec des liens vers des algorithmes pour la mise en œuvre de diagrammes Voronoi.

Il est librement disponible de voronoi de mise en oeuvre 2-d des graphiques en C et en C++ à partir de Stephan Fortune / Shane O'Sullivan:

VoronoiDiagramGenerator.cpp 

VoronoiDiagramGenerator.h 

vous le trouverez à de nombreux endroits. C'est-à-dire: à http://www.skynet.ie / ~sos / masters /

l'algorithme le plus efficace pour construire un diagramme de voronoi est algorithme de Fortune . Il s'exécute en O(n log n).

voici un lien vers son mise en œuvre de référence dans C .

personnellement, J'aime beaucoup le Python implementation de Bill Simons et Carson Farmer, car je l'ai trouvé plus facile à étendre.

Voici une implémentation javascript qui utilise quat-tree et permet la construction incrémentale.

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

alors que la question originale demande comment mettre en œuvre Voronoi, si j'avais trouvé un post qui disait ce qui suit lorsque je cherchais des informations sur ce sujet, il m'aurait sauvé beaucoup de temps:

il y a beaucoup de code C++" presque correct " sur internet pour implémenter des diagrammes Voronoi. La plupart ont rarement déclenché des échecs lorsque les points de graines deviennent très denses. Je recommande de tester n'importe quel code que vous trouvez en ligne intensivement avec le nombre de points vous s'attendre à utiliser dans votre projet terminé avant de perdre trop de temps sur elle.

le meilleur des implémentations que j'ai trouvé en ligne faisait partie du programme MapManager lié d'ici: http://www.skynet.ie/~sos/mapviewer/voronoi.php Il fonctionne la plupart du temps, mais je reçois la corruption de diagramme intermittent en traitant l'ordre 10^6 points. Je n'ai pas réussi à comprendre exactement comment la corruption s'insinue.

la nuit dernière trouvé ce: http://www.boost.org/doc/libs/1_53_0_beta1/libs/polygon/doc/voronoi_main.htm "Le Coup De Pouce.Polygone de Voronoï de la bibliothèque". Il a l'air très prometteur. Cela vient avec des tests de référence pour prouver sa précision et a une grande performance. La bibliothèque dispose d'une interface et d'une documentation adéquates. Je suis surpris de ne pas avoir trouvé cette bibliothèque avant maintenant, d'où mon écriture à ce sujet ici. (J'ai lu ce post au début de ma recherche.)

C'est le plus rapide possible - c'est un simple voronoi mais il semble grand. Il divise les espaces en une grille, place un point dans chaque cellule de grille placée au hasard et se déplace le long de la grille en vérifiant les cellules 3x3 pour trouver comment il se rapporte aux cellules adjacentes.

c'est plus rapide sans la pente.

vous pouvez vous demander ce que serait le voronoi 3d le plus facile. Ce serait fascinant de le savoir. Probablement des cellules 3x3x3 et un gradient de contrôle.

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

et voici la même chose avec la distance chebychev. vous pouvez utiliser un bruit de flotteur 2D random2f d'ici:

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

edit: Je l'ai converti en code C comme

c'était il y a un moment, pour le bénéfice de ceux qui ce qu'il, je crois c'est cool:

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

en fait il y a des implémentations pour 25 langues différentes disponibles sur https://rosettacode.org/wiki/Voronoi_diagram

e. g for 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);
    }
}

Check solution brute-force présentée avec un pseudo-code par Richard Franks dans sa réponse à la question Comment puis-je dériver un diagramme de Voronoi compte tenu de son ensemble de points et de sa triangulation Delaunay?

l'algorithme le plus simple provient de la définition d'un diagramme de voronoi: "Le partitionnement d'un plan avec n points en polygones convexes de telle sorte que chaque polygone contient exactement un point générateur et chaque point dans un polygone donné est plus proche de son point Générateur que de tout autre. " définition de wolfram.

la partie importante ici est à peu près chaque point étant plus proche du point Générateur que n'importe quel autre, d'ici l'algorithme est très simple:

1. ont un réseau de points générateurs.
2. boucle à travers chaque pixel sur votre toile.
3. pour chaque pixel, cherchez le point de génération le plus proche.
4. selon le diagramme que vous souhaitez obtenir la couleur du pixel. Si vous voulez un diagramme séparé avec un bord, vérifiez le deuxième au point le plus proche, puis vérifiez leur différence et la couleur avec la couleur de bord si elle est plus petite que une certaine valeur.

si vous voulez un diagramme de couleur, alors avoir une couleur associée à chaque point générateur et la couleur de chaque pixel avec la couleur associée au point générateur le plus proche. Et c'est tout, ce n'est pas efficace mais très facile à mettre en œuvre.

trouvé cet excellent c # bibliothèque sur google code basé sur l'algorithme de Fortune / Sweep line algorithme

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

Vous avez juste besoin de créer une Liste. Un vecteur peut être créé en passant en deux nombres (coordonnées) comme flotteur. Puis passer la liste en chance.ComputeVoronoiGraph()

, Vous pouvez comprendre le concept de l'algorithme un peu plus de ces les pages de wikipédia:

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

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

bien qu'une chose que je n'ai pas pu comprendre est comment créer une ligne pour les bords partiellement infinis (Je ne sais pas beaucoup sur la géométrie des coordonnées :-)). Si quelqu'un le sait, faites-le moi savoir aussi.

si vous essayez de le dessiner sur une image, vous pouvez utiliser un algorithme de remplissage de la file d'attente.

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; 

}

L'utilisation d'une file d'attente permettra de s'assurer que les régions s'étendent en parallèle, minimisant ainsi le nombre total de pixels visités. Si vous utilisez une pile, le premier point remplira l'image entière, le second remplira les pixels plus près que le premier point. Cela va continuer, ce qui augmente considérablement visite compte. L'utilisation D'une file D'attente FIFO traite les pixels dans l'ordre suivant: ils sont poussés. Les images résultantes seront à peu près les mêmes que vous utilisiez la pile ou la file d'attente, mais le big-O pour la file d'attente est beaucoup plus proche du linéaire (par rapport au nombre de pixels d'image) que le big-O de la pile.l'idée générale est que les régions se propageront au même rythme et les collisions se produiront généralement exactement aux points qui correspondent aux limites de la région.

il y a plusieurs VoronoiDiagramGenerator.cpp / h autour de 151910920"

nécessitant un nettoyage sérieux de la mémoire si vous planifiez une application en temps réel lourde

comme tous fortune sweepline ont des problèmes avec des points très proches au moins

- passage du flotteur au double

- supprimer le point de départ" identique

- puis essayer de traiter avec précision question dans les cas rares