简单说明

需要的数据结构是三角形集合(TriangleSet)，外接圆集合，边缘点集合(edgeSet)。

首先生成一个能将所有点包围住的巨大三角形，称为 superTriangle，然后将 superTriangle 插入三角形集合(TriangleSet)，计算 superTriangle 的外接圆并插入外接圆集合。

将随机点挨个取出，每轮都将边缘点集合清空，遍历外接圆集合，如果此随机点在外接圆内，则将此外接圆对应的三角形的点插入边缘点集合，并将此三角形删除出三角形集合，此外接圆删除出外接圆集合。最终得到边缘点集合，以此轮的这个点与边缘点集合的第一个点的向量为基准，顺时针排序所有边缘点，然后每两个边缘点与此轮的这个点组成一个三角形，直至所有边缘点都遍历完。

上面描述已经通过可视化展示了出来，可以运行一下程序辅助理解。

程序截图

代码实现

#include<graphics.h>
#include<math.h>
#include<vector>
#include<time.h>
#define WIDTH 640
#define HEIGHT 480
using std::vector;

struct Point
{
	double x, y;
	bool	operator==(Point a) { return (this->x == a.x) && (this->y == a.y); }
	bool	operator!=(Point a) { return (this->x != a.x) || (this->y != a.y); }
	Point	operator-(Point ano) { return { this->x - ano.x, this->y - ano.y }; }
	Point	operator+(Point ano) { return { this->x + ano.x, this->y + ano.y }; }
	double	operator*(Point ano) { return this->x * ano.x + this->y * ano.y; }
	Point	operator*(double num) { return { this->x * num, this->y * num }; }
	Point	operator/(double num) { return { this->x / num, this->y / num }; }
	void	operator=(Point ano) { this->x = ano.x; this->y = ano.y; }
};
typedef Point Vec2;

struct Triangle
{
	Point a, b, c;
};

struct Circle
{
	Point center;
	double radius;
};

struct Line
{
	Point a, b;
};

vector<Point> RandPoint(int num)
{
	vector<Point> result;
	for (int i = 0; i < num; i++)
	{
		result.push_back({ (double)(25 + rand() % (WIDTH - 50)), (double)(25 + rand() % (HEIGHT - 50)) });
	}
	return result;
}

void DrawPointSet(vector<Point>& pointset, COLORREF color)
{
	for (Point i : pointset)
	{
		solidcircle((int)(i.x + 0.5), (int)(i.y + 0.5), 5);
	}
}

double GetLength(Vec2 vec)
{
	return sqrt(vec.x * vec.x + vec.y * vec.y);
}

