469. 凸多边形

Difficulty
Medium
Tags
数学
URL
https://leetcode-cn.com/problems/convex-polygon/
Star
给定 X-Y 平面上的一组点 points ，其中 points[i] = [xi, yi] 。这些点按顺序连成一个多边形。
如果该多边形为 凸 多边形（凸多边形的定义）则返回 true ，否则返回 false 。
你可以假设由给定点构成的多边形总是一个 简单的多边形（简单多边形的定义）。换句话说，我们要保证每个顶点处恰好是两条边的汇合点，并且这些边 互不相交 。
示例 1：
notion imagenotion image
输入: points = [[0,0],[0,5],[5,5],[5,0]]
输出: true
示例 2：
notion imagenotion image
输入: points = [[0,0],[0,10],[10,10],[10,0],[5,5]]
输出: false
提示:
  • 3 <= points.length <= 104
  • points[i].length == 2
  • -104 <= xi, yi <= 104
  • 所有点都 不同

法 1 凸包问题

思路
🧵
凸包问题 的简化版，只需要判断挨着的两条边的旋转方向是否一致
题解
class Solution:
    def isConvex(self, points: List[List[int]]) -> bool:
        if len(points)  <= 3:
            return True
    
        flag = None
        # 注意这里需要把最后两个点也判断上去
        for i in range(2, len(points)+2):
            i = i % len(points)
            cur_roat = self.cross(points, i-2, i-1, i)
            
            if flag is None or flag == 0 and cur_roat:
                flag = cur_roat
            if flag * cur_roat < 0:
                return False

        return True
                
    
    def cross(self, points, i, j, k):
        """边 ij 边ik 的旋转角度
        """
        edge_1 = [points[j][0] - points[i][0], points[j][1]- points[i][1]]
        edge_2 = [points[k][0] - points[i][0], points[k][1]- points[i][1]]

        return edge_1[0] * edge_2[1] - edge_1[1] * edge_2[0]