算法思想：

1.在已有的点集合中，首先随机取一点，作为起始点。

2.选取距离起始点最近的一个点，生成一条基线。

3.在剩下的点中，查找符合Delaunay法则的点P。 （Delaunay法则指符合 1.空外接圆法则：三点所构成的三角形的外接圆内没有任何其他点。2.最大最小角法则：假设许多点能与基线构成三角形，那么应该选取构成三角形最小角最大的那一个）

4.点P分别与基线的起点终点连接，形成三角形的两边，并以这两条边作为新的基线，继续查找符合Delaunay法则的点。

5.当没有任何一条基线能够找到新的符合Delaunay法则的点时候，算法结束。

代码实现：

//定义数据结构：
namespace:{
 //点
    public class Point
    {
        public int X;
        public int Y;
        public Point(int x, int y)
        {
            this.X = x;
            this.Y = y;
        }
    }
    //三角形
    public class Triangle
    {
        public List<Point> Points = new List<Point>(3);
    }
    //线段
    public class Line
    {
        public Point Start;
        public Point End;
    }
    //圆
    public class Circumcircle
    {
        public int X;
        public int Y;
        public double Radius;
    }

	public class Program
	{
		//
		public static List<Point> Points=new List<Point>();
		public static List<Point> Added=new List<Point>();
		public static void Main(string[] args){
			//初始化点集合，请自行添加点
			init();
			
		}
		//以一条直线和一个点构成一个三角形
		public static void BuildTriangle(Line line, Point p){
		    //得到三角形
	            var tri = new Triangle();
	            tri.Points.Add(line.Start);
	            tri.Points.Add(line.End);
	            tri.Points.Add(p);
	            this.Triangles.Add(tri);

        	    //记录已经添加的点
	            this.Added.Add(line.Start);
	            this.Added.Add(line.End);
	            this.Added.Add(p);

	            var line2 = new Line()
	            {
	                Start = line.End,
	                End = p
	            };
	            var line3 = new Line()
	            {
	                Start = p,
	                End = line.Start
	            };
	            var d1 = Delaunay(line2);
	            var d2 = Delaunay(line3);
	            if (d1 != null)
	            {
	                BuildTriangle(line2, d1);
	            }
	            if (d2 != null)
	            {
	                BuildTriangle(line3, d2);
	            }
		}

		public static Point Delaunay(Line line){
			 //符合外接圆法则的点集合
            var points = new List<Point>();
          	  foreach (var point in Points)
          	  {
                //排除基线两点
           	     if (line.Start.Equals(point) || line.End.Equals(point) || this.Added.Contains(point))
                	{
	                    continue;
        	        }

                	//求得这三点的外接圆
	                var circle = GetCircumcircle(point, line);
        	        //搜索是否有点在外接圆内部
	                if (InCircle(circle, line, point))
	                {
	                    continue;
	                }
	                points.Add(point);
	            }
            //从符合外接圆法则的点集合中查找最大最小角的点
	            return points.Count == 0 ? null : MaxAngle(points, line);
		}


		public static Point MaxAngle(List<Point> points, Line line){
			//这里懒得在定义数据结构，就用了.NET的匿名对象解释执行，使用方法参考JavaScript对象
			var angles = new List<dynamic>();
	            foreach (var p in points)
	            {
	                Line l1 = line;
	                var l2 = new Line()
	                {
	                    Start = p,
	                    End = line.Start
	                };
	                var l3 = new Line()
	                {
	                    Start = p,
	                    End = line.End
	                };
	                angles.Add(
	                  new
	                  {
			     //求出所有的角度
	                      minAngle = Math.Min(Math.Min(GetAngle(l1, l3), GetAngle(l2, l3)), GetAngle(l1, l2)),
			     //记录对应点的索引信息
	                      index = points.IndexOf(p)
	                  });
	            }
		    //找到最大的最小角
	            var result = angles.Max(v => v.minAngle);
	            var dy = angles.Find(v => v.minAngle == result);
	            return points[dy.index];
		}


