摘要
基于点到角的最小距离提出一种判别点与多边形位置关系的新算法。通过扫描与点距离最小的线段,在多边形中有两个角共有此线段,选择其中任意一个角,定义点到此角的距离取得最小。判断点与角的内外侧关系,确定点与多边形内外侧位置关系。该算法通过点与点的距离运算避免了传统的交点、叉积的求解。比较试验表明,此新算法易于实现、计算速度快。
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.
出处
《淮南师范学院学报》
2012年第5期120-122,共3页
Journal of Huainan Normal University
基金
安徽省高校省级自然科学研究项目(KJ2011Z354)
淮南市科技计划项目(2011A08017)
关键词
点
简单多边形
算法
多边形角
point
simple polygon
algorithm
polygon angle
