判断点是否在凸包内是计算几何领域的经典问题，很多场景都会用到对应的算法模板，其中基于叉积实现的xyz判断点在凸包内模板因为效率高、逻辑清晰被广泛使用，理解这个模板的实现原理能帮助开发者更灵活地应对不同的使用需求。
基础概念铺垫
要理解模板逻辑，首先需要明确几个核心概念。凸包指的是包含给定所有点的最小凸多边形，凸包上的顶点按逆时针排列时，任意相邻两个顶点与凸包内部的点构成的向量叉积都满足非负的条件。
叉积运算在这里是核心判断依据，对于二维平面上的两个向量overrightarrow{a}=(x1,y1)和overrightarrow{b}=(x2,y2)，它们的叉积计算公式为x1*y2 - x2*y1，叉积的结果符号可以判断两个向量的相对方向：结果为正说明overrightarrow{b}在overrightarrow{a}的逆时针方向，为负说明在顺时针方向，为零说明两向量共线。
模板核心逻辑拆解
xyz判断点在凸包内模板的核心思路是遍历凸包的所有相邻边，判断目标点是否在所有边的同一侧（以逆时针排列的凸包为例，目标点需要在所有边的左侧或者边上）。
凸包顶点顺序要求
模板默认凸包的顶点是按逆时针顺序排列的，如果输入的凸包顶点是顺时针顺序，只需要把判断条件中的符号反转即可。如果凸包顶点顺序混乱，模板的判断结果会完全错误，使用前需要先确保凸包顶点顺序正确。
边界情况处理
模板还需要处理点在凸包边上的情况，当叉积结果为零时，还需要进一步判断点是否在该边的线段范围内，避免把凸包外的共线但超出边范围的点误判为内部点。
完整模板代码示例
以下是可直接使用的xyz判断点在凸包内模板代码，采用C++实现，逻辑清晰且效率较高：
#include <vector>
#include <cmath>
using namespace std;
// 定义二维点结构体
struct Point {
double x, y;
Point(double _x = 0, double _y = 0) : x(_x), y(_y) {}
};
// 计算向量叉积 (p1-p0) × (p2-p0)
double cross(const Point& p0, const Point& p1, const Point& p2) {
return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
}
// 判断点p是否在线段p1-p2上（包含端点）
bool onSegment(const Point& p, const Point& p1, const Point& p2) {
// 先判断点是否在线段的包围盒内
if (p.x < min(p1.x, p2.x) || p.x > max(p1.x, p2.x) ||
p.y < min(p1.y, p2.y) || p.y > max(p1.y, p2.y)) {
return false;
}
// 再判断三点是否共线
return fabs(cross(p1, p2, p)) < 1e-8;
}
// 判断点p是否在凸包convex_hull内，convex_hull为逆时针排列的顶点，首尾不重复
bool isPointInConvexHull(const Point& p, const vector<Point>& convex_hull) {
int n = convex_hull.size();
if (n == 0) return false;
if (n == 1) return (fabs(p.x - convex_hull[0].x) < 1e-8 && fabs(p.y - convex_hull[0].y) < 1e-8);
if (n == 2) return onSegment(p, convex_hull[0], convex_hull[1]);
// 遍历所有凸包边，判断点是否在所有边的左侧或边上
for (int i = 0; i < n; ++i) {
int next = (i + 1) % n;
double cr = cross(convex_hull[i], convex_hull[next], p);
if (cr < -1e-8) {
// 点在边的右侧，说明在凸包外
return false;
} else if (fabs(cr) < 1e-8) {
// 共线，判断是否在边上
if (onSegment(p, convex_hull[i], convex_hull[next])) {
return true;
}
}
}
return true;
}
模板使用注意事项
使用这个模板时需要注意几个问题，首先是凸包的顶点不能重复，且需要按逆时针顺序排列，如果凸包是顺时针顺序，只需要把判断条件中的cr < -1e-8改成cr > 1e-8即可。
其次是精度问题，代码中使用了1e-8作为浮点数误差阈值，实际使用时可以根据场景调整这个阈值，如果所有点的坐标都是整数，也可以把叉积和判断逻辑改成整数运算，避免浮点数误差问题。
最后如果凸包是退化的（比如所有点共线），模板也能正确处理，当凸包只有两个点时，会判断点是否在这条线段上，当凸包只有一个点时，会判断点是否和该点重合。