二面体群作用下简单多边形的分类

A Classification Method of Simple Polygons Based on Dihedral Group

针对简单多边形的分类问题,将对称情况看成是相同类别进行分类来简化分类数,提出一种分类方法.首先分析简单多边形顶点的凹凸性,根据简单多边形顶点处凸点和凹点的分布情况,定义了简单多边形的标记矩阵;然后利用标记矩阵将简单多边形的分类问题归结为二面体群作用在状态集(全体标记矩阵组成的集合)上的轨道划分问题;最后利用熟知的Pólya计数定理求解轨道的个数,并给出了新的分类公式.实验结果表明,当简单多边形边数为6时,采用文中方法的分类数小于原来分类数,并且随着边数的增大,这种差距逐渐变大.

In this paper, a new classification method of simple polygons is presented. Being different from the old method, we take the polygons and their mirror reflections into one class in the new classification method, which will reduce the number of classification. The process is as follows. First, the concave-convex property of simple polygons is considered in order to establish an identification matrix which is used to represent a simple polygon. Then we transform the classification problem of simple polygons into computing the number of orbits when the dihedral group acts on the state set that consists of all of the identification matrices. Finally, the number of group obits can be solved by Polya enumeration theorem. The tables in the end of paper show that the classification number computed by the new classification method is less than the one computed by the old method when the sides of a polygon is 6. Also, with the increase of the number of sides, the gap between the two classification numbers is gradually larger.