DCELC++实现-创新互联
DECL
网站题目：DCELC++实现-创新互联
文章URL：http://ybzwz.com/article/cddjhs.html
DECL结构是比较通用的来表示几何的数据结构
主要包括三种数据结构：
1.点 vertex
2.半边 edge
3.面 face
存储点的位置以及任意一条由该点为起点向量的半边
半边其中几何边由两条半边组成
这也是一种表示方式
存储一个面的外边界和内边界，如果外边界或者内边界不存在那么直接等于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;
}
} 
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;
}
}
}
}
} 
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;
} 
正例
反例
1.开始顶点
2.结束顶点
3.普通顶点
4.分裂顶点
5.合并顶点
开始顶点与结束顶点是一对，面向多边形内部的角度是锐角
普通顶点，两个端点是上下一侧
分裂顶点和合并顶点是需要实际操作的，单调多边形拆分主要是拆这两个顶点
分裂顶点是与多边形上边内部点相连内对角线，进行拆分。
合并顶点是与多边形下 边内部点相连内对角线，进行拆分。
如何去决定内对角线应该和谁相连呢？
翻译：
如果边的辅助点的类别在这个顶点结束是一个归并顶点（helper(ei)->merge vertex)，那么我们可以在这个辅助点和当前顶点之间添加一条对角线
从T中删除顶点的端点
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
网站题目：DCELC++实现-创新互联
文章URL：http://ybzwz.com/article/cddjhs.html
