三角化

在计算机图形学领域，当使用OpenGL等API进行绘图时，由于其本身并不支持对凹多边形的直接绘制，因此我们需要通过一种称为"三角化"的过程来将其转换成一系列的三角形。

算法过程

三角化的具体实现可以分为以下几个步骤：

首先，我们利用单向循环链表存储多边形的所有顶点，并对每个顶点的凸凹性质进行判断。

接着，在链表中依次选取三个节点P、Q、R。若Q为凸点，且形成的三角形PQR不包含多边形上的其他顶点，则计算该三角形的特征角，即内部最小的角度。随后，我们将所有的此类三角形记录下来，并选出其中特征角最大的三角形△PQR，将其保存并从链表中删除节点Q。

如果链表中仍然有三个或以上的节点，那么我们就返回步骤二继续处理。

最终，对于链表中剩余的最后三个节点，我们可以直接构建一个新的三角形。

通过这些步骤，我们能够有效地将任意形状的凹多边形分解成多个三角形，从而使得它们能够在OpenGL等API的支持下被正确地绘制出来。

计算机图形学.CSDN博客.2024-10-24

三角化.简书.2024-10-24

OpenGL是什么.CSDN博客.2024-10-24