基于拓扑映射的多边形顶点凸凹判别算法  

Determining Convexo-Concave Vertices of Polygon By Topological Mapping

作　　者：吴春福[1] 陆国栋[1] 张树有[1] 

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

出　　处：《计算机辅助设计与图形学学报》2002年第9期810-814,共5页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家自然科学基金 (5 0 10 60 14 )资助

摘　　要：通过拓扑映射 ,多边形顶点凸凹判别可以转化为映射点在射影直线上的位置关系问题 .首先求得相邻边在两条射影直线上的映射点 ,基于一般映射点归纳得到顶点凸凹判别的 4条规则 ;然后将两条射影直线上的映射点归结为一条射影直线 ,从而得到更有效的映射点求取方法 ,顶点凸凹判别规则统一为两条 ;进一步考虑非固有映射点的求取方法 ,提高了算法的稳定性 .实验结果表明 ,该算法实现简单、速度快。Given a simple polygon, all its edge vectors are connected sequentially in clock wise or counterclockwise sense. A feasible approach of determining the convexity or concavity of a vertex is to compute the sign of the cross product of its two adjacent edge vectors. In our approach, a circle of certain radius is constructed surrounding each vertex and compute the intersection points of every two adjacent edges with a pair of offset lines parallel to the X axis and located at both sides of each vertex. Comparing the X coordinates of these two intersection points immediately predicts the convexity or concavity of a vertex, computing the X coordinates of line line intersections points is quicker than computing the cross product of two vectors.

关 键 词：拓扑映射 多边形 顶点凸凹判别算法 映射点 射影直线 计算机图形学 

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