Email Password Remember me?  Lost your password?

• Download source code - 67.3 KB

Introduction

Voronoi Diagram is a useful mathematic abstraction which has many applications. You can read about it here and here. You can also see some examples here: Visualization of the 2D Voronoi Diagram and the Delaunay Triangulation and Fortune's Voronoi algorithm implemented in C#.

Background

Yesterday, I solved a problem: we have many weather centers and each weather center has coordinates (X, Y) and current temperature value (T). The goal of our solution was to create a temperature map.

Using the code

The structure TemperatureLocation stores data about the weather center: coordinates X, Y, and the temperature value.

public struct TemperatureLocation
{
    private double x;

    public double X
    {
        get { return x; }
        set { x = value; }
    }
    private double y;

    public double Y
    {
        get { return y; }
        set { y = value; }
    }
    private double t;

    public double T
    {
        get { return t; }
        set { t = value; }
    }

    public TemperatureLocation(double x, double y, double t)
    {
        this.x = x;
        this.y = y;
        this.t = t;
    }

    public double GetDistance(TemperatureLocation tl)
    {
        return Math.Sqrt((this.x - tl.x) * (this.x - tl.x) + 
                         (this.y - tl.y) * (this.y - tl.y));
    }
}

The class VoronoiTemparature is designed to create temperature maps. We load data about weather center, the parameters of the image (the color of cold and hot temperatures), and get the image of the map. For a more realistic map (without accurate Voronoi cells), use a simple smooth effect. The result of the test creation map can be seen on Figure 1.

Points of interest

Creating temperature maps is really a problem in meteorology. For a good mapping, we must use interpolation algorithms (for a smooth isotherm). It is one of many Voronoi diagram applications (Voronoi died exactly 100 years ago, on 11-19-1908).

You must Sign In to use this message board.

Per page 102550

FirstPrevNext

