Introduction
This example uses a good implementation of the Fortune's algorithm performed by BenDi (see here). The goal of this application is the visualization of the Voronoi diagram.
Background
For more information, see these articles on Wikipedia:
Using the code
The solution for the visualization problem is very easy. We add two static methods on the Fortune class:
public static Bitmap GetVoronoyMap(int weight, int height, IEnumerable Datapoints)
{
Bitmap bmp = new Bitmap(weight, height);
VoronoiGraph graph = Fortune.ComputeVoronoiGraph(Datapoints);
Graphics g = Graphics.FromImage(bmp);
foreach (object o in graph.Vertizes)
{
Vector v = (Vector)o;
g.DrawEllipse(Pens.Black, (int)v[0]-2, (int)v[1]-2, 4, 4);
}
foreach (object o in Datapoints)
{
Vector v = (Vector)o;
g.DrawEllipse(Pens.Red, (int)v[0]-1, (int)v[1]-1, 2, 2);
}
foreach (object o in graph.Edges)
{
VoronoiEdge edge = (VoronoiEdge)o;
try
{
g.DrawLine(Pens.Brown, (int)edge.VVertexA[0],
(int)edge.VVertexA[1], (int)edge.VVertexB[0],
(int)edge.VVertexB[1]);
}
catch { }
}
return bmp;
}
public static Bitmap GetDelaunayTriangulation(int weight,
int height, IEnumerable Datapoints)
{
Bitmap bmp = new Bitmap(weight, height);
VoronoiGraph graph = Fortune.ComputeVoronoiGraph(Datapoints);
Graphics g = Graphics.FromImage(bmp);
foreach (object o in Datapoints)
{
Vector v = (Vector)o;
g.DrawEllipse(Pens.Red, (int)v[0] - 1, (int)v[1] - 1, 2, 2);
foreach (object obj in graph.Edges)
{
VoronoiEdge edge = (VoronoiEdge)obj;
if ((edge.LeftData[0] == v[0])&(edge.LeftData[1] == v[1]))
{
g.DrawLine(Pens.Black, (int)edge.LeftData[0], (int)edge.LeftData[1],
(int)edge.RightData[0], (int)edge.RightData[1]);
}
}
}
return bmp;
}
And now, we have images with diagrams:
Figure 1.Delaunay triangulation.
Figure 2.Voronoi diagram.
Points of interest
Voronoi diagram is a very useful thing. It has specially interesting applications on terrain generation. I would like to develop a simple terrain generation algorithm based on the Voronoi diagram in future.
|
|
 |
 | Rays
ProphetLOD | 12:01 26 Jun '09 |
|
|
Hello Maxim,
You have a 5 from me for your article, but I have a question. I know you're using BenDi's implementation of Fortune's algorithm. How did you correct the problem with the "rays"?
Some infinite edges, instead of poining outwords, are poining to the top-left corner. I have the same problem with your temperature map article.
Please help me make this problem go away.
Hope to hear from you soon.
Andy
|
|
|
|
|
| Re: Rays
Maxim_Barsuk | 20:13 28 Jun '09 |
|
|
Hello! "Rays" is really problem of this implementation of Voronoi map. I don't know how to solve this problem correctly. I'm using the following method. Look at method GetVoronoyMap(int weight, int height, IEnumerable Datapoints) ....
try
{
g.DrawLine(Pens.Brown, (int)edge.VVertexA[0], (int)edge.VVertexA[1], (int)edge.VVertexB[0], (int)edge.VVertexB[1]);
}
If the edge of diagram is "the ray", it will not be drawn. It's not correct solution of this problem, but it's very simple method. 
Thank you!
|
|
|
|
|
|
|
I've read about the "rays" in BenDi's article. I think I know how he expects the unbounded edges to be drawn, but I still haven't figured out how to implement it. I'll post a solution if I figure it out.
Anyways... you have my 5 for this article and the one with the temperature map based on the voronoi diagram. Came in very handy for me.
Thank you!
Andy
|
|
|
|
|
| Interesting vision
FDemers | 23:13 11 May '09 |
|
|
Hello Maxim
Pity that "Voronoi diagram are not popular in our country" Voronoi was born in Poltava (then Russia, now Ukraine)
I am interested in Voronoi diagrams for "dynamic geography" It think it would be possible to build an application that shows how maps of the world evolved with time. I wonder if Voronoi diagrams could be used to implement it. What do you think? I live in Kiev (then Russia, now Ukraine as well) I can read Russian but not write it 
Francois
|
|
|
|
|
|
|
Hello! Dynamic geography - its new discipline for me. I must think about finding methods that can help in solving this problem. Please, give me links to material about this problem. 
|
|
|
|
|
|
|
I think I may have invented the term "dynamic geography". There should be a "real" word for it. I cannot give you links: I have been searching the web for two days now without finding an example. Imagine Google Earth but with a slider that allows you to travel in time and see how countries and empires are born, expand and shrink with time
Are private emails allowed here? In case they are, mine is francois sobaka demers krapka in krapka ua
FD
|
|
|
|
|
|
|
Yes, I understand. This is a cool idea. I'm not sure that the Voronoi diagram can be applied in classical form for this purpose. Perhaps, solution of this problem needs for expanded methods of approximation. If you want, I will try do something like this (don't promise that it will be done quickly).
|
|
|
|
|
|
|
Someone made a pretty good maps of the Baltics using Voronoi diagrams, please see here: http://www.cosy.sbg.ac.at/~held/projects/vroni/img/baltic_region.gif
|
|
|
|
|
| WPF?
sotona | 5:45 20 Nov '08 |
|
|
А чо не на WPF? Сейчас это очень модно.
Шучу. Век бы его не видеть.
Nice
|
|
|
|
|
|
|
WPF? I think about this technology...)) Re-build this application for WPF, SilverLight or XNA - it's not problem)
|
|
|
|
|
| Delaunay
Günther M. FOIDL | 5:32 19 Nov '08 |
|
|
Hi, great article (5)!
Comment:
Delaunay triangulation is very useful in computational fluid methods. So this is a good point to start visualization of these computations.
Cheers
Günther
|
|
|
|
|
|
|
Thanks! In our country Delaunay triangulation and Voronoi diagram isn't popular. But I interesting in practical application of these things. At soon I will publish other programs with Voronoi and Delaunay algorithms))) 
|
|
|
|
|
|
|
Last Updated 19 Nov 2008 |
Advertise |
Privacy |
Terms of Use |
Copyright ©
CodeProject, 1999-2010
