判定点与三角形位置关系的新算法

针对图形学中现有点与三角形位置关系判定算法平均基本操作次数大、存在不可判定情况等不足,尝试通过添加异常处理进行算法改进,以适当减少基本操作次数。改进后的判定算法采取两次区域划分,将异常简化为求交点问题,来提高判定效率和准确性。在数学证明的基础上所进行的软件仿真结果表明,改进后的算法具有可行性,能够达到判定算法在效率和准确性方面的要求。

A new algorithm for judging location between the points and the triangle

In computer graphics, the classical algorithm for judging location between the points and the triangle has shortages such as the large number of basic operations and the existing of the abnormal cases. In this paper a new algorithm was proposed to reduce the number of basic opera- tions by adding exception handling. The advanced algorithm took twice area dividing; and simpli- fied the exception to calculate the intersection point so that it could promote the efficiency and the accuracy. After the mathematical proving, the simulation results showed that the proposed new algorithm was feasible to achieve the design demands.