algorithm - grafico - voronoi futbol
El algoritmo más fácil del diagrama de Voronoi para implementar? (14)
¿Cuáles son los algoritmos fáciles para implementar el diagrama de Voronoi?
No pude encontrar ningún algoritmo especialmente en pseudo forma. Por favor comparte algunos enlaces del algoritmo del diagrama de Voronoi, tutorial, etc.
Aquí hay una implementación de javascript que usa quat-tree y permite la construcción incremental.
Comprueba la solución de fuerza bruta presentada con pseudocódigo por Richard Franks en su respuesta a la pregunta ¿Cómo obtengo un diagrama de Voronoi dado su conjunto de puntos y su triangulación de Delaunay?
El algoritmo de Bowyer-Watson es bastante fácil de entender. Aquí hay una implementación: http://paulbourke.net/papers/triangulate/ . Es una triangulación delaunay para un conjunto de puntos, pero puedes usarla para obtener el dual del delaunay, es decir, un diagrama 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 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 por Bill Simons y Carson Farmer, ya que me resultó más fácil extenderla.
El algoritmo más simple proviene de la definición de un diagrama de voronoi: "La partición de un plano con n puntos en polígonos convexos, de manera que cada polígono contiene exactamente un punto de generación y cada punto de un polígono dado está más cerca de su punto de generación que cualquier otro . "definición de wolfram.
La parte importante aquí es que cada punto está más cerca del punto de generación que cualquier otro, a partir de aquí el algoritmo es muy simple:
- Tener una variedad de puntos de generación.
- Pasa por cada píxel de tu lienzo.
- Para cada píxel busque el punto de generación más cercano a él.
- Dependiendo de qué diagrama desee obtener el color del píxel. Si desea un diagrama separado con un borde, verifique el segundo hasta el 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 colores, tenga un color asociado con cada punto de generación y coloree cada píxel con el color asociado al punto de generación más cercano. Y eso es todo, no es eficiente, pero es muy fácil de implementar.
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);
}
}
Encontré esta excelente biblioteca de C # en el código de google basado en el algoritmo de Fortune / algoritmo de línea de barrido
https://code.google.com/p/fortune-voronoi/
Solo necesitas crear una lista. Se puede crear un Vector pasando dos números (coordenadas) como flotante. Luego pasa la lista a Fortune.ComputeVoronoiGraph ()
Puedes entender el concepto del algoritmo un poco más desde 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, por favor, hágamelo saber también.
Este es el más rápido posible, es un voronoi simple pero se ve genial. Divide los 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 revisando las celdas 3x3 para encontrar cómo se relaciona con las celdas adyacentes.
Es más rápido sin el gradiente.
Puede preguntar cuál sería el voronoi 3d más fácil. Sería fascinante saberlo. Probablemente células 3x3x3 y gradiente de comprobación.
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í es lo mismo con la distancia chebychev. puedes usar un ruido de flotación 2d aleatorio 2f desde aquí:
https://www.shadertoy.com/view/Msl3DM
editar: he convertido esto en C como código
Esto fue hace un tiempo, para el beneficio de aquellos que lo que, 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 );
}
Hay una implementación de voronoi disponible gratuitamente para gráficos bidimensionales en C y en C ++ de Stephan Fortune / Shane O''Sullivan:
VoronoiDiagramGenerator.cpp
VoronoiDiagramGenerator.h
Lo encontrarás en muchos lugares. Es decir, en http://www.skynet.ie/~sos/masters/
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.
Mas facil? Ese es el enfoque de la fuerza bruta: para cada píxel en tu salida, recorre todos los puntos, calcula la distancia, utiliza el más cercano. Lento como puede ser, pero muy simple. Si el rendimiento no es importante, hace el trabajo. He estado trabajando en un refinamiento interesante yo mismo, pero sigo buscando si alguien más ha tenido la misma idea (bastante obvia).
Mientras que la pregunta original pregunta 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 un montón de código C ++ "casi correcto" en Internet para implementar diagramas de Voronoi. La mayoría rara vez ha desencadenado fallas cuando los puntos de la semilla son muy densos. Recomendaría probar cualquier código que encuentre en línea extensamente 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 formaba parte del programa MapManager vinculado desde aquí: http://www.skynet.ie/~sos/mapviewer/voronoi.php Funciona en su mayoría, pero obtengo corrupción de diagramas intermitentes 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". Se ve muy prometedor. Esto viene con pruebas de referencia para demostrar su precisión y tiene un gran rendimiento. La biblioteca tiene una interfaz y documentación adecuada. Me sorprende que no haya encontrado esta biblioteca antes de ahora, de ahí que escriba sobre esto aquí. (Leí esta publicación al principio de mi investigación).
Un algoritmo fácil para calcular la triangulación de Delaunay de un conjunto de puntos es voltear los bordes . Como 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 volteo es O (n ^ 2). Existen algoritmos mejores, como el barrido de líneas de Fortune, que toman el tiempo O (n log n). Sin embargo, esto es algo complicado de implementar. Si eres flojo (como lo soy yo), sugeriría buscar una implementación existente de una triangulación Delaunay, usarla y luego calcular el gráfico dual.
En general, un buen libro sobre el tema es Geometría Computacional de Berg et al.
hay varios VoronoiDiagramGenerator.cpp / h alrededor
requiriendo toda una limpieza seria en la memoria si planeas una aplicación pesada en tiempo real
al igual que toda la fortuna Sweepline tiene problemas con puntos muy cercanos, al menos,
- pasar de flotar a doble
-remover el punto "idéntico" al inicio
-Entonces trata de lidiar con problemas de precisión en casos excepcionales