1. 概述
在本教程中，我们将讨论如何判断一个点是否位于二维平面上的三角形内部。
我们会介绍三种不同的方法来解决这个问题：
- 利用三角形面积公式
- 利用线段交点判断
- 利用向量叉积判断方向
这些方法都适用于2D空间中的任意三角形和点判断，且时间复杂度均为 **O(1)**。
2. 问题定义
给定一个三角形 T，由三个顶点 A、B、C 构成，以及一个点 P。我们需要判断点 P 是否在三角形内部。
如下图所示：
- 图 A 中，点 P 在三角形外部，结果应为
false - 图 B 中，点 P 在三角形内部，结果应为
true
3. 面积法（Triangles Area Approach）
3.1 原理
判断点 P 是否在三角形 ABC 内部，可以通过比较三角形 ABC 的面积与子三角形 ABP、BCP、CAP 的面积之和是否相等。
- 若相等 ➜ 点 P 在三角形内部
- 若不等 ➜ 点 P 在三角形外部
面积公式如下：
面积 = |(B - A) × (C - A)| / 2
其中 × 表示向量叉积。
3.2 面积计算函数
double triangleArea(Point A, Point B, Point C) {
Vector AB = new Vector(B.x - A.x, B.y - A.y);
Vector AC = new Vector(C.x - A.x, C.y - A.y);
double crossProduct = AB.x * AC.y - AB.y * AC.x;
return Math.abs(crossProduct) / 2.0;
}
3.3 完整判断逻辑
boolean isInsideByArea(Point P, Point A, Point B, Point C) {
double totalArea = triangleArea(A, B, C);
double sum = 0;
sum += triangleArea(A, B, P);
sum += triangleArea(B, C, P);
sum += triangleArea(C, A, P);
return Math.abs(totalArea - sum) < 1e-9;
}
✅ 优点：原理直观
❌ 缺点：浮点运算误差可能造成误判
4. 线段交点法（Line Segment Intersection Approach）
4.1 原理
从点 P 出发画一条射线，判断该射线与三角形边的交点个数：
- 奇数个交点 ➜ 点 P 在三角形内部
- 偶数个交点 ➜ 点 P 在三角形外部
⚠️ 注意：射线方向应随机选择，避免穿过顶点导致误判。
4.2 实现逻辑
boolean isInsideByIntersection(Point P, Point A, Point B, Point C) {
Point farAway = new Point(Double.MAX_VALUE, P.y + 1); // 随机方向射线
Segment ray = new Segment(P, farAway);
int intersections = 0;
intersections += intersects(ray, new Segment(A, B)) ? 1 : 0;
intersections += intersects(ray, new Segment(B, C)) ? 1 : 0;
intersections += intersects(ray, new Segment(C, A)) ? 1 : 0;
return intersections % 2 == 1;
}
✅ 优点：适用于多边形扩展
❌ 缺点：需要实现线段相交判断逻辑
5. 向量叉积方向法（Orientation Approach）
5.1 原理
利用向量叉积判断点 P 是否在三角形每条边的同一侧：
- 如果点 P 在每条边的同一侧 ➜ 点在三角形内部
- 否则 ➜ 点在三角形外部
叉积判断如下：
- 叉积 > 0 ➜ 左侧
- 叉积 < 0 ➜ 右侧
5.2 方向判断函数
int orient(Point A, Point B, Point C) {
double cross = (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
return cross > 0 ? 1 : -1;
}
5.3 完整判断逻辑
boolean isInsideByOrientation(Point P, Point A, Point B, Point C) {
int o1 = orient(A, B, P);
int o2 = orient(B, C, P);
int o3 = orient(C, A, P);
return Math.abs(o1 + o2 + o3) == 3;
}
✅ 优点：无需浮点运算，精度高
✅ 适用于整数坐标
❌ 缺点：对共线点需要额外处理
6. 总结
| 方法 | 时间复杂度 | 是否依赖浮点运算 | 适用场景 |
|---|---|---|---|
| 面积法 | ✅ O(1) | ✅ 是 | 快速实现 |
| 线段交点法 | ✅ O(1) | ✅ 是 | 多边形扩展 |
| 向量叉积方向法 | ✅ O(1) | ❌ 否 | 高精度要求 |
✅ 推荐优先使用 向量叉积方向法，因为它不依赖浮点运算，精度更高。