Click here to Skip to main content
15,868,016 members
Articles / Desktop Programming / Windows Forms
Article

Visualization of the 2D Voronoi Diagram and the Delaunay Triangulation

Rate me:
Please Sign up or sign in to vote.
4.64/5 (17 votes)
18 Nov 2008CPOL 90.4K   3.4K   38   15
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:

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:

delane.JPG

Figure 1.Delaunay triangulation.

voronoi.JPG

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)


Written By
Software Developer
Russian Federation 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

 
BugDon't use this code! Pin
PehGuevara7-Mar-13 6:52
PehGuevara7-Mar-13 6:52 
QuestionWhy when I draw 2 points I don't see a line Pin
seb.4930-May-12 23:49
seb.4930-May-12 23:49 
NewsThis algorithm fails when presented with a large number of points with obtuse angles Pin
Tomcat_101010101014-Sep-10 16:05
Tomcat_101010101014-Sep-10 16:05 
GeneralRays Pin
ProphetLOD26-Jun-09 11:01
ProphetLOD26-Jun-09 11:01 
GeneralRe: Rays Pin
Maxim_Barsuk28-Jun-09 19:13
Maxim_Barsuk28-Jun-09 19:13 
GeneralRe: Rays Pin
ProphetLOD3-Jul-09 5:35
ProphetLOD3-Jul-09 5:35 
GeneralInteresting vision Pin
FDemers11-May-09 22:13
FDemers11-May-09 22:13 
GeneralRe: Interesting vision Pin
Maxim_Barsuk11-May-09 23:34
Maxim_Barsuk11-May-09 23:34 
GeneralRe: Interesting vision Pin
FDemers11-May-09 23:52
FDemers11-May-09 23:52 
GeneralRe: Interesting vision Pin
Maxim_Barsuk12-May-09 1:19
Maxim_Barsuk12-May-09 1:19 
GeneralRe: Interesting vision Pin
FDemers12-May-09 1:28
FDemers12-May-09 1:28 
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
QuestionWPF? Pin
dethtroll20-Nov-08 4:45
dethtroll20-Nov-08 4:45 
AnswerRe: WPF? Pin
Maxim_Barsuk20-Nov-08 6:20
Maxim_Barsuk20-Nov-08 6:20 
GeneralDelaunay Pin
Günther M. FOIDL19-Nov-08 4:32
Günther M. FOIDL19-Nov-08 4:32 
GeneralRe: Delaunay Pin
Maxim_Barsuk19-Nov-08 19:08
Maxim_Barsuk19-Nov-08 19:08 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

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