A General and Fast Triangulation Algorithm

A general algorithm of triangulating arbitrary planar polygonal domain and scattered point set is presented．When it acts on polygonal domain，all the vertices of boundary edges and scattered points within the domain are sorted in scan manner．Each time take a feasible vertex and generate a new triangle on known edge，until the whole domain is triangulated．Swapping the diagonal of a quadrilateral is applied to locally optimize the cell form．