对于二维任意的两类特征样本进行分类，特征提取的好坏直接影响到分类器设计和性能。非线性问题是很多学科研究当中经常遇到的困难，不仅要研究较好分类决策，而且要研究较好的特征提取方法。 本文首先介绍了三角剖分应用、进展和分类的相关知识，以及Voronoi图与Delaunay图的相关定义和性质，用插入法实现Delaunay三角剖分，算法复杂度为O(N2)。根据凸包生成算法原理，用Graham算法实现散乱样本的最小凸包，算法复杂度为O(NlogN)。在此基础上，借助计算几何和离散数学等相关知识，为非线性分类问题中的特征提取提出新的思路—散乱样本凸体分割与逼近算法，算法保证了两类样本形成的凸包两两互不相交，即同类样本之间、同类和异类之间形成的凸包互不相交，并且凸包数量逼近最少，为非线性分类提供了新的研究思路。 该算法的实现，可以应用于非线性分类，神经网络分类学习(包括BP，RBF)，以及二维图像散乱点的填充。