Convex Body Segmentation And Approximation Of Scattered Sample

To distinguish different sample, feature extraction directly influences the design and performance of the classifier. Non-linear classification in many research fields is very difficult. So not only good classified decision but also good method of feature extraction need to be studied.This paper first introduces the application and development of triangulation, the related knowledge about classification and the related definition and property about Voronoi diagram and Delaunay diagram. Then Deluany triangulation is realized by incremental insertion which computational complexity is O(N2). Relying on the theorem of Graham, the sample points are realized the minimal convex hull which computational complexity is O(NlogN).Last a new feature extraction- convex-body segmentation and approximation of scattered sample for non-linear classification based on the knowledge of Computing Geometry and Discrete Mathematics is presented. New algorithm guarantees that every convex hull is unintersectant. Both convex hull between the same classes and convex hull between the different classes are unintersectant. The quantity of convex hull is as less as possible.This algorithm can be applied to non-linear classification, neural classification algorithm(including BP and RBF) and 2D image filling for sample points.