凹凸多边形快速识别和智能剖分技术研究

Concave and Convex Polygon Quick Identifying and Smart Meshing Technology

在SAP2000和ETABS中,楼板的添加是一项相当繁琐的工作,如何快速有效地识别平面多边形并对其自动进行剖分是一个亟待解决的问题。文章改进了平面有向图中最小回路的快速搜索算法。在构造出图中各个顶点的关联顶点的逆时针排列序列的基础上,然后按照逆时钟最小转角原则,搜索得到边界顶点序列。再从各个边界顶点出发,按照顺时针最小转角原则,寻找各个回路边,直到返回出发点得到最小回路。文章同时提出了多边形凹凸性判断的矢量叉积法和内角角度计算的矢量点积法,并提出了以min{θmax-θmin}为目标的凹凸多边形的最优剖分方法。

In SAP2000 and ETABS, drawing floors is a very tedious work. How to identify polygon in plane quickly and mesh it automatically is a problem that should be solved. In this paper, the concept of minimum circle in directed planar graph is presented and the fast search algorithm to find all the minimum circles is pro- posed. Firstly, all edges associated with each vertex and their associated vertices are arranged into a set in counterclockwise; and then the boundary vertex sequence is searched in accordance with the principles of smallest counter-clockwise comer. Each vertex on boundary serves as the starting point to search the edge of circle under the rule of the smallest clockwise comer. When coming back to the starting point, a minimum cir- cle is created. This paper also proposes the vector cross product method to determine concave and convex poly- gons and the vector dot product method to calculate the inner angles of polygon. The optimal mesh method of concave and convex polygon targeting on min {θmax-θmin} is also proposed.