LeetCode 补充题 19. 判断一个点是否在三角形内
题目描述
:::fold-green 相关原题
牛客使用浮点坐标并输出 Yes 或 No，本文采用整数坐标并返回布尔值。
:::
给定三角形的三个顶点
a、b、c，以及待判断点p，请判断p是否位于三角形内，返回布尔值。这里整理为整数坐标版本：点位于边上或顶点上时返回
true；三个顶点共线、无法构成三角形时返回false。
示例 1：
输入：a = [0,0], b = [4,0], c = [0,4], p = [1,1]
输出：true
示例 2：
输入：a = [0,0], b = [4,0], c = [0,4], p = [3,3]
输出：false
提示：
- 点的位置由二维坐标表示，三角形顶点可以按顺时针或逆时针给出。
- 坐标为整数，叉积计算中的乘积及差值在有符号 64 位整数范围内。
- 来源文章使用浮点坐标；本文题面与下方代码统一采用整数坐标，不将整数实现当作浮点实现。
题意分析
给定三角形的三个顶点和一个待判断点，确定这个点是否位于三角形内部。本文把边上和顶点上的点也计为内部，三个顶点共线的退化情况返回
false。实现使用整数坐标，按点相对三条有向边的位置判断，不需要计算斜率，因此竖直边也能正常处理。坐标范围需保证叉积中的乘积及最终差值能用有符号 64 位整数表示。
解法：向量叉积同号判断
核心思路
[!blue]
对起点为
o的两条向量，叉积为(a.x - o.x) × (b.y - o.y) - (a.y - o.y) × (b.x - o.x)。它的符号表示第二条向量位于第一条向量的哪一侧：正值在左侧，负值在右侧，零表示共线。沿顶点顺序使用有向边
a → b、b → c、c → a。如果三个顶点逆时针排列，三角形内部同时位于三条边的左侧；顺时针排列时，内部同时位于三条边的右侧。三角形正是这三个内侧半平面的交集，因此只需检查待判断点是否同时满足三条边的侧向条件。计算点对三条边的叉积。三个结果全非负或全非正时，点满足全部边的内部条件，返回真；同时出现正值和负值时，至少有一条边把它隔在外侧，返回假。统一允许两种符号方向，就不需要提前固定顶点必须按顺时针还是逆时针给出。
零叉积允许点落在边界，但仅与某一条边共线还不够，还要同时满足另外两条边的条件，才能排除延长线上的外部点。三角形自身若叉积为零，就不存在有效的内部区域，应先返回假，再进行点的判断。
计算时先把每个坐标转换为宽整数，再相减和相乘。若先在窄整数中求差，差值可能已经溢出，之后再转换类型也无法恢复正确结果。
解题步骤
- 计算三个顶点的叉积，等于零时返回
false。- 分别计算
cross(a, b, p)、cross(b, c, p)、cross(c, a, p)。- 记录三个结果中是否存在负值、是否存在正值。
- 两种符号同时出现则返回假，否则返回真，包括符合边界条件的零叉积情况。
代码实现
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) * ((long) b.y - o.y) - ((long) a.y - o.y) * ((long) 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)-int64(o.X))*(int64(b.Y)-int64(o.Y)) - (int64(a.Y)-int64(o.Y))*(int64(b.X)-int64(o.X))
}
复杂度分析
- 时间复杂度：$O(1)$。
- 空间复杂度：$O(1)$。
关键点总结
[!green]
- 三条边必须按同一绕行方向排列。
- 零叉积对应边界，判断时保留等号的含义。
易错点总结
[!yellow]
- 先用窄整数相减再转宽，无法修复已经发生的溢出。
- 只接受全正或全负，会漏掉边界点。
- 不排除共线顶点，会把退化情况误当作三角形。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 812. 最大三角形面积 | 简单 | 叉积给出有向面积，本题用各边的符号判断内外并把共线边界计为内部。 |
| 1232. 缀点成线 | 简单 | 共线判定对应叉积为0，本题还要比较三条有向边上的符号是否一致。 |