double GetLength(Point a, Point b)
{
	return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

double GetLength(Line l)
{
	return GetLength(l.a, l.b);
}

double GetCosBetween(Vec2 a, Vec2 b)
{
	return a * b / GetLength(a) / GetLength(b);
}

void DrawLineSegment(Line l)
{
	line((int)(l.a.x + 0.5), (int)(l.a.y + 0.5), (int)(l.b.x + 0.5), (int)(l.b.y + 0.5));
}

void DrawLine(Line l, int left, int top, int right, int bottom)
{
	bool isVertical = false, isHorizontal = false;
	double left_t = 0, right_t = 0, top_t = 0, bottom_t = 0;
	if (l.b.x == l.a.x)
	{
		isVertical = true;
	}
	else
	{
		left_t = (double)(left - l.a.x) / (double)(l.b.x - l.a.x);
		right_t = (double)(right - l.a.x) / (double)(l.b.x - l.a.x);
	}
	if (l.b.y == l.a.y)
	{
		isHorizontal = true;
	}
	else
	{
		top_t = (double)(top - l.a.y) / (double)(l.b.y - l.a.y);
		bottom_t = (double)(bottom - l.a.y) / (double)(l.b.y - l.a.y);
	}
	if (!isVertical && !isHorizontal)
	{
		double min_t = min(min(left_t, right_t), min(top_t, bottom_t));
		double max_t = max(max(left_t, right_t), max(top_t, bottom_t));
		DrawLineSegment({ {(l.a.x + (l.b.x - l.a.x) * min_t), (l.a.y + (l.b.y - l.a.y) * min_t)},
			{(l.a.x + (l.b.x - l.a.x) * max_t), (l.a.y + (l.b.y - l.a.y) * max_t)} });
	}
	else if (isVertical && !isHorizontal)
	{
		DrawLineSegment({ {l.a.x, (double)top}, {l.a.x, (double)bottom} });
	}
	else if (!isVertical && isHorizontal)
	{
		DrawLineSegment({ {(double)left, l.a.y}, {(double)right, l.a.y} });
	}
	else
	{
		putpixel((int)(l.a.x + 0.5), (int)(l.a.y + 0.5), getlinecolor());
	}
}

void DrawCircle(Circle cir)
{
	circle(cir.center.x, cir.center.y, cir.radius);
}

void MidPerpendicular(Line l, int left, int top, int right, int bottom)
{
	double x_middle = l.a.x + (l.b.x - l.a.x) * 0.5, y_middle = l.a.y + (l.b.y - l.a.y) * 0.5;
	bool isVertical = false, isHorizontal = false;
	double left_t = 0, right_t = 0, top_t = 0, bottom_t = 0;
	// x=(y0-y1)t+x_middle
	// y=(x1-x0)t+y_middle
	if (l.b.y == l.a.y)
	{
		isVertical = true;
	}
	else
	{
		left_t = (double)(left - x_middle) / (double)(l.a.y - l.b.y);
		right_t = (double)(right - x_middle) / (double)(l.a.y - l.b.y);
	}
	if (l.b.x == l.a.x)
	{
		isHorizontal = true;
	}
	else
	{
		top_t = (double)(top - y_middle) / (double)(l.b.x - l.a.x);
		bottom_t = (double)(bottom - y_middle) / (double)(l.b.x - l.a.x);
	}
	if (!isVertical && !isHorizontal)
	{
		double min_t = min(min(left_t, right_t), min(top_t, bottom_t));
		double max_t = max(max(left_t, right_t), max(top_t, bottom_t));
		DrawLineSegment({ {(x_middle + (l.a.y - l.b.y) * min_t), (y_middle + (l.b.x - l.a.x) * min_t)},
			{(x_middle + (l.a.y - l.b.y) * max_t), (y_middle + (l.b.x - l.a.x) * max_t)} });
	}
	else if (isVertical && !isHorizontal)
	{
		DrawLineSegment({ {x_middle, (double)top}, {x_middle, (double)bottom} });
	}
	else if (!isVertical && isHorizontal)
	{
		DrawLineSegment({ {(double)left, y_middle}, {(double)right, y_middle} });
	}
	else
	{
		putpixel((int)(l.a.x + 0.5), (int)(l.a.y + 0.5), getlinecolor());
	}
}

Point GetIntersection(Line a, Line b)
{
	double a1 = a.b.x - a.a.x;
	double b1 = a.b.y - a.a.y;
	double a2 = b.b.x - b.a.x;
	double b2 = b.b.y - b.a.y;
	double x1 = a.a.x;
	double y1 = a.a.y;
	double x2 = b.a.x;
	double y2 = b.a.y;
	/*
	* 计算过程
		x = a1t1 + x1			x = a2t2 + x2
		y = b1t1 + y1			y = b2t2 + y2
		t1 = ((x1 - x2)b2 + (y2 - y1)a2)/(b1a2 - a1b2)
		t2 = ((y2 - y1)a1 + (x1 - x2)b1)/(b1a2 - a1b2)
	*/
	double t1 = ((x1 - x2) * b2 + (y2 - y1) * a2) / (b1 * a2 - a1 * b2);
	return { a1 * t1 + x1, b1 * t1 + y1 };
}

Point GetMidPerpendicularIntersection(Line a, Line b)
{
	double a1 = a.a.y - a.b.y;
	double b1 = a.b.x - a.a.x;
	double a2 = b.a.y - b.b.y;
	double b2 = b.b.x - b.a.x;
	double x1 = a.a.x + (a.b.x - a.a.x) * 0.5;
	double y1 = a.a.y + (a.b.y - a.a.y) * 0.5;
	double x2 = b.a.x + (b.b.x - b.a.x) * 0.5;
	double y2 = b.a.y + (b.b.y - b.a.y) * 0.5;
	/*
	* 计算过程
		x = a1t1 + x1			x = a2t2 + x2
		y = b1t1 + y1			y = b2t2 + y2
		t1 = ((x1 - x2)b2 + (y2 - y1)a2)/(b1a2 - a1b2)
		t2 = ((y2 - y1)a1 + (x1 - x2)b1)/(b1a2 - a1b2)
	*/
	double t1 = ((x1 - x2) * b2 + (y2 - y1) * a2) / (b1 * a2 - a1 * b2);
	return { a1 * t1 + x1, b1 * t1 + y1 };
}

void DrawTriangle(Triangle triangle)
{
	DrawLineSegment({ triangle.a, triangle.b });
	DrawLineSegment({ triangle.a, triangle.c });
	DrawLineSegment({ triangle.b, triangle.c });
}

void DrawTriangleSet(vector<Triangle>triangleSet)
{
	for (Triangle& tri : triangleSet)
	{
		DrawTriangle(tri);
	}
}

Circle GetCircumcircle(Triangle triangle)
{
	Circle result = { 0 };
	Line l1 = { triangle.a, triangle.b };
	Line l2 = { triangle.a, triangle.c };
	result.center = GetMidPerpendicularIntersection(l1, l2);
	result.radius = GetLength(result.center, triangle.a);
	return result;
}

bool isInCircle(Circle circle, Point point)
{
	return GetLength(circle.center, point) < circle.radius;
}

bool isNotInPointSet(vector<Point>& pointset, Point point)
{
	for (Point i : pointset)
	{
		if (i == point)return false;
	}
	return true;
}

void PutInPointSet(vector<Point>& pointset, Point point)
{
	if (isNotInPointSet(pointset, point))pointset.push_back(point);
}

void SortEdge(vector<Point>& edgepointset, Point addpoint)
{
	// 根据方向和角度排序
	vector<double>angledeque;
	angledeque.push_back(1);
	Vec2 vec = edgepointset[0] - addpoint;
	vec.y = -vec.y;
	for (int i = 1; i < edgepointset.size(); i++)
	{
		Point temp_poi = edgepointset[i];
		Vec2 temp_vec = edgepointset[i] - addpoint;
		temp_vec.y = -temp_vec.y;
		double temp_angle = GetCosBetween(temp_vec, vec);
		if (temp_vec.y * vec.x - temp_vec.x * vec.y > 0.0)	// 点在左边，数轴上关于 -1 对称一下
		{
			temp_angle = -(temp_angle + 2);
		}
		angledeque.push_back(temp_angle);
		// 插入排序
		int j = i;
		bool flag = false;
		while (j > 0 && angledeque[j - 1] < temp_angle)
		{
			flag = true;
			angledeque[j] = angledeque[j - 1];
			edgepointset[j] = edgepointset[j - 1];
			j--;
		}
		if (flag)
		{
			angledeque[j] = temp_angle;
			edgepointset[j] = temp_poi;
		}
	}
}

vector<Triangle> GenerateTriangleMesh(vector<Point>pointset, bool isSkip = true)
{
	Triangle superTriangle;
	bool flag = false;
	// 得到包括所有点的矩形
	double top = 0, bottom = 0, left = 0, right = 0;
	for (Point i : pointset)
	{
		if (!flag)
		{
			flag = true;
			top = bottom = i.y;
			left = right = i.x;
		}
		else
		{
			if (i.y < top)top = i.y;
			else if (i.y > bottom)bottom = i.y;
			if (i.x < left)left = i.x;
			else if (i.x > right)right = i.x;
		}
	}
	// 略微扩大矩形区域，避免点在三角形边缘上
	bottom += 1;
	top -= 1;
	left -= 1;
	right += 1;
	superTriangle = { {((right - left) / 2 + left), (bottom - (bottom - top) * 2)},
		{(left - (right - left) / 2), bottom}, {(right + (right - left) / 2), bottom} };
	// 逐点插入
	vector<Triangle> generateTriangle;
	vector<Circle> circumcircle;
	vector<Point>edgePointSet;
	generateTriangle.push_back(superTriangle);
	circumcircle.push_back(GetCircumcircle(superTriangle));
	for (int i = pointset.size() - 1; i >= 0; i--)
	{
		edgePointSet.clear();
		Point temp = pointset[i];
		// 判断这个插入的点跟其他点形成的三角形有没有交集
		// 包含这个点的圆的三角形全部删除，三角形的点全部保留
		// 跟边缘点没有交集的圆的三角形可以保留
		// 遍历所有圆，点在圆内就获得组成这个圆的三角形的点，这些点是边界点，生成互不包含的圆，这些圆形成三角形
		// 边缘点一定是凸包，凸包算法可以排序
		// 不过不是对新插入的点进行判断，而是对所有点
		// 找到边缘点，然后对中心点判断其余点，方向同向，角度最小，这里需要排个序
		if (!isSkip)
		{
			cleardevice();
			DrawTriangleSet(generateTriangle);
			solidcircle(temp.x, temp.y, 5);
			system("pause");
		}
		for (int j = 0; j < circumcircle.size(); j++)
		{
			if (isInCircle(circumcircle[j], temp))
			{
				if (!isSkip)
				{
					cleardevice();
					DrawTriangleSet(generateTriangle);
					solidcircle(temp.x, temp.y, 5);
					DrawCircle(circumcircle[j]);
					system("pause");
				}
				PutInPointSet(edgePointSet, generateTriangle[j].a);
				PutInPointSet(edgePointSet, generateTriangle[j].b);
				PutInPointSet(edgePointSet, generateTriangle[j].c);
				generateTriangle.erase(generateTriangle.begin() + j);
				circumcircle.erase(circumcircle.begin() + j);
				j--;
				if (!isSkip)
				{
					cleardevice();
					DrawTriangleSet(generateTriangle);
					solidcircle(temp.x, temp.y, 5);
					system("pause");
				}
			}
		}
		SortEdge(edgePointSet, temp);
		for (int j = 0, k = 1; j < edgePointSet.size(); j++, k++)
		{
			Triangle temp_gentri = { temp, edgePointSet[j], edgePointSet[k % edgePointSet.size()] };
			generateTriangle.push_back(temp_gentri);
			circumcircle.push_back(GetCircumcircle(temp_gentri));
			if (!isSkip)
			{
				cleardevice();
				DrawTriangleSet(generateTriangle);
				solidcircle(temp.x, temp.y, 5);
				system("pause");
			}
		}
	}
	for (int i = 0; i < generateTriangle.size(); i++)
	{
		if (generateTriangle[i].a == superTriangle.a || generateTriangle[i].a == superTriangle.b || generateTriangle[i].a == superTriangle.c ||
			generateTriangle[i].b == superTriangle.a || generateTriangle[i].b == superTriangle.b || generateTriangle[i].b == superTriangle.c ||
			generateTriangle[i].c == superTriangle.a || generateTriangle[i].c == superTriangle.b || generateTriangle[i].c == superTriangle.c)
		{
			generateTriangle.erase(generateTriangle.begin() + i);
			i--;
			if (!isSkip)
			{
				cleardevice();
				DrawTriangleSet(generateTriangle);
				system("pause");
			}
		}
	}
	return generateTriangle;
}

bool DetectEmptyCircle(vector<Triangle>triangleSet, vector<Point>pointSet)
{
	for (Triangle& t : triangleSet)
	{
		Circle cir = GetCircumcircle(t);
		for (Point& p : pointSet)
		{
			if (p != t.a && p != t.b && p != t.c)
			{
				if (isInCircle(cir, p))return false;
			}
		}
	}
	return true;
}

int main()
{
	HWND hwnd = initgraph(WIDTH, HEIGHT);
	int pointNum = 50;
	bool isSkip = true;
	if (MessageBox(hwnd, TEXT("是否跳过可视化"), TEXT("标题"), MB_YESNO) == IDNO)
	{
		isSkip = false;
		pointNum = 20;
		MessageBox(hwnd, TEXT("回车看到下一幕哦"), TEXT("标题"), MB_OK);
	}
	srand((unsigned int)time(NULL));
	vector<Point>pointset = RandPoint(pointNum);
	setfillcolor(WHITE);
	vector<Triangle>triangleSet = GenerateTriangleMesh(pointset, isSkip);
	cleardevice();
	DrawPointSet(pointset, WHITE);
	DrawTriangleSet(triangleSet);
	if (DetectEmptyCircle(triangleSet, pointset))
		MessageBox(hwnd, TEXT("满足空圆特性"), TEXT("标题"), MB_OK);
	else MessageBox(hwnd, TEXT("不满足空圆特性"), TEXT("标题"), MB_OK);
	system("pause");
	return 0;
}