空间两三角形的相交问题

摘要

This paper focuses on geometric singularity and algorithm speed.In our algorithm,a 3D problem is reduced to planes and is further divided to a linear problem.In order to simplify the representation of geometric problem,a computational coordinate system is constructed.Thus,the geometric singularity of two triangles is reduced to planar problems between a line and a triangle,which limits the singularity to co-points and co-lines.Consequently,the complex spatial geometric singularity can be represented by planar drawings simply and visually and the robustness of our algorithm can be certificated theoretically.This paper gives the whole algorithm and detailed schemes.Experiment tests show that the priority in simplifying geometric relations,geometric singularity and calculations is sufficient to make up for the cost of transformation.The speed is 1 million pairs of triangles per second on a notebook computer.%重点考虑几何奇异问题,同时兼顾算法的效率.运用“分而治之”的方法从一维解得到二维解,进而得到三维解,将空间问题变为平面问题、线性问题.基于几何代数化依赖于坐标系,引入“计算坐标系”,简化了几何的表述与关系的类型,使“几何奇异”状态最后归结为平面上线段被三角形裁剪时的共点、共线问题,简单而明晰,从而可从理论上保证算法的鲁棒性,以平面处理的形式给出了两个空间三角形求交的完整解决方案.测试证明,几何关系、几何奇异类型与计算的简化足以弥补因“变换”而增加的额外开销.算法的速度也能达到实用要求——在笔记本电脑上也能达到每秒100万对三角形的相交计算.