Jakie są proste algorytmy do zaimplementowania diagramu Woronoja?
Nie mogłem znaleźć żadnego algorytmu specjalnie w pseudo-formie. Udostępnij kilka linków do algorytmu diagramu Woronoja, samouczka itp.
Odpowiedzi:
Łatwym algorytmem do obliczenia triangulacji Delaunaya zbioru punktów jest odwracanie krawędzi . Ponieważ triangulacja Delaunaya jest podwójnym wykresem diagramu Woronoja, możesz zbudować diagram na podstawie triangulacji w czasie liniowym.
Niestety, najgorszy przypadek czasu działania metody odwracania to O (n ^ 2). Istnieją lepsze algorytmy, takie jak przeciąganie linii Fortune, które wymagają czasu O (n log n). Jest to jednak trudne do wdrożenia. Jeśli jesteś leniwy (tak jak ja), proponuję poszukać istniejącej implementacji triangulacji Delaunaya, użyć jej, a następnie obliczyć podwójny wykres.
Ogólnie rzecz biorąc, dobrą książką na ten temat jest „ Geometria obliczeniowa” autorstwa de Berg et al.
Najłatwiej? To podejście brutalnej siły: dla każdego piksela w Twoim wyniku iteruj przez wszystkie punkty, oblicz odległość, użyj najbliższego. Wolny, jak to tylko możliwe, ale bardzo prosty. Jeśli wydajność nie jest ważna, spełnia swoje zadanie. Sam pracowałem nad ciekawym udoskonaleniem, ale wciąż szukam, czy ktoś inny wpadł na ten sam (raczej oczywisty) pomysł.
Algorytm Bowyer-Watson jest dość łatwy do zrozumienia. Oto implementacja: http://paulbourke.net/papers/triangulate/ . Jest to triangulacja delaunaya dla zbioru punktów, ale można jej użyć do uzyskania dualności delaunaya, czyli diagramu voronoi. BTW. minimalne drzewo rozpinające jest podzbiorem triangulacji delaunaya.
Najbardziej skutecznym algorytmem do konstruowania diagramu Woronoja jest algorytm Fortune . Działa w O (n log n).
Oto link do jego realizacji odniesienia w C .
Osobiście bardzo podoba mi się implementacja Pythona autorstwa Billa Simonsa i Carsona Farmera, ponieważ okazało się, że jest łatwiejsza do rozszerzenia.
Strona Wikipedii ( http://en.wikipedia.org/wiki/Voronoi_diagram ) zawiera sekcję Algorytmy z linkami do algorytmów implementujących diagramy Woronoja.
Istnieje swobodnie dostępna implementacja voronoi dla wykresów dwuwymiarowych w C i C ++ od Stephan Fortune / Shane O'Sullivan:
VoronoiDiagramGenerator.cpp
VoronoiDiagramGenerator.h
Znajdziesz go w wielu miejscach. To znaczy pod adresem http://www.skynet.ie/~sos/masters/
Oto implementacja javascript, która używa quat-tree i umożliwia budowę przyrostową.
Podczas gdy pierwotne pytanie dotyczy tego, jak zaimplementować Voronoi, gdybym szukał informacji na ten temat, znalazłem post, który mówiłby co następuje, zaoszczędziłoby mi to dużo czasu:
W Internecie jest dużo „prawie poprawnego” kodu C ++ do implementacji diagramów Voronoi. Większość z nich rzadko powodowała awarie, gdy punkty nasion stają się bardzo gęste. Zalecałbym dokładne przetestowanie każdego kodu, który znajdziesz w Internecie, z liczbą punktów, które zamierzasz wykorzystać w gotowym projekcie, zanim stracisz na niego zbyt dużo czasu.
Najlepszym z wdrożeń znalazłem w Internecie była częścią programu MapManager połączonego stąd: http://www.skynet.ie/~sos/mapviewer/voronoi.php To głównie działa, ale jestem coraz przerywany schemat korupcji, gdy do czynienia z zamów 10 ^ 6 punktów. Nie byłem w stanie dokładnie określić, w jaki sposób wkrada się korupcja.
Ostatniej nocy znalazłem to: http://www.boost.org/doc/libs/1_53_0_beta1/libs/polygon/doc/voronoi_main.htm „The Boost.Polygon Voronoi library”. Wygląda bardzo obiecująco. Zawiera testy porównawcze, które potwierdzają jego dokładność i doskonałą wydajność. Biblioteka posiada odpowiedni interfejs i dokumentację. Dziwię się, że wcześniej nie znalazłem tej biblioteki, stąd piszę o tym tutaj. (Przeczytałem ten post na początku moich badań).
W rzeczywistości istnieją implementacje dla 25 różnych języków dostępnych na https://rosettacode.org/wiki/Voronoi_diagram
Np. Dla 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);
}
}
Najprostszy algorytm pochodzi z definicji diagramu Woronoja: „Podział płaszczyzny z n punktami na wypukłe wielokąty w taki sposób, że każdy wielokąt zawiera dokładnie jeden punkt generujący, a każdy punkt w danym wielokącie jest bliżej swojego punktu generowania niż jakikolwiek inny . ”definicja z wolframu.
Ważną częścią tutaj jest to, że każdy punkt jest bliżej punktu generowania niż jakikolwiek inny, stąd algorytm jest bardzo prosty:
Jeśli chcesz mieć diagram kolorów, miej kolor powiązany z każdym punktem generowania i pokoloruj każdy piksel najbliższym kolorem skojarzonym z punktem generowania. I to wszystko, nie jest wydajne, ale bardzo łatwe do wdrożenia.
To najszybsze możliwe - to zwykły voronoi, ale wygląda świetnie. Dzieli przestrzenie w siatkę, umieszcza kropkę w każdej komórce siatki losowo umieszczonej i przesuwa się po siatce, sprawdzając komórki 3x3, aby dowiedzieć się, jak odnosi się do sąsiednich komórek.
Bez gradientu jest szybciej.
Możesz zapytać, jaki byłby najłatwiejszy voronoi 3D. Fascynujące byłoby wiedzieć. Prawdopodobnie komórki 3x3x3 i sprawdzanie gradientu.
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 );
}
i tak samo jest z odległością Chebychev. możesz użyć szumu float random2f 2d stąd:
https://www.shadertoy.com/view/Msl3DM
edycja: przekonwertowałem to na kod podobny do C.
To było jakiś czas temu, dla dobra tych, którzy co to, uważam, że to jest fajne:
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 );
}
ivec2? czy vec2? To jest nieczytelne.
Sprawdź rozwiązanie siłowe przedstawione za pomocą pseudokodu przez Richarda Franksa w jego odpowiedzi na pytanie Jak uzyskać diagram Woronoja, biorąc pod uwagę jego zbiór punktów i triangulację Delaunaya?
Znalazłem tę doskonałą bibliotekę C # w kodzie Google w oparciu o algorytm Fortune / algorytm Sweep line
https://code.google.com/p/fortune-voronoi/
Musisz tylko utworzyć listę. Wektor można utworzyć, przekazując dwie liczby (współrzędne) jako liczbę zmiennoprzecinkową. Następnie przekaż listę do Fortune.ComputeVoronoiGraph ()
Możesz nieco lepiej zrozumieć koncepcję algorytmu na tych stronach Wikipedii:
http://en.wikipedia.org/wiki/Fortune%27s_algorithm
http://en.wikipedia.org/wiki/Sweep_line_algorithm
Chociaż jedna rzecz, której nie byłem w stanie zrozumieć, to jak utworzyć linię dla częściowo nieskończonych krawędzi (niewiele wiem o geometrii współrzędnych :-)). Jeśli ktoś wie, daj mi też znać.
Jeśli próbujesz narysować go na obrazie, możesz użyć algorytmu wypełniania zalewowego opartego na kolejce.
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;
}
Korzystanie z kolejki zapewni równoległe rozprzestrzenianie się regionów, minimalizując całkowitą liczbę odwiedzin pikseli. Jeśli używasz stosu, pierwszy punkt wypełni cały obraz, a drugi wypełni wszystkie piksele bliżej niego niż pierwszy punkt. Będzie to trwało, znacznie zwiększając liczbę wizyt. Korzystanie z kolejki FIFO przetwarza piksele w kolejności, w jakiej są one przekazywane. Wynikowe obrazy będą mniej więcej takie same, niezależnie od tego, czy użyjesz stosu, czy kolejki, ale duże-O dla kolejki jest znacznie bliższe liniowości (w odniesieniu do liczby pikseli obrazu) niż duże-O algorytmu stosu. Ogólna idea jest taka, że regiony będą się rozprzestrzeniać w tym samym tempie, a kolizje będą zwykle następować dokładnie w punktach, które odpowiadają granicom regionu.