Algoritmo do diagrama de Voronoi mais fácil de implementar? [fechadas]

88

Quais são os algoritmos fáceis para implementar o diagrama de Voronoi?

Não consegui encontrar nenhum algoritmo especialmente na forma pseudo. Compartilhe alguns links do algoritmo do diagrama de Voronoi, tutorial etc.

fireball003
fonte
1
Veja o código e a API em saturnapi.com/vpartition/voronoi-seed-partition-plot
FullStack de

Respostas:

32

Um algoritmo fácil para calcular a triangulação Delaunay de um conjunto de pontos é inverter as arestas . Como uma triangulação de Delaunay é o gráfico dual de um diagrama de Voronoi, você pode construir o diagrama a partir da triangulação em tempo linear.

Infelizmente, o pior caso de tempo de execução da abordagem de inversão é O (n ^ 2). Existem algoritmos melhores, como a varredura de linha da Fortune, que levam um tempo O (n log n). No entanto, isso é um tanto complicado de implementar. Se você é preguiçoso (como eu), sugiro que você procure uma implementação existente de uma triangulação de Delaunay, use-a e calcule o gráfico dual.

Em geral, um bom livro sobre o assunto é Geometria Computacional de de Berg et al.

rodion
fonte
19

Mais fácil? Essa é a abordagem da força bruta: para cada pixel em sua saída, itere por todos os pontos, calcule a distância e use o mais próximo. Lento como pode ser, mas muito simples. Se o desempenho não for importante, ele faz o trabalho. Tenho trabalhado em um refinamento interessante, mas ainda estou procurando para ver se mais alguém teve a mesma ideia (bastante óbvia).

Suricou Raven
fonte
14

O algoritmo Bowyer-Watson é bastante fácil de entender. Aqui está uma implementação: http://paulbourke.net/papers/triangulate/ . É uma triangulação delaunay para um conjunto de pontos, mas você pode usá-la para obter o dual de delaunay, ou seja, um diagrama de voronoi. BTW. a árvore de abrangência mínima é um subconjunto da triangulação delaunay.

Gigamegs
fonte
12

O algoritmo mais eficiente para construir um diagrama de voronoi é o algoritmo de Fortune . Ele é executado em O (n log n).

Aqui está um link para a sua implementação de referência em C .

Pessoalmente, gosto muito da implementação do python por Bill Simons e Carson Farmer, pois achei mais fácil estender.

Marco Pashkov
fonte
o link para a implementação c não parece mais funcionar :(
FutureCake
1
@FutureCake Internet Archive para o resgate: web.archive.org/web/20181018224943/http://ect.bell-labs.com/who/…
polettix
9

Há uma implementação voronoi disponível gratuitamente para gráficos 2-d em C e em C ++ de Stephan Fortune / Shane O'Sullivan:

VoronoiDiagramGenerator.cpp 

VoronoiDiagramGenerator.h 

Você o encontrará em muitos lugares. Ou seja, em http://www.skynet.ie/~sos/masters/

RED SOFT ADAIR
fonte
4
Amplamente referenciado, não documentado e quase todas as reimplementações que vi com base neste código estão erradas (em diferentes linguagens, muitas pessoas precisam do Voronoi, poucos podem entendê-lo bem o suficiente para portar corretamente). As únicas portas funcionais que vi são da comunidade científica / acadêmica e têm assinaturas de funções extremamente complicadas - ou extremamente otimizadas (de modo que não podem ser usadas para a maioria dos propósitos), tornando-as inutilizáveis ​​por programadores normais.
Adam
VoronoiDiagramGenerator.cpp tem funcionalidade limitada. Ele produzirá um conjunto não ordenado de arestas. Extrair polígonos reais disso não é trivial. No lado positivo, ele apresenta um clipe contra um retângulo delimitador, de forma que nenhum ponto infinito seja gerado.
Bram
6

Embora a pergunta original seja sobre como implementar o Voronoi, se eu tivesse encontrado um post que dizia o seguinte quando estava procurando informações sobre esse assunto, teria me economizado muito tempo:

Existem muitos códigos C ++ "quase corretos" na Internet para a implementação de diagramas de Voronoi. A maioria raramente dispara falhas quando os pontos de semente ficam muito densos. Eu recomendaria testar qualquer código que você encontrar online extensivamente com o número de pontos que você espera usar em seu projeto concluído, antes de perder muito tempo com ele.

A melhor das implementações que encontrei online foi parte do programa MapManager linkado aqui: http://www.skynet.ie/~sos/mapviewer/voronoi.php Funciona principalmente, mas estou recebendo corrupção intermitente de diagrama ao lidar com peça 10 ^ 6 pontos. Não consegui descobrir exatamente como a corrupção está se infiltrando.

Ontem à noite eu encontrei este: http://www.boost.org/doc/libs/1_53_0_beta1/libs/polygon/doc/voronoi_main.htm "A biblioteca Boost.Polygon Voronoi". Parece muito promissor. Isso vem com testes de benchmark para provar sua precisão e excelente desempenho. A biblioteca possui interface e documentação adequadas. Estou surpreso por não ter encontrado essa biblioteca antes, por isso escrevi sobre ela aqui. (Eu li esta postagem no início da minha pesquisa.)

mrdunk
fonte
4

Na verdade, existem implementações para 25 idiomas diferentes disponíveis em https://rosettacode.org/wiki/Voronoi_diagram

Por exemplo, 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);
    }
}
0xBADF00D
fonte
3

