一、核心定义对于三角形 △ABC平面上任意一点 P 都可以唯一表示为三个顶点 A,B,C 的加权线性组合且满足归一化约束这里的就是点 P 的重心坐标。几何直觉极其重要等于“对边三角形” △PBC的面积占比。等于△PCA的面积占比。等于△PAB的面积占比。如果点 P 在三角形内部则 α,β,γ 全部 0如果在外部至少有一个 0如果在边上则某个 0。二、计算方法方法一代数法解线性方程组既然且代入得设。这是一个二维/三维方程解这个二元一次方程组利用叉积/点积对两边同时叉乘v1和v2注意在 2D 中cross 是标量在 3D 中取叉积结果的模长或对应轴向分量。方法二面积比法几何直观最稳健设整个三角形面积为那么优点任何维度2D/3D都能直接算且不容易出现除零异常。方法三边缘函数法GPU 光栅化专用最高效光栅化时不需要除法求面积而是计算带符号的边函数Edge Function。对于逆时针顶点 A→B→C同理算出和。这三个值分别对应中心坐标的分子即这种方法的优势是计算全屏像素时可以增量步进只需加常数极其适合硬件并行。三、通用代码实现1二维三角形重心坐标代数法#include cmath #include algorithm struct Vec2 { double x, y; }; // 返回重心坐标 (alpha, beta, gamma) // 如果返回的 gamma 0 或 1说明点在外面需自行判断 bool computeBarycentric2D(const Vec2 A, const Vec2 B, const Vec2 C, const Vec2 P, double alpha, double beta, double gamma) { // 1. 计算向量 Vec2 v1 {B.x - A.x, B.y - A.y}; Vec2 v2 {C.x - A.x, C.y - A.y}; Vec2 v {P.x - A.x, P.y - A.y}; // 2. 计算叉积 (二维叉积得到标量) double denom v1.x * v2.y - v1.y * v2.x; // 即 cross(v1, v2) // 防除零退化三角形面积为零 if (fabs(denom) 1e-8) { // 处理退化三角形这里简单返回 false alpha beta gamma 0.0; return false; } // 3. 克雷默法则求解 beta 和 gamma // beta cross(v, v2) / cross(v1, v2) double beta_num v.x * v2.y - v.y * v2.x; // gamma cross(v1, v) / cross(v1, v2) double gamma_num v1.x * v.y - v1.y * v.x; beta beta_num / denom; gamma gamma_num / denom; alpha 1.0 - beta - gamma; // 满足归一化 // 返回是否在内部包含边界 return (alpha 0.0 beta 0.0 gamma 0.0); }2三维空间中的重心坐标面积比法3D 顶点不在同一平面不存在的三角形必共面。但直接求叉积模长比较繁琐我们可以用投影法把 3D 点投影到某个坐标平面XY/XZ/YZ降维成 2D 算。struct Vec3 { double x, y, z; }; // 辅助函数2D 叉积 double cross2D(const Vec3 O, const Vec3 A, const Vec3 B) { return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x); } bool computeBarycentric3D(const Vec3 A, const Vec3 B, const Vec3 C, const Vec3 P, double alpha, double beta, double gamma) { // 关键优化选择投影平面防止因垂直投影导致精度丢失 // 选择法向量中绝对值最大的分量作为忽略轴 Vec3 normal { (B.y - A.y) * (C.z - A.z) - (B.z - A.z) * (C.y - A.y), (B.z - A.z) * (C.x - A.x) - (B.x - A.x) * (C.z - A.z), (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x) }; // 寻找绝对值最大的轴 int ignoreAxis 0; if (fabs(normal.y) fabs(normal.x)) ignoreAxis 1; if (fabs(normal.z) fabs(normal.x) fabs(normal.z) fabs(normal.y)) ignoreAxis 2; // 定义一个映射函数把 Vec3 降维成 Vec2扔掉 ignoreAxis auto project [](const Vec3 v) - Vec2 { if (ignoreAxis 0) return {v.y, v.z}; if (ignoreAxis 1) return {v.x, v.z}; return {v.x, v.y}; }; Vec2 A2 project(A), B2 project(B), C2 project(C), P2 project(P); // 用 2D 面积比法计算 double totalArea cross2D(A2, B2, C2); if (fabs(totalArea) 1e-8) return false; // 注意面积比公式alpha Area(PBC) / Area(ABC) // 但叉积方向要一致否则会得到负面积这里必须统一方向 alpha cross2D(P2, B2, C2) / totalArea; beta cross2D(A2, P2, C2) / totalArea; gamma cross2D(A2, B2, P2) / totalArea; // 内部检查软渲染器通常包含边界 return (alpha 0 beta 0 gamma 0); }3光栅化边缘函数法GPUstruct Vec2i { int x, y; }; // 整数屏幕坐标 // 计算边函数 (对于顶点 A-B判断点 P 在左侧还是右侧) int edgeFunction(const Vec2i A, const Vec2i B, const Vec2i P) { return (B.x - A.x) * (P.y - A.y) - (B.y - A.y) * (P.x - A.x); } // 三角形光栅化测试 (假设 A,B,C 为逆时针顺序) bool isInsideTriangle(const Vec2i A, const Vec2i B, const Vec2i C, const Vec2i P) { // 如果三个边函数全部 0则点在内部 int e1 edgeFunction(A, B, P); int e2 edgeFunction(B, C, P); int e3 edgeFunction(C, A, P); return (e1 0 e2 0 e3 0); } // 如何从边函数得到真正的重心坐标用于插值 // 当扫描到像素 P 时真实的 alpha e1 / e1_total // 其中 e1_total edgeFunction(A, B, C) 注意顺序 A-B 是边但对顶点C做边函数 void getBarycentricFromEdges(const Vec2i A, const Vec2i B, const Vec2i C, const Vec2i P, double alpha, double beta, double gamma) { double e1 edgeFunction(B, C, P); // 对顶点 A 的对面边 BC double e2 edgeFunction(C, A, P); // 对顶点 B 的对面边 CA double e3 edgeFunction(A, B, P); // 对顶点 C 的对面边 AB double total edgeFunction(B, C, A); // 注意顺序必须统一B-C-A // 或者 total e1 e2 e3 因为线性关系 alpha e1 / total; beta e2 / total; gamma e3 / total; }利用中心坐标进行属性插值算重心坐标不是为了好看是为了平滑插值颜色、UV、法线struct Attribute { double r, g, b; }; // 假设顶点的颜色属性 Attribute interpolateAttribute(const Attribute A, const Attribute B, const Attribute C, double alpha, double beta, double gamma) { Attribute result; result.r alpha * A.r beta * B.r gamma * C.r; result.g alpha * A.g beta * B.g gamma * C.g; result.b alpha * A.b beta * B.b gamma * C.b; return result; }工业级致命细节透视校正插值必须看你在屏幕空间经过视口变换后算出来的重心坐标(alpha, beta, gamma)是屏幕空间的重心坐标。但是如果你想插值世界空间/观察空间下的属性如深度 Z、纹理 UV、光照法线不能直接插值原因投影变换破坏了线性关系透视除法导致屏幕空间和观察空间不是线性映射。正确做法透视校正插值你要分别保存每个顶点的1/w即观察空间深度的倒数也就是clip.w的倒数。假设顶点 A 的w为B 的​C 的​。设屏幕空间重心坐标为。先计算插值后的1/w然后再计算插值后的属性 / w最后真实的插值属性为struct VertexOut { double x, y, z; // 屏幕坐标 double u, v; // 纹理坐标 double invW; // 1 / clip.w }; double interpolatePerspective(double attrA, double invWA, double attrB, double invWB, double attrC, double invWC, double alpha, double beta, double gamma) { // 1. 插值 (attr / w) double attr_over_w alpha * (attrA * invWA) beta * (attrB * invWB) gamma * (attrC * invWC); // 2. 插值 (1 / w) double inv_w_final alpha * invWA beta * invWB gamma * invWC; // 3. 相除还原 return attr_over_w / inv_w_final; }如果不做透视校正纹理会在屏幕上呈现严重的“扭曲”和“弯曲”3D 物体旋转时纹理像粘在硬纸板上滑动。做了透视校正后纹理才会像真实世界一样有立体感三角形重心坐标计算1. 背景介绍三角形是计算机图形学中最常用的表面表示单元。复杂模型通常会被离散成大量三角形渲染器再逐个处理这些三角形。因此判断一个二维点是否落在三角形内部是光栅化、鼠标拾取、二维几何判断和简单碰撞检测中的基础问题。重心坐标提供了一种描述 点相对于三角形三个顶点位置关系 的方式。它不仅可以用于判断点是否位于三角形内部还可以作为三角形内部属性插值的权重。在实际渲染中顶点颜色、深度、纹理坐标、法向量等信息都需要从顶点传播到三角形内部的像素位置。本题将这些应用背景简化为二维平面中的点与三角形关系判断。学生需要输出查询点是否位于三角形内并在内部时给出该点相对于三个顶点的权重结果。2. 题目描述给定二维三角形和若干查询点判断查询点是否位于三角形内部或边界上并在内部时输出相对于三个顶点的重心坐标。本题只要求输出指定数值结果不要求生成图片或调用图形 API。输入数据规模较小重点在于正确理解几何约定、坐标约定和输出格式。支持语言本题支持使用 Python 3 或 C17 实现。程序必须从标准输入读取数据并将答案输出到标准输出不要输出额外提示文字、调试信息或文件路径。3. 输入格式plaintext1 ax ay 2 bx by 3 cx cy 4 Q 5 qx0 qy0 6 qx1 qy1 7 ...4. 输入数据含义ax ay两个实数表示三角形第一个顶点 A 的二维坐标。bx by两个实数表示三角形第二个顶点 B 的二维坐标。cx cy两个实数表示三角形第三个顶点 C 的二维坐标。Q整数表示需要判断的查询点数量。qxi qyi两个实数表示第 i 个查询点的二维坐标。查询点按输入顺序逐个输出结果。5. 输出格式对每个查询点输出一行。若查询点在三角形内部或边界上输出:plaintext1 inside alpha beta gamma若查询点在三角形外部输出:plaintext1 outside其中:alpha查询点相对于顶点 A 的重心坐标权重。beta查询点相对于顶点 B 的重心坐标权重。gamma查询点相对于顶点 C 的重心坐标权重。浮点数保留 6 位小数。C 中可使用cout fixed setprecision(6);Python 中可使用格式化字符串如f{x:.6f}。OJ 判题时会按题面约定检查输出格式和数值结果。6. 重要约定边界点应被视为inside。输出重心坐标时三个权重的顺序必须对应输入顶点 A B C。测试数据中的三角形均为非退化三角形。三角形顶点顺序可能为顺时针或逆时针程序不应依赖固定方向。输出时不要添加额外说明文字。7. 数据范围1 ≤ Q ≤ 500坐标为有限实数三角形面积不为 08. 测试数据说明输入plaintext1 0 0 2 2 0 3 0 2 4 4 5 0.5 0.5 6 1 1 7 2 2 8 0 1输出plaintext1 inside 0.500000 0.250000 0.250000 2 inside 0.000000 0.500000 0.500000 3 outside 4 inside 0.500000 0.000000 0.500000代码实现#includeiostream #includevector #include iomanip using namespace std; const double eps 1e-8; struct Point { double x_; double y_; Point(double x 0.0, double y 0.0) : x_(x), y_(y) {} }; double Cross(const Point A, const Point B) { return A.x_ * B.y_ - B.x_ * A.y_; } int main() { Point A, B, C; cin A.x_ A.y_; cin B.x_ B.y_; cin C.x_ C.y_; Point AB(B.x_ - A.x_, B.y_ - A.y_); Point AC(C.x_ - A.x_, C.y_ - A.y_); double f Cross(AC, AB); int N; cin N; vectorPointPoints(N); cout fixed setprecision(6); for (int i 0; i N; i) { cin Points[i].x_ Points[i].y_; } for (int i 0; i N; i) { Point AP(Points[i].x_ - A.x_, Points[i].y_ - A.y_); double t Cross(AP,AB) / f; double s Cross(AP, AC) / -f; double a 1.0 - t - s; if (a -eps s -eps t -eps) { if (a eps)a 0.0; if (s eps)s 0.0; if (t eps)t 0.0; cout inside a s tendl; } else { cout outsideendl; } } }