Delaunay Triangulation And Application Study Of Polygonal Domains

In Computational Geometry (CG) Delaunay Triangulation (DT) is a very important research topic. As an important geometrical structure, Delaunay triangle is generated accordingly under the constraint of empty circle criterion, which guarantees that DT gets the maximum value of minimum angle among different triangulations. Besides that, DT has a considerably systematic theory basis so that it has been widely used in many research areas, including computer graphics, mechanical engineering, virtual reality, GIS, robotics, image processing, CAD etc., and it is also an effective tool to solve other problems in CG, such as collision detection, skeletonization, visibility computation and so on. In recent years it has also been employed into the process of shape matching for object recognition, for example, minutia matching of fingerprint.This thesis takes an in-depth study on the theory of DT for polygonal domains and based on it studies to solve the problems of fast skeleton computing that occur in our research of computer graphics and virtual reality, and feature extraction of online handwritings recognition. These research topics arouse from our software systems ICAPD (Integrated Computer Aided Patterns Design and Plate-making System) and Online Handwritings Recognition System carried out during my visiting student phase in MSRA, and have important academic and practical meanings.The contributions of this thesis are:1. For arbitrary planar polygonal domains, constrained Delaunay triangles can becomputed in local ranges based on the incremental idea and the uniform grid. No triangles outside the valid region of the domain are computed and for domains with poly-lines, scattered points and holes, no extra operations need to be performed. The tested analysis shows that for simply polygonal domains randomly generated, the algorithm has fast computation and has an almost linear run time.2. For a special kind of polygons formed by the boundary of such band-images as texts, industrial patterns, etc., the Constrained Delaunay Triangulation (CDT) algorithm is optimized by fully utilizing the characteristic of approximately equal width and has been applied for fast skeleton extraction of band-images. The CDT algorithm has simple data structure, easy implementation, and little overhead cost. So the skeletonization algorithm based on it is also easy to implement and obviously accelerated.3. For online English handwritten characters, considering their rich temporal characteristics and geometrical and topological shape features, a CDT algorithm along constrained edges is developed and the Delaunay triangle descriptor as a novel shape context descriptor is presented to extract efficient features. Such triangle descriptor covers much of global features, and the test shows that it can obviously improve recogmtion accuracy and build up the system's stability and robustness compared with other conventional feature combination.4. For online English handwritings, a recognition system is constructed based on Discrete Hidden Markov Model (DHMM). For each letter class, multi-model may be generated by iterative Baum-Welch reestimation algorithm. Then based on the letter HMM book, a Cascade Connection HMM (CCHMM) method is employed for word recognition. The proposed pruning technique on model and recognition level reduces the search space considerably with a little improvement on the recognition performance compared to an exhaustive search.