美术馆定理

最少只需多少名保安便可监视任意一个形状为简单多边形的美术馆


首先必须知道只需要一个保安就可以监视凸多边形

10年积累的网站制作、做网站经验，可以快速应对客户对网站的新想法和需求。提供各种问题对应的解决方案。让选择我们的客户得到更好、更有力的网络服务。我虽然不认识你，你也不认识我。但先网站设计后付款的网站建设流程，更有沛县免费网站建设让你可以放心的选择与我们合作。问题转化

首先不考虑最优解，我们先考虑简单的情况，就是将简单多边形三角拆分成一个个三角形，每个三角形放一个保安那么肯定是满足这个问题的解。

优化

这么看来一些三角形可以被多个保安看到，那么这说明这不是最优解。

三角拆分

可以三角拆分的多边形必须满足下面这个条件：

简单凸多边形可以拆分为边数n，n-2个三角形

然后进行三染色问题的简化，最后可以得到n/3向下取整个三角形

把保安放在最少的颜色的那些个顶点上，即满足解法。
推出下面这个答案

三角拆分问题

对角线是由两个位于多边形内部的不连续的顶点组成
1.对角线的端点应该是多边形的顶点
2.对角线必须完全位于多边形内部

像上面两条线就不是对角线

Ear Clipping三角拆分算法

比方说，一个多边形的顶点是由三个连续的顶点构成的V1 v2 v3其中v2是凸顶点。
V1和V3之间的连线应为一条对角线。
如下图所示：

判断v2点在v1v3向量的相对位置，如果是左边那么v2就是凸点，否则就是凹点。

例子

但是可以看到如果按顺序去分割会出现相交点

优化

一旦连接则移除

此时H D不是凸点

结果

伪代码

ps：自己想的一种优化算法

1.初始化一个stack，先往里面push 三个vertex
while(stack.size()>=3)
	2.top三个vertex 将倒数第三个vertex与栈顶的vertex组成向量，然后计算倒数第二个vertex的相对位置，
	3.if 如果倒数第二个vertex是在左边:
		那么重新push倒数第三个与栈顶的vertex，记录对角线。
		continue;
	  else:
		否则三个vertex按照之前顺序push
		push个新的vertex

多边形的数据结构表示

这里用简化版本

templatestruct Vertex
	{yhaida::Vectorpoint;
		Vertex* next;
		Vertex* prev;

		Vertex(yhaida::Vector& _point, Vertex* _next=nullptr, Vertex* _prev=nullptr)
			:point(_point), next(_next), prev(_prev)
		{}
	};

	typedef VertexVertex2d;
	typedef VertexVertex3d;

	templateclass Polygon
	{std::vector*>vertex_list;
	public:
		Polygon(const std::vector>& points)
		{	const int size = points.size();
			if (size< 3)
				std::cout<< "Not enough points to construct a polygon\n"<< std::endl;

			for (auto _point : points)
			{		vertex_list.push_back(new Vertex(_point));
			}
			for (size_t i = 0; i< size; i++)
			{		vertex_list[i]->next = vertex_list[(i + 1) / size];
				if (i != 0)
					vertex_list[i]->prev = vertex_list[i - 1];
				else
					vertex_list[i]->prev = vertex_list[size - 1];
			}
		}

		std::vector< Vertex*>getVertices()
		{	return vertex_list;
		}
	};

	typedef PolygonPolygonS3d;
	typedef PolygonPolygonS2d;

Ear check

1.检查顶点是否是个凸点
2.检查相邻两个顶点是否能连接对角线（主要是判断对角线是否在多边形内）

注意单独检查是否有交点不足判断对角线是否处于内部。
比如下图

判断步骤

static bool leftOrBeyond(const Point2d& a, const Point2d& b, const Point2d& c)
{int position = orientation2d(a, b, c);
	return (position == RELATIVE_POSITION::LEFT || position == RELATIVE_POSITION::BEYOND);
}
static bool left(const Point2d& a, const Point2d& b, const Point2d& c)
{return orientation2d(a, b, c) == RELATIVE_POSITION::LEFT;
}

static bool interiorCheck(const Vertex2d* v1, const Vertex2d* v2)
{if (leftOrBeyond(v1->point, v1->next->point, v1->prev->point)) {// v1 is vonvx vertex
		return left(v1->point, v2->point, v1->prev->point)
			&& left(v2->point, v1->point, v1->next->point);
	}
	// v1 is relex vertex
	return !(leftOrBeyond(v1->point, v2->point, v1->next->point)
		&& leftOrBeyond(v2->point, v1->point, v1->prev->point));
}

bool isDiagonal(const Vertex2d* v1, const Vertex2d* v2, PolygonS2d* poly)
{bool prospect = true;
	std::vectorvertices;

	//1.先把vertex存入vector中
	if (poly)
		vertices = poly->getVertices();
	else
	{auto vertex_ptr = v1->next;
		vertices.push_back((Vertex2d*)v1);
		while (vertex_ptr != v1)
		{	vertices.push_back(vertex_ptr);
			vertex_ptr = vertex_ptr->next;
		}
	}

	//2.判断是否相交
	Vertex2d* current, * next;
	current = vertices[0];
	do
	{next = current->next;
		if (current != v1 && next != v1 && current != v2 && next != v2
			&& yhaida::Intersection(v1->point, v2->point, current->point, next->point))
		{	prospect = false;
			break;
		}
		current = next;
	} while (current != vertices[0]);
	return prospect && interiorCheck(v1, v2) && interiorCheck(v2, v1);
}

算法

static bool  isConvex(Vertex2d* v0, Vertex2d* v1, Vertex2d* v2)
{return leftOrBeyond(v1->point, v2->point, v0->point);
}

static void initialize_ear_status(PolygonS2d* polygon)
{Vertex2d* v0, * v1, * v2;
	auto vertices = polygon->getVertices();
	v1 = vertices[0];
	do
	{v0 = v1->prev;
		v2 = v1->next;
		if (isConvex(v0, v1, v2))//判断是否是凸点
			v1->is_ear = isDiagonal(v0, v2);//是否是内对角线是通用函数
		v1 = v1->next;
	} while (v1 != vertices[0]);
}

void Triangulate_earclipping(PolygonS2d* poly, std::vector& edge_list)
{initialize_ear_status(poly);
	auto vertex_list = poly->getVertices();
	int no_vertex_to_process = vertex_list.size();
	Vertex2d* v0, * v1, * v2, * v3, * v4;
	while (no_vertex_to_process >3)
	{for (size_t i = 0; i< vertex_list.size(); i++)
		{	v2 = vertex_list[i];
			if (v2->is_ear && !v2->is_processed)//v2应该被处理，并且还未被处理
			{		v1 = v2->prev;
				v0 = v1->prev;

				v3 = v2->next;
				v4 = v2->next;

				edge_list.push_back(Edge2d(*v1, *v3));
				v2->is_processed = true;

				//删除v2
				v1->next = v3;
				v3->prev = v1;

				//更新
				if (isConvex(v1->prev, v1, v1->next))
					v1->is_ear = isDiagonal(v0, v3,nullptr);
				if (isConvex(v3->prev, v3, v3->next))
					v3->is_ear = isDiagonal(v1, v4, nullptr);

				no_vertex_to_process--;
				if (no_vertex_to_process<= 3)
					break;
			}
		}
	}
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

名称栏目：美术馆定理三角划分c++实现-创新互联
本文路径：http://ybzwz.com/article/ecidp.html