前言判断平面内两条线段的位置关系是计算几何里最基础也最容易写错的一类问题。它看似只有「相交」和「不相交」两种答案实际至少要区分两条线段在内部真正穿过、只在端点相接、共线且部分重叠、共线但分离、完全平行且分离。如果只写一个「跨立」判断端点接触和共线重叠都会被漏掉如果直接用浮点数算斜率垂直线段又会除零。另一个常见误区是把「直线相交」当成「线段相交」。两条直线总有交点平行除外但交点可能落在两条线段的延长线上线段判定必须额外检查交点是否位于两条线段的参数范围内。本文用向量叉积cross product做方向判断全程只比较符号与大小不引入除法因而对整数坐标是精确的。示例以 C17 为基准坐标使用long long。文中会说明整数溢出的边界、浮点容差的用法以及退化线段两个端点重合的处理。代码按标准语义推演不声称在某个编译器上运行过。一、用叉积判断点的方向给定三点O、A、B定义二维叉积cross(O, A, B) (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x)它的几何意义是三角形OAB有向面积的两倍。符号告诉我们B在向量OA的哪一侧符号含义共线时的补充大于 0B在OA左侧逆时针—小于 0B在OA右侧顺时针—等于 0三点共线还需判断B是否落在线段OA上叉积只用到乘法与减法不涉及除法因此整数输入下结果是精确的代价是乘法可能溢出后文详述。用叉积而不是斜率还避免了垂直线段斜率无穷大的问题——这是计算几何里优先用向量法的直接原因。// 适用于 C17#include algorithmstruct Point {long long x 0;long long y 0;};bool operator(const Point lhs, const Point rhs) {return lhs.x rhs.x lhs.y rhs.y;}long long cross(const Point o, const Point a, const Point b) {return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);}int sign(long long value) {if (value 0) return 1;if (value 0) return -1;return 0;}sign返回 -1、0、1之后所有判断都只依赖符号不需要关心叉积的具体数值。这也让逻辑更容易测试只要符号对结论就对。二、跨立实验内部相交的判定两条线段AB与CD在内部相交等价于「C、D分别位于直线AB的两侧」且「A、B分别位于直线CD的两侧」。用叉积表达就是sign(cross(A, B, C)) ! sign(cross(A, B, D))且sign(cross(C, D, A)) ! sign(cross(C, D, B))严格来说还要排除某一侧为 0 的情况——那表示端点落在另一条线段的直线上属于后续要单独处理的边界情况。因此「严格跨立」要求两组叉积都非零且异号。// 适用于 C17bool proper_intersect(const Point a, const Point b,const Point c, const Point d) {const long long d1 cross(a, b, c);const long long d2 cross(a, b, d);const long long d3 cross(c, d, a);const long long d4 cross(c, d, b);return ((d1 0 d2 0) || (d1 0 d2 0)) ((d3 0 d4 0) || (d3 0 d4 0));}这个函数只回答「是否在内部穿过」。如果题目只要求二值答案「相交/不相交」还需要补上端点与共线的情况否则会漏判。举一个反例A(0,0)、B(2,0)、C(2,0)、D(2,2)两条线段在BC处相接但cross(A,B,C)0严格跨立不成立proper_intersect返回false。三、共线、端点与退化情况完整判定需要先定义「点P在线段AB上」。在已知三点共线叉积为 0的前提下只需检查P的坐标是否落在A、B构成的包围盒内// 适用于 C17bool on_segment(const Point a, const Point b, const Point p) {return std::min(a.x, b.x) p.x p.x std::max(a.x, b.x) std::min(a.y, b.y) p.y p.y std::max(a.y, b.y);}这个函数假设三点已经共线。如果直接对任意点调用它会把包围盒内的非共线点也判为在线段上所以调用前必须先确认cross(a, b, p) 0。完整的相交判定按以下顺序进行计算四个叉积d1 cross(A,B,C)、d2 cross(A,B,D)、d3 cross(C,D,A)、d4 cross(C,D,B)。如果两组都严格异号返回「内部相交」。否则若d1 0且C在线段AB上相交C是接触点对d2、d3、d4同理。都不满足则不相交。第 3 步的四个条件缺一不可d1 0只说明C在直线AB上还要确认它落在线段范围内四个条件分别覆盖「C碰AB」「D碰AB」「A碰CD」「B碰CD」四种接触方式。// 适用于 C17bool segments_intersect(const Point a, const Point b,const Point c, const Point d) {const long long d1 cross(a, b, c);const long long d2 cross(a, b, d);const long long d3 cross(c, d, a);const long long d4 cross(c, d, b);if (((d1 0 d2 0) || (d1 0 d2 0)) ((d3 0 d4 0) || (d3 0 d4 0))) {return true;}if (d1 0 on_segment(a, b, c)) return true;if (d2 0 on_segment(a, b, d)) return true;if (d3 0 on_segment(c, d, a)) return true;if (d4 0 on_segment(c, d, b)) return true;return false;}退化线段A B或C D也能被这套逻辑覆盖若A B则d1与d2都等于 0只需判断该点是否在另一条线段上。但要注意如果两条线段都退化成同一个点四个条件都会命中返回「相交」语义上正确。四、细分关系与交点坐标如果不仅要知道「是否相交」还要知道「属于哪种关系」可以定义一个枚举并单独处理共线// 适用于 C17enum class Relation {Disjoint, // 相离ProperIntersect, // 内部穿过EndpointTouch, // 端点接触CollinearOverlap // 共线且有重叠};Relation classify(const Point a, const Point b,const Point c, const Point d) {if (proper_intersect(a, b, c, d)) {return Relation::ProperIntersect;}if (!segments_intersect(a, b, c, d)) {return Relation::Disjoint;}const long long d1 cross(a, b, c);const long long d2 cross(a, b, d);const long long d3 cross(c, d, a);const long long d4 cross(c, d, b);const bool collinear (d1 0 d2 0 d3 0 d4 0);if (!collinear) {return Relation::EndpointTouch;}// 共线投影到较长的一根轴上判断重叠区间const bool use_x (a.x ! b.x) || (c.x ! d.x);const long long a1 use_x ? a.x : a.y;const long long a2 use_x ? b.x : b.y;const long long c1 use_x ? c.x : c.y;const long long c2 use_x ? d.x : d.y;const long long lo std::max(std::min(a1, a2), std::min(c1, c2));const long long hi std::min(std::max(a1, a2), std::max(c1, c2));return (lo hi) ? Relation::CollinearOverlap : Relation::EndpointTouch;}共线判定用d1 d2 d3 d4 0是否充分对于两条非退化线段只要A、B与C、D分别共线四个叉积都会是 0反过来四个都为 0 说明C、D都在直线AB上确实共线。这里的前提是线段非退化如果允许退化A B时d1 d2 0恒成立就需要改用「方向向量平行」的判断。示例为了简洁假定输入是非退化线段工程代码应显式处理退化情形。求交点坐标时用参数方程。设交点P A t(B - A)代入直线CD的方程可得t cross(C - A, D - C) / cross(B - A, D - C)分母为 0 表示两直线平行或共线此时没有唯一交点。该公式只在「内部相交」时有意义端点接触的交点直接取对应的端点即可。// 适用于 C17struct PointD {double x 0.0;double y 0.0;};bool intersection_point(const Point a, const Point b,const Point c, const Point d,PointD out) {const long long rx b.x - a.x;const long long ry b.y - a.y;const long long sx d.x - c.x;const long long sy d.y - c.y;const long long denom rx * sy - ry * sx;if (denom 0) {return false; // 平行或共线无唯一交点}const long long num (c.x - a.x) * sy - (c.y - a.y) * sx;const double t static_castdouble(num) / static_castdouble(denom);out.x static_castdouble(a.x) t * static_castdouble(rx);out.y static_castdouble(a.y) t * static_castdouble(ry);return true;}把long long转成double再除是因为整数除法会截断。坐标很大时double只有约 15~17 位有效十进制数字交点精度会下降需要高精度时可以用long double或直接以有理数形式保留分子分母。五、完整示例// 适用于 C17#include algorithm#include iostreamstruct Point {long long x 0;long long y 0;};bool operator(const Point lhs, const Point rhs) {return lhs.x rhs.x lhs.y rhs.y;}long long cross(const Point o, const Point a, const Point b) {return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);}bool on_segment(const Point a, const Point b, const Point p) {return std::min(a.x, b.x) p.x p.x std::max(a.x, b.x) std::min(a.y, b.y) p.y p.y std::max(a.y, b.y);}bool segments_intersect(const Point a, const Point b,const Point c, const Point d) {const long long d1 cross(a, b, c);const long long d2 cross(a, b, d);const long long d3 cross(c, d, a);const long long d4 cross(c, d, b);if (((d1 0 d2 0) || (d1 0 d2 0)) ((d3 0 d4 0) || (d3 0 d4 0))) {return true;}if (d1 0 on_segment(a, b, c)) return true;if (d2 0 on_segment(a, b, d)) return true;if (d3 0 on_segment(c, d, a)) return true;if (d4 0 on_segment(c, d, b)) return true;return false;}int main() {// 内部穿过std::cout segments_intersect({0, 0}, {4, 4}, {0, 4}, {4, 0}) \n;// 端点接触std::cout segments_intersect({0, 0}, {2, 0}, {2, 0}, {2, 2}) \n;// 共线重叠std::cout segments_intersect({0, 0}, {3, 0}, {2, 0}, {5, 0}) \n;// 共线分离std::cout segments_intersect({0, 0}, {1, 0}, {2, 0}, {3, 0}) \n;// 平行分离std::cout segments_intersect({0, 0}, {4, 0}, {0, 1}, {4, 1}) \n;return 0;}按判定逻辑推演五组输出应当依次为1、1、1、0、0。第二组是端点接触d1 cross((0,0),(2,0),(2,0)) 0且(2,0)在第一条线段上命中第三个条件。第四组共线但两条线段的 x 区间[0,1]与[2,3]不相交四个条件都不满足返回0。常见坑点❌ 只用「两组叉积异号」判断相交漏掉端点接触与共线重叠。✅ 补充四个「叉积为 0 且点在线段上」的条件。❌ 计算on_segment前不检查叉积是否为 0把包围盒内的非共线点误判为在线段上。✅ 先确认cross(a, b, p) 0再检查包围盒。❌ 用斜率(y2-y1)/(x2-x1)判断方向垂直线段除零。✅ 用叉积只做乘法与减法。❌ 坐标接近10^9时仍用int存叉积乘法溢出是未定义行为。✅ 用long long接近10^9时乘积可达4×10^18已接近long long上限必要时用__int128GCC/Clang 扩展非标准。❌ 对整数坐标用1e-9的浮点容差比较叉积。✅ 整数输入下直接与 0 比较结果是精确的容差只用于浮点输入。❌ 浮点坐标下用 0判断共线因舍入误差永远不成立。✅ 用相对容差并结合坐标量级选择阈值。❌ 求交点时用整数除法num / denom结果被截断为 0。✅ 转成double再除并注意大坐标下的精度损失。❌ 不处理退化线段A B导致共线分支的方向判断失效。✅ 单独处理点在线段上的情形或在文档中明确输入要求。总结判定方法注意点点在哪侧叉积符号只比较符号不做除法内部相交两组叉积严格异号排除某个叉积为 0 的情况端点接触叉积为 0 且点在线段包围盒内四个条件都要检查共线重叠四个叉积全为 0再比较投影区间选非退化的一根轴投影交点坐标参数方程t cross(C-A, D-C) / cross(B-A, D-C)分母为 0 无唯一交点数值稳健整数精确、浮点用容差防溢出、防截断线段位置判定的核心是把几何关系翻译成「符号 边界」的代数条件叉积定方向包围盒定范围参数方程定坐标。把内部相交、端点接触、共线重叠、退化输入这四类情况分别想清楚再根据坐标类型选择精确比较或容差比较代码就能覆盖绝大多数实际场景。 
长河君 · 2026/10/21 16:01:21 · 阅读 1.2k C++／STL实现判断平面内两条线段的位置关系代码示例
前言判断平面内两条线段的位置关系是计算几何里最基础也最容易写错的一类问题。它看似只有「相交」和「不相交」两种答案实际至少要区分两条线段在内部真正穿过、只在端点相接、共线且部分重叠、共线但分离、完全平行且分离。如果只写一个「跨立」判断端点接触和共线重叠都会被漏掉如果直接用浮点数算斜率垂直线段又会除零。另一个常见误区是把「直线相交」当成「线段相交」。两条直线总有交点平行除外但交点可能落在两条线段的延长线上线段判定必须额外检查交点是否位于两条线段的参数范围内。本文用向量叉积cross product做方向判断全程只比较符号与大小不引入除法因而对整数坐标是精确的。示例以 C17 为基准坐标使用long long。文中会说明整数溢出的边界、浮点容差的用法以及退化线段两个端点重合的处理。代码按标准语义推演不声称在某个编译器上运行过。一、用叉积判断点的方向给定三点O、A、B定义二维叉积cross(O, A, B) (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x)它的几何意义是三角形OAB有向面积的两倍。符号告诉我们B在向量OA的哪一侧符号含义共线时的补充大于 0B在OA左侧逆时针—小于 0B在OA右侧顺时针—等于 0三点共线还需判断B是否落在线段OA上叉积只用到乘法与减法不涉及除法因此整数输入下结果是精确的代价是乘法可能溢出后文详述。用叉积而不是斜率还避免了垂直线段斜率无穷大的问题——这是计算几何里优先用向量法的直接原因。// 适用于 C17#include algorithmstruct Point {long long x 0;long long y 0;};bool operator(const Point lhs, const Point rhs) {return lhs.x rhs.x lhs.y rhs.y;}long long cross(const Point o, const Point a, const Point b) {return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);}int sign(long long value) {if (value 0) return 1;if (value 0) return -1;return 0;}sign返回 -1、0、1之后所有判断都只依赖符号不需要关心叉积的具体数值。这也让逻辑更容易测试只要符号对结论就对。二、跨立实验内部相交的判定两条线段AB与CD在内部相交等价于「C、D分别位于直线AB的两侧」且「A、B分别位于直线CD的两侧」。用叉积表达就是sign(cross(A, B, C)) ! sign(cross(A, B, D))且sign(cross(C, D, A)) ! sign(cross(C, D, B))严格来说还要排除某一侧为 0 的情况——那表示端点落在另一条线段的直线上属于后续要单独处理的边界情况。因此「严格跨立」要求两组叉积都非零且异号。// 适用于 C17bool proper_intersect(const Point a, const Point b,const Point c, const Point d) {const long long d1 cross(a, b, c);const long long d2 cross(a, b, d);const long long d3 cross(c, d, a);const long long d4 cross(c, d, b);return ((d1 0 d2 0) || (d1 0 d2 0)) ((d3 0 d4 0) || (d3 0 d4 0));}这个函数只回答「是否在内部穿过」。如果题目只要求二值答案「相交/不相交」还需要补上端点与共线的情况否则会漏判。举一个反例A(0,0)、B(2,0)、C(2,0)、D(2,2)两条线段在BC处相接但cross(A,B,C)0严格跨立不成立proper_intersect返回false。三、共线、端点与退化情况完整判定需要先定义「点P在线段AB上」。在已知三点共线叉积为 0的前提下只需检查P的坐标是否落在A、B构成的包围盒内// 适用于 C17bool on_segment(const Point a, const Point b, const Point p) {return std::min(a.x, b.x) p.x p.x std::max(a.x, b.x) std::min(a.y, b.y) p.y p.y std::max(a.y, b.y);}这个函数假设三点已经共线。如果直接对任意点调用它会把包围盒内的非共线点也判为在线段上所以调用前必须先确认cross(a, b, p) 0。完整的相交判定按以下顺序进行计算四个叉积d1 cross(A,B,C)、d2 cross(A,B,D)、d3 cross(C,D,A)、d4 cross(C,D,B)。如果两组都严格异号返回「内部相交」。否则若d1 0且C在线段AB上相交C是接触点对d2、d3、d4同理。都不满足则不相交。第 3 步的四个条件缺一不可d1 0只说明C在直线AB上还要确认它落在线段范围内四个条件分别覆盖「C碰AB」「D碰AB」「A碰CD」「B碰CD」四种接触方式。// 适用于 C17bool segments_intersect(const Point a, const Point b,const Point c, const Point d) {const long long d1 cross(a, b, c);const long long d2 cross(a, b, d);const long long d3 cross(c, d, a);const long long d4 cross(c, d, b);if (((d1 0 d2 0) || (d1 0 d2 0)) ((d3 0 d4 0) || (d3 0 d4 0))) {return true;}if (d1 0 on_segment(a, b, c)) return true;if (d2 0 on_segment(a, b, d)) return true;if (d3 0 on_segment(c, d, a)) return true;if (d4 0 on_segment(c, d, b)) return true;return false;}退化线段A B或C D也能被这套逻辑覆盖若A B则d1与d2都等于 0只需判断该点是否在另一条线段上。但要注意如果两条线段都退化成同一个点四个条件都会命中返回「相交」语义上正确。四、细分关系与交点坐标如果不仅要知道「是否相交」还要知道「属于哪种关系」可以定义一个枚举并单独处理共线// 适用于 C17enum class Relation {Disjoint, // 相离ProperIntersect, // 内部穿过EndpointTouch, // 端点接触CollinearOverlap // 共线且有重叠};Relation classify(const Point a, const Point b,const Point c, const Point d) {if (proper_intersect(a, b, c, d)) {return Relation::ProperIntersect;}if (!segments_intersect(a, b, c, d)) {return Relation::Disjoint;}const long long d1 cross(a, b, c);const long long d2 cross(a, b, d);const long long d3 cross(c, d, a);const long long d4 cross(c, d, b);const bool collinear (d1 0 d2 0 d3 0 d4 0);if (!collinear) {return Relation::EndpointTouch;}// 共线投影到较长的一根轴上判断重叠区间const bool use_x (a.x ! b.x) || (c.x ! d.x);const long long a1 use_x ? a.x : a.y;const long long a2 use_x ? b.x : b.y;const long long c1 use_x ? c.x : c.y;const long long c2 use_x ? d.x : d.y;const long long lo std::max(std::min(a1, a2), std::min(c1, c2));const long long hi std::min(std::max(a1, a2), std::max(c1, c2));return (lo hi) ? Relation::CollinearOverlap : Relation::EndpointTouch;}共线判定用d1 d2 d3 d4 0是否充分对于两条非退化线段只要A、B与C、D分别共线四个叉积都会是 0反过来四个都为 0 说明C、D都在直线AB上确实共线。这里的前提是线段非退化如果允许退化A B时d1 d2 0恒成立就需要改用「方向向量平行」的判断。示例为了简洁假定输入是非退化线段工程代码应显式处理退化情形。求交点坐标时用参数方程。设交点P A t(B - A)代入直线CD的方程可得t cross(C - A, D - C) / cross(B - A, D - C)分母为 0 表示两直线平行或共线此时没有唯一交点。该公式只在「内部相交」时有意义端点接触的交点直接取对应的端点即可。// 适用于 C17struct PointD {double x 0.0;double y 0.0;};bool intersection_point(const Point a, const Point b,const Point c, const Point d,PointD out) {const long long rx b.x - a.x;const long long ry b.y - a.y;const long long sx d.x - c.x;const long long sy d.y - c.y;const long long denom rx * sy - ry * sx;if (denom 0) {return false; // 平行或共线无唯一交点}const long long num (c.x - a.x) * sy - (c.y - a.y) * sx;const double t static_castdouble(num) / static_castdouble(denom);out.x static_castdouble(a.x) t * static_castdouble(rx);out.y static_castdouble(a.y) t * static_castdouble(ry);return true;}把long long转成double再除是因为整数除法会截断。坐标很大时double只有约 15~17 位有效十进制数字交点精度会下降需要高精度时可以用long double或直接以有理数形式保留分子分母。五、完整示例// 适用于 C17#include algorithm#include iostreamstruct Point {long long x 0;long long y 0;};bool operator(const Point lhs, const Point rhs) {return lhs.x rhs.x lhs.y rhs.y;}long long cross(const Point o, const Point a, const Point b) {return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);}bool on_segment(const Point a, const Point b, const Point p) {return std::min(a.x, b.x) p.x p.x std::max(a.x, b.x) std::min(a.y, b.y) p.y p.y std::max(a.y, b.y);}bool segments_intersect(const Point a, const Point b,const Point c, const Point d) {const long long d1 cross(a, b, c);const long long d2 cross(a, b, d);const long long d3 cross(c, d, a);const long long d4 cross(c, d, b);if (((d1 0 d2 0) || (d1 0 d2 0)) ((d3 0 d4 0) || (d3 0 d4 0))) {return true;}if (d1 0 on_segment(a, b, c)) return true;if (d2 0 on_segment(a, b, d)) return true;if (d3 0 on_segment(c, d, a)) return true;if (d4 0 on_segment(c, d, b)) return true;return false;}int main() {// 内部穿过std::cout segments_intersect({0, 0}, {4, 4}, {0, 4}, {4, 0}) \n;// 端点接触std::cout segments_intersect({0, 0}, {2, 0}, {2, 0}, {2, 2}) \n;// 共线重叠std::cout segments_intersect({0, 0}, {3, 0}, {2, 0}, {5, 0}) \n;// 共线分离std::cout segments_intersect({0, 0}, {1, 0}, {2, 0}, {3, 0}) \n;// 平行分离std::cout segments_intersect({0, 0}, {4, 0}, {0, 1}, {4, 1}) \n;return 0;}按判定逻辑推演五组输出应当依次为1、1、1、0、0。第二组是端点接触d1 cross((0,0),(2,0),(2,0)) 0且(2,0)在第一条线段上命中第三个条件。第四组共线但两条线段的 x 区间[0,1]与[2,3]不相交四个条件都不满足返回0。常见坑点❌ 只用「两组叉积异号」判断相交漏掉端点接触与共线重叠。✅ 补充四个「叉积为 0 且点在线段上」的条件。❌ 计算on_segment前不检查叉积是否为 0把包围盒内的非共线点误判为在线段上。✅ 先确认cross(a, b, p) 0再检查包围盒。❌ 用斜率(y2-y1)/(x2-x1)判断方向垂直线段除零。✅ 用叉积只做乘法与减法。❌ 坐标接近10^9时仍用int存叉积乘法溢出是未定义行为。✅ 用long long接近10^9时乘积可达4×10^18已接近long long上限必要时用__int128GCC/Clang 扩展非标准。❌ 对整数坐标用1e-9的浮点容差比较叉积。✅ 整数输入下直接与 0 比较结果是精确的容差只用于浮点输入。❌ 浮点坐标下用 0判断共线因舍入误差永远不成立。✅ 用相对容差并结合坐标量级选择阈值。❌ 求交点时用整数除法num / denom结果被截断为 0。✅ 转成double再除并注意大坐标下的精度损失。❌ 不处理退化线段A B导致共线分支的方向判断失效。✅ 单独处理点在线段上的情形或在文档中明确输入要求。总结判定方法注意点点在哪侧叉积符号只比较符号不做除法内部相交两组叉积严格异号排除某个叉积为 0 的情况端点接触叉积为 0 且点在线段包围盒内四个条件都要检查共线重叠四个叉积全为 0再比较投影区间选非退化的一根轴投影交点坐标参数方程t cross(C-A, D-C) / cross(B-A, D-C)分母为 0 无唯一交点数值稳健整数精确、浮点用容差防溢出、防截断线段位置判定的核心是把几何关系翻译成「符号 边界」的代数条件叉积定方向包围盒定范围参数方程定坐标。把内部相交、端点接触、共线重叠、退化输入这四类情况分别想清楚再根据坐标类型选择精确比较或容差比较代码就能覆盖绝大多数实际场景。