pls help daskan 0:35 8 Aug '09   i want to use this algorithm, input some point data and get the coordnateds of the voronoi polygons of those point data. i tried to understand how this is implemented but it is hard for me. i can input the point data but i can't find from which method i can get the coordinates of the polygons. can you help by telling how i can get the polygon coordinates (from which method?) dk Sign In·View Thread·PermaLink implementation in SharMap agelospanagiotakis 4:23 15 Feb '09   Hi great code! I am trying to change your algorithm to fit the needs of SharMap.geometries.point. Sharpamap is a GIS .net . http://sharpmap.codeplex.com/[^] As you can imagine I am having some difficulties. any ideas on the steps i should take on converting the data structures to fit my needs? I can always upload a demo of my work. Sign In·View Thread·PermaLink Re: implementation in SharMap Maxim_Barsuk 22:49 15 Feb '09   Hello! SharpMap is very interesting project for me. Please send me detailed description of your problem, I will try to help you. Thanks! Sign In·View Thread·PermaLink Re: implementation in SharMap agelospanagiotakis 3:04 16 Feb '09   Hi i am trying to find the voronoi polygins for a given set of points. Please Read the full discussion online on the sharpmap codeplex discussion forum. http://www.codeplex.com/SharpMap/Thread/View.aspx?ThreadId=18994&ANCHOR#Post157880[^] I am having proplems geting correct answers from this algorithm. Propably due to the datatypes used in the calculations(points/doubles). Any help will be greatly appreciated. Best Regards, Agelos Sign In·View Thread·PermaLink Re: implementation in SharMap agelospanagiotakis 3:09 16 Feb '09   Oh I forgot to thank you for this article. I intend to use a color theme in the produced polygons too! You might also want to donwload my demo application with sharpmap and advice me accordingly : http://147.102.85.132/testsForVoronoi.rar [^] Sign In·View Thread·PermaLink Re: implementation in SharMap Maxim_Barsuk 23:35 16 Feb '09   Hello! I look your application as soon as possible (I have a lot of hard work today and tomorrow). Is your problem very critical? What is deadline for this solution? Sign In·View Thread·PermaLink 5.00/5 Re: implementation in SharMap agelospanagiotakis 13:11 6 Mar '09   hi ! i finaly did it using sharpmap and the Emgu CV (openCV a cross platform .Net wrapper to the Intel OpenCV image-processing library). You can download the demo here: http://energy.chemeng.ntua.gr/openCV_Sharpmap_Voronoi_Delauny.rar You can see the entire conversation http://sharpmap.codeplex.com/Thread/View.aspx?ThreadId=18994[^] I am now off to do the inverse distance interpolation method. :( Sign In·View Thread·PermaLink Black areas are missing? nnononnnon 8:26 14 Dec '08   Hi Maxim, Thanks for your efforts. This was exactly what I was looking for: a fast algorithm to atrribute a "nearest neighbour" value to each pixel of a bitmap. The final tessel drawing in .net is very slow though. (Compare this Flash implementation: http://www.dasprinzip.com/pExamples/p70_0.html that achieves 25 fps for 100 data points. My real question: shouldn't the black edges also be red? Also in the other voronoi visualization I noticed, that at the edges some lines were missing. I could accept the slow speed of .net, but not the errors. Sign In·View Thread·PermaLink Re: Black areas are missing? Maxim_Barsuk 19:56 16 Dec '08   Hello! Its not error of algorithm, this problem is defect of graphic implementation. Сolor regions based on a set of triangles: foreach (TemperatureLocation t in temperature) { Vector v = new Vector(t.X,t.Y); foreach (object obj in graph.Edges) { VoronoiEdge e = (VoronoiEdge)obj; if (((e.LeftData[0] == v[0]) & (e.LeftData[1] == v[1]))|((e.RightData[0] == v[0]) & (e.RightData[1] == v[1]))) { ... g.FillPolygon(brush, new Point[3] {new Point((int)v[0],(int)v[1]), new Point((int)e.VVertexA[0],(int)e.VVertexA[1]), new Point((int)e.VVertexB[0],(int)e.VVertexB[1])}); ... } } } The black areas located near the borders charts, diagram's ribs here go to infinity: e.VVertexA[0] or e.VVertexA[1] is NaN. Smooth of image severely slowed construction of map: public Bitmap GetMapTemperature(int weight, int height) { ... //return Smooth(bmp); return bmp; } Thank you! Sign In·View Thread·PermaLink Interesting... Paul Conrad 10:47 20 Nov '08   Nice article and very interesting. "The clue train passed his station without stopping." - John Simmons / outlaw programmer "Real programmers just throw a bunch of 1s and 0s at the computer to see what sticks" - Pete O'Hanlon "Not only do you continue to babble nonsense, you can't even correctly remember the nonsense you babbled just minutes ago." - Rob Graham Sign In·View Thread·PermaLink Date overflow laserbaronen 2:50 20 Nov '08   Creating temperature maps is really problem of meteorology. For good mapping we must use interpolation algorithms (for smooth isotherm). Its one of many Voronoi diagram applications (Voronoi died exactly 100 years ago, on 11-19-1908). There are not 19 months betonglasermur.FeedDwarf(pur_is, 17); ProcessStartupInfo.AintNotCreateNoWindow = (false && !true) != (true || false) ? false == true ? true : false : (true != false && false); Morgonen är tröttmans mecka Sign In·View Thread·PermaLink 1.00/5 Re: Date overflow Maxim_Barsuk 5:26 20 Nov '08   11-19-1908 is 19th of November))) Sign In·View Thread·PermaLink 1.33/5 Re: Date overflow Skymir 5:25 20 Jul '09   US standard date format is Month, Day, Year. Just to make sure that converting metric to english units isn't the only problem programmers run in to. The true man wants two things: danger and play. For that reason he wants woman, as the most dangerous plaything. Sign In·View Thread·PermaLink

Last Visit: 10:39 24 Nov '09     Last Update: 10:39 24 Nov '09 1