java - 四边数据结构 makeEdge 逻辑

Question

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

我正在关注本网站上提到的实现 Quad Edge data Structure Java .

简而言之，Quad 边结构由 2 个操作组成，即

1. makeEdge -> 返回分割中出现的边 e 的四边形
2. splice(a,b) -> 用于更改与四边形边 a 和 b 相关联的拓扑的函数。

现在，Quad Edge 数据结构由 2 个字段组成，即数据和下一个指针。

下一个字段是使用公式计算的， e[r].Next = e(Rot^r)Oneext.

关于 Onext 的想法，我附上了 Guibas-Stolfi 论文中的一张图

现在，示例代码为四边形的所有 4 个部分设置了下一个指针。它们设置如下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 具有相同原点的下一个逆时针边)是边本身，为什么在采用双边时它是另一条边。

Answer 1

看起来 q1 和 q3 的原点都在同一点(无穷远的虚拟点)。这就是为什么 q1.oNext == q3 和 q3.oNext == q1。