updateDec 30 2025 点在多边形内概要写在前面简单实现求线段AP在线段AB上的投影长度 求点P在线段AB上的投影点的坐标 判断点P的投影点是否在线段AB内 求∠PAB的角度值 判断∠PAB是锐角、直角还是钝角。 求向量AP和AB组成的平行四边形的面积 若有另外一点Q判断向量PQ与AB是否平行 判断点P在向量AB的左侧还是右侧。方法有三种向量法可以求的答案多、此外还有面积法和待定系数求解法设pp的坐标为x,y直接推导#includeiostream#includealgorithm#includecmath#includethread#includemutex#includeiostream#includeglog/logging.husingnamespacestd;intmain(intargc,char*argv[]){google::InitGoogleLogging(argv[0]);google::SetStderrLogging(google::GLOG_ERROR);FLAGS_colorlogtostderrtrue;FLAGS_logtostderrtrue;FLAGS_minloglevel0;// questionsfloatdistance_PtoAB0;pairint,intamake_pair(1,1);pairint,intbmake_pair(2,4);pairint,intpmake_pair(3,3);pairint,intapmake_pair(2,2);pairint,intabmake_pair(1,3);pairint,intbpmake_pair(1,-1);pairint,intbamake_pair(-1,-3);floatAP_lsqrt(ap.first*ap.firstap.second*ap.second);floatBP_lsqrt(bp.first*bp.firstbp.second*bp.second);floatAB_lsqrt(ab.first*ab.firstab.second*ab.second);floatthetaPAB_cos(ap.first*ab.firstap.second*ab.second)/AP_l/AB_l;floatthetaABP_cos(ba.first*bp.firstba.second*bp.second)/BP_l/AB_l;LOG(INFO)thetaPAB_cos: thetaPAB_cos;LOG(INFO)thetaABP_cos: thetaABP_cos;coutthetaPAB: acos(thetaPAB_cos)endl;if(thetaPAB_cos0){distance_PtoABsqrt(ap.first*ap.firstap.second*ap.second);if(thetaPAB_cos!0){coutPAB is obtuse angleendl;coutProject of P is outside ABendl;}}elseif(thetaABP_cos0){distance_PtoABsqrt(bp.first*bp.firstbp.second*bp.second);if(thetaABP_cos!0){coutPAB is acute angleendl;coutProject of P is outside ABendl;}}else{distance_PtoAB(ap.first)*sqrt((1-thetaPAB_cos*thetaPAB_cos));coutPAB is acute angleendl;coutProject of P(PP) is inside ABendl;// cal unit vector of ABpairfloat,floatAB_unitvector(ab.first/AB_l,ab.second/AB_l);LOG(INFO)AB_unitvector: AB_unitvector.first,AB_unitvector.second;floatAPP_l(ap.first*ab.firstap.second*ab.second)/AB_l;pairfloat,floatAPP(APP_l*AB_unitvector.first,APP_l*AB_unitvector.second);pairfloat,floatPP(APP.first-a.first,APP.second-a.second);coutand the PP is PP.first,PP.secondendl;}std::coutdistance_PtoAB: distance_PtoABstd::endl;google::ShutdownGoogleLogging();}sin相关求向量AP和AB组成的平行四边形的面积 若有另外一点Q判断向量PQ与AB是否平行 判断点P在向量AB的左侧还是右侧。问题比较简单 通过观察叉乘的结果就可以判断判断点P在向量AB的左侧还是右侧 用叉乘顺逆时针即可判断。 向量BA和PA做叉乘右手螺旋纸外为正。从BA到PA。cross (B − A) × (P − A) (Bx−Ax)(Py−Ay) − (By−Ay)(Px−Ax)cross EPS ⇒ P 在 AB 的左侧逆时针cross −EPS ⇒ P 在 AB 的右侧顺时针|cross| ≤ EPS ⇒ 共线向量 PQ 与 AB 是否平行仍用叉乘判断两向量的“面积”为 0。crossABPQ (B−A) × (Q−P)|crossABPQ| ≤ EPS ⇒ 平行含同向/反向方向区分dot (B−A)·(Q−P)dot 0 同向dot 0 反向判定点在多边形内在工作中涉及到了雷达的遮蔽问题某个细节需要能判定点在多边形内实际上是四个角落雷达设定了重叠区域和非重叠区域划分了多边形同时对于object 通过设置代表了是那个传感器看到的bitmask此时需要判定一下object是否在fov和探测距离分段划分好的多边形内工程细节不论概要是1 多边形顶点要够 代码里设定为大于32 临接多边形顶点遍历 并且排除水平可能性3 点与边的判断 要点是水平向右以pt点为起点做射线 1 pt点的y在边的顶点y中间 2 插值法看到 pt点x小于交点x 同时满足1 和2设定相交一次射线遍历多边形所有边后相交次数为偶数则点在多边形外 反之在内。0 这里也是算不在if(((vi_ypt_y)!(vj_ypt_y))(pt_x(vj_x-vi_x)*(pt_y-vi_y)/y_diffvi_x)){inside!inside;}AI 再此归纳 简单的计算几何问题8个向量问题的求解方法设坐标\vec{A} (x_A, y_A)\vec{B} (x_B, y_B)\vec{P} (x_P, y_P)① 线段AP在AB上的投影长度思路投影长度 AP 在 AB 方向上的标量投影t \frac{\vec{AP} \cdot \vec{AB}}{|\vec{AB}|} \frac{(P_x - A_x)(B_x - A_x) (P_y - A_y)(B_y - A_y)}{\sqrt{(B_x - A_x)^2 (B_y - A_y)^2}}⚠️ 这里 t 可正可负表示投影方向与 AB 相同或相反。若只求长度取绝对值 |t|。② 点P在AB上的投影点坐标思路参数 t \dfrac{\vec{AP} \cdot \vec{AB}}{\vec{AB} \cdot \vec{AB}}即 0 \le t \le 1 时投影在线段内\vec{H} \vec{A} t \cdot \vec{AB}即H_x A_x t(B_x - A_x)H_y A_y t(B_y - A_y)③ 判断投影点是否在线段AB内思路用上面的 t 值判断0 \le t \le 1 \quad \iff \quad \text{投影点在线段AB上}即判断0 \le \vec{AP} \cdot \vec{AB} \le |\vec{AB}|^2④ ∠PAB的角度值思路用点乘公式求夹角\cos\angle PAB \frac{\vec{AP} \cdot \vec{AB}}{|\vec{AP}||\vec{AB}|}\angle PAB \arccos\left(\frac{\vec{AP} \cdot \vec{AB}}{|\vec{AP}||\vec{AB}|}\right)⑤ 判断∠PAB是锐角/直角/钝角思路只看点乘符号无需算角度条件 结论\vec{AP} \cdot \vec{AB} 0 锐角\vec{AP} \cdot \vec{AB} 0 直角\vec{AP} \cdot \vec{AB} 0 钝角因为 \cos\theta 的正负完全由点乘决定。⑥ 向量AP和AB组成的平行四边形面积思路二维叉乘的模 面积S \left| \vec{AP} \times \vec{AB} \right| \left| (P_x - A_x)(B_y - A_y) - (P_y - A_y)(B_x - A_x) \right|二维叉乘退化为标量行列式值取绝对值即为平行四边形面积。⑦ 判断PQ与AB是否平行思路叉乘为 0 ⟺ 平行\vec{PQ} \times \vec{AB} 0 \quad \iff \quad (Q_x - P_x)(B_y - A_y) - (Q_y - P_y)(B_x - A_x) 0或者用比例判断\frac{Q_x - P_x}{B_x - A_x} \frac{Q_y - P_y}{B_y - A_y}注意处理分母为 0 的情况⑧ 判断点P在向量AB的左侧还是右侧思路二维叉乘的符号决定左右cross \vec{AB} \times \vec{AP} (B_x - A_x)(P_y - A_y) - (B_y - A_y)(P_x - A_x)cross 符号 结论0 P 在 AB 的左侧逆时针 0 P 在 AB 直线上 0 P 在 AB 的右侧顺时针 总结公式速查点乘 AP · AB dx1dx2 dy1dy2 → 投影、角度、左右判断叉乘 AP × AB dx1dy2 - dy1dx2 → 面积、平行、左右判断参数 tt (AP·AB) / |AB|² → 投影点、是否在线段内 核心技巧几乎所有问题都归结为点乘和叉乘两个运算掌握这两个工具就能解决全部8个问题。