基于拓扑映射的点集在凸多边形内外判断算法  

An Algorithm for Determining the Points of Set Inclusion of Convex Polygon Based on Topological Mapping

作　　者：温星[1] 陆国栋[1] 李基拓[1] 

机构地区：[1]浙江大学CAD&CG国家重点实验室,杭州310027

出　　处：《中国图象图形学报（A辑）》2003年第4期468-471,共4页Journal of Image and Graphics

基　　金：创新群体科学研究基金 ( 60 0 2 12 0 1) ;国家自然科学基金 ( 5 0 10 60 14 )

摘　　要：通过拓扑映射 ,点在凸多边形内外的判别可以转化为映射点在射影直线上的位置关系问题 .首先通过设置中心点 ,获取凸多边形各顶点的拓扑映射点 ,对于每个检测点 ,根据其映射点与顶点拓扑映射点的相对位置关系 ,即可确定检测点位于多边形哪条边的范围内 ;然后将检测点与该边进行包围盒测试 ,对于点在边包围盒外的情况 ,只需根据比较判别即可得到结果 ,对于点在边包围盒边界上或内部的情况 ,则需通过叉积运算进行判别 .该方法几何意义清晰 ,实验结果表明 ,该算法运行可靠 ,对于单个点或多点组成的点集均有较高的检测速度 .Via topological mapping, the inclusion test of whether a set of points is in a polygon or not can be converted to comparing the projected points' position on the projection line. At first, the center point for topological mapping must be figured out, then the method maps vertices of the polygon onto the projection line. To each point of the set, according to the position of its mapping point and the mapping points of the vertices, it is confirmed that the point is in the area of two lines from the center point to the two vertices of one of the polygon's edges. And then, according to the two cases, whether the point is in the edge's box or not, we can draw a conclusion. If the point is out of the edge's box, the calculation of comparing its position with the edge's box's is only needed,and if the point is in or on the boundary of the edge's box, the calculation of cross product must be added. To the points of set, througth pre calculation of the polygon's vertices this algorithm can greatly reduce calculation of each point. Experiments show that this algorithm is rapid, robust and can be implemented easily.

关 键 词：拓扑映射 点集 凸多边形内外判断 计算机图形学 判断方法 拓扑变换 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术] TN911.73[自动化与计算机技术—计算机科学与技术]