math - 如何计算多边形三角剖分中两段的内角

Question

语境

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

输入是存储为双连接边列表的多边形。第一步是将多边形划分为单调块。为此，需要执行线扫描并根据每个顶点的类型对其进行处理。据作者介绍，顶点类型描述如下：

我们在 P 中区分了五种类型的顶点——见图 3.3。其中四种类型是转弯顶点：开始顶点、分割顶点、结束顶点和合并顶点。它们定义如下。如果顶点 v 的两个邻居位于其下方并且 v 处的内角小于 π，则该顶点 v 是起始顶点；如果内角大于 π，则 v 是一个分裂顶点。（如果两个邻居都在 v 之下，那么内角不能正好是 π。）如果一个顶点的两个邻居都在它之上并且 v 处的内角小于 π，那么它就是一个结束顶点。如果内角大于 π 那么 v 是一个合并顶点。不是转弯顶点的顶点是常规顶点。因此，一个规则顶点的一个邻居在它上面，另一个邻居在它下面。

问题

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

附加信息

我的 DCEL 数据结构是这样的

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

标签： mathgeometrytriangulation

Answer 1

也许如果您跟踪多边形边界的逆时针方向（即保持边缘定向），您可以区分两者。假设连续的顶点是 v[i-1]、v[i]、v[i+1] 和 v[i-1]，并且 v[i+1] 低于 v[i]。然后形成二维向量 v[i]-v[i-1] 和 v[i+1]-v[i]。之后，计算行列式 det( v[i]-v[i-1] , v[i+1]-v[i] )。如果行列式是正的，那么顶点是开始的。如果行列式为负，则分割顶点。