三维数据场造型的一种有效方法就是对三维点集进行三角剖分，即将二维(三维)空间中任意分布的散乱点用直线段连接起来，形成的空间上既不重叠又无间隙的紧邻的三角形(四面体)集，每个三角形(四面体)的顶点即为原始散乱点。也就是说，在二维情况下得到的是三角形网格，在三维情况下得到的是四面体网格。对于平面散乱点集，剖分出来的各三角形应当尽量接近正三角形；同样，对三维散乱点，要求剖分出来的各四面体应尽可能接近于正四面体。目前存在着多种三角剖分规则的优化规则，但是目前公认的具有最好几何拓扑性质的剖分就是符合Delaunay规则的三角剖分。 Delaunay三角剖分的优化规则就是Delaunay三角形的两个重要性质——空外接圆(空外接球)性质和最小角最大化(最小空间角最大化)性质。可以证明这两个性质是等价的，并且这两个性质任意一个即可当作Delaunay三角剖分的准则。目前，对于Delaunay三角剖分存在很多种算法，经典的算法有：逐点插入法、分割归并法、三角形生长法和扫描线算法，这些经典算法都是属于确定性算法的范畴。最近，有人尝试使用遗传算法来解决三角剖分问题，但是其主要研究对象是最小权三角剖分，而不是Delaunay三角剖分。 遗传算法是一种全局优化自适应概率搜索算法，它使用群体搜索技术，通过对当前群体施加选择、交叉、变异等一系列遗传操作，从而产生新一代的群体，并逐步使群体进化到包含或接近最优解的状态。由于其具有思想简单、易于实现、应用效果良好等优点而被众多应用领域所接受，并在自适应控制、组合优化、模式识别、机器学习、人工生命、管理决策等领域得到了广泛的应用。遗传算法实际上是一种通用的算法框架，该框架不依赖于问题的种类，其实现细节是非常灵活的。遗传算法是一类具有较强鲁棒性的优化算法，特别是对于一些大型的、复杂非线性系统，它更表现出了比其他传统优化方法更加独特和优越的性能。隐含并行性和全局所搜特性是遗传算法的两大显著特征。 正是基于遗传算法在处理优化问题方面的优势，结合Delaunay三角剖分的图形优化的本质，本文尝试采用遗传算法来解决Delaunay三角剖分问题。针对Delaunay三角剖分的特点，本文采用邻接矩阵的编码方式来表示个体的基因型，所有的遗传操作将在个体的邻 接矩阵上进行；对于交叉操作，本文提出了二维平面散乱点的多边形交叉算子和三维空间散乱点的虚拟交叉算子；对于变异，本文提出了针对二维的简单交换对角线变异，而对于三维情况，本文没有使用变异算子，所以文中称为基于交叉的三维空间散乱点Delaunay三角剖分遗传算法；最后，本文还针对二维和三维分别提出了有效的评价函数，采用了优胜劣汰的进化策略，有效地平衡了种群多样性和全局收敛性之间的矛盾。实验证明，利用遗传算法解决Delaunay三角剖分问题是切实可行的，在实际应用中具有一定的实用价值。