		//求距离最近的点
		 public static Point GetNearst(Point point)
       		 {
	            Point pt = Points[1];
	            Points.ForEach(p =>
	            {
	                if (p.X == point.X && p.Y == point.Y) return;
	                if (GetDistence(p, point) < GetDistence(pt, point))
	                {
	                    pt = p;
        	        }
	            });
	            return pt;
	        }
		//求两点之间距离
		 public static double GetDistence(Point p1, Point p2)
       		 {
	            return Math.Sqrt((p1.X - p2.X) * (p1.X - p2.X) + (p1.Y - p2.Y) * (p1.Y - p2.Y));
	        }	


		//求两条线的角度
		 public static double GetAngle(Line l1, Line l2)
	        {
	            int k1 = int.MinValue, k2 = int.MinValue;
	            if (l1.Start.X != l1.End.X)
	            {
	                k1 = (l1.Start.Y - l1.End.Y) / (l1.Start.X - l1.End.X);
	            }
	            if (l2.Start.X != l2.End.X)
	            {
	                k2 = (l2.Start.Y - l2.End.Y) / (l2.Start.X - l2.End.X);
	            }
	            if (k1 == int.MinValue && k2 == int.MinValue)
	            {
	                return 0;
	            }
	            if (k1 == int.MinValue)
	            {
	                double a2 = Math.Atan(k2);
	                return ((Math.PI / 2) - a2) > 0 ? ((Math.PI / 2) - a2) : -((Math.PI / 2) - a2);
	            }
	            if (k2 == int.MinValue)
	            {
	                double a1 = Math.Atan(k1);
	                return ((Math.PI / 2) - a1) > 0 ? ((Math.PI / 2) - a1) : -((Math.PI / 2) - a1);
	            }
	            return Math.Atan2(k1, k2);
	        }	


		//判断外接圆内是否有其他点
		public static bool InCircle(Circumcircle circumcircle, Line line, Point pt)
	        {
	            foreach (var p in Points)
	            {
	                if (line.End.Equals(p) || line.Start.Equals(p) || pt.Equals(p)) continue;
	                if (IsInCircle(circumcircle, p))
	                {
	                    return true;
	                }
	            }
	            return false;
	        }
		

		//点是否在外接圆内
		 public static bool IsInCircle(Circumcircle circumcircle, Point point)
	        {
	            double distence = Math.Sqrt((circumcircle.X - point.X) * (circumcircle.X - point.X) +
	                (circumcircle.Y - point.Y) * (circumcircle.Y - point.Y));
        	    return distence <= circumcircle.Radius;
	        }
		

		//求外接圆
		public static Circumcircle GetCircumcircle(Point point, Line line)
	        {
	            int x1 = point.X, x2 = line.Start.X, x3 = line.End.X;
	            int y1 = point.Y, y2 = line.Start.Y, y3 = line.End.Y;
	            int A1 = 2 * (x2 - x1);
	            int B1 = 2 * (y2 - y1);
	            int C1 = x2 * x2 + y2 * y2 - x1 * x1 - y1 * y1;
	            int A2 = 2 * (x3 - x2);
	            int B2 = 2 * (y3 - y2);
	            int C2 = x3 * x3 + y3 * y3 - x2 * x2 - y2 * y2;
	            int x = ((C1 * B2) - (C2 * B1)) / ((A1 * B2) - (A2 * B1));
	            int y = ((A1 * C2) - (A2 * C1)) / ((A1 * B2) - (A2 * B1));
	            var circle = new Circumcircle
	            {
	                X = x,
	                Y = y,
	                Radius = Math.Sqrt((x1 - x) * (x1 - x) + (y1 - y) * (y1 - y))
	            };
	            return circle;
        	}
	}
}

运行效果：

完整代码:

基于.NET Framework 4.5 附件