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

第十届岩石力学与工程大会论文集 判断点与多面体空间位置关系的一个新算法 石 露，白 冰，李小春 ( 中国科学院 武汉岩土力学研究所，湖北 武汉 430071) 摘要：在有限元和计算几何的一些算法中，经常需要判断任意已知坐标点同某个单元或多面体之间的位置关系。倘若算法不 优，对于需要大量判断的问题计算量将显著增加，从而降低问题求解速度。此外，因多面体或单元形状的多变性，判断算法 在原理和实现上也应具有一般性才能适应各种情形。而通常使用的体积判别法，即计算该点同多面体各表面形成的小多面体 的体积之和与该多面体的体积对比来判断该点同多面体的位置关系。该方法虽然在总体思想上具有一般性，但是其核心是多 面体体积的计算，由于空间体积计算编程繁琐，并且计算量大，这就给这种判断算法带来了缺点。本文基于空间向量的性质， 提出了一种新的判断思想和算法，该算法克服了体积判别法的缺点，在算法思想和实现上都有良好的通用性，具有计算速度 快和易于编程实现的优点。 关键词：多面体；单元；点；空间向量；数量积 中图分类号：TU413.6+2; TU457 文献标识码：A 文章编号：1000 –6915(2006)01 –0001 –03 NEW ALGORITHM TO JUDGE THE RELATION OF SPATIAL LOCATION BETWEEN POINT AND POLYHEDRON SHI Lu，BAI Bing ，LI Xiao-chun (Institute of rock and soil mechanics, Chinese Academy of Science, Whuhan 430071, China) Abstract ：Judging the position of specific points relative to a geometrical entity is frequently performed in the FEM code or computational geometry. If the algorithm is not efficient, the computational velocity will be turned down due to large number of judgements, which surely increase calculated amount remarkably. Furthermore, for the polytrope of polyhedron, the algorithm must be provided with universality so as to adapting to different situations. The volumetric discriminance, commonly used by others, is implemented by contrasting two volumes, one is the volume of the polyhedron, and the other is the summation of small polyhedrons formed by the point and surfaces of the polyhedron. The core of this method is to calculate the volume of polyhedron, which brings disadvantage because of inconvenient programming and large calculated amount. Basing on the properties of dimensional vector, we