1概述

     多边形三角剖分是计算几何( Computational Geometry)中的经典问题，起源于一个有趣的艺术画廊问题。目前有很多不同的算法实现了对多边形的三角剖分，三角化算法所追求的目标主要有两个：形状匀称和计算速度快，这也决定了多边形三角剖分的两个不同的应用方向。在形状匀称方面，人们对三角化的性质、 形状最优准则及算法进行了深入研究 ，采用较多的是 Delaunay 准则。这些算法在保证形状匀称的前提下，也尽可能考虑了提高计算速度。在有限元分析等许多应用场合三角形匀称是必须的，对单元质量是有一定要求的。但有些应用场合对三角形匀称性的要求不高，甚至没有匀称性要求。例如用 OpenGL显示图形时，不同的三角化策略对图形效果基本没有影响。在三角化时考虑匀称性，会使算法思想受到限制，从而影响算法效率。因此追求较高计算效率的三角化算法还是有意义的。本文所探讨的即是时间复杂度为O(n log n)的多边形三角剖分算法,这也是很多经典计算几何教材所给出的经典算法。     多边形三角剖分是计算几何( Computational Geometry