【Python】判断多边形的形状为凸多边形还是凹多边形

清疚 2022-01-15 13:55 452阅读 0赞

> **凸多边形**是一个内部为凸集的简单多边形。凸多边形（Convex Polygon）指如果把一个多边形的所有边中，任意一条边向两方无限延长成为一直线时，**其他各边都在此直线的同旁**，那么这个多边形就叫做凸多边形，其内角应该全不是优角，任意两个顶点间的线段位于多边形的内部或边上。

判断是否为凸多边形的关键在于以一边及其延长线为参照，其他各边是否在此边同旁，也可以转化为其他顶点是否位于此边同旁。观察下图可知，图左的多边形无论是哪两个顶点组成一条边，其余顶点要么都在该边及其延长线的上方，要么都在该边及其延长线的下方，即始终位于同旁，因此可以判断该多边形为凸多边形。而与之形成对比的图右中，则存在顶点位于边及其延长线两侧的情况，图中红圈和绿圈标记的顶点位于直线两侧，因此该多边形为凹多边形。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWR1XzI2NjQ2MTI5_size_16_color_FFFFFF_t_70_pic_center]  
基于上述分析，我们可以总结出判断凸多边形的思路：

1.  相邻两个顶点组成一条直线，得到该条直线的表达式
2.  计算组成顶点外的其余顶点到1中直线的距离
3.  判断2中的所有距离是否均为相同符号，若为相同符号则为凸多边形，否则为凹多边形

**需要特别注意的是**，构成多边形的点要按照顺时针或者逆时针的顺序依次排列，其顺序不能有跳跃，否则会造成误判。因此在输入多边形所有顶点坐标前，必须先确保其定点顺序依次排列。

''' 计算直线表达式 :param vertex1: 前一个顶点 :param vertex2: 后一个顶点 :return (type, param): 返回直线的类别及其描述参数 '''
    def kb(vertex1, vertex2):
        x1 = vertex1[0]
        y1 = vertex1[1]
        x2 = vertex2[0]
        y2 = vertex2[1]
        
        if x1==x2:
            return (0, x1)      # 0-垂直直线
        if y1==y2:              
            return (1, y1)      # 1-水平直线
        else:
            k = (y1-y2)/(x1-x2)
            b = y1 - k*x1
            return (2, k, b)    # 2-倾斜直线
    
    ''' 判断是否为凸多边形 :param vertexes: 构成多边形的所有顶点坐标列表，如[[0，0], [50, 0], [0, 50]] :return convex: 布尔类型，为True说明该多边形为凸多边形，否则为凹多边形 '''
    def isConvex(vertexes):
        # 默认为凸多边形
        convex = True   
        
        # 多边形至少包含三个顶点
        l = len(vertexes)
        if l<3:
            raise ValueError("多边形至少包含三个顶点！")
        
        # 对每两个点组成的直线做判断
        for i in range(l):
            pre = i
            nex = (i+1)%l
            
            # 得到直线
            line = kb(vertexes[pre], vertexes[nex])
            
            # 计算所有点和直线的距离（可能为正也可能为负）
            if line[0]==0:
                offset = [vertex[0]-vertexes[pre][0] for vertex in vertexes]
            elif line[0]==1:
                offset = [vertex[1]-vertexes[pre][1] for vertex in vertexes]
            else:
                k, b = line[1], line[2]
                offset = [k*vertex[0]+b-vertex[1] for vertex in vertexes]
            
            # 计算两两距离的乘积，如果出现负数则存在两个点位于直线两侧，因此为凹多边形
            for o in offset:
                for s in offset:
                    if o*s<0:
                        convex = False
                        break
                if convex==False:
                    break
                        
            if convex==False:
                break
                
    	# 打印判断结果
        if convex==True:
            print("该多边形为凸多边形！")
        else:
            print("该多边形为凹多边形！")
        
        return convex

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWR1XzI2NjQ2MTI5_size_16_color_FFFFFF_t_70_pic_center]: /images/20220115/58a25c9d2afc4eca9224854be7f50e28.png