1.1.三角剖分定义
    【定义】三角剖分：假设V是二维实数域上的有限点集，边e是由点集中的点作为端点构成的封闭线段, E为e的集合。那么该点集V的一个三角剖分T=(V,E)是一个平面图G，该平面图满足条件：
    1.除了端点，平面图中的边不包含点集中的任何点。
    2.没有相交边。
    3.平面图中所有的面都是三角面，且所有三角面的合集是散点集V的凸包。
1.2.  Delaunay三角剖分的定义
    在实际中运用的最多的三角剖分是Delaunay三角剖分，它是一种特殊的三角剖分。先从Delaunay边说起：
    【定义】Delaunay边：假设E中的一条边e（两个端点为a,b），e若满足下列条件，则称之为Delaunay边：存在一个圆经过a,b两点，圆内(注意是圆内，圆上最多三点共圆)不含点集V中任何其他的点，这一特性又称空圆特性。
    【定义】Delaunay三角剖分：如果点集V的一个三角剖分T只包含Delaunay边，那么该三角剖分称为Delaunay三角剖分。
1.3.Delaunay三角剖分的准则
    要满足Delaunay三角剖分的定义，必须符合两个重要的准则：
    1、空圆特性：Delaunay三角网是唯一的（任意四点不能共圆），在Delaunay三角形网中任一三角形的外接圆范围内不会有其它点存在。如下图所示：

1.4.Delaunay三角剖分的特性
    以下是Delaunay剖分所具备的优异特性：

    LOP处理过程如下图所示：

    这一算法的关键的第2步图示如下：

数学之美 系列十八 － 矩阵运算和文本处理中的分类问题