空间两三角形的相交问题

摘要

重点考虑几何奇异问题,同时兼顾算法的效率。运用＂分而治之＂的方法从一维解得到二维解,进而得到三维解,将空间问题变为平面问题、线性问题。基于几何代数化依赖于坐标系,引入＂计算坐标系＂,简化了几何的表述与关系的类型,使＂几何奇异＂状态最后归结为平面上线段被三角形裁剪时的共点、共线问题,简单而明晰,从而可从理论上保证算法的鲁棒性,以平面处理的形式给出了两个空间三角形求交的完整解决方案。测试证明,几何关系、几何奇异类型与计算的简化足以弥补因＂变换＂而增加的额外开销。算法的速度也能达到实用要求——在笔记本电脑上也能达到每秒100万对三角形的相交计算。