近年来随着激光等三维数据采样技术以及硬件设备的日益完善和机器人技术以及计算机技术的发展,基于散乱数据的物体三维重建获得了越来越广泛的应用。散乱数据点的三角剖分是物体三维重建中的重要环节,也是进行三维重建的前提和基础。所以本文对散乱数据的三角剖分进行了理论和实验研究,目的是通过对移动机器人激光测距仪采集的数据进行三角剖分,对物体进行三维重建。 首先,在平面三角剖分方面,本文在总结和比较目前存在的平面三角剖分方法的基础上,采用分治法和逐点插入法相结合的方法,将数据点数目超过分割阈值的散乱点集分割成若干部分分别剖分后再相连,提高了算法效率并且减少了占用的内存。通过实验得到了屋顶数据合理的三角剖分结果,并针对不同的分割阈值进行实验,对算法执行时间与分割阈值的关系进行分析。 其次,在约束三角剖分方面,本文采用先建立初始网格再插入约束线段的方法,对现存的算法进行了改进,将点集、边及三角形分块索引,减少了搜索时间。算法不需要块间的合并,降低了算法的复杂度。算法对影响区域的数据也进行了有效的管理,减少了三角网局部重建的时间,提高了算法的执行效率。通过实验得到了走廊数据的三角剖分,并对该算法所主要耗费时间的方面进行分析。 最后,在空间三角剖分方面,本文根据采集的数据仅是物体表面数据的特点,建立物体表面轮廓线,采用最短对角线法、控制点匹配法在相邻轮廓线之间进行三角剖分,得到了箱子和人的合理的三维重建结果。然后对这两种方法进行了比较,并分析了控制点匹配法优于最短对角线法的原因。在数据点减少时,使用插值函数代替线段连接轮廓线,使得网格简化时具有更好的效果。