点与简单多边形位置关系判别新算法  

New algorithm for determining position relation between simple polygon and point

作　　者：陈金林[1] 刘谢进[1] 李宁[1] 

机构地区：[1]淮南师范学院数学与计算科学系,安徽淮南232038

出　　处：《淮南师范学院学报》2012年第5期120-122,共3页Journal of Huainan Normal University

基　　金：安徽省高校省级自然科学研究项目(KJ2011Z354);淮南市科技计划项目(2011A08017)

摘　　要：基于点到角的最小距离提出一种判别点与多边形位置关系的新算法。通过扫描与点距离最小的线段,在多边形中有两个角共有此线段,选择其中任意一个角,定义点到此角的距离取得最小。判断点与角的内外侧关系,确定点与多边形内外侧位置关系。该算法通过点与点的距离运算避免了传统的交点、叉积的求解。比较试验表明,此新算法易于实现、计算速度快。Give a new algorithm about point visibility for simple polygon based on the minimum distance problem of point and angle.A preprocessing is used to establish the segment that has the minimum distance with point.There are two angles in simple polygon there this segment,select any angle.A new algorithm for determining the position relation between the location of points and the angle is proposed.Algorithm did not use the cross,point of intersection operation to reduce the multiplications by finding the distance between points and line segment.Comparison experiments show that the method has a very effective computational behavior and effectiveness,and decrease the time.

关 键 词：点 简单多边形 算法 多边形角 

分 类 号：TP391.72[自动化与计算机技术—计算机应用技术]