多边形三角剖分中两段内角的计算

Question

我必须为学校作业实现多边形三角测量算法。我选择遵循《计算几何：算法与应用》一书中描述的算法。

输入是存储为双连通边列表的多边形。第一步是将多边形分割成单调的部分。为了做到这一点，有必要执行线扫描，并根据每个顶点的类型对其进行处理。根据作者的说法，顶点类型描述如下：

我们在P-图中区分了五种类型的顶点，见图3.3。其中四种类型是旋转顶点：开始顶点、分割顶点、结束顶点和合并顶点。它们的定义如下。如果一个顶点v的两个邻接点位于其下方，且v处的内角小于π，则该顶点v为起始顶点；如果内角大于π，那么v是一个分裂顶点。（如果两个邻域都在v以下，则内角不能精确为π。）如果一个顶点的两个相邻顶点位于其上方，且v处的内角小于π，则该顶点为endpoint；如果内角大于π，那么v是一个合并顶点。非旋转顶点的顶点是规则顶点。因此，一个规则顶点的一个邻居在其上方，另一个邻居在其下方。

我不知道如何区分起始顶点和分割顶点，或结束顶点和合并顶点。我该怎么做？

我的DCELhtml" target="_blank">数据结构是这样的

class HalfEdge {
 HalfEdge *previous, *next, *twin;
 Point *to, *from;
};

Answer 1

也许如果你跟踪多边形边界的反时钟方向（即保持边指向），你可以区分两者。假设连续的顶点是v[i-1]，v[i]，v[i 1]和v[i-1]，v[i 1]低于v[i]。然后形成2D向量v[i]-v[i-1]和v[i 1]-v[i]。之后，计算行列式det（v[i]-v[i-1]，v[i 1]-v[i]）。如果行列式为正，则顶点开始。如果行列式为负，则顶点被分割。