DCELC++实现-创新互联

DECL

DECL结构是比较通用的来表示几何的数据结构
主要包括三种数据结构:
1.点 vertex
2.半边 edge
3.面 face

创新互联建站2013年开创至今,是专业互联网技术服务公司,拥有项目网站设计制作、网站制作网站策划,项目实施与项目整合能力。我们以让每一个梦想脱颖而出为使命,1280元和硕做网站,已为上家服务,为和硕各地企业和个人服务,联系电话:13518219792点

存储点的位置以及任意一条由该点为起点向量的半边

半边

其中几何边由两条半边组成
在这里插入图片描述
这也是一种表示方式
在这里插入图片描述

存储一个面的外边界和内边界,如果外边界或者内边界不存在那么直接等于nullptr
在这里插入图片描述
像下面这种情况内部空洞需要用一个vector来存储了
在这里插入图片描述

通用的表达方式

在这里插入图片描述

数据结构简单实现(不包括具体操作)
templatestruct VertexDCEL
	{Vectorpoint;// 1.Coordinates
		EdgeDCEL* incident_edge = nullptr;// 2.以point任意为起点的半边

		VertexDCEL(Vector& _point) :point(_point) {}

		//......
	};

	templatestruct EdgeDCEL
	{//1.起始点
		VertexDCEL* origin = nullptr;

		//2.与该半边相关联的三条半边
		EdgeDCEL* twin = nullptr;
		EdgeDCEL* next = nullptr;
		EdgeDCEL* prev = nullptr;

		//3.该半边对应的面
		FaceDCEL* incident_face = nullptr;

		int id = -1;
		EdgeDCEL() :id(-1) {}
		EdgeDCEL(VertexDCEL* _origin) :origin(_origin)
		{	id++;
		}

		VertexDCEL* destination()
		{	return twin->origin;
		}

		//......
	};

	templatestruct FaceDCEL
	{EdgeDCEL* outer = nullptr;
		std::vector< EdgeDCEL*>inner;//可能会有空洞
		
		void print()//只输出外边界
		{	if (outer)
			{		auto edge_ptr = outer;
				auto next_ptr = outer->next;

				edge_ptr->origin->print();
				while (next_ptr != edge_ptr) {next_ptr->origin->print();
					next_ptr = next_ptr->next;
				}
			}
		}
		//......
	};

	templateclass PolygonDCEL
	{typedef VectorVetorNf;
		std::vector< VertexDCEL* >vertex_list;
		std::vector< EdgeDCEL* >edge_list;
		std::vector< FaceDCEL* >face_list;

		//保存空的边,没有组成面->边集合
		EdgeDCEL* empty_edge = new EdgeDCEL();
	public:
		explicit PolygonDCEL(std::vector< VetorNf>&);
		
		bool split(VertexDCEL* _v1, VertexDCEL* _v2);

		bool join(VertexDCEL* _v1, VertexDCEL* _v2);

		std::vector*>getVertexList();

		std::vector*>getFaceList();

		std::vector*>getEdgeList();

		VertexDCEL* getVertex(VectorNf&);

		void getEdgesWithSamefaceAndGivenOrigins(VertexDCEL* _v1, VertexDCEL* _v2,
			EdgeDCEL** edge_leaving_v1, EdgeDCEL** edge_leaving_v2);
	};
