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

By , 18 Nov 2008
Add a reason or comment to your vote: x
Votes of 3 or less require a comment

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

```/// <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.

## About the Author

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

## Comments and Discussions

 First PrevNext
 Don't use this code! PehGuevara 7-Mar-13 6:52
 Why when I draw 2 points I don't see a line seb.49 30-May-12 23:49
 Rays ProphetLOD 26-Jun-09 11:01
 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 28-Jun-09 19:13
 Re: Rays ProphetLOD 3-Jul-09 5:35
 Interesting vision FDemers 11-May-09 22:13
 Re: Interesting vision Maxim_Barsuk 11-May-09 23:34
 Re: Interesting vision FDemers 11-May-09 23:52
 Re: Interesting vision Maxim_Barsuk 12-May-09 1:19
 Last Visit: 31-Dec-99 18:00     Last Update: 11-Dec-13 14:03 Refresh 12 Next »

General    News    Suggestion    Question    Bug    Answer    Joke    Rant    Admin

| Advertise | Privacy | Mobile
Web02 | 2.7.131211.1 | Last Updated 19 Nov 2008
Article Copyright 2008 by Maxim_Barsuk