女生和32岁大厂程序员交往半年多，最近纠结要不要分手，原因直接给我看懵了：“他不行”…

先把场景脑补一下哈：周五晚上，测完接口正准备下班，产品突然甩过来一句——“给你一堆点，你看看这是不是凸多边形，顺便用 Java 写个算法，后面还要用”。所以这篇就当是你写完代码、顺手记下来的随手笔记，别太学术那种。

啥是凸多边形？

特别简单，你就记一个标准：

对于一个多边形里的任意两点，连一条线，这条线要“完全待在”多边形里面，那它就是凸的。

反过来，如果你画一条线会戳出多边形外面一截，那就是凹的。 再直白一点：凸多边形的外形不会有“内凹进去的小坑”。

编程上我们一般有一串点 P0, P1, P2, ..., Pn-1，按顺时针或逆时针连起来，就是一个多边形。问题就是：这串点对应的这玩意儿，到底凸不凸？

看拐弯方向是不是一直一样

几何里有个很好用的小工具：叉积（cross product）。 你不用推导公式，直接记结论就行：

对三个点 A、B、C，看向量 AB 和 BC 的叉积：

• 叉积 > 0：一个方向拐（比如统一逆时针）
• 叉积 < 0：反方向拐（顺时针）
• 叉积 = 0：三点共线，不拐

如果一个简单多边形是凸的，那你沿着边走一圈，所有“拐弯方向”要么全是左转，要么全是右转，不能中途“反悔”一下。

所以算法就变成：

1. 遍历每个点 i，取三点：prev = i-1、curr = i、next = i+1（注意用取模，首尾要连起来）。
2. 计算 cross((curr - prev), (next - curr))。
3. 记录第一个非 0 的叉积符号，后面每次出现非 0 的，符号必须跟它一样，否则就不是凸多边形。

时间复杂度 O(n)，一圈扫完就行。

直接上代码，写得口语一点，方便你改：

publicclassConvexPolygonChecker{

// 简单的点结构
staticclassPoint{
long x;
long y;
        Point(long x, long y) {
this.x = x;
this.y = y;
        }
    }

// 计算叉积： (b - a) × (c - b)
privatestaticlongcross(Point a, Point b, Point c){
long abx = b.x - a.x;
long aby = b.y - a.y;
long bcx = c.x - b.x;
long bcy = c.y - b.y;
return abx * bcy - aby * bcx;
    }

// 判断一串点是否构成凸多边形（假设点按顺/逆时针给好，且不自交）
publicstaticbooleanisConvex(List<Point> points){
int n = points.size();
if (n < 3) returnfalse; // 三个点以下没法叫多边形

int sign = 0; // 记录第一次非 0 的叉积符号

for (int i = 0; i < n; i++) {
            Point a = points.get((i - 1 + n) % n);
            Point b = points.get(i);
            Point c = points.get((i + 1) % n);

long crossVal = cross(a, b, c);
if (crossVal == 0) {
// 共线就先忽略，看后面
continue;
            }

int currSign = crossVal > 0 ? 1 : -1;
if (sign == 0) {
                sign = currSign; // 第一次发现拐弯方向
            } elseif (sign != currSign) {
// 出现反方向拐弯，必然不是凸多边形
returnfalse;
            }
        }

// 如果全是共线（degenerate）那算不算凸你可以按题意决定
return sign != 0;
    }
}

几个小点随手说一下：

• 坐标我用 long，防止大数据乘法爆 int。
• 如果所有点共线（sign 一直是 0），理论上这是个“退化多边形”，有的题会说不是多边形，有的会当成特殊凸多边形，根据题目要求改 return。
• 前提是点已经按顺时针或逆时针排好了；如果是乱序点，那是凸包问题，得先做一遍凸包再说。

点在凸多边形内判断

既然都聊到凸多边形了，面试常见搭配还有一句：“再顺便写下点在凸多边形内的判断呗”。

凸多边形就有个好处：判断是不是在里面，可以用“方向一致”这套逻辑再用一次。 思路很像刚才：

• 固定一个点 P；
• 对每条边 (Vi, V(i+1))，算叉积 cross(Vi, V(i+1), P)；
• 如果所有叉积都同号（允许等于 0，说明在边上），就认为在多边形内。

简化版代码大概这样：

publicstaticbooleanpointInConvexPolygon(List<Point> poly, Point p){
int n = poly.size();
int sign = 0;

for (int i = 0; i < n; i++) {
        Point a = poly.get(i);
        Point b = poly.get((i + 1) % n);
long crossVal = cross(a, b, p);
if (crossVal == 0) continue;

int currSign = crossVal > 0 ? 1 : -1;
if (sign == 0) {
            sign = currSign;
        } elseif (sign != currSign) {
returnfalse;
        }
    }
returntrue; // 在内部或边上
}

很多 OJ 会把这两个题一起考：先判断是不是凸多边形，再判断一堆点是不是在里面，代码直接复用叉积就行。

乱序点怎么变成凸多边形（凸包）

现实里更多是这样一个需求：给你一堆散点，先把“外壳”找出来——这层外壳其实就是一个凸多边形，这个操作就叫求凸包。

常见做法有 Graham Scan、Andrew 算法，核心都是：

1. 先把点按 x、y 排个序；
2. 从左到右构建下凸壳，每加一个点就看“是不是反方向拐弯”，如果是就把中间那个点弹掉；
3. 再从右到左构建上凸壳；
4. 拼在一起就是一圈凸多边形点。

你会发现，还是那句老话：全靠叉积看拐弯方向，套路非常统一。

Java 写一遍也不难，就是排序 + 一个栈维护，篇幅就不展开写全代码了，你要是后面真要用，我可以帮你把凸包那段也补全成工具类，直接丢项目里用。

大概就这样，凸多边形相关的几个常用算法： 判断是不是凸、点是否在凸多边形内、以及顺嘴提了一下如何从一堆点“长出”一个凸多边形。 剩下就是老三件套：多测几组数据、注意顺逆时针、注意 long 溢出，就差不多可以愉快交差了。

-END-

我为大家打造了一份RPA教程，完全免费：songshuhezi.com/rpa.html