构造简单多边形的函数
templateinline PolygonDCEL::PolygonDCEL(std::vector& _points)
	{int size = _points.size();
		if (size< 3)
			return;
		//1.根据所给点,创建vertex
		for (size_t y = 0; i< _points.size(); ++i)
		{	vertex_list.push_back(new VertexDCEL(_points[i]));
		}
		//2.根据创建vertex,创建半边
		for (size_t i = 0; i<= vertex_list.size() - 2; ++i)
		{	auto hfedge = new EdgeDCEL(vertex_list[i]);
			vertex_list[i]->incident_dege = hfedge;

			auto edge_twin = new EdgeDCEL(vertex_list[i + 1]);

			hfedge->twin = edge_twin;
			edge_twin->twin = hfedge;

			edge_list.push_back(hfedge);
			edge_list.push_back(edge_twin);
		}
		//最后一条边
		auto hfedge = new EdgeDCEL(vertex_list.back());
		vertex_list[vertex_list.size() - 1]->incident_dege = hfedge;

		auto edge_twin = new EdgeDCEL(vertex_list.front());

		hfedge->twin = edge_twin;
		edge_twin->twin = hfedge;

		edge_list.push_back(hfedge);
		edge_list.push_back(edge_twin);

		//设置next,prev指针
		//edge_list里面是根据半边的顺序存储,所以注意是每隔2个处理一次
		for (size_t i = 2; i<= edge_list.size() - 3; ++i)
		{	if (i % 2 == 0)//设置半边
			{		edge_list[i]->prev = edge_list[i - 2];
				edge_list[i]->next = edge_list[i + 2];
			}
			else//设置twin半边
			{		edge_list[i]->prev = edge_list[i + 2];
				edge_list[i]->next = edge_list[i - 2];
			}
		}
		edge_list[0]->prev = edge_list[edge_list.size() - 2];
		edge_list[0]->next = edge_list[2];
		edge_list[1]->prev = edge_list[3];
		edge_list[1]->next = edge_list[edge_list.size() - 1];

		edge_list[edge_list.size() - 2]->prev = edge_list[edge_list.size() - 4];
		edge_list[edge_list.size() - 2]->next = edge_list[0];
		edge_list[edge_list.size() - 1]->prev = edge_list[1];
		edge_list[edge_list.size() - 1]->next = edge_list[edge_list.size() - 3];
		
		//3.新建face
		FaceDCEL* f1 = new FaceDCEL();//简单多边形的内半边
		FaceDCEL* f2 = new FaceDCEL();//简单多边形的外半边

		f1->outer = edge_list[0];
		f2->inner.push_back(edge_list[1]);

		//设置整个内部face f1外边界的半边对应incident_face
		f1->outer->incident_face = f1;
		EdgeDCEL* edge = f1->outer->next;
		while (edge!= f1->outer)
		{	edge->incident_face = f1;
			edge = edge->next;
		}
		 
		//设置整个外部face f2内边界的半边对应incident_face
		f2->inner[0]->incident_face = f2;
		edge = f2->inner[0]->next;
		while (edge != f2->inner[0])
		{	edge->incident_face = f2;
			edge = edge->next;
		}
	}
重要操作一 找到一个vertex的所有出度边

在这里插入图片描述

templateinline void PolygonDCEL::getEdgesWithSamefaceAndGivenOrigins(VertexDCEL* _v1, VertexDCEL* _v2, EdgeDCEL** edge_leaving_v1, EdgeDCEL** edge_leaving_v2)
	{std::vector*>edges_with_v1_ori, edges_with_v2_ori;
		auto v1_inci_edge = _v1->incident_edge;
		edges_with_v1_ori.push_back(v1_inci_edge);

		auto next_edge = v1_inci_edge->twin->next;
		while (next_edge != v1_inci_edge)
		{	edges_with_v1_ori.push_back(next_edge);
			next_edge = next_edge->twin->next;
		}

		auto v2_inci_edge = _v2->incident_edge;
		edges_with_v2_ori.push_back(v2_inci_edge);

		auto next_edge = v2_inci_edge->twin->next;
		while (next_edge != v2_inci_edge)
		{	edges_with_v2_ori.push_back(next_edge);
			next_edge = next_edge->twin->next;
		}

		//edges_with_v1_ori与edges_with_v2_ori里面存的半边对应的incident_face是不一样的
		for (auto& ev1 : edges_with_v1_ori)
		{	for (auto& ev2 : edges_with_v2_ori)
			{		if (ev1->incident_face->outer != nullptr) {//找内部的面
					if (ev1->incident_face == ev2->incident_face) {//找相同的内部面
						//这两条半边必定是相反的方向!!!!可以根据其遍历两个部分
						**edge_leaving_v1 = ev1;
						*edge_leaving_v2 = ev2;
						return;
					}
				}
			}
		}
	}
