基于边向量斜率比较的简单多边形顶点凸凹性快速判别算法  

An Algorithm for Rapidly Identifying Convexo-Concave Vertices of Simple Polygon Based on Comparing the Slopes of Two Adjacent Edge Vectors

作　　者：庞明勇[1] 卢章平[1] 

机构地区：[1]江苏大学图形技术研究所,镇江212013

出　　处：《工程图学学报》2004年第3期71-77,共7页Journal of Engineering Graphics

摘　　要：对于给定的平面简单多边形顶点序列,判别多边形方向和顶点凸凹性的传统方法为:先计算多边形相邻边向量的叉积或相邻3个顶点所确定三角形的有向面积,再由叉积或有向面积的符号来确定顶点的凸凹性,使得处理一个顶点需要2次以上的乘法运算。笔者通过边向量斜率的计算和比较,将多边形顶点的凸凹性与边向量的斜率联系起来,并采用“假设-检验”方法,提出了一种快速判别简单多边形方向与顶点凸凹性的新算法,其时间复杂度为)(nO,判别多边形任一顶点凸凹性所需的乘法运算平均不超过1次。该算法原理直观简单,实现容易。实际运行结果表明,该算法速度快捷、运行稳定。For a given simple polygon in plane that all its edge vectors are connected sequentially in clockwise or counterclockwise sense, a feasible approach of identifying convexo-concave vertices of it is to calculate the sign of the cross-products of its adjacent edge vector pairs. This will expend product operators at least 2 times for each vertex. In this paper, a new algorithm, which has time-complexity of )(nO, to rapidly identify the orientation of a arbitrary simple planar polygon and convexity-concavity of its vertices is presented. In the algorithm, the plane is divided into two parts by a line contacted with a vertex of the polygon and 4 configurations of two vertices in the two parts adhered to the vertex can be obtained subsequently. Each configuration gives us a relation between convexity-concavity of vertices of the polygon and the slopes of lines decided by two edge vectors. According to the relation, the convexity-concavity of the vertices can be determined using a predicting and checking method and no more than one times of the product operating is involved in calculation for a vertex.

关 键 词：计算机应用 计算几何 凸凹性判别 边向量比较 简单多边形 算法 

分 类 号：TP301[自动化与计算机技术—计算机系统结构] TP391.72[自动化与计算机技术—计算机科学与技术]