LeetCode 补充题 19. 判断一个点是否在三角形内

约 8 分钟
文章信息 9 个分类 1 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 字节跳动 美团 腾讯 高频面试题
标签
数学
目录

题目描述

✅ 补充题 19. 判断一个点是否在三角形内

题意分析

给出平面上三个顶点 a、b、c 和一个待测点 p，要回答 p 是否落在这个三角形围成的区域里（含边界）。

第一个约束信号是这道题只要一个布尔答案，不要求算出交点、距离或面积数值。这意味着解法应该只关心「相对位置」这一类定性信息，任何需要开方或除法的量化计算都是多余的负担。

第二个信号是坐标以整数给出。整数意味着可以完全避开浮点数，从根本上消除精度误差；但同时要留意乘法带来的数值放大，坐标绝对值稍大时中间量就可能超出 32 位。

边界要单独想清楚三种：p 恰好落在某条边上、p 恰好与某个顶点重合、以及三个顶点本身共线（此时根本不构成三角形，退化成一条线段）。本文按常见口径把前两种视为「在三角形内」返回 true，把退化情形视为非法输入返回 false。

解法：向量叉积同号判断

核心思路

一个直觉解法是面积法：算出三角形 abc 的面积，再算 pab、pbc、pca 三个小三角形的面积，若三者之和等于总面积就说明 p 在内部。这个思路是对的，但用浮点数算面积会引入精度误差，判断「相等」时需要设阈值，阈值大了误判、小了漏判，在整数输入下白白把问题搞脏。

瓶颈其实在于「求面积」这一步做多了。真正需要的信息不是面积的大小，而是 p 相对每条边在哪一侧——这是纯粹的定性问题。

观察一条有向边 a → b：整个平面被它所在的直线切成两半。定义 cross(a, b, p) = (b.x - a.x)(p.y - a.y) - (b.y - a.y)(p.x - a.x)，这个值的正负恰好表示 p 在有向边的左侧还是右侧，为 0 则表示三点共线。它是纯整数运算，没有任何除法。

关键性质来了：把三角形的三条边写成首尾相接的有向环 a → b、b → c、c → a，那么这个环要么是逆时针的、要么是顺时针的。不变量是：p 在三角形内部当且仅当它始终位于这三条有向边的同一侧，即 cross(a,b,p)、cross(b,c,p)、cross(c,a,p) 三者要么全部非负，要么全部非正。 因为这里没有预设顶点的绕向，所以不能只查「全正」，而要查「符号不冲突」——只要正号和负号同时出现，就说明 p 被某条边挡在了外面。等于 0 的项对应边界或顶点，不制造冲突，自然被判为 true。

退化情形要单独挡掉：三点共线时 cross(a, b, c) 为 0，三角形没有内部，此时「符号不冲突」这条规则会把整条直线上的点都判成内部，因此必须在最前面提前返回 false。

解题步骤

  • 定义一个只含 x、y 的 Point 结构。用整数存坐标，是为了让后续全部判断都停留在精确算术里。
  • 先算 cross(a, b, c)，为 0 则直接返回 false。这一步排除退化三角形；放在最前面是因为后面的同号规则以「存在真实内部」为前提。
  • 依次计算 c1 = cross(a, b, p)、c2 = cross(b, c, p)、c3 = cross(c, a, p)。三条边必须按同一个环绕方向写，否则符号体系被打乱，同号判断立刻失效。
  • 用两个布尔量分别记录「是否出现过负数」和「是否出现过正数」。之所以不直接判断「三者是否都大于 0」，是因为顶点顺序可能是顺时针，那样内部点的三个叉积会全是负数。
  • 返回 !(hasNeg && hasPos)。正负同时出现意味着 p 至少被一条边分隔在外，其余情况都算在内或在界上。
  • 叉积用 64 位类型承接。坐标差最大可到两倍坐标上界，两个差相乘再相减，很容易越过 32 位范围。

以 a = (0,0)、b = (4,0)、c = (0,4)、p = (1,1) 走一遍：先查退化，cross(a, b, c) = (4-0)(4-0) - (0-0)(0-0) = 16，非零，是合法三角形。接着 c1 = cross(a, b, p) = (4-0)(1-0) - (0-0)(1-0) = 4。再 c2 = cross(b, c, p) = (0-4)(1-0) - (4-0)(1-4) = -4 + 12 = 8。最后 c3 = cross(c, a, p) = (0-0)(1-4) - (0-4)(1-0) = 0 + 4 = 4。三个值 4、8、4 全为正，hasNeg 为假、hasPos 为真，返回 true。换成 p = (5,5) 再走一遍：c1 = 4 * 5 - 0 = 20，c2 = (0-4)(5-0) - (4-0)(5-4) = -20 - 4 = -24，c3 = (0-0)(5-4) - (0-4)(5-0) = 20。此时 hasNeg 与 hasPos 同时为真，返回 false。再取边界点 p = (2,0)：c1 = 4 * 0 - 0 * 2 = 0，c2 = (-4)(0-0) - 4(2-4) = 8，c3 = 0 \times (0-4) - (-4)(2-0) = 8，没有负数，返回 true，符合「边界算内部」的约定。

代码实现

