四边形边缘数据结构的makeEdge逻辑

Question

我正在阅读Guibas-Stolfi论文，该论文描述了一种可用于计算Delaunay三角剖分的四边形边数据结构。我正在使用Java来实现QuadEdge数据结构。

我正在遵循此网站 Quad Edge data Structure Java中提到的实现。

简而言之，四边形边结构包括两个操作，即：

1. makeEdge->返回子细分中存在的边e的四边形边。 2. splice(a，b)->用于更改与四边形边a和b相关联的拓扑的函数。

现在，四边形边数据结构由两个字段Data和Next指针组成。

下一个字段是通过以下公式计算的： e[r].Next = e(Rot^r)Onext。

为了了解Onext，我在这里附上Guibas-Stolfi论文中的一张图。

现在，示例代码设置四个四边形边缘的下一个指针。它们如下所示1。

q0 = new QuadEdge();
q1 = new QuadEdge();
q2 = new QuadEdge();
q3 = new QuadEdge();

q0.Onext = q0; 
q1.Onext = q3; //on the sphere, left=right (How?? or Why??)
q2.Onext = q2; 
q3.Onext = q1;

如果Onext（即具有与e相同起点的下一个逆时针边缘）是该边本身，为什么在采用对偶边缘时它是另一条边缘。

- chaitanya

Answer 1

看起来q1和q3都有一个共同的原点（虚拟的无限远点）。这就是为什么q1.oNext == q3和q3.oNext == q1。

- Andrey Naumenko

Answer 2

问题中的链接已经失效，但幸运的是它在正文中包含了足够的信息。

Quad-edge数据结构是由LEONIDAS GUIBAS和JORGE STOLFI在论文Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams中介绍的。我认为它包含了你问题的答案。

四个边记录QuadEdge（原始图的两个相反方向的边和对偶图的两个相反方向的边）构成了一个与细分中的边对应的组：

图片上的箭头指向下一个共享相同起点的边（对于原始边来说是相同的顶点，对于对偶边来说是相同的面）- Onext。

MakeEdge 函数构建了一个球形细分，包含一个无向边、一个面和两个顶点：

q0和q2是原始图的相对定向边，其起点在一个顶点上。由于每个顶点只有一条有向边，因此我们有：q0.Onext = q0和q2.Onext = q2。

q1和q3是对偶图的相对定向边，它们是环边，因为它们的起点和终点在细分的同一（也是唯一的）面内。这个面是q1和q3的起点，因此它们的oNext形成一个循环：

q1.Onext = q3;
q3.Onext = q1;

请注意，对于半边数据结构，操作makeEdge和splice同样有意义。您可以在例如MeshLib中找到它们的实现，查看MeshTopology::makeEdge() 和 MeshTopology::splice( EdgeId a, EdgeId b )。

- Fedor