当前位置：首页 > article >正文

半边数据结构(Half-Edge Data Structures)详细介绍

article 2025/2/11 15:56:17

半边数据结构(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;	//自己的index
	int 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);
}

总结：

半边数据结构通过将每条边拆分成两个方向相反的“半边”来表示，加入指向性后，半边数据结构能够高效地访问网格的拓扑信息，如邻接顶点、邻接边和邻接面。半边数据结构非常适合执行复杂的网格操作，如边的分裂、合并、翻转等（都是对边的操作）。这些操作在其他数据结构中可能非常复杂，但在半边数据结构中可以高效地实现。