O algoritmo mais simples vem da definição de um diagrama de voronoi: "O particionamento de um plano com n pontos em polígonos convexos de modo que cada polígono contenha exatamente um ponto gerador e cada ponto em um determinado polígono esteja mais próximo de seu ponto gerador do que de qualquer outro . "definição de volfrâmio.

A parte importante aqui é que cada ponto está mais próximo do ponto de geração do que qualquer outro, a partir daqui o algoritmo é muito simples:

  1. Tenha uma série de pontos geradores.
  2. Percorra cada pixel em sua tela.
  3. Para cada pixel, procure o ponto gerador mais próximo a ele.
  4. Dependendo de qual diagrama você deseja obter a cor do pixel. Se você quiser um diagrama separado por uma borda, verifique o segundo ao ponto mais próximo e, a seguir, verifique a diferença e a cor com a cor da borda se for menor que algum valor.

Se você quiser um diagrama de cores, tenha uma cor associada a cada ponto gerador e colora cada pixel com a cor associada ao ponto gerador mais próximo. E é isso, não é eficiente, mas muito fácil de implementar.

Alon Kellner
fonte
3

Este é o mais rápido possível - é um voronoi simples, mas parece ótimo. Ele divide os espaços em uma grade, coloca um ponto em cada célula da grade colocada aleatoriamente e se move ao longo da grade verificando as células 3x3 para descobrir como ela se relaciona com as células adjacentes.

É mais rápido sem o gradiente.

Você pode perguntar qual seria o voronoi 3D mais fácil. Seria fascinante saber. Provavelmente 3x3x3 células e gradiente de verificação.

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

e aqui é o mesmo com distância chebychev. você pode usar um ruído de flutuação 2d random2f aqui:

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

editar: eu converti isso para código C like

Isso foi há um tempo atrás, para o benefício de quem o quê, eu acho que isso é legal:

 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 );
 }
aliential
fonte
Por que você usa tantas variáveis ​​de uma letra que não são autoexplicativas? E o que é ivec2? ou vec2? Isso é ilegível.
shinzou de
Bom ponto, acho que lutei o dia todo com isso também: answers.unity3d.com/questions/638662/… atualizei este texto com o código
aliential
0

Encontrei esta excelente biblioteca C # no código do Google com base no algoritmo / algoritmo de linha de varredura da Fortune

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

Você só precisa criar uma lista. Um vetor pode ser criado passando em dois números (coordenadas) como flutuante. Em seguida, passe a lista para Fortune.ComputeVoronoiGraph ()

Você pode entender o conceito do algoritmo um pouco mais nestas páginas da Wikipedia:

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

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

Embora uma coisa que eu não fui capaz de entender é como criar uma linha para arestas parcialmente infinitas (não sei muito sobre geometria de coordenadas :-)). Se alguém souber, por favor, me informe também.

Hetansh
fonte
2
Embora esses links possam responder à pergunta, é melhor incluir as partes essenciais da resposta aqui e fornecer o link para referência. As respostas somente com link podem se tornar inválidas se a página vinculada mudar.
Kmeixner
0

Se você está tentando desenhá-lo em uma imagem, pode usar um algoritmo de preenchimento com base em fila.

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; 

}

O uso de uma fila garantirá que as regiões se espalhem em paralelo, minimizando o número total de visitas de pixels. Se você usar uma pilha, o primeiro ponto preencherá a imagem inteira e o segundo preencherá todos os pixels mais próximos a ela do que o primeiro ponto. Isso vai continuar, aumentando muito o número de visitas. O uso de uma fila FIFO processa os pixels na ordem em que são enviados. As imagens resultantes serão aproximadamente as mesmas se você usar pilha ou fila, mas o big-O para a fila está muito mais próximo do linear (em relação ao número de pixels da imagem) do que o big-O do algoritmo de pilha. A ideia geral é que as regiões se espalharão na mesma taxa e as colisões geralmente acontecerão exatamente em pontos que correspondem aos limites da região.

RollerSimmer
fonte