重要操作二 split

在这里插入图片描述

templateinline bool PolygonDCEL::split(VertexDCEL* _v1, VertexDCEL* _v2)
	{EdgeDCEL* edge_oriV1;
		EdgeDCEL* edge_oriV2;
		getEdgesWithSamefaceAndGivenOrigins(_v1, _v2, &edge_oriV1, &edge_oriV2);
		if (edge_oriV1->id == -1 || edge_oriV2->id == -1)
			return false;
		//判断是否是邻边
		if (edge_oriV1->next->origin == _v2 || edge_oriV1->prev->origin == _v2)
			return false;

		//创建新对边
		auto half_edge1 = new EdgeDCEL(_v1);
		auto half_edge2 = new EdgeDCEL(_v2);
		//设置新半边
		half_edge1->twin = half_edge2;
		half_edge2->twin = half_edge1;

		half_edge1->next = edge_oriV2;
		half_edge2->next = edge_oriV1;

		half_edge1->next->prev = half_edge1;
		half_edge2->next->prev = half_edge2;

		half_edge1->prev = edge_oriV1->prev;
		half_edge2->prev = edge_oriV2->prev;

		half_edge1->prev->next = half_edge1;
		half_edge2->prev->next = half_edge2;

		//新建两个面,并删除旧的面,设置面
		FaceDCEL* new_face1 = new FaceDCEL();
		new_face1->outer = half_edge1;
		half_edge1->incident_face = new_face1;
		auto temp_edge = half_edge1->next;
		while (temp_edge != half_edge1) {	temp_edge->incident_face = new_face1;
			temp_edge = temp_edge->next;
		}

		FaceDCEL* new_face2 = new FaceDCEL();
		new_face2->outer = half_edge2;
		half_edge2->incident_face = new_face2;
		temp_edge = half_edge2->next;
		while (temp_edge != half_edge2) {	temp_edge->incident_face = new_face2;
			temp_edge = temp_edge->next;
		}

		face_list.push_back(new_face1);
		face_list.push_back(new_face2);

		//删除原先的面
		FaceDCEL* previous_face = edge_oriV1->incident_face;
		auto itr = std::find(face_list.begin(), face_list.end(), previous_face);
		if (itr != face_list.end()) {	face_list.erase(itr);
			delete previous_face;
		}

		return true;
	}
单调多边形

在这里插入图片描述
正例
在这里插入图片描述
反例
在这里插入图片描述

单调多边形拆分

在这里插入图片描述
在这里插入图片描述

vertex种类

1.开始顶点
2.结束顶点
3.普通顶点
4.分裂顶点
5.合并顶点
在这里插入图片描述
在这里插入图片描述

开始顶点与结束顶点是一对,面向多边形内部的角度是锐角
在这里插入图片描述
普通顶点,两个端点是上下一侧
在这里插入图片描述
分裂顶点和合并顶点是需要实际操作的,单调多边形拆分主要是拆这两个顶点
在这里插入图片描述
分裂顶点是与多边形上边内部点相连内对角线,进行拆分。
合并顶点是与多边形下 边内部点相连内对角线,进行拆分。

Plane sweep algorithm

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

伪代码

在这里插入图片描述
在这里插入图片描述

辅助顶点

在这里插入图片描述
如何去决定内对角线应该和谁相连呢?
在这里插入图片描述

对于不同vertex不同的操作 start vertex

在这里插入图片描述

end顶点

在这里插入图片描述
翻译:
如果边的辅助点的类别在这个顶点结束是一个归并顶点(helper(ei)->merge vertex),那么我们可以在这个辅助点和当前顶点之间添加一条对角线
从T中删除顶点的端点

分裂顶点

在这里插入图片描述

合并顶点

在这里插入图片描述

普通顶点

在这里插入图片描述

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


网页名称:DCELC++实现-创新互联
网页URL:http://abwzjs.com/article/cddjhs.html