行为
功能 #441
打开如何判断一维线段是否重叠？
状态:
新建
优先级:
普通
指派给:
-
开始日期:
2025-09-19
计划完成日期:
% 完成:
0%
预期时间:
#2:
描述
一、问题重述¶
我们需要判断两个一维线段是否重叠。一维线段可以用区间表示，例如线段A为 [a1, a2]，线段B为 [b1, b2]，其中 a1 ≤ a2，b1 ≤ b2。
二、直观理解¶
两个线段重叠意味着它们在数轴上有公共部分。换句话说，存在一个点 x，使得 x 同时属于 [a1, a2] 和 [b1, b2]。
三、逻辑推理¶
为了找到重叠的条件，我们可以考虑不重叠的情况，然后取反。
1. 不重叠的情况¶
两个线段不重叠有两种情况：
- 线段A完全在线段B的左侧：a2 < b1
- 线段A完全在线段B的右侧：a1 > b2
2. 重叠的条件¶
重叠是不重叠的反面，因此重叠的条件为：
¬(a2 < b1 ∨ a1 > b2)
即：
a2 ≥ b1 且 a1 ≤ b2
3. 验证¶
我们可以用几个例子验证这个条件：
- 例子1：A = [1, 3], B = [2, 4]
a2 = 3 ≥ b1 = 2，且 a1 = 1 ≤ b2 = 4 → 重叠（正确） - 例子2：A = [1, 2], B = [3, 4]
a2 = 2 < b1 = 3 → 不重叠（正确） - 例子3：A = [3, 4], B = [1, 2]
a1 = 3 > b2 = 2 → 不重叠（正确） - 例子4：A = [1, 4], B = [2, 3]
a2 = 4 ≥ b1 = 2，且 a1 = 1 ≤ b2 = 3 → 重叠（正确）
四、总结¶
两个一维线段 [a1, a2] 和 [b1, b2] 重叠的条件是：
a2 ≥ b1 且 a1 ≤ b2
五、扩展¶
如果需要计算重叠部分的长度，可以：
- 先判断是否重叠（满足上述条件）。
- 如果重叠，重叠部分为 [max(a1, b1), min(a2, b2)]，长度为 min(a2, b2) - max(a1, b1)。
六、最终答案¶
两个一维线段 [a1, a2] 和 [b1, b2] 重叠的条件是：
(\boxed{a_2 \geq b_1 \text{ 且 } a_1 \leq b_2})
由 李立奎 更新于 4 个月 之前
如何判断二维线段是否重叠？¶
判断两条二维线段是否重叠，比一维情况复杂得多。
“重叠”在二维里可能有三种含义：
- 共线且有一段公共部分（真正的“重叠”）。
- 仅有一个交点（严格说叫“相交”而非“重叠”）。
- 线段完全相同或部分重合。
下面给出**“共线且有公共部分”**这一最严格定义的判定算法，这也是工程里通常说的“二维线段重叠”。
一、核心思路
两条线段 AB 和 CD 满足
① 四点共线 ② 在公共直线上的一维投影区间重叠。
二、算法步骤（浮点可带容差 ε）
输入：线段1 A(x₁,y₁) → B(x₂,y₂)
线段2 C(x₃,y₃) → D(x₄,y₄)
容差 ε（通常 1e-8）
-
快速排斥（包围盒快速剔除）
min₁x = min(x₁,x₂); max₁x = max(x₁,x₂); …
若矩形 [min₁x,max₁x]×[min₁y,max₁y] 与
矩形 [min₂x,max₂x]×[min₂y,max₂y] 无交，则返回 false。 -
方向叉积检验共线
计算
ABC = (B−A)×(C−A) = (x₂−x₁)(y₃−y₁) − (y₂−y₁)(x₃−x₁)
ABD = (B−A)×(D−A)
若 |ABC|>ε 或 |ABD|>ε，则四点不共线 → 返回 false。 -
把问题降到一维
取单位方向向量 u = (B−A)/‖B−A‖（若 A=B 则直接算 AC 与 AD 是否同向且长度≤ε）。
计算四点在线段 AB 所在直线上的有向投影（内积）：
t₁ = 0 // A
t₂ = (B−A)·u = ‖B−A‖ // B
t₃ = (C−A)·u
t₄ = (D−A)·u
得到两条一维区间 I₁ = [min(t₁,t₂), max(t₁,t₂)]
I₂ = [min(t₃,t₄), max(t₃,t₄)] -
调用一维重叠测试
若 I₁ 与 I₂ 重叠（即 max(start) ≤ min(end)），则返回 true，否则 false。
三、复杂度
上述全程 O(1) 时间、O(1) 空间，仅含若干次加减乘除和两次比较。
四、代码模板（Python，含 ε）
import math
def seg2d_overlap(a1, a2, b1, b2, eps=1e-8):
(x1,y1), (x2,y2) = a1, a2
(x3,y3), (x4,y4) = b1, b2
# 1. 快速排斥
def bbox(p, q):
return (min(p[0],q[0]), max(p[0],q[0]), min(p[1],q[1]), max(p[1],q[1]))
l1 = bbox(a1,a2); l2 = bbox(b1,b2)
if l1[1] < l2[0]-eps or l2[1] < l1[0]-eps: return False
if l1[3] < l2[2]-eps or l2[3] < l1[2]-eps: return False
# 2. 叉积共线
cross = lambda u,v: u[0]*v[1] - u[1]*v[0]
ab = (x2-x1, y2-y1)
abc = cross(ab, (x3-x1, y3-y1))
abd = cross(ab, (x4-x1, y4-y1))
if abs(abc) > eps or abs(abd) > eps:
return False
# 3. 降维投影
len2 = ab[0]*ab[0] + ab[1]*ab[1]
if len2 < eps*eps: # 线段1退化成一个点
return (math.hypot(x3-x1,y3-y1) <= eps and
math.hypot(x4-x1,y4-y1) <= eps)
t1, t2 = 0.0, math.sqrt(len2)
t3 = ((x3-x1)*ab[0] + (y3-y1)*ab[1]) / math.sqrt(len2)
t4 = ((x4-x1)*ab[0] + (y4-y1)*ab[1]) / math.sqrt(len2)
i1 = (min(t1,t2), max(t1,t2))
i2 = (min(t3,t4), max(t3,t4))
# 4. 一维重叠
return i1[1] >= i2[0]-eps and i2[1] >= i1[0]-eps
五、常见误区
- 只判断“相交”——那样会漏掉共线但端点不重合的情况。
- 直接用参数方程求交点——共线时方程组退化，需要特殊处理。
- 忽略浮点精度——必须引入 ε 容差。
六、一句话总结
“二维线段重叠” ⇔ 四点共线且它们在一维投影区间重叠。
按上面 4 步即可 O(1) 判定。
由 李立奎 更新于 4 个月 之前
用c 实现¶
下面给出一份完整、可直接编译运行的 C11 代码，实现「二维线段是否重叠」的判定。
核心思路与前面完全一致：
- 快速包围盒剔除
- 叉积验证四点共线
- 把 4 个端点投影到线段所在直线，变为一维区间重叠问题
- 浮点比较带 EPS 容差
-------------------------------- seg2d_overlap.c --------------------------------
#include <stdio.h>
#include <math.h>
#include <stdbool.h>
#define EPS 1e-8
typedef struct { double x, y; } Point;
/* 二维向量叉积 */
static double cross(const Point a, const Point b)
{
return a.x * b.y - a.y * b.x;
}
/* 快速包围盒测试 */
static bool bbox_overlap(const Point p1, const Point q1,
const Point p2, const Point q2)
{
double min1x = fmin(p1.x, q1.x), max1x = fmax(p1.x, q1.x);
double min1y = fmin(p1.y, q1.y), max1y = fmax(p1.y, q1.y);
double min2x = fmin(p2.x, q2.x), max2x = fmax(p2.x, q2.x);
double min2y = fmin(p2.y, q2.y), max2y = fmax(p2.y, q2.y);
if (max1x < min2x - EPS || max2x < min1x - EPS) return false;
if (max1y < min2y - EPS || max2y < min1y - EPS) return false;
return true;
}
/* 判断两条线段是否共线且有公共部分 */
bool seg2d_overlap(const Point a1, const Point a2,
const Point b1, const Point b2)
{
/* 1. 包围盒快速剔除 */
if (!bbox_overlap(a1, a2, b1, b2)) return false;
/* 2. 叉积验证四点共线 */
Point ab = { a2.x - a1.x, a2.y - a1.y };
double abc = cross(ab, (Point){ b1.x - a1.x, b1.y - a1.y });
double abd = cross(ab, (Point){ b2.x - a1.x, b2.y - a1.y });
if (fabs(abc) > EPS || fabs(abd) > EPS) return false;
/* 3. 把问题降到一维：投影到直线 a1a2 上 */
double len2 = ab.x * ab.x + ab.y * ab.y;
if (len2 < EPS * EPS) { /* 线段 a 退化为点 */
double d1 = hypot(b1.x - a1.x, b1.y - a1.y);
double d2 = hypot(b2.x - a1.x, b2.y - a1.y);
return d1 <= EPS && d2 <= EPS;
}
double inv = 1.0 / sqrt(len2);
double t1 = 0.0;
double t2 = sqrt(len2);
double t3 = ((b1.x - a1.x) * ab.x + (b1.y - a1.y) * ab.y) * inv;
double t4 = ((b2.x - a1.x) * ab.x + (b2.y - a1.y) * ab.y) * inv;
double i1min = fmin(t1, t2), i1max = fmax(t1, t2);
double i2min = fmin(t3, t4), i2max = fmax(t3, t4);
/* 4. 一维区间重叠测试 */
return i1max >= i2min - EPS && i2max >= i1min - EPS;
}
/* ---------------- 测试 ---------------- */
int main(void)
{
Point a1 = {0, 0}, a2 = {4, 4};
Point b1 = {2, 2}, b2 = {6, 6};
printf("%s\n", seg2d_overlap(a1, a2, b1, b2) ? "overlap" : "no overlap");
Point c1 = {0, 0}, c2 = {1, 1};
Point d1 = {2, 2}, d2 = {3, 3};
printf("%s\n", seg2d_overlap(c1, c2, d1, d2) ? "overlap" : "no overlap");
return 0;
}
-------------------------------- 使用说明 --------------------------------
$ gcc seg2d_overlap.c -lm -std=c11 -O2
$ ./a.out
overlap
no overlap
代码无任何第三方依赖，可直接嵌入工程。
由 李立奎 更新于 4 个月 之前
inline bool
IsOverlap(const double& a1,
const double& a2,
const double& b1,
const double& b2,
double eps = 1e-8)
{
return a2 >= b1 - eps && b2 >=a1 - eps;
}
class XPoint2d
{
public:
double m_x, m_y;
public:
XPoint2d(const double &x, const double &y)
:m_x(x),m_y(y){}
double len() const {
return std::hypot(m_x, m_y);
}
double dot(const XPoint2d &r) const {
return m_x * r.m_x + m_y * r.m_y;
}
double cross(const XPoint2d &r) const {
return m_x * r.m_y - m_y * r.m_x;
}
double abs_cross(const XPoint2d &r) const {
return std::fabs(cross(r));
}
XPoint2d operator-(const XPoint2d &r) const {
return XPoint2d(m_x - r.m_x, m_y - r.m_y);
}
} ;
class XBBox2d
{
public:
XPoint2d m_ptMin;
XPoint2d m_ptMax;
public:
XBBox2d(const XPoint2d &ptMin, const XPoint2d &ptMax)
:m_ptMin(ptMin),m_ptMax(ptMax){}
bool isDisjoint(const XBBox2d &r, double eps = 1e-8) const {
return m_ptMax.m_x < r.m_ptMin.m_x - eps ||
r.m_ptMax.m_x < m_ptMin.m_x - eps ||
m_ptMax.m_y < r.m_ptMin.m_y - eps ||
r.m_ptMax.m_y < m_ptMin.m_y - eps;
}
bool IsOverlap(const XBBox2d &r, double eps = 1e-8) const {
return !isDisjoint(r, eps);
}
};
class XLineSeg2d
{
public:
XPoint2d m_ptStart;
XPoint2d m_ptEnd;
public:
XLineSeg2d(const XPoint2d &ptStart, const XPoint2d &ptEnd)
:m_ptStart(ptStart),m_ptEnd(ptEnd){}
XBBox2d GetBBox() const {
return XBBox2d(
XPoint2d(std::min(m_ptStart.m_x, m_ptEnd.m_x),
std::min(m_ptStart.m_y, m_ptEnd.m_y)),
XPoint2d(std::max(m_ptStart.m_x, m_ptEnd.m_x),
std::max(m_ptStart.m_y, m_ptEnd.m_y)));
}
bool IsOverlap(const XLineSeg2d &other, double eps = 1e-8) const {
//if (GetBBox().isDisjoint(other.GetBBox(), eps))
// return false;
XPoint2d ac = other.m_ptStart - m_ptStart;
XPoint2d ad = other.m_ptEnd - m_ptStart;
XPoint2d ab = m_ptEnd - m_ptStart;
if (ab.abs_cross(ac) > eps)
return false;
if (ab.abs_cross(ad) > eps)
return false;
double len2 = ab.dot(ab);
if (len2 < eps * eps)
return ac.len() <= eps && ad.len() <= eps;
double t2 = std::sqrt(len2);
double inv = 1.0 / t2;
double t3 = ac.dot(ab) * inv;
double t4 = ad.dot(ab) * inv;
double i2min = std::min(t3, t4),
i2max = std::max(t3, t4);
return ::IsOverlap(0.0,t2,i2min,i2max,eps);
}
};
class CWallInfo
{
public:
XLineSeg2d m_ln;
double m_Thick;
double m_H;
double m_E;
XBBox2d m_box;
public:
CWallInfo(const XLineSeg2d &ln)
:m_ln(ln),
m_Thick(200),m_H(3000),m_E(0),
m_box(ln.GetBBox())
{}
double GetTop() const {
return m_E + m_H;
}
bool IsOverlap(const CWallInfo &r, double eps = 1e-8) const {
if (!::IsOverlap(m_E, GetTop(), r.m_E, r.GetTop(), eps))
return false;
if (m_box.isDisjoint(r.m_box, eps))
return false;
return m_ln.IsOverlap(m_ln, eps);
}
};
class CWallInfos
{
public:
std::vector<CWallInfo> m_arWallInfo;
public:
bool IsOverlap(const CWallInfo &rWallInfo, double eps = 1e-8) const{
for (size_t i=0;i<m_arWallInfo.size();++i){
if (rWallInfo.IsOverlap(m_arWallInfo[i], eps))
return true;
}
return false;
}
bool Add(const CWallInfo &rWallInfo, double eps = 1e-8){
if (IsOverlap(rWallInfo, eps))
return false;
m_arWallInfo.push_back(rWallInfo);
return true;
}
};
由 李立奎 更新于 4 个月 之前
计算点到直线的距离¶
计算二维点 P 到直线 AB 的距离，只需一行向量公式：
1. 几何公式（无需开方，先算面积再求高）¶
double distancePointToLine(const XPoint2d& A,
const XPoint2d& B,
const XPoint2d& P,
double eps = 1e-8)
{
XPoint2d ab = B - A;
XPoint2d ap = P - A;
double crossVal = ab.cross(ap); // 平行四边形面积 ×2
double len = hypot(ab.m_x, ab.m_y);
if (len < eps) // AB 退化成一个点
return hypot(ap.m_x, ap.m_y); // 直接返回 AP 距离
return fabs(crossVal) / len; // 面积 / 底边 = 高
}
- crossVal = |AB|·h → h = |crossVal| / |AB|
- 只调用一次
hypot（或sqrt），效率最高。
2. 另一种写法（参数式，结果相同）¶
double t = (ap.m_x * ab.m_x + ap.m_y * ab.m_y) / (ab.m_x * ab.m_x + ab.m_y * ab.m_y);
XPoint2d proj(A.m_x + t * ab.m_x, A.m_y + t * ab.m_y);
return hypot(P.m_x - proj.m_x, P.m_y - proj.m_y);
- 先求垂足，再算两点距离；
- 需要开方两次，稍慢，但可额外得到垂足坐标。
3. 使用示例¶
XPoint2d A(0, 0), B(4, 4), P(1, 3);
printf("dist = %.6f\n", distancePointToLine(A, B, P)); // 输出 1.414214
一句话总结¶
点到直线距离 = |AB × AP| / |AB|，一行代码即可。
行为