半边数据结构(Half-Edge Data Structures)详细介绍
半边数据结构，看起来我认为它很复杂，而且构建和维护都很烧脑的东西，实际是能够提供高效遍历能力的数据结构，这篇文章就是要讲清楚这个半边数据结构。
0.为什么用半边数据结构，有什么好处
为什么要学习和使用半边数据结构，这点我在使用VTK的时候感受就很大。首先你是做三维几何处理算法的，需要细到跟顶点和三角面打交道。你就知道常用的三维模型文件，STL、OBJ、PLY文件。文件里面基本存的都是顶点坐标和每个三角形(三个顶点的顶点索引)。确实读取后能够根据这些信息构建得到网格模型，也能够通过三角形的顶点索引找到相应的顶点坐标。
VTK的数据结构也是提供了顶点集合(vtkPoints)和三角面集合(vtkCellArray)的数据结构，但是每次要遍历邻居的时候，都很不方便。我能够访问当前顶点的所有邻居三角形(GetPointCells)，但是得到的结果是无序无指向性的，我想要有指向性地去遍历访问的时候，这就变得很不方面，总觉得缺少了联系顶点和三角面的桥梁。
而半边数据结构补足了这一点，它让我变得很方便去遍历顶点和三角面邻居。
1.认识半边概念
半边数据结构由英文翻译而来，字面意思可能会出现歧义，就是说有人会理解成将三角形边对半切成两个半边。我觉得用”阴阳边“去理解会更贴切一点。
半边（阴阳边）是指将三角形边h加入指向性，三角形边有两个顶点，v1和v2，加入指向性的话可以说一个是起点，一个是终点。当v1作为起点，v2作为终点，那么这条边视作h阳边；反而来v1作为终点，v2作为起点，那这条边视作h阴边。也就是说加入指向性后，边h可以根据方向被看成两条边。
就像阴阳一样。
2.认识半边数据结构
首先三维模型文件里面都不提供关于边的信息，而半边数据结构是关于边的信息，所以没法直接从模型文件获取，需要根据顶点和三角形索引这两项信息去构建该数据结构。这是认识半边数据结构的前提。
接下来忘掉阴阳边的概念，因为我们知道半边有指向性即可，我们不需要规定方向，不理会顺时针逆时针的事情。
我们现在开始读一个STL文件，这个STL只有一个三角形面face1，三个顶点：point1, point2和point3。构建的起来的话想下面左图一样，没有边的信息，也没有边的概念。
我们要构建半边数据结构，就要看到右边那样，我们人为地赋予其边的信息，看着一共三条边，我们就会得到6条半边。很明显，不管是处于内侧的红色边还是处于外侧的黑色边，都是有一个指向性的：当前边的终点，是下一条边的起点，而且内侧的红色边会形成一个循环。从e1出发，走完一圈e2到e3，还是会回到e1。
那么重点来了，半边数据结构应该长什么样：
我们描述一条半边，就是要记录它的关键信息指向性，说到指向性就会想到链表。首先半边有个自己的索引id，然后要记下来自己的起点是哪个顶点id，接着记下自己下一条边next是谁（指向性），还有自己的对边twin是谁（完整性）。这几项是最基础的必要信息。而如果想半边更高效，那么再记录上自己的前一条边pre是谁，还有自己关联的三角面face_index是谁，或者说自己是属于哪个三角面（位于哪个三角形内侧，完整性）。
总结一下，半边数据结构的成员包括：
struct HalfEdge
{int halfedge_index; //自己的indexint point_index; //起点顶点的索引HalfEdge *next; //下一条边的指针HalfEdge *twin; //对边的指针HalfEdge *pre; //上一条边的指针int face_index; //关联的三角形面id
}
重要：关注半边数据结构的同时，也应该关注顶点和三角面的数据结构
很多介绍会忽略顶点和三角面的数据结构，其实也很重要，要看顶点和三角面是怎么样跟半边联系的，这样了解半边数据结构才完整。
3.重要：补充认识顶点和三角面的数据结构
顶点数据结构应该加入其作为起点的半边，而三角面也应该加入其内侧的半边。
顶点数据结构的成员包括：
struct Point
{int point_index; //自己的顶点索引HalfEdge halfedge; //作为起点的半边double coord[3]; //顶点坐标值... //其他成员
}
三角面数据结构的成员包括：
struct Face
{int face_index; //自己的索引HalfEdge halfedge; //内侧的一条半边... //其他成员
}
一个顶点可能是很多条半边的起点，只需要随意关联其中一条半边即可。
一个三角面有三条内侧半边，也是只需要随意关联其中一条半边的即可。
因为遍历的时候会先找到半边，再从半边开始遍历，所以顶点和三角面中关联的半边是起到定位的作用。
4.使用1：遍历一个三角面
遍历一个三角形面获得他的所有半边和顶点
void Iterating_a_Face(Face face)
{HalfEdge start_he = face.helfedge);HalfEdge he = start_he;do{do somthing using he;he = he.next;}while(he != start_he);}
5.使用2： 围绕顶点遍历边
以逆时针顺序围绕顶点遍历所有边
void Iterating_around_Point(Point point)
{HalfEdge start_he = point.halfedge;HalfEdge he = start_he;do{do somthing using he;he = he.pre.twin;}while(he != start_he);
}
以顺时针顺序围绕顶点遍历所有边
void Iterating_around_Point(Point point)
{HalfEdge start_he = point.halfedge;HalfEdge he = start_he;do{do somthing using he;he = he.twin.next; //区别之处}while(he != start_he);
}
总结：
半边数据结构通过将每条边拆分成两个方向相反的“半边”来表示，加入指向性后，半边数据结构能够高效地访问网格的拓扑信息，如邻接顶点、邻接边和邻接面。半边数据结构非常适合执行复杂的网格操作，如边的分裂、合并、翻转等（都是对边的操作）。这些操作在其他数据结构中可能非常复杂，但在半边数据结构中可以高效地实现。
参考资料：
[1]https://jerryyin.info/geometry-processing-algorithms/half-edge/
[2]https://cs418.cs.illinois.edu/website/text/halfedge.html
