判断点与多面体空间位置关系的一个新算法

摘 要：

      在有限元和计算几何的一些算法中，经常需要判断任意已知坐标点同某个单元或多面体之间的位置关系。倘若算法不优，对于需要大量判断的问题计算量将显著增加，从而降低问题求解速度。此外，因多面体或单元形状的多变性，判断算法在原理和实现上也应具有一般性才能适应各种情形。而通常使用的体积判别法，即计算该点同多面体各表面形成的小多面体的体积之和与该多面体的体积对比来判断该点同多面体的位置关系。该方法虽然在总体思想上具有一般性，但是其核心是多面体体积的计算，由于空间体积计算编程繁琐，并且计算量大，这就给这种判断算法带来了缺点。本文基于空间向量的性质，提出了一种新的判断思想和算法，该算法克服了体积判别法的缺点，在算法思想和实现上都有良好的通用性，具有计算速度快和易于编程实现的优点。

判断点与多面体空间位置关系的一个新算法.pdf