数据三角化

按照随机的顺序依次插入点集中的点，在整个过程中都要维护并更新一个与当前点集对应的Delaunay 三角剖分。考虑插入vi点的情况，由于前面插入所有的点v1,v2,...,vi-1构成的DT(v1,v2,...,vi-1)已经是Delaunay 三角剖分，只需要考虑插入vi点后引起的变化，并作调整使得DT(v1,v2,...,vi-1) U vi成为新的Delaunay三角剖分DT(v1,v2,...,vi)。 (插入调整过程：首先确定vi落在哪个三角形中（或边上），然后将vi 与三角形三个顶点连接起来构成三个三角形（或与共边的两个三角形的对顶点连接起来构成四个三角形），由于新生成的边以及原来的