구현하기 가장 쉬운 보로 노이 다이어그램 알고리즘? [닫은]
Voronoi 다이어그램을 구현하는 쉬운 알고리즘은 무엇입니까?
특별히 의사 형태의 알고리즘을 찾을 수 없었습니다. Voronoi 다이어그램 알고리즘, 튜토리얼 등의 링크를 공유하십시오.
포인트 세트의 들로네 삼각 분할을 계산하는 쉬운 알고리즘은 가장자리를 뒤집는 것입니다 . 들로네 삼각 분할은 보로 노이 다이어그램의 이중 그래프이므로 선형 시간의 삼각 분할에서 다이어그램을 구성 할 수 있습니다.
불행히도, 뒤집기 접근법의 최악의 실행 시간은 O (n ^ 2)입니다. Fortune의 라인 스윕과 같은 더 나은 알고리즘이 존재하며 O (n log n) 시간이 걸립니다. 그러나 이것은 구현하기가 다소 까다 롭습니다. 당신이 게으르다면 (나처럼) Delaunay 삼각 측량의 기존 구현을 찾아서 사용하고 이중 그래프를 계산하는 것이 좋습니다.
일반적으로 주제에 대한 좋은 책은 de Berg et al.의 Computational Geometry 입니다.
가장 쉬울까요? 이것이 무차별 대입 방식입니다. 출력의 각 픽셀에 대해 모든 점을 반복하고 거리를 계산하고 가장 가까운 것을 사용합니다. 가능한 한 느리지 만 매우 간단합니다. 성능이 중요하지 않으면 제대로 작동합니다. 나는 흥미로운 개선 작업을하고 있지만, 다른 사람이 같은 (아주 분명한) 아이디어를 가지고 있는지 여전히 찾고 있습니다.
Bowyer-Watson 알고리즘은 이해하기 매우 쉽습니다. 다음은 구현입니다 : http://paulbourke.net/papers/triangulate/ . 점 집합에 대한 delaunay 삼각 분할이지만 delaunay의 이중, 즉 voronoi 다이어그램을 구하는 데 사용할 수 있습니다. BTW. 최소 스패닝 트리는 들로네 삼각 분할의 하위 집합입니다.
보로 노이 다이어그램을 구성하는 가장 효율적인 알고리즘은 Fortune의 알고리즘 입니다. O (n log n)에서 실행됩니다.
개인적 으로 Bill Simons와 Carson Farmer 의 파이썬 구현이 정말 마음에 듭니다 .
Wikipedia 페이지 ( http://en.wikipedia.org/wiki/Voronoi_diagram )에는 보로 노이 다이어그램을 구현하기위한 알고리즘에 대한 링크가있는 알고리즘 섹션이 있습니다.
Stephan Fortune / Shane O'Sullivan의 C 및 C ++의 2 차원 그래프에 대해 무료로 사용할 수있는 voronoi 구현이 있습니다.
VoronoiDiagramGenerator.cpp
VoronoiDiagramGenerator.h
여러 곳에서 찾을 수 있습니다. 예 : http://www.skynet.ie/~sos/masters/
다음은 쿼트 트리를 사용하고 증분 구성을 허용하는 자바 스크립트 구현입니다.
http://code.google.com/p/javascript-voronoi/
원래 질문은 Voronoi를 구현하는 방법에 대해 묻지 만이 주제에 대한 정보를 검색 할 때 다음과 같은 게시물을 찾았다면 많은 시간을 절약 할 수 있었을 것입니다.
Voronoi 다이어그램을 구현하기위한 "거의 정확한"C ++ 코드가 인터넷에 많이 있습니다. 대부분은 시드 포인트가 매우 밀집되어있을 때 거의 실패를 유발하지 않았습니다. 너무 많은 시간을 낭비하기 전에 완성 된 프로젝트에서 사용할 것으로 예상되는 포인트 수로 온라인에서 찾은 코드를 광범위하게 테스트하는 것이 좋습니다.
내가 온라인에서 찾은 최고의 구현은 여기에서 링크 된 MapManager 프로그램의 일부였습니다. http://www.skynet.ie/~sos/mapviewer/voronoi.php 대부분 작동하지만 다룰 때 간헐적 인 다이어그램 손상이 발생합니다. 10 ^ 6 포인트를 주문하십시오. 나는 부패가 어떻게 들어오고 있는지 정확히 알 수 없었습니다.
어제 밤에 http://www.boost.org/doc/libs/1_53_0_beta1/libs/polygon/doc/voronoi_main.htm "The Boost.Polygon Voronoi library"를 찾았습니다. 매우 유망 해 보입니다. 여기에는 정확성과 뛰어난 성능을 입증하기위한 벤치 마크 테스트가 함께 제공됩니다. 라이브러리에는 적절한 인터페이스와 문서가 있습니다. 지금까지이 라이브러리를 찾지 못해서 놀랐습니다. 그래서 여기에 글을 씁니다. (저는 연구 초기에이 게시물을 읽었습니다.)
실제로 https://rosettacode.org/wiki/Voronoi_diagram에서 사용할 수있는 25 개 언어에 대한 구현이 있습니다.
예 : 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);
}
}
This is the fastest possible - it's a simple voronoi but it looks great. It divides spaces into a grid, places a dot in each grid cell randomly placed and moves along the grid checking 3x3 cells to find how it relates to adjacent cells.
It's faster without the gradient.
You may ask what the easiest 3d voronoi would be. It would be fascinating to know. Probably 3x3x3 cells and checking gradient.
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 );
}
and here is the same with chebychev distance. you can use a random2f 2d float noise from here:
https://www.shadertoy.com/view/Msl3DM
edit: I have converted this to C like code
This was a while ago, for the benefit of those who what it, i believe this is 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 );
}
Check brute-force solution presented with pseudo-code by Richard Franks in his answer on the question How do I derive a Voronoi diagram given its point set and its Delaunay triangulation?
The simplest algorithm comes from the definition of a voronoi diagram: "The partitioning of a plane with n points into convex polygons such that each polygon contains exactly one generating point and every point in a given polygon is closer to its generating point than to any other." definition from wolfram.
The important part here is about every point being closer to the generating point than any other, from here the algorithm is very simple:
- Have an array of generating points.
- Loop through every pixel on your canvas.
- For every pixel look for the closest generating point to it.
- Depending on what diagram you wish to get color the pixel. If you want a diagram separated with a border, check for the second to closest point, then check their difference and color with the border color if it's smaller than some value.
If you want a color diagram then have a color associated with every generating point and color every pixel with it's closest generating point associated color. And that's about it, it's not efficient but very easy to implement.
Found this excellent C# library on google code based on Fortune's algorithm/Sweep line algorithm
https://code.google.com/p/fortune-voronoi/
You just need to create a List. A Vector can be created by passing in two numbers (coordinates) as float. Then pass the list into Fortune.ComputeVoronoiGraph()
You can understand the concept of the algorithm a bit more from these wikipedia pages:
http://en.wikipedia.org/wiki/Fortune%27s_algorithm
http://en.wikipedia.org/wiki/Sweep_line_algorithm
Though one thing I was not able to understand is how to create a line for Partially Infinite edges (don't know much about coordinate geometry :-)). If someone does know, please let me know that as well.
If you are trying to draw it to an image, you can use a queue-based flood-filling algorithm.
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;
}
Using a queue will ensure that regions spread in parallel, minimizing total number of pixel visits. If you use a stack the first point will fill the whole image, then the second will fill any pixels closer to it than the first point. This will continue, greatly increasing visit counts. Using a FIFO queue processes pixels in the order that they are pushed. The resulting images will be roughly the same whether you use stack or queue, but the big-O for queue is far closer to linear (in relation to number of image pixels) than the stack algoritm's big-O. The general idea is that the regions will spread at the same rate and collisions will generally happen exactly at points that correspond to region boundaries.
참고URL : https://stackoverflow.com/questions/973094/easiest-algorithm-of-voronoi-diagram-to-implement
'developer tip' 카테고리의 다른 글
| Android ID 명명 규칙 : 밑줄이있는 소문자 대 낙타 대소 문자 (0) | 2020.09.19 |
|---|---|
| WPF 앱과 비즈니스 앱용 Winform의 장점은 무엇입니까? (0) | 2020.09.19 |
| Visual Studio, 솔루션 별 들여 쓰기 설정 (0) | 2020.09.19 |
| 참조 또는 값으로 스마트 포인터 (shared_ptr)를 반환하는 방법은 무엇입니까? (0) | 2020.09.19 |
| Bootstrap 3의`data-target` 속성은 무엇입니까? (0) | 2020.09.19 |