14,973,482 members
Articles / Desktop Programming / Windows Forms
Article
Posted 18 Nov 2008

83.2K views
36 bookmarked

# Visualization of the 2D Voronoi Diagram and the Delaunay Triangulation

Rate me:
18 Nov 2008CPOL
An add-on for the Fortune's algorithm.

## 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.

## Using the code

The solution for the visualization problem is very easy. We add two static methods on the `Fortune` class:

C#
```/// <summary>
/// Visualization of 2D Voronoi map.
/// </summary>
/// <param name="weight">Weight of result image.</param>
/// <param name="height">Height of result image.</param>
/// <param name="Datapoints">Array of data points.</param>
/// <returns>Result bitmap.</returns>
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;
}

/// <summary>
/// Visualization of Delaunay Triangulation
/// </summary>
/// <param name="weight">Weight of result image.</param>
/// <param name="height">Height of result image.</param>
/// <param name="Datapoints">Result bitmap.</param>
/// <returns></returns>
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.

## Share

 Software Developer Russian Federation
Hello! My name is Maxim Subbotin.

Now I work in sphere of web-development. I'm interesting researches in SEO field.
If you interesting, you can see this tool:

KeywordCompetitor

 First Prev Next
 Don't use this code! PehGuevara7-Mar-13 6:52 PehGuevara 7-Mar-13 6:52
 Why when I draw 2 points I don't see a line seb.4930-May-12 23:49 seb.49 30-May-12 23:49
 This algorithm fails when presented with a large number of points with obtuse angles Tomcat_101010101014-Sep-10 16:05 Tomcat_1010101010 14-Sep-10 16:05
 Rays ProphetLOD26-Jun-09 11:01 ProphetLOD 26-Jun-09 11:01
 Re: Rays Maxim_Barsuk28-Jun-09 19:13 Maxim_Barsuk 28-Jun-09 19:13
 Re: Rays ProphetLOD3-Jul-09 5:35 ProphetLOD 3-Jul-09 5:35
 Interesting vision FDemers11-May-09 22:13 FDemers 11-May-09 22:13
 Re: Interesting vision Maxim_Barsuk11-May-09 23:34 Maxim_Barsuk 11-May-09 23:34
 Re: Interesting vision FDemers11-May-09 23:52 FDemers 11-May-09 23:52
 Re: Interesting vision Maxim_Barsuk12-May-09 1:19 Maxim_Barsuk 12-May-09 1:19
 Re: Interesting vision FDemers12-May-09 1:28 FDemers 12-May-09 1:28
 WPF? dethtroll20-Nov-08 4:45 dethtroll 20-Nov-08 4:45
 А чо не на WPF? Сейчас это очень модно. Шучу. Век бы его не видеть. Nice
 Re: WPF? Maxim_Barsuk20-Nov-08 6:20 Maxim_Barsuk 20-Nov-08 6:20
 Delaunay Günther M. FOIDL19-Nov-08 4:32 Günther M. FOIDL 19-Nov-08 4:32
 Re: Delaunay Maxim_Barsuk19-Nov-08 19:08 Maxim_Barsuk 19-Nov-08 19:08
 Last Visit: 31-Dec-99 18:00     Last Update: 27-Jul-21 3:09 Refresh 1