二维 Voronoi 图和 Delaunay 三角剖分的视化

• 下载源代码 - 55.7 KB

引言

这个例子使用了 BenDi 实现的一个优秀的 Fortune 算法（参见 这里）。这个应用程序的目标是 Voronoi 图的可视化。

背景

有关更多信息，请参阅维基百科上的这些文章

• Voronoi 图
• Delaunay 三角剖分

使用代码

可视化问题的解决方案非常简单。我们在 Fortune 类上添加了两个静态方法

/// <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;
}

现在，我们有了带有图表的图像

关注点

Voronoi 图是非常有用的东西。它在地形生成方面有特别有趣的用途。我希望将来开发一个基于 Voronoi 图的简单地形生成算法。