文章目录
- 摘要
- 描述
- 什么是凸多边形，用人话说就是：
- 题解答案
- 题解代码分析
- 题解代码分析
- 为什么用叉积？
- 为什么只关心“符号”，不关心大小？
- 为什么要跳过 `cross == 0`？
- `% n` 是干嘛的？
- 示例测试及结果
- 示例 1：凸多边形
- 示例 2：凹多边形
- 时间复杂度
- 空间复杂度
- 总结
摘要
《凸多边形》是一道看起来很数学，其实很工程的题。
它不考复杂公式，也不要求你会高等几何，真正的核心只有一个：
所有拐弯方向是不是一致的
如果你写过地图路径、UI 绘制、图形编辑器、甚至简单的碰撞检测，这道题的思想你大概率已经用过，只是没意识到它叫“凸多边形判断”。
描述
题目给你一组点points，表示一个多边形的顶点，顶点是按顺序给出的（顺时针或逆时针都可以）。
你的任务是判断：
这个多边形是不是凸多边形
什么是凸多边形，用人话说就是：
- 任意一条边往内看，不会凹进去
- 从任意一个顶点转弯，转向方向始终一致
- 不会出现“左转一下，右转一下”的情况
注意几个隐藏前提：
- 点的数量 ≥ 3
- 不需要考虑自交（题目默认是合法多边形）
- 不要求严格凸（共线允许）
题解答案
这道题的经典解法来自一个非常实用的几何思想：
用叉积判断转向方向
具体思路是：
- 对每三个连续的点
(A, B, C) - 计算向量
AB和BC的叉积 - 记录叉积的符号（正 or 负）
- 只要中途出现方向不一致，立刻返回
false
如果所有拐弯方向都一致，那它一定是凸多边形。
题解代码分析
下面是完整的 Swift 实现，可以直接在 LeetCode 或 Playground 里运行。
classSolution{funcisConvex(_points:[[Int]])->Bool{letn=points.countifn<3{returnfalse}varprevCross=0foriin0..<n{letp0=points[i]letp1=points[(i+1)%n]letp2=points[(i+2)%n]letcross=crossProduct(p0,p1,p2)ifcross!=0{ifprevCross!=0&&cross*prevCross<0{returnfalse}prevCross=cross}}returntrue}privatefunccrossProduct(_a:[Int],_b:[Int],_c:[Int])->Int{letx1=b[0]-a[0]lety1=b[1]-a[1]letx2=c[0]-b[0]lety2=c[1]-b[1]returnx1*y2-y1*x2}}题解代码分析
为什么用叉积？
叉积在二维空间里有一个非常好用的特性：
- 结果 > 0 ：逆时针转（左转）
- 结果 < 0 ：顺时针转（右转）
- 结果 = 0 ：三点共线
也就是说，它本质是在回答一个问题：
从 A → B → C，是往哪边拐？
为什么只关心“符号”，不关心大小？
因为这道题只在乎方向是否一致：
- 全是左转 → 凸
- 全是右转 → 凸
- 左右混着来 → 凹
至于拐得多猛，完全不重要。
为什么要跳过cross == 0？
ifcross!=0{...}这是为了允许共线点的存在。
现实中非常常见，比如：
- UI 边框上多给了几个点
- 地图边界是直线拆成多段
只要方向不反转，就依然是凸的。
% n是干嘛的？
points[(i+1)%n]这是为了让最后一个点能和第一个、第二个点组成一组，形成一个“闭环”。
多边形一定是闭合的，这一步非常关键。
示例测试及结果
示例 1：凸多边形
letsolution=Solution()print(solution.isConvex([[0,0],[0,1],[1,1],[1,0]]))这是一个标准正方形：
- 每一次转向方向一致
- 输出：
true示例 2：凹多边形
print(solution.isConvex([[0,0],[0,10],[10,10],[5,5],[10,0]]))中间有一个点明显往里凹：
- 转向方向发生变化
- 输出：
false时间复杂度
只遍历了一次数组，每次做常数计算：
O(n)空间复杂度
只使用了少量变量，没有额外数据结构：
O(1)总结
《凸多边形》是一道非常值得记住思路的几何题。
它教会你的不是几何公式，而是：
- 如何把“形状判断”转化成“方向一致性判断”
- 如何用一个简单的数学工具（叉积）解决工程问题
- 如何写出既严谨又能容忍真实数据噪声的代码
