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

Determining Convexo-Concave Vertices of Polygon By Topological Mapping

通过拓扑映射 ,多边形顶点凸凹判别可以转化为映射点在射影直线上的位置关系问题 .首先求得相邻边在两条射影直线上的映射点 ,基于一般映射点归纳得到顶点凸凹判别的 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.