开头≥200字每年的秋招季都会有一批“看着像小公司、实际上技术题难出天际”的存在酷家乐绝对算其中一个。作为一家做云设计平台的公司它2020校招的几何算法A卷在圈子里流传度相当高不是因为题目有多偏多怪而是它把“家装设计”这个场景里的几何问题浓缩成了一份非常典型的算法考卷。凡是投过图形学、CAD、BIM、渲染相关岗位的同学多半都听过这份卷子的名号。这份卷子考察的东西并不玄乎核心就是二维平面几何和三维空间的表达、计算、判交与变换。但它牛就牛在每道题背后都对应着酷家乐实际业务里真实发生过的场景户型图的墙体识别、橱柜拉手在转角处的碰撞、吊顶与灯槽的路径计算、水电管道在墙体里的走向排布。换句话说这不是一份纯刷LeetCode能搞定的卷子它要求你既会推公式又能把公式落到工程代码里。这篇文章我会把这份“几何算法A卷”的考察方向、背后的业务逻辑、每一类题型的解题思路以及实际考场上的踩坑经验全部拆开讲一遍。文章面向两类人一是准备投酷家乐或其他云设计、CAD、渲染方向岗位的应届生二是对计算几何感兴趣、想知道这些算法在真实产品里怎么落地的开发者。看完你会明白这份卷子考的其实不只是几何而是你能否用数学解决工程问题的综合能力。1. 为什么一家云设计平台会拿几何算法当校招考题想搞明白这份卷子得先搞明白酷家乐是家什么公司。它做的是“云设计平台”也就是让用户在浏览器里完成户型绘制、室内设计、效果图渲染和施工图输出。这个产品形态决定了它的技术栈里几何计算不是某一个模块的事情而是渗透到了产品的每一个角落。1.1 云设计场景里的几何问题无处不在我这里随便列几个酷家乐产品里真实存在的功能你感受一下用户画户型图的时候墙体是一个一个矩形拼出来的但两堵墙相交之后墙角处会出现一条45度的斜切缝系统要把这个缝自动补平。这是典型的“多边形并集/布尔运算”问题。设计师把一个柜子拖进房间里系统要自动判断柜子有没有穿模、是不是贴着墙、离门有没有留出开启空间。这是“碰撞检测”和“最小距离计算”。渲染效果图的时候阳光透过窗户照进来光斑要落在木地板上并随着太阳角度变化而移动。这是“射线与平面求交”的实时计算。水电布线的时候管道要从配电箱走到各个插座走线路径要避开梁柱、沿着墙根走。这是“最短路径障碍物规避”的组合问题。这些功能有一个共同点它们都发生在“三维空间里、但最终呈现在二维屏幕和几何数据上”的交叉地带。而校招笔试不可能让你现场做一整套产品功能出来所以出题人把里面最核心的数学内核抽出来变成了试卷上那七八道纯几何题。你把这些题做对了基本上就证明你具备了处理上述真实场景的数学功底和编码能力。1.2 酷家乐对几何算法岗位的真实能力画像从这份A卷的题型结构来看酷家乐对校招候选人的能力预期是很具体的。它不指望你是一个成熟的图形学大佬但希望你具备三样东西第一扎实的高中/大学几何基础。向量运算、点线关系、多边形性质这些不能打磕巴。第二把几何问题“程序化”的能力。给你一个几何描述你得能想到用哪种数据结构去表达、用哪个公式去计算、边界条件是什么。第三空间想象力。题目会给你一个三维场景的文字描述你需要在脑子里把它转成坐标系和方程再转成代码逻辑。这三样东西对应到试卷上就是不同分值的题目梯度。基础题考向量和点线关系中等题考多边形和面积计算难题考三维变换和射线求交。整张卷子下来不会出现“偏题怪题”但它会把简单问题藏在复杂的场景描述里考察你是不是真的理解了本质而不是只会套公式。2. 拆解几何算法笔试的核心考察范围我根据当年流出来的题目回忆版和多个参与过笔试的同学反馈把这份A卷的考察范围大致归成了六个方向。这六个方向不仅适用于酷家乐也适用于几乎所有云设计、CAD、游戏引擎方向的算法岗笔试。2.1 二维基础向量与点线关系的判断这一块是整张卷子的地基。向量加减、点积叉积、两点间距离、点到直线的距离、判断点在直线哪一侧……这些知识本身不复杂但出题人会换着花样把它们组合起来。举个例子试卷里有一道很经典的题给定一个点P和一个由A、B两点构成的线段判断P在线段的左侧、右侧还是线上。很多人第一反应是“用斜率比较”但这在工程上是错误的做法因为斜率在垂直线段上会变成无穷大直接除以零崩溃。正确的做法是用叉积符号来判断AB B - A AP P - A cross AB.x * AP.y - AB.y * AP.x如果cross大于0P在AB左侧小于0则在右侧等于0说明共线。但共线之后还要再判断P是否真的落在线段范围内而不是在延长线上这就需要再加一步“点的包围盒判断”。这题看起来简单但能把“叉积判向包围盒判段”写完整、边界条件处理干净的人其实不到一半。另一个高频基础题是“判断两个线段是否相交”。标准做法是“跨立实验”对线段AB和CD先判断A、B是否在CD两侧再判断C、D是否在AB两侧。但这里有个非常隐蔽的坑当两条线段共线时跨立实验会失效需要额外处理。很多人在这一步没注意导致特殊情况下判错。我见过大量候选人在这种“简单题”上扣分非常可惜。2.2 多边形操作面积、凸包与点在多边形内多边形相关的题目在A卷里占了相当大的比重因为它与户型图编辑、区域划分的业务强相关。面积计算是最基本的。给定一个顶点按顺序排列的多边形求它的面积。标准做法是用“鞋带公式”也叫叉积坐标公式area 0 for i in range(n): j (i 1) % n area polygon[i].x * polygon[j].y area - polygon[j].x * polygon[i].y area abs(area) / 2这个公式的原理是“把多边形分割成若干个三角形然后求有向面积之和的一半”。理解这个原理比背公式重要因为它顺便解释了另一个问题为什么顶点是顺时针还是逆时针会影响area的正负号但取绝对值后结果一样。凸包的考察方式通常是“给定一堆点求包含所有点的最小凸多边形”。经典解法有Graham扫描法和Andrew单调链法。坦白说这道题是整张卷子里最“计算机科学”的题因为它不仅考几何还考排序和栈的应用。Andrew算法的手写模板我建议每个候选人都提前备好毕竟考场上现推容易出bug。“判断点是否在多边形内”也是常客。射线法是最常用的从点P向右发一条水平射线统计它与多边形边的交点数奇数是内部偶数是外部。但工程里的坑在于当射线恰好经过多边形的顶点时需要特殊处理“顶点重叠计数”的问题。我的处理技巧是“约定射线穿过顶点时只统计边的一侧比如只统计y坐标递增方向经过该顶点的边”这样能稳定避免歧义。2.3 三维扩展空间几何体与变换如果说二维题是热身那三维题目就是分水岭了。酷家乐毕竟是云设计平台三维空间的处理能力是核心中的核心。三维向量的叉积、点积、混合积是基础但更关键的是三维图形的表达和变换。试卷里常见的题型包括给定三维空间中的一个三角形和一个点判断点是否在三角形上给定一条射线与一个平面求交点坐标给定一个模型变换矩阵旋转平移求一个点在变换后的新坐标。这里我必须强调一个点很多人在准备这类题时把精力放在了“记忆旋转矩阵”上但酷家乐真正想考察的是“你理不理解变换的内在逻辑”。因为在实际产品里设计师拖拽模型时系统需要把屏幕上的鼠标移动量转换成三维空间里的模型旋转量这背后是“视锥体坐标转换”和“矩阵链式乘法”的组合。如果只背公式而不理解换一个场景就抓瞎了。三维部分最常见的扣分点是“坐标系习惯不一致”。比如旋转矩阵在左手坐标系的定义和右手坐标系会差一个负号如果你做题前没有留意题目用的是哪种坐标系很可能方向就反了。我的建议是拿到题目先判断坐标系类型再动笔。哪怕题目没说也要在答题时注明“假设使用右手坐标系”。2.4 几何工具库的合理使用笔试题目通常会注明“禁止调用现成几何库”或者“允许使用标准库但必须实现核心逻辑”。实际上在LeetCode一类的平台上计算几何题目自带的STL支持很有限你几乎总是需要自己手写Point和Vector类。我个人的习惯是在笔试开始前先在草稿纸上写好一个最小可用的几何工具模板class Point: def __init__(self, x0, y0): self.x x self.y y def cross(a, b, c): return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x) def dot(a, b, c): return (b.x - a.x) * (c.x - a.x) (b.y - a.y) * (c.y - a.y)先说结论这个模板在真实笔试里价值不大。为什么因为笔试的题通常都是“多步计算”而非“单点函数调用”。比如“判断一个四边形是否为矩形”这道题考察的是对角线相等且互相平分的性质不是让你调一个isRectangle()函数。你会手写Point类和cross函数只是及格线真正拉开差距的是你能否快速把这些工具组合起来解决一道完整的问题。但另一个角度看提前准备好模板能帮你节省“边写边回忆语法”的时间让你更快进入状态这在实际限时笔试里也是一种优势。3. 实战向的解题思路与代码模板接下来我把A卷里出现概率最高、最值得提前准备的几类题目展开讲每一类都给出解题思路和可直接套用的代码。3.1 判断两条线段是否相交含共线处理先说结论。两条线段AB和CD相交分两种情况规范相交交点在线段内部和非规范相交交点是端点或者共线重叠。规范相交的判断用跨立实验叉积(cross(A,B,C) * cross(A,B,D)) 0说明C和D分别在AB的两侧叉积(cross(C,D,A) * cross(C,D,B)) 0说明A和B分别在CD的两侧如果两个条件同时满足必然相交。但工程上更稳妥的做法是判断“ 0”这样把“端点恰好落在另一条线段上”的情况也算进去了。共线重叠的判断方式先用叉积判断四点是否共线cross(A,B,C) 0且cross(A,B,D) 0然后判断投影区间是否重叠。这里有个小技巧不需要同时判断x轴和y轴投影只需要判断x轴投影如果线段不垂直于x轴或者y轴投影如果线段垂直于x轴就可以了。稳妥起见就两个轴都判断。我写一个完整的Python实现class Point: def __init__(self, x, y): self.x x self.y y def cross(p1, p2, p3): return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x) def on_segment(p1, p2, p3): return (min(p1.x, p2.x) p3.x max(p1.x, p2.x) and min(p1.y, p2.y) p3.y max(p1.y, p2.y)) def segments_intersect(p1, p2, p3, p4): d1 cross(p3, p4, p1) d2 cross(p3, p4, p2) d3 cross(p1, p2, p3) d4 cross(p1, p2, p4) if ((d1 0 and d2 0) or (d1 0 and d2 0)) and \ ((d3 0 and d4 0) or (d3 0 and d4 0)): return True if d1 0 and on_segment(p3, p4, p1): return True if d2 0 and on_segment(p3, p4, p2): return True if d3 0 and on_segment(p1, p2, p3): return True if d4 0 and on_segment(p1, p2, p4): return True return False这个代码的好处是覆盖了规范相交和所有非规范相交情况。注意最后的四个if判断顺序无所谓但不能少。少了任何一个都会漏判“端点在另一条线段上”的情况。踩坑提醒不要为了图快写成“只判断跨立实验就返回”的版本那个版本碰到共线是必挂的。也别用斜率比较法除以零的问题会让你后期debug到怀疑人生。3.2 计算多边形面积与判断顶点顺序多边形的面积计算听着简单但实际代码里有一个非常常见的错误忘记处理“自相交多边形”。什么是自相交多边形就是顶点顺序绕圈时边与边之间发生了交叉。比如五角星它的顶点如果按顶点索引正序连接会得到一个五角星形状的自相交多边形。这种情况下鞋带公式算出来的是一个“有向代数面积”的累积而不是直观的图形面积。如果题目没有特别说明“输入多边形保证是简单多边形”你可以默认它一定是简单多边形因为出题人不会在这个地方故意坑你。但你自己心里要清楚鞋带公式适用于简单多边形。如果题目明确说明“多边形可能自交”那就得先把多边形三角剖分再分别求每个三角形的面积这个复杂度会高很多一般笔试不会出。顶点顺序的判断也很简单用鞋带公式算出来的“带符号面积”如果为正就是逆时针为负就是顺时针。这个结论在二维几何里非常常用比如实现多边形填充算法时需要保证顶点是逆时针顺序否则渲染管线会做背面剔除导致显示异常。一个常被忽略的细节浮点数精度。鞋带公式累加的数值可能很大特别是多边形顶点坐标值达到百万级别时float会丢精度。建议用double并且最终取绝对值时再处理。这行字看着不起眼但在真实笔试里真的有人因为用float丢精度而挂掉。3.3 点在多边形内的射线法实现射线法的完整实现看起来简单但有几个边界条件需要仔细处理。我先把代码放出来def is_point_in_polygon(pt, poly): n len(poly) inside False for i in range(n): p1 poly[i] p2 poly[(i 1) % n] if (p1.y pt.y) ! (p2.y pt.y): x_intersect (p2.x - p1.x) * (pt.y - p1.y) / (p2.y - p1.y) p1.x if pt.x x_intersect: inside not inside return inside这里用的是经典的水平射线法。核心逻辑是如果点P的y坐标恰好落在一条边的两个端点的y坐标之间注意是严格一侧上、一侧下就计算这条边在P所在高度上的x坐标判断射线是否穿过。边界条件处理当P的y坐标恰好等于某个顶点的y坐标时会出现“射线穿过顶点”的情况。这个实现里用(p1.y pt.y) ! (p2.y pt.y)来规避如果两个端点都在同一侧或者恰好有一个端点等于P的y坐标条件都不会满足从而避免重复计数。当P落在多边形边上时这个函数会返回True或False结果不确定。如果题目要求“把边上的点也算作内部”需要额外加一步判断。这段代码是“能跑且大概率正确”的版本。但在竞赛与笔试中还有更快的方案——基于“扫描线”的做法但那需要先做预处理排序对笔试短时间内完成来说性价比不高。除非你提前准备了模板否则还是用射线法稳妥。3.4 三维射线与平面求交三维部分的高频题给定一个平面用法向量n和平面上一点P0表示和一条射线起点O、方向向量d求射线与平面的交点。解题步骤如下计算denom dot(n, d)。如果|denom|小于某个极小值比如1e-9说明射线与平面平行或共面没有唯一交点。计算t dot(n, P0 - O) / denom。如果t 0说明交点在射线的反方向实际上射线没有打到平面。否则交点坐标就是O t * d。代码实现def ray_plane_intersect(ray_origin, ray_dir, plane_point, plane_normal): denom dot(plane_normal, ray_dir) if abs(denom) 1e-9: return None t dot(plane_normal, plane_point - ray_origin) / denom if t 0: return None return ray_origin ray_dir * t这个题最容易被忽略的点是符号问题。P0 - O的方向写反会导致t的符号反了交点到射线的反方向去了。这种bug不看实际运行结果根本发现不了。实际笔试中这个考点通常会和“射线与三角形求交”结合在一起。如果你已经解出了射线与平面交点那么下一步就是判断这个点是否在三角形内部。判断方法可以用“重心坐标法”也可以用“同向法”——分别判断点是否在三角形三条边的同一侧。两个方法都可以但重心坐标法对浮点误差的容忍度更高也更规范。3.5 复合题型矩形重叠与最近点对A卷里还有一类“看似简单实则全考细节”的题。典型代表是“判断两个矩形是否重叠”和“求一组点中距离最近的两个点”。矩形重叠判断最简单的方法是反证法两个矩形不重叠意味着其中一个在另一个的左边、右边、上边或下边。写成代码def is_rect_overlap(r1, r2): return not (r1.x2 r2.x1 or r2.x2 r1.x1 or r1.y2 r2.y1 or r2.y2 r1.y1)这个解法比“枚举所有顶点是否在另一个矩形内”高效得多也更准确地处理了“边重合但面积为零”的边界情况。最近点对问题则有明显的水平区分。暴力法两两求距离是O(n^2)n为几千的时候勉强能跑但笔试的数据量如果到十万级别就必须用分治法。分治法的核心是把点集按x坐标排序。递归分治求左半和右半内部的最近点对距离d。只在“距离中线距离小于d”的带状区域里检查跨左右两边的点对。这个分治法在笔试时间紧张时不容易徒手写对。我的建议是如果目标岗位是几何算法方向提前背熟分治模板。如果你只是其他方向的候选人看到这道题应该评估时间成本实在不行就写暴力法拿部分分数也比空着强。4. 阅卷视角这些细节决定了你能否进面试笔试不是只考“做对没有”还考“做得像不像一个合格的工业级开发者”。我从参加过这类卷子批改的面试官朋友那里听到过一些反馈这里分享给你。4.1 命名规范与代码可读性整洁的变量命名会影响面试官对你的第一印象。如果你的代码里全是p1、p2、p3、p4这样的命名面试官会认为你平时写代码时不太考虑可维护性。命名建议用point_a, point_b而不是p1, p2。用cross_value、dot_value而不是d1, d2。用is_intersect而不是check()。本质上面试官在阅卷时会试图判断“这个候选人的代码能不能进生产环境”。虽然笔试代码不是生产代码但代码风格会暴露你平时的习惯。即使题目做对了一个整洁的命名风格绝对能加分。4.2 边界条件的完备性我给候选人的建议是每写完一道题自己立刻检查三类边界条件空输入多边形没有顶点、点集为空。重复输入多个点坐标相同。退化情况三点共线、线段长度为0、法向量为零向量。这三点如果在代码里都考虑到了即使最终答案有细微bug面试官也会认为你具备工程严谨性。反之如果主逻辑写出来了但边界条件一塌糊涂面试官会认为“这人在生产环境里会写出低级的崩溃事故”。4.3 时间复杂度与空间复杂度的权衡说明试卷上的每道题都标了数据范围你需要在答题时根据数据范围选择合适的算法。比如“判断点是否在多边形内”如果多边形顶点数不超过100O(n)的射线法就够了。但如果多边形顶点数达到10^6你需要用扫描线预处理成O(log n)查询这就是不同的解法了。面试官期待看到的是候选人能够自己判断复杂度并在答案中注明“这个解法是O(n log n)因为需要先排序”。不要在O(n^2)的暴力法代码旁边什么都不写面试官会默认你不知道还有更优解。哪怕你写的是最优解也建议在注释里用一行说明时间复杂度这样能更直观地展示计算思维能力。5. 常见扣分点与备赛建议速查根据往年笔试的反馈我整理了一个高频扣分点对照表你可以对照着自查。5.1 高频扣分点列表扣分点具体表现解决方式坐标系方向混乱使用斜率判断线段相交时除以零使用叉积和点积避免斜率除法浮点数精度丢失使用float计算面积或距离统一用double必要时设置误差阈值1e-9边界条件缺失未判断三角形退化、点重合、线段共线写完代码后主动枚举退化输入测试射线与平面命名符号错误把P0-O写成O-P0导致奇点逻辑错误明确写出t的计算公式并代入简单数据验证矩形重叠判断复杂化枚举顶点、判断包含关系导致逻辑混乱用反证法三个判断条件一行代码解决排序的稳定性忽略凸包题排序时未处理坐标相同点在Point类中重写比较函数相等时合并没有注明复杂度代码可以用但没写注释每道题末行注释“时间复杂度/空间复杂度”答题状态不佳因为第一题卡壳浪费大量时间先扫描全卷从高分题开始写5.2 备赛建议三条实际可执行的路径先说基础路线。如果你的时间只有两周我建议你把重心放在以下内容上向量与点线关系包括叉积点积的所有性质、线段相交判断、多边形面积与凸包、点在多边形内判断。这些是A卷的“必考送分题”。你不需要背太多模板但需要能在30分钟内手写完成并保证无bug。再说进击路线。如果你的时间有四周可以在基础之上加入三维向量与空间平面、射线与三角形求交、坐标变换与矩阵乘法、矩形重叠与最近点对。这些都是中高难度题目能做出这类题基本意味着你已经超过80%的候选人了。最后是模拟路线。无论准备多久考前一定要做至少三次完整的定时模拟。找一份类似的几何算法题集设定90分钟倒计时完全模拟笔试环境。你会发现“平时的自己能想出来的思路”和“考场上的自己能在有限时间内写出来的代码”差距极大。模拟的价值就是让你提前适应这种差距调整做题节奏。6. 写在最后一些关于几何算法的碎碎念我从第一次接触计算几何到现在前前后后背过、手写过、踩坑过不少这类题目。如果你问我这份酷家乐A卷到底难不难我会说它比纯算法题要“接地气”得多因为它考的东西基本都能在真实产品里找到对应的功能模块。但同时这也意味着它容不得你“背模板糊弄过去”。我个人的体会是几何算法的备考和别的算法方向不太一样。普通的算法题考的是“数据结构逻辑”而几何算法题更考“数学直觉空间想象力精度意识”三者的结合。很多人刷了几百道LeetCode再去考几何卷反而被一道“判断点在三角形内部”的题打懵了原因就是他们从来没有真正理解过叉积这个工具在几何里的核心地位。如果你打算投相关岗位我会建议你花一个下午的时间完整推导一遍“叉积为什么可以用来判断点与直线的左右关系”弄懂“鞋带公式为什么能算面积”搞清楚“射线法遇到顶点时为什么要做特殊处理”。这三个问题想明白了至少能覆盖这份考卷60%以上的考点。剩下的就是多练习、多踩坑、多复盘。最后分享一个小技巧考场时间不够的时候“拿能拿的分”比“挑战难题”更重要。A卷的题目通常会从易到难排列但偶尔也有“开头即难题”的变态情况。建议拿到卷子后先花两分钟扫一遍全部题目然后从“思路最清晰、代码最熟练”的题开始写而不是盲目地按顺序做题。这个策略帮我在多次笔试里稳稳保住及格线也推荐给你。祝顺利。