65.9K
CodeProject is changing. Read more.
Home

Visualization of the 2D Voronoi Diagram and the Delaunay Triangulation

starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.64/5 (16 votes)

Nov 19, 2008

CPOL
viewsIcon

92456

downloadIcon

3403

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:

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.