12,819,950 members (22,418 online)
Add your own
alternative version

Stats

63.4K views
3K downloads
32 bookmarked
Posted 18 Nov 2008

Visualization of the 2D Voronoi Diagram and the Delaunay Triangulation

, 18 Nov 2008 CPOL
 Rate this:
Please Sign up or sign in to vote.
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.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

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

 FirstPrev Next
 Re: Interesting vision FDemers12-May-09 2:28 FDemers 12-May-09 2:28
 WPF? sotona20-Nov-08 5:45 sotona 20-Nov-08 5:45
 Re: WPF? Maxim_Barsuk20-Nov-08 7:20 Maxim_Barsuk 20-Nov-08 7:20
 Delaunay Günther M. FOIDL19-Nov-08 5:32 Günther M. FOIDL 19-Nov-08 5:32
 Re: Delaunay Maxim_Barsuk19-Nov-08 20:08 Maxim_Barsuk 19-Nov-08 20:08
 Last Visit: 31-Dec-99 19:00     Last Update: 25-Mar-17 15:11 Refresh « Prev12

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.

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.170308.1 | Last Updated 19 Nov 2008
Article Copyright 2008 by Maxim_Barsuk
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid