LeetCode 469 凸多边形

摘要

《凸多边形》是一道看起来很数学，其实很工程的题。

它不考复杂公式，也不要求你会高等几何，真正的核心只有一个：

所有拐弯方向是不是一致的

如果你写过地图路径、UI 绘制、图形编辑器、甚至简单的碰撞检测，这道题的思想你大概率已经用过，只是没意识到它叫“凸多边形判断”。

描述

题目给你一组点points，表示一个多边形的顶点，顶点是按顺序给出的（顺时针或逆时针都可以）。

你的任务是判断：

这个多边形是不是凸多边形

什么是凸多边形，用人话说就是：

• 任意一条边往内看，不会凹进去
• 从任意一个顶点转弯，转向方向始终一致
• 不会出现“左转一下，右转一下”的情况

注意几个隐藏前提：

• 点的数量 ≥ 3
• 不需要考虑自交（题目默认是合法多边形）
• 不要求严格凸（共线允许）

题解答案

这道题的经典解法来自一个非常实用的几何思想：

用叉积判断转向方向

具体思路是：

1. 对每三个连续的点(A, B, C)
2. 计算向量AB和BC的叉积
3. 记录叉积的符号（正 or 负）
4. 只要中途出现方向不一致，立刻返回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)

总结

《凸多边形》是一道非常值得记住思路的几何题。

它教会你的不是几何公式，而是：

• 如何把“形状判断”转化成“方向一致性判断”
• 如何用一个简单的数学工具（叉积）解决工程问题
• 如何写出既严谨又能容忍真实数据噪声的代码