class Solution {
    static class Point {
        int x;
        int y;

        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public boolean isPointInTriangle(Point a, Point b, Point c, Point p) {
        if (cross(a, b, c) == 0) {
            return false;
        }

        long c1 = cross(a, b, p);
        long c2 = cross(b, c, p);
        long c3 = cross(c, a, p);

        // 只要相对三条边没有同时出现正负号，就在三角形内或边界上。
        boolean hasNeg = c1 < 0 || c2 < 0 || c3 < 0;
        boolean hasPos = c1 > 0 || c2 > 0 || c3 > 0;
        return !(hasNeg && hasPos);
    }

    private long cross(Point o, Point a, Point b) {
        return (long) (a.x - o.x) * (b.y - o.y) - (long) (a.y - o.y) * (b.x - o.x);
    }
}

type Point struct {
    X int
    Y int
}

func isPointInTriangle(a, b, c, p Point) bool {
    if cross(a, b, c) == 0 {
        return false
    }

    c1 := cross(a, b, p)
    c2 := cross(b, c, p)
    c3 := cross(c, a, p)

    // 只要相对三条边没有同时出现正负号，就在三角形内或边界上。
    hasNeg := c1 < 0 || c2 < 0 || c3 < 0
    hasPos := c1 > 0 || c2 > 0 || c3 > 0
    return !(hasNeg && hasPos)
}

func cross(o, a, b Point) int64 {
    return int64(a.X-o.X)*int64(b.Y-o.Y) - int64(a.Y-o.Y)*int64(b.X-o.X)
}

复杂度分析

  • 时间复杂度：$O(1)$，一共只做四次叉积，每次是两次乘法和一次减法，与输入规模无关。
  • 空间复杂度：$O(1)$，只用了三个 64 位中间量和两个布尔量，没有任何随输入增长的结构。

关键点总结

  • 定性问题要用定性工具。判断「在哪一侧」只需要叉积的符号，用不上面积、距离这些需要除法或开方的量，整数输入下这么做可以彻底摆脱浮点精度。
  • 「符号不冲突」比「符号全正」更稳健，因为它不依赖顶点是顺时针还是逆时针给出。凡是题目没有承诺绕向的几何判定，都应该写成这种对称形式。
  • 叉积为 0 是一个信息量很大的信号：既能表示点落在边上，也能表示三点共线导致图形退化。同一个表达式服务两种语义，所以退化检查必须先做，否则语义会混在一起。
  • 整数几何题的第一反射是估算中间量的量级。两个坐标差相乘就已经是平方级，32 位很容易被冲破，提前升到 64 位是零成本的保险。
  • 面试视角：先说面积法并主动指出它的浮点隐患，再切到叉积法，能同时展示几何直觉和工程判断力。面试官常追问「边界点算不算内部」，要主动确认口径而不是默认一种写法。
  • 面试视角：如果被追问推广到凸多边形，可以答同一套同号规则直接适用（按顺序遍历所有边）；若要求 $O(\log n)$，则改成先用叉积二分定位扇区，再判一次，这条延伸很常见。

易错点总结

  • 错误写法：三条边写成 ab、bc、ac，最后一条没有闭合成环。用例 a = (0,0)、b = (4,0)、c = (0,4)、p = (1,1) → cross(a, c, p) = (0-0)(1-0) - (4-0)(1-0) = -4，与前两个正值冲突，内部点被误判为 false。
  • 错误写法：直接判断 c1 > 0 && c2 > 0 && c3 > 0。用例把上面的三角形顶点顺序改成 a = (0,0)、b = (0,4)、c = (4,0)、p = (1,1) → 三个叉积全为负，内部点被误判为 false。
  • 错误写法：叉积用 int 承接。用例 a = (0,0)、b = (100000, 1)、p = (1, 100000) → 乘积量级达到 $10^{10}$，32 位溢出后符号翻转，判定结果随机出错。
  • 错误写法：省掉 cross(a, b, c) == 0 的退化检查。用例 a = (0,0)、b = (1,1)、c = (2,2)、p = (5,5) → 三个叉积全为 0，规则判定「无冲突」返回 true，但根本不存在三角形。
  • 错误写法：把 cross 写成 (a.x - o.x) * (b.x - o.x) - (a.y - o.y) * (b.y - o.y)，即误写成点积形式。用例 a = (0,0)、b = (4,0)、c = (0,4)、p = (1,1) → 算出的是投影量而非旋转方向，符号与位置无关，结果毫无意义。
  • 错误写法：改用面积法且用 double 比较 s1 + s2 + s3 == s。用例任意坐标较大的三角形 → 浮点舍入让等式几乎不可能精确成立，内部点被大面积误判为外部。
  • 错误写法：认为「点在三角形内」等价于「点的横纵坐标都落在三个顶点的最小最大范围内」。用例 a = (0,0)、b = (4,0)、c = (0,4)、p = (3,3) → 坐标都在包围盒里，但它在斜边外侧，应为 false 却被判成 true。
  • 错误写法：把 hasNeg 和 hasPos 写成非严格比较，例如 c1 <= 0 || ...。用例任意内部点 → 只要有一个叉积为 0（边界点）就同时点亮两个标志，边界点全被误判为外部。

相似题目

题目 难度 考察点
812. 最大三角形面积 简单 用叉积绝对值直接取面积，枚举所有三点组合
836. 矩形重叠 简单 轴对齐图形只需比较投影区间，无需向量运算
149. 直线上最多的点数 困难 用共线判定做分组计数，重点在避免斜率除法
223. 矩形面积 中等 求重叠面积的数值而非位置关系，含容斥处理
335. 路径交叉 困难 判定线段相交，需要按情形讨论有限种交叉模式