12,555,044 members (59,311 online)
alternative version

61.7K views
32 bookmarked
Posted

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

, 18 Nov 2008 CPOL
 Rate this:
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.

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

## You may also be interested in...

 Pro Pro

## Comments and Discussions

 View All Threads First Prev Next
 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
 Last Visit: 31-Dec-99 18:00     Last Update: 25-Oct-16 18:52 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.