基于夹边边对的凸多边形间快速相交检测算法

本文在对现有的相交检测算法进行研究的基础上，提出了基于夹边边对的空间平面凸多边形快速相交检测算法，为平面凸多边形间判交问题提供了一致的计算方法，并将算法的应用对象扩展到任意空间平面凸多边形。该算法分为两步：第一步，确定所要检测的两个凸多边形是否都存在相对于另一凸多边形所在平面的夹边边对，如果至少一个凸多多边形中不存在相对于另一凸多边形所在平面的夹边边对，那么立即返回两个多边形不相交；第二步，根据前面计算得到的两个凸多边形中的夹边边对，计算两组边对间对应夹边的符号距离判断两个多边形是否相交

Research of the Fast Intersection Test Algorithm on Spatial Convex Polygons

Based on the existing intersection test algorithms,a fast coincident intersection test algorithm for 3-D convex polygons based on clamping-edge pairs is presented, which provides a coincident computational method for the overlap judgement between convex polygons,and expands the algorithm application object to the free 3-D convex polygons. There are two steps in this algorithm. First,decide whether there is a clamping-edge pair in each polygon to the plane in which the other polygon lies. If the answer is no, it can be determined immediately that the two polygons do not overlap. Second, you should calculate the signed line-line distance between the two clamping-edge pairs of the two polygons and determine wheth- er the two polygons intersect.