自由曲线到自由曲线曲面Hausdorff距离近似值的计算

论文摘要

Hausdorf距离定义在两个有界点集之间，是点集内所有点到另一点集最近距离中的最大值，可用来衡量两个点集的匹配程度。Hausdorf距离在计算机图形学、模式识别等领域有着广泛的应用。计算机辅助设计中自由曲线到自由曲线曲面的Hausdorf距离可用来进行误差控制和重合判定。本文计算平面折线之间的Hausdorf距离作为平面自由曲线之间Hausdorf距离的近似值。平面折线之间的Hausdorf距离计算基于平面线段到平面折线Hausdorf距离计算的增量式算法实现。为了排除折线上不产生Hausdorf距离的无效线段，本文根据Hausdorf距离的性质提出两个剪枝策略并结合R-Tree结构加以应用，提高了算法的效率。相对于现有的解方程方法，采用折线方法计算平面自由曲线Hausdorf距离具有误差可控、易于实现等优点。对于空间自由曲线之间的Hausdorf距离，本文计算空间折线之间的Hausdorf距离作为其近似值。空间内折线之间Hausdorf距离计算基于空间线段到空间折线Hausdorf距离计算的增量式算法。该算法依赖于空间折线Voronoi图分割线段所得的子线段集合，本文通过分析空间线段平分面的构成情况以及求解直线与平分面交点方程求得该集合。本文还应用剪枝策略和R-Tree结构对空间折线上的无效线段进行排除，以提高算法效率。本文的实验表明，在满足105级别的距离误差条件下，本文所提出的方法在速度上优于现有的解方程方法。空间自由曲线到自由曲面的Hausdorf距离由空间折线到三角网格的Hausdorf距离来近似。空间折线到三角网格的Hausdorf距离计算基于线段到三角网格Hausdorf距离的增量式算法实现。对于无效的空间线段和三角面片，本文应用剪枝策略加以排除，实验中折线和三角网格上的排除率均达到了99%。

论文目录

• 摘要
• Abstract
• 第1章 引言
• 1.1 Hausdorf距离定义
• 1.2 Hausdorf距离的研究现状
• 1.3 Hausdorf距离的一些性质
• 第2章 平面自由曲线之间Hausdorf距离近似值计算
• 2.1 曲线离散化算法及误差控制
• 2.2 平面内线段到折线的单向Hausdorf距离
• 2.2.1 增量式算法
• 2.2.2 平面内线段与两线段平分线求交
• 2.3 折线到折线单向Hausdorf距离算法
• 1上的无效线段'>2.3.1 排除折线d₁上的无效线段
• 2上的无效线段'>2.3.2 排除折线d₂上的无效线段
• 2.3.3 复杂度分析
• 2.3.4 R-Tree加速
• 2.4 平面内自由曲线之间Hausdorf距离近似值算法
• 2.5 实验结果及分析
• 2.5.1 增量式算法与构建Voronoi图方法对比
• 2.5.2 平面自由曲线的Hausdorf距离实验结果
• 2.5.2.1 平面Bezier曲线上的实验结果
• 2.5.2.2 平面B样条曲线上的实验结果
• 2.5.2.3 平面NURBS曲线上的实验结果
• 第3章 空间自由曲线之间Hausdorf距离近似值计算
• 3.1 空间内线段与线段平分面求交
• 3.1.1 空间内线段平分面构成情况
• 3.1.2 空间内直线与线段平分面求交
• 3.1.2.1 直线与点-点平分面求交
• 3.1.2.2 直线与点-线平分面求交
• 3.1.2.3 直线与线-线平分面求交
• 3.2 空间折线上的R-Tree加速
• 3.3 空间内自由曲线之间Hausdorf距离近似值算法
• 3.4 实验结果及分析
• 第4章 自由曲线到曲面单向Hausdorf距离近似值计算
• 4.1 曲面离散化及误差控制
• 4.2 线段与三角面片平分面求交
• 4.2.1 三角面片之间平分面的构成情况
• 4.2.2 直线与三角面片平分面求交
• 4.2.2.1 直线与点-面平分面求交
• 4.2.2.2 直线与线-面平分面求交
• 4.2.2.3 直线与面-面平分面求交
• 4.3 曲线到曲面Hausdorf距离近似值算法
• 4.4 实验结果及分析
• 4.4.1 计算曲线到曲面Hausdorf距离近似值
• 4.4.2 实际工程样例应用
• 第5章 总结与展望
• 5.1 总结
• 5.2 展望
• 参考文献
• 致谢
• 个人简历、在学期间发表的学术论文与研究成果