★ FEATURED ARTICLE 1. 从“点到多边形的切线”说起这个几何问题到底在解决什么“点到多边形的切线”这个说法第一次听到的人多半会愣一下——切线不是圆才有的概念吗点跟多边形之间怎么会有切线其实这正是计算几何里一个非常经典、也非常实用的问题给定平面上的一个点和一个简单多边形求从该点出发、与多边形“擦边而过”的那两条射线。这两条射线与多边形之间形成的夹角区域就是从这个点能“看见”多边形的全部范围。我第一次接触这个问题是在做一个二维可见性判断的小工具时。当时的需求很朴素场景里有一个观察点还有一堆多边形障碍物我需要快速判断哪些区域是可见的、哪些被挡住了。如果对每个方向都去和多边形的每条边做求交测试计算量会大到没法接受。而“点到多边形的切线”恰好能把这个问题从“逐边测试”压缩成“先求两条切线再在夹角内处理”效率提升是数量级的。所以这篇文章想聊的不只是“怎么算两条切线”这么简单。我会把这个问题拆开它背后的几何直觉是什么、为什么切线一定是经过多边形某个顶点的、怎么用叉积和极角排序把候选顶点筛出来、遇到凹多边形和退化情况怎么兜底、以及在实际代码里怎么把它写稳。适合正在做碰撞检测、可见性分析、路径规划、图形编辑器、GIS 空间查询这类工作的朋友参考也适合单纯想补一补计算几何基础的读者。需要先说明一点下面涉及的具体实现细节是基于这类问题的常见工程实践做的合理补充不同场景下会有取舍你可以根据自己的精度要求和数据规模调整。2. 核心思路拆解为什么切线一定“踩”在顶点上2.1 切线的几何直觉从“看见”到“擦边”先把概念说清楚。假设平面上有一个点 P和一个简单多边形边不自交的封闭图形。从 P 向多边形看过去多边形在视野里占据了一个角度范围。这个范围的两条边界射线就是我们要找的切线。左边那条叫左切线右边那条叫右切线两条射线夹住的扇形区域就是从 P 出发能“看到”多边形的方向集合。用生活化的类比你站在一个房间门口往里看房间里的家具多边形在你视野里占了一块。你视野的左边缘和右边缘正好擦着家具最外侧的轮廓——那两条边缘线就是切线。家具完全在你视野内但再往外偏一点点你就看不到它了。这个“擦边”的性质直接决定了切线的两个关键特征第一切线一定经过多边形的某个顶点第二在这个顶点处多边形整体位于切线的同一侧。2.2 为什么候选点只能是顶点很多人第一反应是切线会不会切在某条边的中间答案是对于多边形这种由直线段组成的图形不会。理由可以用反证法想。假设一条切线 T 与多边形的某条边 E 相交于边的内部某点 Q而不是端点。因为 E 是直线段T 也是直线两条直线相交于 Q。如果 T 不是沿着 E 的方向那么在 Q 附近E 会穿过 T也就是 E 的一部分在 T 的一侧、另一部分在另一侧。这就意味着多边形在 T 的两侧都有点那 T 就不是“擦边”而是“穿过”了不符合切线的定义。如果 T 恰好沿着 E 的方向那 T 和 E 重合切线就退化成了边所在直线这属于特殊情况通常我们要求切线只在一个顶点处接触多边形。所以结论很干净非退化的切线接触点一定是多边形的顶点。这个结论把搜索空间从“无穷多条边上的无穷多个点”直接压缩到了“有限个顶点”这是整个算法能高效的基础。2.3 左切线与右切线的判定条件光知道候选是顶点还不够还得能判断某个顶点到底是不是切点、是左切还是右切。设当前候选顶点为 VP 到 V 的射线方向记为 d。要判断这条射线是不是切线核心看多边形其他顶点相对于这条射线的位置。具体来说用叉积来判断对多边形上任意另一个顶点 W计算向量 PV 和 PW 的叉积也就是 (V-P) × (W-P)。叉积的符号告诉我们 W 在 PV 的左侧还是右侧。如果所有其他顶点都在 PV 的同一侧叉积符号一致或者为零那 PV 就是一条切线。如果所有点都在左侧那这是左切线从 P 看多边形整体在射线左边。如果所有点都在右侧那这是右切线。这里有个容易踩的坑叉积为零的情况。当 W 恰好落在 PV 所在直线上时叉积为零。这种情况在多边形有共线顶点时很常见处理不好会导致判定失败或者选错切点。后面讲退化处理时会专门说。2.4 和凸包的关系一个能省事的观察如果你处理的多边形是凸的那问题会简单很多。凸多边形的切线本质上就是从点 P 看凸包的极值方向。而且凸多边形上从某个顶点出发叉积符号是单调变化的可以用二分查找在 O(log n) 时间内找到切点不需要遍历所有顶点。但现实里的多边形往往是凹的。凹多边形没有这种单调性二分查找会失效只能老老实实遍历。不过有个折中办法先求多边形的凸包在凸包上找切线然后再把凹进去的部分单独处理。这个思路在可见性分析里很常用因为凸包上的切线能快速给出一个“粗筛”范围把明显不可能的方向排除掉。我个人的经验是如果多边形顶点数在几百以内直接遍历完全够用代码简单不容易出错如果顶点数上千甚至上万再考虑凸包加速或者空间索引。不要一上来就过度优化先把正确性做对。3. 核心细节与实操要点叉积、极角与边界情况3.1 叉积整个算法的计算基石叉积二维里也叫叉乘、外积是这个问题里用得最多的运算。对两个二维向量 a (ax, ay) 和 b (bx, by)叉积定义为cross(a, b) ax * by - ay * bx它的几何意义是以 a 和 b 为邻边的平行四边形的有向面积。符号表示 b 在 a 的左侧正还是右侧负绝对值是面积的两倍。在判断顶点相对于射线的位置时我们实际算的是 cross(V - P, W - P)。这个值的符号就是 W 相对于有向直线 PV 的位置。这里有个细节叉积的绝对值大小和距离有关但我们只关心符号所以不用担心数值大小只要注意浮点误差就行。提示如果你的坐标是整数尽量用整数运算算叉积避免浮点误差。如果坐标是浮点数叉积结果接近零时要设一个 epsilon 阈值比如 1e-9把绝对值小于阈值的当作零处理。3.2 极角排序把顶点按方向排好队一个很自然的实现思路是先把所有顶点相对于 P 的极角算出来按角度排序然后在这个有序序列上找切点。这样做的好处是切点在角度序列里一定是“极值”——左切线对应角度最小或最大的那个方向右切线对应另一个极值。但极角排序有几个坑。第一atan2 的计算有精度损失而且速度比叉积慢。第二角度跨越 -π 到 π 的边界时排序会出问题需要特殊处理。第三当两个顶点相对于 P 方向完全相同时共线排序结果不稳定。我的建议是如果只是为了找切线不一定要真的做完整排序。可以用“扫描”的方式维护当前最优的切点候选遍历一遍顶点用叉积比较更新候选。这样是 O(n) 时间O(1) 额外空间比排序的 O(n log n) 更省而且避开了 atan2 的精度问题。3.3 左切与右切的统一处理框架实际写代码时我习惯把左切和右切用同一套逻辑处理只是比较方向相反。具体做法是初始化左切候选为任意一个顶点比如第一个顶点。遍历所有顶点对每个顶点 V检查它是否比当前候选“更靠左”。“更靠左”的判定设当前候选为 C如果 cross(V - P, C - P) 的符号表明 C 在 V 的右侧或者两者共线但 V 离 P 更远就更新候选为 V。右切同理把比较方向反过来。这个框架的好处是逻辑统一不容易写错。但要注意这个简单的“贪心更新”在凹多边形上不一定一次遍历就能得到正确答案因为凹多边形的可见性边界可能不是全局极值。稳妥的做法是先做一次遍历得到候选再用“所有点是否在同一侧”做一次验证如果验证失败说明遇到了凹多边形的复杂情况需要换更严格的算法。3.4 退化情况的分类与处理退化情况是这类几何算法最容易翻车的地方。我整理了几种常见的退化类型具体表现处理策略点落在多边形内部P 在多边形内不存在切线先用射线法或环绕数法判断内外内部直接返回无切线点落在多边形边上P 在某条边上视为特殊情况切线方向沿边方向需单独定义点与某顶点重合P 恰好是某个顶点切线方向由相邻两条边决定需特殊处理多个顶点共线从 P 看多个顶点方向相同取最远的那个作为切点忽略中间的多边形退化顶点数少于 3或面积为零提前校验输入拒绝非法多边形注意点落在多边形内部这个情况很多人会忽略。如果 P 在内部从 P 出发的射线会与多边形边界相交根本不存在“擦边”的切线。所以第一步一定要先做内外判定别急着找切点。3.5 精度控制epsilon 怎么选浮点误差是几何算法的天敌。epsilon 选太大会把本来不共线的点误判为共线选太小又会漏掉真正的共线情况。我的经验是如果坐标范围在 [-1000, 1000]用 1e-9 比较合适。如果坐标范围很大比如 GIS 里的经纬度或者大比例尺坐标epsilon 要按坐标量级缩放比如用 1e-9 * max(|坐标|)。更好的做法是尽量用整数坐标或者把浮点坐标乘以一个比例因子转成整数从根上避免误差。还有一个技巧在比较叉积符号时不要直接和零比而是和一个相对阈值比。比如if (cross eps)判正if (cross -eps)判负中间的区域当作共线。这样能显著减少边界抖动。4. 完整实操流程从输入到输出两条切线4.1 输入校验与预处理拿到点 P 和多边形顶点列表后先做几件事检查顶点数是否至少为 3。少于 3 个点构不成多边形直接报错。检查多边形是否有重复顶点、自交等非法情况。自交检测比较耗时如果数据来源可靠可以跳过但重复顶点一定要去重。判断 P 是否在多边形内部。用射线法从 P 向任意方向发一条射线统计与多边形边的交点个数奇数在内偶数在外。注意处理射线经过顶点、与边重合等边界情况。如果 P 在内部直接返回“无切线”。如果 P 在边界上按特殊规则处理。这一步看起来简单但实际项目里输入数据的质量往往很差不做校验后面会出各种莫名其妙的 bug。4.2 计算每个顶点相对于 P 的方向对每个顶点 V计算向量 V - P。这个向量包含了方向和距离信息。如果某个顶点恰好和 P 重合距离为零要特殊标记因为它的方向没有定义。在实际代码里我通常不直接算角度而是保留向量本身后面用叉积比较。这样既快又准。4.3 找左切点一次遍历加验证左切的寻找逻辑用伪代码表示大概是candidate vertices[0] for each vertex V in vertices: if isMoreLeft(V, candidate, P): candidate V # 验证 if allVerticesOnOneSide(candidate, P, vertices): leftTangent candidate else: # 凹多边形复杂情况走备用逻辑 leftTangent findTangentByScan(candidate, P, vertices)其中 isMoreLeft 的判定核心是比较 cross(V-P, candidate-P) 的符号。如果 V 在 candidate 的左侧或者共线但更远就更新。验证步骤很关键。因为贪心更新在凹多边形上可能停在局部极值验证能帮我们发现这种情况。如果验证失败说明需要更严格的扫描从候选出发沿着多边形顶点顺序走找到第一个让叉积符号翻转的顶点那才是真正的切点。4.4 找右切点镜像逻辑右切和左切是对称的把比较方向反过来就行。但要注意左切和右切不能独立地随便找它们必须满足一个一致性条件从 P 看多边形整体位于左切线的右侧、右切线的左侧两条切线夹住的扇形正好覆盖多边形。如果分别找出来的左切和右切不满足这个关系说明中间某一步出错了需要回退检查。我在实际项目里会加一个断言cross(leftTangent - P, rightTangent - P) 的符号应该和预期一致不一致就抛异常方便定位问题。4.5 输出切线的表示方式切线的输出形式取决于你的下游怎么用。常见的有几种用两个点表示P 和切点。这是最直接的。用方向向量表示从 P 出发的单位向量。用角度表示极角方便做角度范围判断。如果下游要做可见性判断我建议输出方向向量加一个角度范围这样判断某个方向是否可见时只需要比较角度是否落在范围内非常快。4.6 一个完整的数值例子假设 P (0, 0)多边形顶点按逆时针为 (2, 1), (4, 3), (3, 5), (1, 4), (0, 2)。先判断 P 是否在内部。用射线法从 P 向 x 轴正方向发射线统计交点。这个多边形大致在第一象限P 在外部。计算各顶点相对 P 的向量(2,1), (4,3), (3,5), (1,4), (0,2)。找左切从 (2,1) 开始。比较 (4,3) 和 (2,1)cross((4,3),(2,1)) 41 - 32 -2负说明 (4,3) 在 (2,1) 右侧不更新。比较 (3,5)cross((3,5),(2,1)) 31 - 52 -7负不更新。比较 (1,4)cross((1,4),(2,1)) 11 - 42 -7负不更新。比较 (0,2)cross((0,2),(2,1)) 01 - 22 -4负不更新。所以左切候选是 (2,1)。验证检查所有点是否都在 (2,1) 的同一侧。算 cross((2,1), W) 对每个 W(2,1) 自己为 0(4,3) 为 -2(3,5) 为 -7(1,4) 为 -7(0,2) 为 -4。全部非正验证通过。左切点为 (2,1)。找右切类似地遍历这次找“更靠右”的。从 (2,1) 开始比较 (4,3)cross((4,3),(2,1)) -2负说明 (4,3) 在右侧更新候选为 (4,3)。比较 (3,5)cross((3,5),(4,3)) 33 - 54 9 - 20 -11负更新为 (3,5)。比较 (1,4)cross((1,4),(3,5)) 15 - 43 5 - 12 -7负更新为 (1,4)。比较 (0,2)cross((0,2),(1,4)) 04 - 21 -2负更新为 (0,2)。所以右切候选是 (0,2)。验证cross((0,2), W) 对每个 W(2,1) 为 01 - 22 -4(4,3) 为 03 - 24 -8(3,5) 为 05 - 23 -6(1,4) 为 04 - 21 -2(0,2) 自己为 0。全部非正验证通过。右切点为 (0,2)。所以从 P 看这个多边形左切线是 P 到 (2,1) 的射线右切线是 P 到 (0,2) 的射线。两条射线夹住的扇形就是可见范围。这个例子是凸多边形所以贪心一次就对了。凹多边形的情况会更复杂但基本框架是一样的。5. 常见问题与排查技巧实录5.1 切点找错症状、原因与修复最常见的症状是找出来的“切线”明显穿过了多边形而不是擦边。这通常有几个原因。第一个原因是叉积符号判断写反了。左切和右切的比较方向容易搞混建议写单元测试用几个已知答案的简单多边形验证。第二个原因是共线顶点处理不当。当多个顶点从 P 看方向相同时如果选了中间那个而不是最远的切线就会“切”在多边形内部。修复方法是共线时总是选离 P 最远的顶点。第三个原因是凹多边形的局部极值陷阱。贪心更新可能停在某个凹角上误以为是切点。修复方法是加验证步骤验证失败就切换到严格扫描。5.2 数值不稳定抖动与误判浮点误差导致的抖动表现为稍微移动 P 一点点切点就跳变到另一个顶点。这在交互式应用里很影响体验。缓解办法有几个。一是用整数坐标或定点数从根上消除误差。二是增大 epsilon但要小心别把真正的切点也过滤掉。三是在切点附近做平滑比如当两个候选切点的角度差小于某个阈值时取中间方向。这个平滑是工程上的妥协不严格但实用。5.3 性能瓶颈什么时候该优化如果多边形顶点数不多几百以内O(n) 的遍历完全够用不用优化。如果顶点数上万每次查询都遍历一遍会很慢这时候可以考虑预处理凸包在凸包上找切线把候选范围缩小。用空间索引比如网格、四叉树快速排除远离 P 的顶点。如果 P 的位置固定、多边形也固定切线可以预计算缓存。但我要提醒一句优化之前先测性能别凭感觉优化。我见过太多项目花大力气做了复杂优化结果 profile 一看瓶颈根本不在切线计算上。5.4 常见问题速查表问题现象可能原因排查方向切线穿过多边形叉积符号判断反了检查左切右切的比较逻辑切点选在边的中间共线顶点未取最远检查共线时的更新条件凹多边形切点错误贪心陷入局部极值加验证步骤失败则严格扫描结果抖动浮点误差用整数坐标或调大 epsilonP 在内部仍返回切线缺少内外判定先做射线法内外检测顶点重合导致除零未处理零向量预处理去重标记重合点5.5 几个我踩过的坑第一个坑忘了处理 P 在多边形边上的情况。这时候切线方向其实有歧义我当时的处理是直接返回边的两个方向作为切线结果下游逻辑全乱了。后来改成P 在边上时把多边形在 P 处“切开”分别处理两侧才正确。第二个坑多边形顶点顺序。我默认输入是逆时针结果遇到顺时针的数据叉积符号全反了切线找得乱七八糟。后来加了自动检测算多边形的有向面积正的就是逆时针负的就反转顶点顺序。第三个坑epsilon 设成了固定值遇到大坐标数据就失效。后来改成按坐标范围动态计算 epsilon才稳定下来。6. 这个算法的延伸与组合玩法6.1 可见性多边形切线的直接应用切线最直接的应用就是构造可见性多边形。从 P 出发两条切线夹住的扇形区域与多边形本身求交得到的区域就是从 P 能看到的全部范围。这个在游戏 AI 的视野判断、监控摄像头覆盖分析里非常常用。具体做法是把左切点和右切点之间的多边形边界沿着可见的那一侧取出来和两条切线一起构成一个封闭的可见性多边形。注意要处理多边形被切线“切掉”的部分只保留可见的那一段边界。6.2 路径规划切线作为绕行参考在路径规划里如果要从 P 走到多边形另一侧的某个目标点切线可以作为绕行的参考方向。沿着切线走到切点再沿着多边形边界走往往能得到一条比较短的绕行路径。当然真正的最短路径还要考虑多边形的具体形状但切线提供了一个很好的初始解。6.3 多边形的切线对从单点到多点如果场景里有多个观察点每个点都有自己的切线对。这些切线对的交集就是所有点都能看到的公共区域。这个在多摄像头覆盖、多传感器融合里很有用。计算上就是把每个点的可见扇形求交几何上是多个扇形区域的布尔运算。6.4 动态场景点或多边形移动时怎么办如果 P 或多边形在移动切线需要每帧重算。对于顶点数不多的多边形每帧重算的开销可以接受。如果多边形很复杂可以考虑增量更新只重算受移动影响的那部分顶点而不是全部遍历。不过增量更新的正确性维护比较麻烦除非性能真的卡脖子否则不建议。7. 写在最后一些个人体会这个“点到多边形的切线”问题看起来是个小问题但真正写稳、写对需要处理的细节比想象中多。我的体会是几何算法的难点从来不在核心思路而在边界情况和数值稳定性。核心思路可能十行代码就写完了但把各种退化情况处理好代码量会翻好几倍。另外一个体会是不要迷信“最优算法”。O(log n) 的二分查找听起来很美但只适用于凸多边形而且实现复杂、容易出错。对于大多数实际场景O(n) 的遍历加验证简单、可靠、够用。先把正确性做对再考虑性能这个顺序不能反。最后分享一个小技巧写这类几何代码时一定要准备一套可视化调试工具。把点、多边形、切线画出来一眼就能看出哪里不对。纯靠打印坐标调试效率低到让人崩溃。我现在的习惯是每写一个几何函数就配一个小的可视化 demo边写边看出错率能降一大半。
阅读完成 · 觉得有帮助？
