我拿到这份“酷家乐2020校园招聘-几何算法A卷”的时候第一反应不是翻题而是去想为什么一家做家居云设计的公司校招笔试要放这么多几何题进去。后来再想就通了——酷家乐的核心业务是让用户在浏览器里完成户型绘制、硬装软装布置、实时渲染这些功能落到代码层面几乎每一步都在跟点、线、面、体的计算打交道。你拖一扇门、转一个沙发、判断一堵墙能不能被相机看到底层全是几何算法。所以这份卷子考的不是冷门数学而是这家公司日常业务里真的会用到的东西。这篇内容我打算直接从考点拆解、题型分类、完整解题流程、踩坑经验四个角度来讲把几何算法题背后“为什么这么考”的逻辑捋清楚同时给出可以直接复用的核心代码思路。不管你是正在备战校招算法岗还是已经在做图形学、CAD、渲染相关开发这份拆解都值得看一看。1. 试卷背后的业务逻辑几何算法为什么是核心考点1.1 家居云设计场景里的几何计算比你想象中更底层很多人对酷家乐的理解是“一个可以在线画户型图的网站”但真正产品级的云设计工具复杂度比想象中大得多。用户在页面上画一面墙底层其实是在二维平面内生成一条有厚度的线段拖拽一件沙发底层是检测这个多边形是否与墙体、其他家具发生碰撞调整相机视角实时预览底层是视锥体裁剪和遮挡关系判断甚至吊顶、地砖的铺贴方案都涉及多边形分割和区域填充。这些场景有一个共同点它们都是在“几何元素”之上做空间推理。几何算法如果写得不够稳就会出现家具穿模、墙体缝隙、旋转后位置错乱这些肉眼可见的Bug。所以校招卷子里的几何题本质上是在筛选那些具备“空间思维严谨边界处理”能力的人而不只是会背公式的人。我后来跟业内做图形引擎的朋友聊过他说过一句话我特别认同“图形学的面试里几何算法好不好直接决定这个人能不能做渲染引擎或CAD内核。”原因很简单——几何算法是整个上层业务的地基地基不稳后面所有功能都是白搭。1.2 校招几何算法卷的能力考察矩阵一份几何算法试卷通常不会只考单一知识点而是通过几道题组合起来全面考察候选人的基础扎实度、代码实现能力和工程意识。根据我对同类公司笔试的观察可以整理成一张能力矩阵能力维度典型考查方式考察意图向量与基础计算判断点与线段的位置关系、求向量夹角看你对最基础运算是否形成肌肉记忆多边形处理求多边形面积、判断点是否在多边形内、凸包看你对平面几何经典问题的理解深度碰撞检测矩形相交、圆与矩形碰撞、线段相交看你对实际业务场景中空间关系的敏感度三维扩展思维平面法向量、点到平面距离、包围盒计算看你能不能从二维平滑过渡到三维数值稳定性浮点精度、共线处理、退化情况看你的工程经验是否吃过浮点误差的亏这套矩阵其实也是很多图形学岗位通用的考察框架。如果你能把每一条都吃透那么不管题目怎么变核心思路是一致的。2. 高频题型逐类拆解从原理到代码一次讲透2.1 向量叉积与点、线、面的位置关系几何算法里最基础也最常用的运算就是向量叉积。二维平面上两个向量的叉积结果是一个标量它的绝对值等于两个向量围成的平行四边形的面积符号则表示第二个向量相对第一个向量的旋转方向。我们用叉积可以做三件高频的事判断点在线段的哪一侧、判断两条线段是否相交、求多边形面积。其中判断点在线段哪一侧最简单// 返回向量 ab 与向量 ap 的叉积 // 大于0p在ab左侧小于0p在ab右侧等于0三点共线 double cross(const Point a, const Point b, const Point p) { return (b.x - a.x) * (p.y - a.y) - (b.y - a.y) * (p.x - a.x); }这里有个新手很容易忽视的细节屏幕坐标系和数学坐标系的 y 轴方向是相反的如果不统一坐标朝向叉积的正负含义会颠倒。实际笔试时我习惯先注释清楚“当前坐标系 y 轴向上/向下”再写后续逻辑这样能避免很多定位问题。线段相交的判断稍微复杂一点但在业务中非常常见比如判断新画的墙是否与已有墙相交。标准做法是“快速排斥实验 跨立实验”两步快速排斥实验先检查两条线段的外包矩形是否相交如果矩形都不相交线段必然不相交可以直接返回 false省掉后续计算。跨立实验判断每条线段的两个端点是否分别位于另一条线段的两侧用前面提到的叉积符号来判断。两步缺一不可。快速排斥负责剪枝跨立负责精确判定尤其是处理共线、端点重合这类边界情况时只做跨立实验很容易漏判。2.2 多边形面积、包含判定与凸包三维业务的地基多边形相关的题几乎是几何算法笔试的必考题。最经典的是用鞋带公式求多边形面积double polygonArea(const vectorPoint pts) { double area 0.0; int n pts.size(); for (int i 0; i n; i) { int j (i 1) % n; area pts[i].x * pts[j].y; area - pts[j].x * pts[i].y; } return fabs(area) / 2.0; }注意这里返回的是绝对值因为顶点的环绕方向顺时针或逆时针会导致面积正负不同。很多题目会在这个基础上加一个条件比如“输入点是顺时针排列的求面积”——这时就要去掉 fabs根据正负号判断顶点顺序是否正确反向的话甚至需要把多边形反转否则后续计算全部出错。点是否在多边形内常用的有射线法和射线转角法射线法实现更简单也更容易在笔试中快速写出正确代码。思路是从待判断点向右发射一条水平射线统计它与多边形边的交点数奇数则在多边形内部偶数则在外部。写的时候特别要注意交点恰好经过多边形顶点的情况否则计数会出错常规做法是对这种情况做偏移处理或者规定只有“边的上端点被穿过”才算一次相交。凸包相对难一些但高频出现因为很多复杂几何问题可以先用凸包简化数据。Graham扫描算法是推荐的做法先找到最左下角的点作为基准点然后按极角排序再用栈维护一个“逆时针转向”的凸包边界。核心代码不复杂但排序的稳定性、共线点的取舍都是容易被扣分的点。2.3 碰撞检测与空间关系判断摆放场景的直接需求如果你在酷家乐里拖拽一个柜子系统需要实时反馈“这个位置能不能放”这就是典型的碰撞检测问题。笔试里常考的主要是二维空间里的几类轴对齐矩形相交判断两个矩形是否重叠条件是max(x1_min, x2_min) min(x1_max, x2_max)且max(y1_min, y2_min) min(y1_max, y2_max)。圆与矩形碰撞只需要先找到矩形上离圆心最近的点再计算该点与圆心的距离是否小于半径。这个思路可以避免分情况讨论代码量小且不易漏边界。线段与圆相交先求圆心到线段的投影点再判断投影点是否在线段范围内最后比较距离。投影点不在线段上时要退化成判断圆心到两个端点的距离。这些题目看起来简单但实际笔试里通过率并不高原因主要是边界条件考虑不全。比如矩形相交时两个矩形边刚好重合算不算相交圆和矩形相切算不算碰撞不同题目对边界定义不同开卷前最好先确认清楚或者直接在代码注释里说明自己的定义这样即使判题不通过面试官也能看到你的思考过程。2.4 三维扩展考点从平面几何到空间几何的平滑过渡校招笔试不会考得太深但通常会有一两道题把维度从二维扩展到三维考验你的空间想象力。最常见的是已知平面法向量和平面上一点求点到平面的距离判断一个点是否在长方体内通常用AABB轴对齐包围盒判断求两条三维线段的最近距离或者判断直线与三角形是否相交射线与三角形求交。这类题目的共同点是核心仍然是二维几何那套“向量 叉积 点积”的组合拳只是多了一个维度。如果你把向量运算的基本功打扎实了三维题并不会更可怕。我在实际业务里遇到最多的场景是“家具能不能放进这个房间”这本质上是把三维问题降到二维平面判断地面投影再加上高度判断。如果投影不碰撞高度也足够那就可以放。所以不要把三维想象成多高深的东西它只是多算了一维而已。3. 实操过程与核心环节实现用一道模拟题走完完整流程3.1 题目设定判断旋转后的矩形家具能否放入多边形房间我拿一个和酷家乐业务高度相关的题目做完整演示你可以把它当作A卷里“综合应用题”的模拟版本现有一个房间其地面轮廓由多边形表示顶点按逆时针排列无自交有一件矩形家具长和宽为给定值可以旋转任意角度。请判断是否存在一个位置和角度使得家具完全位于房间内部且不会碰到房间边界。这道题综合了旋转、碰撞检测、点包含、多边形相交等多个知识点非常接近现实场景。3.2 解题思路与核心实现我采用的方案是“离散角度采样 几何合法性检查”。思路是先枚举家具的旋转角度把矩形转换成四个顶点再检查四个顶点是否都在房间内部最后检查矩形四条边是否跟房间边界相交。如果所有顶点都在内部且边不相交就认为该角度下存在合法摆放位置。为什么要枚举角度而不是直接解方程因为“找到可行位置”本身是一个连续优化问题笔试环境下直接求解析解非常复杂离散采样配合足够细的步长已经能在绝大多数情况下得到正确答案而且代码更简单、不容易错。检查顶点是否在多边形内用前面讲过的射线法。检查矩形边是否与房间边界相交用前面讲过的线段相交判断。核心代码可以这样组织bool canPlace(const Polygon room, double w, double h, double angleStep) { for (double angle 0; angle 360; angle angleStep) { vectorPoint rect getRectCorners(w, h, angle); bool inside true; for (auto p : rect) { if (!pointInPolygon(p, room)) { inside false; break; } } if (!inside) continue; bool noIntersect true; for (int i 0; i 4; i) { Segment s1 {rect[i], rect[(i 1) % 4]}; for (int j 0; j room.size(); j) { Segment s2 {room[j], room[(j 1) % room.size()]}; if (segmentIntersect(s1, s2)) { noIntersect false; break; } } if (!noIntersect) break; } if (inside noIntersect) return true; } return false; }这个代码看起来不长但每一行都有讲究。getRectCorners要处理矩形的旋转中心是几何中心还是某个角点结果完全不同segmentIntersect里快速排斥实验的线段细分处理直接决定相交判断的准确性pointInPolygon对顶点在多边形边上的情况也需要提前约定算内还是算外。3.3 测试用例设计与边界情况逐项验证很多同学笔试时容易忽略测试这一步但恰恰是边界用例最能区分高下。我按下面几类用例去验证上面的代码房间是标准的矩形家具刚好比房间小一点点旋转后应当可以放进去。房间是L形家具放在拐角处四个顶点有些在房间内、有些在房间外应当返回不能放置。家具的对角线长度大于房间的对角线但旋转后可能卡在角落这种情况要返回 false。房间顶点顺序不小心传成顺时针pointInPolygon可能计算出完全相反的结果。我实测过的结果是角度步长 1 度时普通房间和家具的判定结果已经足够稳定但如果房间轮廓特别复杂比如有很多凹角建议把步长缩到 0.5 度代价是运行时间翻倍笔试时间充裕时可以用。更精确的做法是改成连续优化比如用三分搜索找最优角度但那对比赛来说有点超纲了。4. 常见问题与排查技巧实录这些坑我替你先踩了4.1 浮点数精度问题第一杀手的处理方式几何算法里最常见的Bug来源就是浮点数比较。直接写a b判断两个 double 是否相等十次有九次会出错因为浮点数的二进制表示本身就有误差。比如两个理论上相等的点经过一系列矩阵运算后坐标值可能是 1.0000000000000002 和 0.9999999999999999。我现在的习惯是全局定义一个极小量EPS所有判断都用区间判断替代等值判断const double EPS 1e-9; bool dcmp(double x) { return fabs(x) EPS; }叉积判断共线时别用cross 0要用fabs(cross) EPS。点积为零判断垂直时同理。这个习惯在笔试中可能只影响一两个用例但真实业务中浮点误差积累到一定程度会直接导致渲染画面出现裂缝做好精度控制是基本功。4.2 边界条件遗漏顶点重合、共线、退化多边形另一个高频问题是对退化情况的处理。当多边形的连续三个顶点共线时鞋带公式依然能算出面积但算出来的面积不一定是预期的那个值当两条线段共线且部分重叠时快速排斥实验能通过跨立实验会因为叉积为零出现误判当房间多边形顶点按顺序排好但首尾重复时循环遍历会多算一条边。我总结的处理原则是在几何函数入口处先做一次“参数合法性校验”把退化输入统一拦截掉。比如多边形至少要有3个不共线的点、线段长度要大于EPS、矩形长宽必须大于零。这类防御性代码不会降低性能但能省掉大量定位时间。4.3 从TLE到AC的优化路径几何题的性能陷阱几何题普遍数据量不大但也存在需要优化的情况。比如极角排序里的atan2调用比较耗时数据量大时可以考虑用象限排序替代点在多边形内判断如果要执行几万次可以先用 AABB 做一次粗筛只对包围盒重合的图形做精确判断碰撞检测里最耗时的部分往往是线段相交可以先用空间网格或四叉树分桶减少不必要的两两判断。笔试阶段不会要求你用特别复杂的数据结构但至少要能想到“先粗筛再精判”这个思路。这也是面试官考察的点之一——软件工程意识而不仅仅是会写算法。4.4 画图调试法比打印日志高效十倍几何题的调试方式和普通业务代码不太一样。打印一堆坐标数字人眼很难判断哪里出错更好的做法是把输入输出可视化出来。笔试环境一般没有图形界面我会在本地用 Python 写一个小脚本把点、线段、多边形画到一张图上再用同样的数据去跑 C 的实现对比结果。这招在“多边形包含判定”和“线段相交判断”这两类题上特别有用。有一次我遇到一个判断结果恰好反过来的情况画图之后立刻发现是顶点顺序问题——输入数据是顺时针但我的射线法默认按逆时针处理。这种问题光靠读代码很难一眼看出来但可视化之后一目了然。5. 个人体会几何算法怎么复习才真正有效笔试刷题和实际业务有一个很大的区别刷题时的用例都是精心构造好的而业务里的数据永远是脏的、乱的、带噪声的。我见过不少算法功底不错的同学一到项目里写几何计算就开始懵原因就是习惯了“输入保证合法”的题目不知道真实数据里什么鬼情况都有。我个人建议的复习路径是先花一周把向量叉积、点积、线段相交、点在多边形内、凸包、鞋带公式这六个基础点彻底吃透做到不用查资料也能写出正确代码然后专门找十道以上带“边界情况”的几何题练习训练自己对退化输入的敏感度最后再来模拟这种“旋转 碰撞 包含”的综合题把多个基础点组合起来。这类笔试里还会有一个隐藏考点代码的鲁棒性。面试官不一定只看你最后答案对不对还会看你有没有考虑到浮点误差、退化输入、角度旋转方向这些细节。你在代码注释里写清楚自己的假设和取舍比硬写出一个奇慢无比但“看似完美”的解法要加分得多。还有一个很现实的建议复习几何算法时多用画图的方式去推导别只对着公式空想。脑子里能画出空间结构代码实现自然就顺了。这份卷子背后的业务场景——家居设计、云渲染、CAD——决定了它就是需要这种“能想象空间关系”的人这点在面试时也会通过追问暴露出来。