Handbook of Data Structures and Applications学习:Kinetic Data Structures 2
KDS 的性能度量指标详解
背景理解
KDS（动态数据结构）和经典数据结构的类比：
经典数据结构： KDS（运动学数据结构）：
查询 ←→ 更新 属性读取 ←→ 证书维护
↓ ↓ ↓ ↓
要快 不能太慢 要知道结果 证书不能太多/太贵
KDS 的核心矛盾：知道太少 → 属性计算困难；知道太多 → 维护代价过高。
证书集的选择必须在「经济性」和「稳定性」之间找到平衡。
四大性能指标
1. 响应性（Responsiveness）
通俗理解： 当某个证书失效时，修复的速度要快。
证书失效 = 某个几何关系发生了改变（比如两点的相对顺序翻转）
量化要求： 修复代价是问题规模 n n n 的多对数级别，即：
修复代价 = polylog ( n ) = O ( log k n ) , k 为常数 \text{修复代价} = \text{polylog}(n) = O(\log^k n), \quad k \text{ 为常数} 修复代价=polylog(n)=O(logkn),k 为常数
或者至多 O ( n ) O(n) O(n)。
// 示意：响应性好的 KDS 证书修复
// 假设维护一维点集的最大值，证书：相邻点的顺序关系
#include <iostream>
#include <set>
#include <map>
#include <cmath>
#include <vector>
// 运动中的点
struct Point {
int id;
double pos; // 当前位置
double vel; // 速度（线性运动）
// 在时刻 t 的位置
double posAt(double t) const {
return pos + vel * t;
}
};
// 证书：point[i] 在 point[j] 左边（posAt(t) < posAt(t)）
// 失效时间：两点位置相等的时刻
double failureTime(const Point& a, const Point& b, double curTime) {
// a.pos + a.vel*t = b.pos + b.vel*t
// => t = (b.pos - a.pos) / (a.vel - b.vel)
double dv = a.vel - b.vel;
if (std::abs(dv) < 1e-9) return 1e18; // 平行，永不相交
double t = (b.pos - a.pos) / dv;
return (t > curTime) ? t : 1e18; // 只关心未来
}
// 响应性好：证书失效后，O(log n) 时间内修复
// 这里演示最简单的情况：只交换相邻元素，代价 O(log n)
void repairCertificate(std::vector<Point>& pts, int i, double curTime) {
// 证书 pts[i] < pts[i+1] 失效
// 修复：交换两者，更新相邻证书（只影响常数个证书）
std::swap(pts[i], pts[i + 1]);
// 只需重新计算 i-1,i 和 i+1,i+2 的失效时间
// => O(1) 次重计算，整体 O(log n)（若用优先队列）
std::cout << "[修复] 交换点 " << pts[i].id
<< " 和 " << pts[i+1].id
<< " @ t=" << curTime << "\n";
}
int main() {
// 简单演示
std::vector<Point> pts = {{0, 0.0, 2.0}, // id=0, 初始位置0, 速度2
{1, 3.0, 0.0}}; // id=1, 初始位置3, 速度0
double curTime = 0;
double ft = failureTime(pts[0], pts[1], curTime);
std::cout << "证书失效时间: t=" << ft << "\n";
// 推进到失效时刻
repairCertificate(pts, 0, ft);
return 0;
}
输出示例：
证书失效时间: t=1.5
[修复] 交换点 1 和 0 @ t=1.5
2. 效率性（Efficiency）
通俗理解： KDS 处理的「内部事件」总数，不应远超「真正必要的变化次数」。
定义两类事件：
外部事件（external events）
=
属性本身发生变化的次数
\text{外部事件（external events）} = \text{属性本身发生变化的次数}
外部事件（external events）=属性本身发生变化的次数
内部事件（total events）
=
所有证书失效的总次数
\text{内部事件（total events）} = \text{所有证书失效的总次数}
内部事件（total events）=所有证书失效的总次数
效率要求：
效率比
=
内部事件总数
外部事件数
=
small（多对数级或常数）
\text{效率比} = \frac{\text{内部事件总数}}{\text{外部事件数}} = \text{small（多对数级或常数）}
效率比=外部事件数内部事件总数=small（多对数级或常数）
伪代数运动（pseudo-algebraic motions）的约束： 每个证书在整个运动过程中，从真变假（或假变真）的次数有上界，即：
每个证书的翻转次数
≤
s
(
s
为常数，通常由代数次数决定
)
\text{每个证书的翻转次数} \leq s \quad (s \text{ 为常数，通常由代数次数决定})
每个证书的翻转次数≤s(s 为常数，通常由代数次数决定)
外部事件（真正的结构变化）：
时间轴: ----[*]----------[*]----[*]----------->
↑ ↑ ↑
属性变化 属性变化 属性变化 共3次
内部事件（证书失效）：
时间轴: --[x]--[x]--[x]--[x]--[x]--[x]------>
↑ ↑ ↑ ↑ ↑ ↑
证书 证书 证书 证书 证书 证书 共6次
效率比 = 6/3 = 2 ← 很好！
若效率比 = 1000 ← 很差，做了大量无用功
3. 紧凑性（Compactness）
通俗理解： 证书的数量不能太多，要接近系统自由度的线性量级。
设系统有
n
n
n 个运动对象，自由度为
O
(
n
)
O(n)
O(n)，则：
∣
证书集
∣
=
O
(
n
)
或
O
(
n
log
k
n
)
|\text{证书集}| = O(n) \quad \text{或} \quad O(n \log^k n)
∣证书集∣=O(n)或O(nlogkn)
若证书集大小为
O
(
n
2
)
O(n^2)
O(n2)，则认为不紧凑。
紧凑 KDS（凸包，O(n) 证书）： 不紧凑（O(n²) 证书）：
顶层: 最大值 每对点都有证书：
|------------| p0-p1, p0-p2, ..., p_{n-1}-p_n
上层: 左半最大 右半最大 → n*(n-1)/2 个证书
|------| |------|
底层: p0 p1 p2 p3 n=1000 时：约 500000 个证书！
4. 局部性（Locality）
通俗理解： 每个对象参与的证书数量不能太多。
∀
对象
o
,
∣
{
c
∈
证书集
∣
o
∈
c
}
∣
=
O
(
polylog
(
n
)
)
\forall \text{ 对象 } o, \quad |\{c \in \text{证书集} \mid o \in c\}| = O(\text{polylog}(n))
∀ 对象 o,∣{c∈证书集∣o∈c}∣=O(polylog(n))
为什么重要？ 当一个对象改变运动规律时，需要重新计算它参与的所有证书的失效时间。若参与太多证书，更新代价极高。
// 局部性示意：记录每个点参与的证书数量
#include <iostream>
#include <vector>
#include <unordered_map>
struct Certificate {
int objA, objB; // 参与该证书的两个对象
};
int main() {
int n = 8; // 8个运动点
std::vector<Certificate> certs;
// 好的设计：每个点只参与 O(log n) 个证书（如线段树结构）
// 演示：类似"锦标赛树"的证书结构
//
// 顶层: root
// |-------------|
// 再上层: [0,3] [4,7]
// |-------| |-------|
// 上层: [0,1] [2,3] [4,5] [6,7]
// |---| |---| |---| |---|
// 底层: 0 1 2 3 4 5 6 7
// 相邻层之间的"胜者"证书
// 底层比较（共 n/2 = 4 个证书）
certs.push_back({0, 1}); // 0 vs 1
certs.push_back({2, 3}); // 2 vs 3
certs.push_back({4, 5}); // 4 vs 5
certs.push_back({6, 7}); // 6 vs 7
// 上层比较（共 n/4 = 2 个证书，用胜者代表）
certs.push_back({0, 2}); // 胜者0 vs 胜者2（代表[0,1]组 vs [2,3]组）
certs.push_back({4, 6}); // 胜者4 vs 胜者6
// 顶层（1个证书）
certs.push_back({0, 4}); // 最终冠军比较
// 统计每个对象参与的证书数
std::unordered_map<int, int> participation;
for (auto& c : certs) {
participation[c.objA]++;
participation[c.objB]++;
}
std::cout << "各点参与的证书数（局部性检查）：\n";
for (int i = 0; i < n; i++) {
std::cout << " 点 " << i << " 参与了 "
<< participation[i] << " 个证书\n";
}
// 理想情况：每个点参与 O(log n) ≈ 3 个证书
std::cout << "log2(" << n << ") = " << std::log2(n) << "\n";
return 0;
}
各点参与的证书数（局部性检查）：
点 0 参与了 3 个证书
点 1 参与了 1 个证书
点 2 参与了 2 个证书
点 3 参与了 1 个证书
点 4 参与了 3 个证书
点 5 参与了 1 个证书
点 6 参与了 2 个证书
点 7 参与了 1 个证书
log2(8) = 3
最坏情况参与数为 O ( log n ) O(\log n) O(logn)，局部性良好。
四大指标总结对比
指标 关注点 好的标准 差的情况
-----------------------------------------------------------------------
响应性 单次修复代价 O(polylog n) O(n) 或更高
效率性 内外事件之比 比值为常数/polylog 比值为 O(n)
紧凑性 证书集总大小 O(n) 或 O(n log n) O(n²)
局部性 单对象参与证书数 O(polylog n) O(n)
类比经典数据结构：
响应性
⏟
≈
查询速度
效率性
⏟
≈
更新代价
紧凑性
⏟
≈
空间复杂度
局部性
⏟
≈
索引耦合度
\underbrace{\text{响应性}}_{\approx\text{查询速度}} \quad \underbrace{\text{效率性}}_{\approx\text{更新代价}} \quad \underbrace{\text{紧凑性}}_{\approx\text{空间复杂度}} \quad \underbrace{\text{局部性}}_{\approx\text{索引耦合度}}
≈查询速度
响应性≈更新代价
效率性≈空间复杂度
紧凑性≈索引耦合度
局部性
一个好的 KDS 需要在这四个维度上同时表现良好，这正如经典数据结构需要在时间和空间之间寻找最优平衡一样。
运动学碰撞检测 (Kinetic Collision Detection) 详解
一、问题背景：为什么碰撞检测很难？
想象你在写一个游戏引擎或物理模拟器，屏幕上有很多物体在移动。你需要实时判断：哪两个物体撞在一起了？
1.1 传统方法的困境：固定时间步长
传统方法是每隔固定时间 Δ t \Delta t Δt 检查一次所有物体的位置：
时间线：
t=0 t=Δt t=2Δt t=3Δt t=4Δt
│ │ │ │ │
▼ ▼ ▼ ▼ ▼
检查 检查 检查 检查 检查
问题1：Δt 太大 → 漏检（两次检查之间物体穿过了彼此）
t=0 t=Δt
A●────→ ←────●B A● ●B
穿过了！没检测到！
问题2：Δt 太小 → 浪费（大部分时间物体离得很远，白白计算）
t=0 t=1 t=2 t=3 ... t=999 t=1000
●→ ●→ ●→ ●→ ●→ ●●碰撞！
前999次检查都是浪费！
1.2 运动学方法的优势
运动学方法 (Kinetic Data Structure, KDS) 的核心思想：
不按固定间隔检查，而是预测"下一个重要事件什么时候发生"，直接跳到那个时刻。
传统方法： 检查 检查 检查 检查 检查 检查 检查 检查 碰撞！
↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑
大量无用计算
运动学方法：预测 ─────────────────────────────→ 碰撞！
↑ ↑
只在"证书失效"时才重新计算
二、核心概念：证书 (Certificate)
2.1 什么是证书？
证书是一个当前为真的几何条件，它保证了某种安全状态。只要证书有效，就不需要做任何事情。
例子：两个圆形物体 A 和 B
证书："A 和 B 的圆心距离 > A的半径 + B的半径"
●A ●B
/ \ / \
( rA ) ( rB )
\ / \ /
证书条件: dist(A, B) > rA + rB
只要这个条件成立 → 保证不碰撞 → 什么都不用做！
当条件即将失效 → 触发事件 → 重新处理
2.2 证书的失效时间
对于线性运动的物体，可以精确计算证书什么时候失效：
物体 A 在时刻
t
t
t 的位置：
p
A
(
t
)
=
p
A
0
+
v
A
⋅
t
\mathbf{p}_A(t) = \mathbf{p}_{A0} + \mathbf{v}_A \cdot t
pA(t)=pA0+vA⋅t
物体 B 在时刻
t
t
t 的位置：
p
B
(
t
)
=
p
B
0
+
v
B
⋅
t
\mathbf{p}_B(t) = \mathbf{p}_{B0} + \mathbf{v}_B \cdot t
pB(t)=pB0+vB⋅t
两物体距离：
d
(
t
)
=
∥
p
A
(
t
)
−
p
B
(
t
)
∥
d(t) = \|\mathbf{p}_A(t) - \mathbf{p}_B(t)\|
d(t)=∥pA(t)−pB(t)∥
证书失效条件（即碰撞条件）：
d
(
t
)
=
r
A
+
r
B
d(t) = r_A + r_B
d(t)=rA+rB
展开后变成关于
t
t
t 的二次方程：
∥
p
A
0
−
p
B
0
+
(
v
A
−
v
B
)
t
∥
2
=
(
r
A
+
r
B
)
2
\|\mathbf{p}_{A0} - \mathbf{p}_{B0} + (\mathbf{v}_A - \mathbf{v}_B) t\|^2 = (r_A + r_B)^2
∥pA0−pB0+(vA−vB)t∥2=(rA+rB)2
求解这个方程就能精确知道碰撞时刻！
三、方法1：凸多边形的外层级碰撞检测
3.1 基本思想
对于两个移动的凸多边形，构建"外层级"(outer hierarchy)。层级中的每一层提供越来越粗略的包围。
精细层: 实际多边形轮廓
╱╲
╱ ╲
╱ ╲
╱______╲
中间层: 简化的包围多边形
┌────────┐
│ ╱╲ │
│ ╱ ╲ │
│╱ ╲ │
│╱______╲│
└────────┘
粗略层: 包围圆
╭────╮
╭─│ ╱╲ │─╮
│ │╱ ╲│ │
│ │ │ │
╰─│____│─╯
╰────╯
查询时从粗到细：
步骤1: 两个包围圆相交吗？
○A ○B → 不相交 → 肯定没碰撞，结束！
步骤2: 包围矩形相交吗？
□A □B → 不相交 → 没碰撞，结束！
步骤3: 精确多边形相交吗？
△A △B → 需要精确判断
3.2 事件数量与分离度的关系
运动学算法的关键优势：事件数量取决于两个多边形的"相对分离程度"。
情况1：物体离得很远 → 事件极少
○ ○
A B
只有最外层的粗包围需要偶尔更新
情况2：物体靠得很近 → 事件较多
○○
AB
需要频繁更新内层的精细证书
这正是我们想要的行为！
远离时省计算，靠近时才花精力。
四、方法2：伪三角剖分 (Pseudotriangulation)
4.1 什么是伪三角剖分？
伪三角形是一个只有3个凸顶点的简单多边形（边可以是凹的）。
普通三角形: 伪三角形（3个凸顶点，边可以弯）:
╱╲ ╱‾‾‾╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╭╮ ╲
╱______╲ ╱___╰╯____╲
3个直边 3个凸角，边可以是凹的
4.2 伪三角剖分用于碰撞检测
核心思想：用伪三角形填充物体周围的自由空间。如果自由空间被完整铺满，就证明物体没有相交。
两个物体 A 和 B 之间的自由空间用伪三角形铺满：
┌─────────────────────────────────┐
│ ╱╲ │
│ ╱╲ ╱ ╲ ╱╲ │
│ ╱A ╲ T1 ╱ T2 ╲ ╱B ╲ │
│ ╲ ╱ ╲ ╱ ╲ ╱ │
│ ╲╱ T3 ╲ ╱ T4 ╲╱ │
│ ╲╱ │
└─────────────────────────────────┘
T1, T2, T3, T4 = 伪三角形，铺满了 A 和 B 之间的空间
只要铺满 → 证明 A 和 B 没有碰撞
4.3 图 24.7 的解读（四个快照）
图 24.7 展示了一个内部四边形向右移动时，伪三角剖分如何自适应调整：
快照(i): 内部四边形在左侧
┌──────────────────┐
│ ┌──┐ │
│ │四│ △ △ △ │ 黑线 = 即将失效的证书边
│ │边│ │
│ │形│ △ △ │
│ └──┘ │
└──────────────────┘
快照(ii): 四边形稍微右移
┌──────────────────┐
│ ┌──┐ │
│ │ │ △ △ │ 之前的证书边失效了
│ │ │ │ 新的证书边出现（黑线换了位置）
│ └──┘ △ │
└──────────────────┘
快照(iii): 四边形继续右移
┌──────────────────┐
│ ┌──┐ │
│ △ │ │ △ │ 伪三角形重新铺设
│ │ │ │ 只有局部发生了变化！
│ △ └──┘ │
└──────────────────┘
快照(iv): 四边形到了更右边
┌──────────────────┐
│ ┌──┐ │
│ △ △ │ │ │ 再次局部调整
│ │ │ │ 大部分伪三角形不变
│ △ └──┘ │
└──────────────────┘
关键优势：物体移动时，伪三角剖分只需要局部重新铺设（local retiling），不需要整体重建。相比普通三角剖分，伪三角剖分的组合变化更少。
五、方法3：包围体层级 (Bounding Volume Hierarchy)
5.1 传统包围体层级
用球体（或其他简单形状）层层包裹物体：
包围球层级（直杆状态）：
小球: ○ ○ ○ ○ ○ ○ ○ ○ ← 每个小球包住一小段
●──●──●──●──●──●──●──● ← 杆上的点
中球: (○ ○) (○ ○) (○ ○) ← 每个中球包住两个小球
◎ ◎ ◎
大球: ((○ ○)(○ ○)) ← 大球包住两个中球
◉
最大球: (((所有))) ← 一个球包住整体
◎
树形结构:
顶层: 最大球
|----------------|
中层: 左大球 右大球
|--------| |--------|
底层: 小球1 小球2 小球3 小球4 ...
| | | |
最底层: 段1 段2 段3 段4
5.2 可变形物体的问题
传统方法：包围球的中心和半径是固定的数值。物体变形后，原来的球不再包住对应的部分，必须整体重建。
直杆:
○──○──○──○──○──○──○──○ ← 包围球正好
●──●──●──●──●──●──●──●
弯曲后:
○ ○ ← 原来的球位置不对了！
● ● 需要全部重新计算！
● ● ← 物体弯了
● ●
○ ○ ← 这些球的位置也全错了
5.3 隐式定义的包围球（图 24.8 的方法）
核心创新：不用"中心+半径"定义包围球，而是用4个特征点隐式定义。
传统定义: 隐式定义:
中心 = (3.0, 5.0) 由点 P1, P2, P3, P4 确定
半径 = 2.5 球 = 过这4点的最小包围球
球是固定的数值 球随着点的移动自动变化！
4个点确定一个球的原理：
在三维空间中，4个不共面的点唯一确定一个球面。在二维空间中，3个不共线的点确定一个圆。
球
=
MinEnclosingBall
(
P
1
,
P
2
,
P
3
,
P
4
)
\text{球} = \text{MinEnclosingBall}(P_1, P_2, P_3, P_4)
球=MinEnclosingBall(P1,P2,P3,P4)
当物体变形时，特征点跟着移动，包围球自动跟踪变形：
直杆状态:
P1●──────●P2──────●P3──────●P4
最小包围球自动计算:
╭──────────────────────────╮
( P1●────●P2────●P3────●P4 )
╰──────────────────────────╯
弯曲后:
P3●
●P2 ●P4
P1●
最小包围球自动调整:
╭─────────╮
( P3● )
( ●P2 ●P4 )
( P1● )
╰─────────────╯
球的"定义"（4个点）没变，球的形状自动跟着变了！
不需要重建层级！
5.4 图 24.8 的解读
左图（直杆）: 右图（弯曲的杆）:
╭──────────╮ ╭───╮
╱ ╭──╮╭──╮ ╲ ╭──╯ ╰──╮
╱ ( ○ )( ○ ) ╲ ╱ ○ ○ ○ ╲
│ ○──○──○──○──○ │ │ ○ ● ● ● ○ │
│ ●──●──●──●──● │ │ ● ● ● │
╲ ( ○ )( ○ ) ╱ ╲ ○ ○ ╱
╲ ╰──╯╰──╯ ╱ ╰──╮ ╭──╯
╰──────────╯ ╰───╯
小圆 = 底层包围球（每个包住一小段杆）
中圆 = 中层包围球（包住两个小球）
大圆 = 顶层包围球（包住整体）
关键观察：弯曲后，只有顶层的大球改变了形状！
底层和中层的球的"组合定义"（哪4个点定义它）没变！
→ 极少的更新代价！
六、完整 C++ 演示代码
#include <iostream>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
#include <iomanip>
#include <string>
#include <limits>
#include <functional>
// ============================================================
// 基础数学结构
// ============================================================
// 二维向量
struct Vec2 {
double x, y;
Vec2(double x = 0, double y = 0) : x(x), y(y) {}
Vec2 operator+(const Vec2& v) const { return {x + v.x, y + v.y}; }
Vec2 operator-(const Vec2& v) const { return {x - v.x, y - v.y}; }
Vec2 operator*(double s) const { return {x * s, y * s}; }
double dot(const Vec2& v) const { return x * v.x + y * v.y; }
double norm() const { return std::sqrt(x * x + y * y); }
double normSq() const { return x * x + y * y; }
};
// 计算两点之间的距离
double dist(const Vec2& a, const Vec2& b) {
return (a - b).norm();
}
// ============================================================
// 移动圆形物体
// ============================================================
struct MovingCircle {
int id;
Vec2 pos; // 当前位置（参考时刻t=0）
Vec2 vel; // 速度向量
double radius;
std::string name;
// 预测 t 时刻的位置
// 公式: p(t) = pos + vel * t
Vec2 posAt(double t) const {
return pos + vel * t;
}
void print() const {
std::cout << " " << name
<< ": 位置(" << pos.x << "," << pos.y << ")"
<< " 速度(" << vel.x << "," << vel.y << ")"
<< " 半径=" << radius << "\n";
}
};
// ============================================================
// 证书 (Certificate)
// 表示两个物体"当前不碰撞"这个事实
// 包含预计的失效时间（即碰撞时间）
// ============================================================
struct Certificate {
int objA, objB; // 两个物体的索引
double failTime; // 证书失效时间（预计碰撞时间）
bool valid; // 证书是否仍然有效
// 用于优先队列：失效时间早的优先
bool operator>(const Certificate& other) const {
return failTime > other.failTime;
}
};
// ============================================================
// 计算两个移动圆的碰撞时间
// 返回最早的碰撞时间，如果不会碰撞则返回正无穷
// ============================================================
//
// 推导过程：
// 设相对位置: dp = posA - posB
// 相对速度: dv = velA - velB
//
// t 时刻距离的平方:
// d²(t) = |dp + dv*t|² = |dp|² + 2(dp·dv)t + |dv|²t²
//
// 碰撞条件: d(t) = rA + rB，即:
// |dv|²t² + 2(dp·dv)t + |dp|² - (rA+rB)² = 0
//
// 这是关于t的二次方程 at² + bt + c = 0
// a = |dv|²
// b = 2(dp·dv)
// c = |dp|² - (rA+rB)²
//
double computeCollisionTime(const MovingCircle& A,
const MovingCircle& B) {
Vec2 dp = A.pos - B.pos; // 相对位置
Vec2 dv = A.vel - B.vel; // 相对速度
double a = dv.normSq(); // |dv|²
double b = 2.0 * dp.dot(dv); // 2(dp·dv)
double rSum = A.radius + B.radius;
double c = dp.normSq() - rSum * rSum; // |dp|² - (rA+rB)²
// 如果 c <= 0，说明当前已经碰撞了
if (c <= 1e-9) {
return 0.0;
}
// 如果 a ≈ 0，说明相对速度为0，永远不碰撞
if (std::abs(a) < 1e-12) {
return std::numeric_limits<double>::infinity();
}
// 判别式 Δ = b² - 4ac
double discriminant = b * b - 4.0 * a * c;
// Δ < 0：没有实数解，不会碰撞
if (discriminant < 0) {
return std::numeric_limits<double>::infinity();
}
// 两个解
double sqrtD = std::sqrt(discriminant);
double t1 = (-b - sqrtD) / (2.0 * a);
double t2 = (-b + sqrtD) / (2.0 * a);
// 取最小的正数解（未来最早碰撞时间）
double tMin = std::numeric_limits<double>::infinity();
if (t1 > 1e-9) tMin = std::min(tMin, t1);
if (t2 > 1e-9) tMin = std::min(tMin, t2);
return tMin;
}
// ============================================================
// 方法1：固定时间步长碰撞检测（传统方法，用于对比）
// ============================================================
void fixedTimeStepDetection(
const std::vector<MovingCircle>& objects,
double dt, // 时间步长
double maxTime) // 模拟总时间
{
std::cout << "【方法1: 固定时间步长 (Δt=" << dt << ")】\n\n";
int totalChecks = 0;
int n = objects.size();
for (double t = 0; t <= maxTime; t += dt) {
// 每个时间步，检查所有物体对
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
totalChecks++;
Vec2 pi = objects[i].posAt(t);
Vec2 pj = objects[j].posAt(t);
double d = dist(pi, pj);
double rSum = objects[i].radius + objects[j].radius;
if (d <= rSum) {
std::cout << " t=" << std::fixed
<< std::setprecision(2) << t
<< ": " << objects[i].name
<< " 与 " << objects[j].name
<< " 碰撞! (距离=" << std::setprecision(3)
<< d << ")\n";
}
}
}
}
std::cout << " 总检查次数: " << totalChecks << "\n\n";
}
// ============================================================
// 方法2：运动学碰撞检测 (KDS方法)
// 基于证书和事件驱动
// ============================================================
void kineticCollisionDetection(
const std::vector<MovingCircle>& objects,
double maxTime)
{
std::cout << "【方法2: 运动学碰撞检测 (KDS)】\n\n";
int n = objects.size();
int totalEvents = 0;
// 第一步：为每对物体创建证书，计算失效时间
// 使用最小堆（优先队列），最早失效的证书在队首
std::priority_queue<Certificate,
std::vector<Certificate>,
std::greater<Certificate>> eventQueue;
std::cout << " 初始证书建立:\n";
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
double tCollide = computeCollisionTime(objects[i],
objects[j]);
Certificate cert;
cert.objA = i;
cert.objB = j;
cert.failTime = tCollide;
cert.valid = true;
if (tCollide <= maxTime) {
eventQueue.push(cert);
std::cout << " " << objects[i].name
<< " vs " << objects[j].name
<< " → 预计碰撞时间 t="
<< std::fixed << std::setprecision(3)
<< tCollide << "\n";
} else {
std::cout << " " << objects[i].name
<< " vs " << objects[j].name
<< " → 在模拟时间内不会碰撞\n";
}
}
}
// 第二步：处理事件队列
std::cout << "\n 事件处理:\n";
while (!eventQueue.empty()) {
Certificate event = eventQueue.top();
eventQueue.pop();
// 跳过已失效的事件
if (!event.valid) continue;
// 跳过超出模拟时间的事件
if (event.failTime > maxTime) break;
totalEvents++;
std::cout << " 事件 #" << totalEvents
<< ": t=" << std::fixed << std::setprecision(3)
<< event.failTime << " → "
<< objects[event.objA].name
<< " 与 " << objects[event.objB].name
<< " 碰撞!\n";
// 在真实系统中，碰撞后物体会改变速度（反弹等）
// 然后需要重新计算相关的证书
// 这里简化处理，只报告碰撞
}
std::cout << "\n 总事件数: " << totalEvents
<< "（远少于固定步长的检查次数！）\n\n";
}
// ============================================================
// 包围球层级 (Bounding Sphere Hierarchy)
// 用于可变形物体的碰撞检测
// ============================================================
// 包围球
struct BoundingSphere {
Vec2 center;
double radius;
// 判断两个球是否相交
bool intersects(const BoundingSphere& other) const {
double d = dist(center, other.center);
return d <= radius + other.radius;
}
};
// 从一组点计算最小包围圆（简化版：使用轴对齐包围盒的外接圆）
BoundingSphere computeMinEnclosingCircle(
const std::vector<Vec2>& points)
{
if (points.empty()) return {{0, 0}, 0};
// 找到包围盒
double minX = points[0].x, maxX = points[0].x;
double minY = points[0].y, maxY = points[0].y;
for (const auto& p : points) {
minX = std::min(minX, p.x);
maxX = std::max(maxX, p.x);
minY = std::min(minY, p.y);
maxY = std::max(maxY, p.y);
}
BoundingSphere s;
s.center = {(minX + maxX) / 2.0, (minY + maxY) / 2.0};
// 半径 = 中心到最远点的距离
s.radius = 0;
for (const auto& p : points) {
s.radius = std::max(s.radius, dist(s.center, p));
}
return s;
}
// 包围球层级的节点
struct BVHNode {
BoundingSphere sphere; // 该节点的包围球
std::vector<int> pointIndices; // 叶节点包含的点索引
BVHNode* left; // 左子树
BVHNode* right; // 右子树
bool isLeaf;
int level; // 层级（根=0）
BVHNode() : left(nullptr), right(nullptr),
isLeaf(false), level(0) {}
};
// 递归构建包围球层级
BVHNode* buildBVH(const std::vector<Vec2>& points,
std::vector<int> indices,
int level = 0)
{
BVHNode* node = new BVHNode();
node->level = level;
// 收集当前节点包含的所有点
std::vector<Vec2> nodePoints;
for (int idx : indices) {
nodePoints.push_back(points[idx]);
}
// 计算包围球
node->sphere = computeMinEnclosingCircle(nodePoints);
// 如果只有1-2个点，作为叶节点
if (indices.size() <= 2) {
node->isLeaf = true;
node->pointIndices = indices;
return node;
}
// 按x坐标中位数分成两半
std::sort(indices.begin(), indices.end(),
[&points](int a, int b) {
return points[a].x < points[b].x;
});
int mid = indices.size() / 2;
std::vector<int> leftIndices(indices.begin(),
indices.begin() + mid);
std::vector<int> rightIndices(indices.begin() + mid,
indices.end());
node->left = buildBVH(points, leftIndices, level + 1);
node->right = buildBVH(points, rightIndices, level + 1);
return node;
}
// 打印包围球层级
void printBVH(BVHNode* node, const std::string& prefix = "",
bool isRight = false)
{
if (node == nullptr) return;
std::string connector = isRight ? "├── " : "└── ";
std::string extension = isRight ? "│ " : " ";
std::cout << prefix << connector;
std::cout << "球[中心=(" << std::fixed << std::setprecision(1)
<< node->sphere.center.x << ","
<< node->sphere.center.y << ") r="
<< std::setprecision(2)
<< node->sphere.radius << "]";
if (node->isLeaf) {
std::cout << " 叶{点:";
for (int i : node->pointIndices) {
std::cout << " P" << i;
}
std::cout << "}";
}
std::cout << "\n";
if (!node->isLeaf) {
printBVH(node->right, prefix + extension, true);
printBVH(node->left, prefix + extension, false);
}
}
// 释放 BVH 内存
void freeBVH(BVHNode* node) {
if (node == nullptr) return;
freeBVH(node->left);
freeBVH(node->right);
delete node;
}
// ============================================================
// 演示：隐式包围球在变形下的稳定性
// ============================================================
void demonstrateImplicitSpheres() {
std::cout << "【方法3: 隐式包围球层级（可变形物体）】\n\n";
// 直杆状态：8个点排成一条线
std::cout << " === 状态1: 直杆 ===\n";
std::vector<Vec2> straightRod = {
{0, 0}, {1, 0}, {2, 0}, {3, 0},
{4, 0}, {5, 0}, {6, 0}, {7, 0}
};
std::cout << " 点的位置:\n ";
for (int i = 0; i < (int)straightRod.size(); i++) {
std::cout << "P" << i << "("
<< straightRod[i].x << ","
<< straightRod[i].y << ") ";
}
std::cout << "\n\n";
// ASCII 可视化直杆
std::cout << " 直杆可视化:\n";
std::cout << " P0──P1──P2──P3──P4──P5──P6──P7\n";
std::cout << " ●───●───●───●───●───●───●───●\n\n";
// 构建 BVH
std::vector<int> allIndices;
for (int i = 0; i < (int)straightRod.size(); i++) {
allIndices.push_back(i);
}
BVHNode* bvh1 = buildBVH(straightRod, allIndices);
std::cout << " 包围球层级:\n";
printBVH(bvh1, " ", false);
std::cout << "\n";
// 弯曲状态：8个点弯成弧形
std::cout << " === 状态2: 弯曲的杆 ===\n";
std::vector<Vec2> bentRod = {
{0.0, 0.0}, {0.7, 0.7}, {1.0, 1.5}, {0.7, 2.3},
{0.0, 3.0}, {-0.7, 2.3}, {-1.0, 1.5}, {-0.7, 0.7}
};
std::cout << " 点的位置:\n ";
for (int i = 0; i < (int)bentRod.size(); i++) {
std::cout << "P" << i << "("
<< std::setprecision(1) << bentRod[i].x << ","
<< bentRod[i].y << ") ";
}
std::cout << "\n\n";
// ASCII 可视化弯曲杆
std::cout << " 弯曲杆可视化:\n";
std::cout << " P4\n";
std::cout << " ●\n";
std::cout << " / \\\n";
std::cout << " P3● ●P5\n";
std::cout << " | |\n";
std::cout << " P2● ●P6\n";
std::cout << " \\ /\n";
std::cout << " P1● ●P7\n";
std::cout << " |\n";
std::cout << " ●P0\n\n";
// 构建 BVH
BVHNode* bvh2 = buildBVH(bentRod, allIndices);
std::cout << " 包围球层级:\n";
printBVH(bvh2, " ", false);
std::cout << "\n";
// 对比分析
std::cout << " === 对比分析 ===\n\n";
std::cout << " 直杆 顶层球: 中心=("
<< std::setprecision(1) << bvh1->sphere.center.x
<< "," << bvh1->sphere.center.y
<< ") 半径=" << std::setprecision(2)
<< bvh1->sphere.radius << "\n";
std::cout << " 弯杆 顶层球: 中心=("
<< std::setprecision(1) << bvh2->sphere.center.x
<< "," << bvh2->sphere.center.y
<< ") 半径=" << std::setprecision(2)
<< bvh2->sphere.radius << "\n\n";
std::cout << " 关键观察:\n";
std::cout << " → 底层叶节点的"组合定义"不变（包含哪些点不变）\n";
std::cout << " → 只有顶层球需要更新其形状\n";
std::cout << " → 层级的树形结构完全不需要重建！\n\n";
freeBVH(bvh1);
freeBVH(bvh2);
}
// ============================================================
// 伪三角剖分的简化演示
// ============================================================
void demonstratePseudotriangulation() {
std::cout << "【方法4: 伪三角剖分碰撞检测（概念演示）】\n\n";
// 外部边界（矩形）
std::cout << " 场景: 矩形边界内，一个三角形物体在移动\n\n";
// 不同时刻的伪三角剖分变化
std::cout << " t=0: 物体在左侧\n";
std::cout << " ┌────────────────────────────┐\n";
std::cout << " │╲ T1 ╱ │\n";
std::cout << " │ ╲ ╱╲ ╱ T3 │\n";
std::cout << " │ T2╲╱物╲╱ │\n";
std::cout << " │ ╱体 ╲╲ │\n";
std::cout << " │ ╱ ╲╱ ╲ T4 │\n";
std::cout << " │╱ T5 ╲ │\n";
std::cout << " └────────────────────────────┘\n";
std::cout << " 5个伪三角形铺满自由空间 → 证明没碰撞\n";
std::cout << " 每个伪三角形 = 一个证书\n\n";
std::cout << " t=3: 物体移到中间\n";
std::cout << " ┌────────────────────────────┐\n";
std::cout << " │ ╲ T1 ╱ │\n";
std::cout << " │ T2 ╲╱╲ ╱ T3 │\n";
std::cout << " │ ╲物╲╱ │\n";
std::cout << " │ ╱体╱╲ │\n";
std::cout << " │ T5 ╱╲╱ ╲ T4 │\n";
std::cout << " │ ╱ T6 ╲ │\n";
std::cout << " └────────────────────────────┘\n";
std::cout << " 部分伪三角形重新铺设（T1,T2位置变了）\n";
std::cout << " 但大部分结构保持不变 → 局部更新！\n\n";
std::cout << " 伪三角剖分 vs 普通三角剖分:\n";
std::cout << " ┌──────────────────┬──────────────────┐\n";
std::cout << " │ 普通三角剖分 │ 伪三角剖分 │\n";
std::cout << " ├──────────────────┼──────────────────┤\n";
std::cout << " │ 边数多 │ 边数少 │\n";
std::cout << " │ 变化频繁 │ 变化少 │\n";
std::cout << " │ 全局影响 │ 局部影响 │\n";
std::cout << " │ 证书数量 O(n²) │ 证书数量 O(n) │\n";
std::cout << " └──────────────────┴──────────────────┘\n\n";
}
// ============================================================
// 主函数
// ============================================================
int main() {
std::cout << std::fixed << std::setprecision(2);
std::cout << "═══════════════════════════════════════════════\n";
std::cout << " 运动学碰撞检测 (Kinetic Collision Detection)\n";
std::cout << " 完整演示\n";
std::cout << "═══════════════════════════════════════════════\n\n";
// ── 创建测试物体 ──
std::vector<MovingCircle> objects = {
{0, { 0, 0}, { 2.0, 1.0}, 0.5, "物体A"},
{1, {10, 0}, {-1.5, 0.5}, 0.5, "物体B"},
{2, { 5, 8}, { 0.0,-1.0}, 0.5, "物体C"},
{3, { 0, 5}, { 1.0,-0.5}, 0.5, "物体D"},
};
std::cout << "【场景设定】4个圆形物体在移动:\n";
for (const auto& obj : objects) {
obj.print();
}
std::cout << "\n";
// 可视化初始位置
std::cout << " t=0 初始位置图:\n";
std::cout << " y\n";
std::cout << " 8 │ C● \n";
std::cout << " 7 │ \n";
std::cout << " 6 │ \n";
std::cout << " 5 │ D● \n";
std::cout << " 4 │ \n";
std::cout << " 3 │ \n";
std::cout << " 2 │ \n";
std::cout << " 1 │ → ← \n";
std::cout << " 0 │ A●─────────────────●B \n";
std::cout << " └──────────────────────── x \n";
std::cout << " 0 1 2 3 4 5 6 7 8 9 10\n";
std::cout << " A→右上 B→左上 C→正下 D→右下\n\n";
double maxTime = 10.0;
// ── 方法1: 固定时间步长 ──
fixedTimeStepDetection(objects, 0.1, maxTime);
// ── 方法2: 运动学方法 ──
kineticCollisionDetection(objects, maxTime);
// ── 方法3: 包围球层级 ──
demonstrateImplicitSpheres();
// ── 方法4: 伪三角剖分概念 ──
demonstratePseudotriangulation();
// ── 总结对比 ──
std::cout << "═══════════════════════════════════════════════\n";
std::cout << " 四种方法对比总结\n";
std::cout << "═══════════════════════════════════════════════\n\n";
std::cout << " ┌──────────────┬────────────┬────────────┬──────────────┐\n";
std::cout << " │ 方法 │ 适用场景 │ 计算量 │ 关键优势 │\n";
std::cout << " ├──────────────┼────────────┼────────────┼──────────────┤\n";
std::cout << " │ 固定时间步长 │ 通用 │ O(n²/Δt) │ 实现简单 │\n";
std::cout << " ├──────────────┼────────────┼────────────┼──────────────┤\n";
std::cout << " │ KDS证书方法 │ 线性运动 │ O(事件数) │ 跳过空闲期 │\n";
std::cout << " ├──────────────┼────────────┼────────────┼──────────────┤\n";
std::cout << " │ 隐式包围球 │ 可变形体 │ 层级查询 │ 变形免重建 │\n";
std::cout << " ├──────────────┼────────────┼────────────┼──────────────┤\n";
std::cout << " │ 伪三角剖分 │ 复杂多边 │ O(n)证书 │ 局部更新 │\n";
std::cout << " │ │ 形场景 │ │ 变化最少 │\n";
std::cout << " └──────────────┴────────────┴────────────┴──────────────┘\n\n";
std::cout << " 形象比喻:\n\n";
std::cout << " 固定步长 ≈ 每秒钟看一次所有车有没有撞\n";
std::cout << " → 大部分时间都在做无用功\n\n";
std::cout << " KDS方法 ≈ 算好每辆车什么时候可能撞，定闹钟\n";
std::cout << " → 闹钟响了才起来处理\n\n";
std::cout << " 隐式包围球 ≈ 给绳子套上一系列自动伸缩的保护套\n";
std::cout << " → 绳子怎么弯，保护套自动调整\n\n";
std::cout << " 伪三角剖分 ≈ 用气球填满物体之间的空隙\n";
std::cout << " → 物体移动时气球只需局部调整形状\n\n";
return 0;
}
https://godbolt.org/z/hdYasPcnr
七、关键公式汇总
7.1 碰撞时间计算
两个圆形物体
A
,
B
A, B
A,B 的碰撞时间方程：
a
t
2
+
b
t
+
c
=
0
a t^2 + b t + c = 0
at2+bt+c=0
其中：
a
=
∥
v
A
−
v
B
∥
2
a = \|\mathbf{v}_A - \mathbf{v}_B\|^2
a=∥vA−vB∥2
b
=
2
(
p
A
−
p
B
)
⋅
(
v
A
−
v
B
)
b = 2(\mathbf{p}_A - \mathbf{p}_B) \cdot (\mathbf{v}_A - \mathbf{v}_B)
b=2(pA−pB)⋅(vA−vB)
c
=
∥
p
A
−
p
B
∥
2
−
(
r
A
+
r
B
)
2
c = \|\mathbf{p}_A - \mathbf{p}_B\|^2 - (r_A + r_B)^2
c=∥pA−pB∥2−(rA+rB)2
判别式：
Δ
=
b
2
−
4
a
c
\Delta = b^2 - 4ac
Δ=b2−4ac
- Δ < 0 \Delta < 0 Δ<0：不碰撞
- Δ ≥ 0 \Delta \geq 0 Δ≥0：碰撞时间 t = − b − Δ 2 a t = \dfrac{-b - \sqrt{\Delta}}{2a} t=2a−b−Δ（取较小正根）
7.2 证书失效
证书
σ
\sigma
σ 在时刻
t
t
t 有效当且仅当：
d
(
A
(
t
)
,
B
(
t
)
)
>
r
A
+
r
B
d(A(t), B(t)) > r_A + r_B
d(A(t),B(t))>rA+rB
证书失效时刻
t
∗
t^*
t∗ 满足：
d
(
A
(
t
∗
)
,
B
(
t
∗
)
)
=
r
A
+
r
B
d(A(t^*), B(t^*)) = r_A + r_B
d(A(t∗),B(t∗))=rA+rB
7.3 最小包围球
给定
n
n
n 个点
P
1
,
P
2
,
…
,
P
n
P_1, P_2, \ldots, P_n
P1,P2,…,Pn，最小包围球
S
S
S 满足：
S
=
arg
min
S
′
r
(
S
′
)
s.t.
P
i
∈
S
′
∀
i
S = \arg\min_{S'} r(S') \quad \text{s.t.} \quad P_i \in S' \ \forall i
S=argS′minr(S′)s.t.Pi∈S′ ∀i
在二维中由最多3个点确定，在三维中由最多4个点确定。
7.4 KDS 效率指标
设 n n n 个物体， k k k 次实际碰撞：
| 方法 | 检查次数 |
|---|---|
| 固定步长 | O ( n 2 ⋅ T Δ t ) O\left(\dfrac{n^2 \cdot T}{\Delta t}\right) O(Δtn2⋅T) |
| KDS | O ( n 2 ) O(n^2) O(n2) 初始化 + O ( k ) O(k) O(k) 事件处理 |
当 k ≪ n 2 T Δ t k \ll \dfrac{n^2 T}{\Delta t} k≪Δtn2T 时，KDS 大幅优于固定步长。
八、核心概念图解总结
8.1 KDS 的事件驱动架构
┌──────────────┐
│ 事件优先队列 │
│ (按时间排序) │
└──────┬───────┘
│ 取出最早的事件
▼
┌──────────────┐
│ 处理事件 │
│ (证书失效) │
└──────┬───────┘
│
┌─────────┴─────────┐
▼ ▼
┌──────────────┐ ┌──────────────┐
│ 报告碰撞 │ │ 更新相关证书 │
│ 或状态变化 │ │ 重新入队 │
└──────────────┘ └──────────────┘
8.2 包围球层级在变形下的行为
变形前: 变形后:
顶层: (────────────) 顶层: (──────) ← 只有这层变了!
╱ ╲ ╱ ╲
中层: (──────) (──────) 中层: (───) (───) ← 形状变了但定义没变
╱ ╲ ╱ ╲ ╱ ╲╱ ╲
底层: (──) (──) (──) (──) (──)(──)(──)(──) ← 同上
●● ●● ●● ●● ●● ●● ●● ●●
定义方式: 每个球由其包含的特征点隐式定义
→ 点移动了，球自动变
→ 不需要重建树的结构！
8.3 伪三角剖分的局部更新
物体移动前: 物体移动后:
┌──────────────────┐ ┌──────────────────┐
│╲ T1 ╱╲ T2 ╱ │ │ ╲ T1'╱╲T2'╱ │
│ ╲╱ 物体 ╲╱ │ → │ ╲╱物体╲╱ │
│ ╱╲ ╱╲ │ │ ╱╲ ╱╲ │
│╱ T3 ╲╱ T4 ╲ │ │ ╲╱ T3 ╲╱T4'╲ │
└──────────────────┘ └──────────────────┘
只有 T1→T1', T2→T2', T4→T4' 发生了变化
T3 完全没动！ → 减少证书更新次数
24.5.5 连通性与聚类（Connectivity and Clustering）
一、引言：移动几何对象的连通性
移动通信（如手机、无人机、传感器网络）中，节点（站点）之间能否建立链路，往往取决于它们的物理距离或视线可见性。
用几何语言描述：
- 每个通信站的覆盖范围可建模为一个几何区域（如圆形、矩形）
- 两站之间能通信 ⟺ 它们对应的区域相互重叠
于是问题变成：如何动态维护一组移动几何区域的连通分量（Connected Components）？
已有研究针对以下两类情形给出了算法： - 矩形区域的连通分量维护（文献 [28]）
- 单位圆盘的连通分量维护（文献 [29]）
二、聚类（Clustering）：建立通信层次结构
2.1 为什么需要聚类？
在移动自组织网络（Ad Hoc Network）中，聚类是组织通信层次的关键步骤：
- 近邻节点：直接通信，协议简单
- 远距离簇：复用稀缺资源（同一频段、时分复用方案），互不干扰
示意：3个簇，簇内直接通信，簇间通过簇头转发
簇1 簇2 簇3
[A]--[B] [D]--[E] [G]--[H]
| | | |
[C] [头]--~~~~--[头]--~~~~-- [头]
↑ ↑ ↑
簇头 簇头 簇头
(cluster head)
2.2 聚类的核心矛盾
| 目标 | 含义 |
|---|---|
| 紧凑性（Tightness） | 聚类结果尽量接近最优解 |
| 稳定性（Stability） | 节点移动时，聚类变化尽量少 |
这两者之间存在权衡（Trade-off）：过于追求最优聚类，节点每次移动都需要重新分簇；过于强调稳定，聚类质量下降。
2.3 随机化聚类方案（文献 [30]）
核心思路：基于**迭代选主（Leader Election）**算法。
性质保证：
- 簇的数量在最优数量的常数倍以内（近似最优）
- 簇变化次数也是渐近最优的
应用（文献 [31]）：
基于此聚类方案，可在移动节点上维护一张路由图（Routing Graph），满足： - 图始终稀疏（边数少，维护代价低）
- 通信路径质量接近完整通信图中的最优路径
三、最小生成树（MST）的动态维护
3.1 问题背景
给定平面上
n
n
n 个移动点，如何动态维护它们之间的最小生成树（Minimum Spanning Tree，MST）？
这与参数化生成树（Parametric Spanning Tree）问题密切相关：图的边权是参数
λ
\lambda
λ 的函数，在动态几何中
λ
\lambda
λ 就是时间
t
t
t。
3.2 算法思路与复杂度演进
基础算法（朴素方法）
核心观察：
MST 由边权的排序顺序决定（Kruskal 算法本质是按权重排序后贪心）。
因此，只需维护所有边权的排序列表 + 辅助数据结构即可。
复杂度分析：
- n n n 个点 → 完全图有 O ( n 2 ) O(n^2) O(n2) 条边
- 维护排序列表的事件数： O ( n 4 ) O(n^4) O(n4)（每对边权函数可能有 O ( 1 ) O(1) O(1) 个交叉点，共 O ( n 4 ) O(n^4) O(n4) 个）
- 总时间复杂度：
O
(
n
4
)
O(n^4)
O(n4)
边数 = ( n 2 ) = O ( n 2 ) , 事件数 ≈ O ( ( n 2 2 ) ) = O ( n 4 ) \text{边数} = \binom{n}{2} = O(n^2), \quad \text{事件数} \approx O\!\left(\binom{n^2}{2}\right) = O(n^4) 边数=(2n)=O(n2),事件数≈O((2n2))=O(n4)
改进算法（边权为时间的线性函数）
当边权是时间
t
t
t 的线性函数时（即点做匀速直线运动，两点距离平方是
t
t
t 的二次函数，但若考虑某些简化情形），对于平面图或其他 minor-closed 族图，事件数可降至：
接近
O
(
n
11
/
6
)
（次二次，文献 [33]）
\text{接近 } O(n^{11/6}) \quad \text{（次二次，文献 [33]）}
接近 O(n11/6)（次二次，文献 [33]）
这比朴素的
O
(
n
4
)
O(n^4)
O(n4) 有显著改进（
n
11
/
6
≈
n
1.833
≪
n
4
n^{11/6} \approx n^{1.833} \ll n^4
n11/6≈n1.833≪n4）。
欧氏距离情形（点真实移动）
当边权为移动点之间的欧氏距离时：
w
(
e
i
j
)
=
∥
p
i
(
t
)
−
p
j
(
t
)
∥
2
w(e_{ij}) = \|p_i(t) - p_j(t)\|_2
w(eij)=∥pi(t)−pj(t)∥2
目前仅知近似算法，最优事件界接近：
O
(
n
3
)
（接近三次，文献 [18]）
O(n^3) \quad \text{（接近三次，文献 [18]）}
O(n3)（接近三次，文献 [18]）
3.3 复杂度对比总结
| 情形 | 事件数上界 |
|---|---|
| 朴素算法 | O ( n 4 ) O(n^4) O(n4) |
| 线性权重 + minor-closed 图 | ≈ O ( n 11 / 6 ) \approx O(n^{11/6}) ≈O(n11/6) |
| 欧氏距离（近似） | ≈ O ( n 3 ) \approx O(n^3) ≈O(n3) |
四、MST 动态维护 C++ 示例
以下代码演示**静态 MST（Kruskal 算法）**作为基础，并展示如何在点移动时重新计算 MST（简化版，便于理解核心逻辑）。
#include <bits/stdc++.h>
using namespace std;
// ============================================================
// 并查集（Union-Find）——用于 Kruskal 算法判断连通性
// ============================================================
struct UnionFind {
vector<int> parent, rank_;
// 初始化：n 个独立节点
UnionFind(int n) : parent(n), rank_(n, 0) {
iota(parent.begin(), parent.end(), 0); // parent[i] = i
}
// 路径压缩查找根节点
int find(int x) {
if (parent[x] != x)
parent[x] = find(parent[x]); // 递归压缩路径
return parent[x];
}
// 按秩合并，返回是否成功合并（原来不在同一集合）
bool unite(int x, int y) {
int rx = find(x), ry = find(y);
if (rx == ry) return false; // 已连通，形成环
if (rank_[rx] < rank_[ry]) swap(rx, ry);
parent[ry] = rx; // 将秩小的挂到秩大的下面
if (rank_[rx] == rank_[ry]) rank_[rx]++;
return true;
}
};
// ============================================================
// 二维点结构（支持移动）
// ============================================================
struct Point {
double x, y;
// 欧氏距离的平方（避免开方，提高精度）
double distSq(const Point& o) const {
double dx = x - o.x, dy = y - o.y;
return dx * dx + dy * dy;
}
// 欧氏距离
double dist(const Point& o) const {
return sqrt(distSq(o));
}
};
// ============================================================
// 边结构：连接两点，权重为当前欧氏距离
// ============================================================
struct Edge {
int u, v; // 两端点编号
double weight; // 当前权重（欧氏距离）
};
// ============================================================
// Kruskal 算法求静态 MST
// 返回：MST 的边集合，以及 MST 总权重
// ============================================================
pair<vector<Edge>, double> kruskalMST(int n, vector<Edge> edges) {
// Step 1：按边权升序排序（MST 核心步骤）
sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
return a.weight < b.weight;
});
UnionFind uf(n);
vector<Edge> mstEdges;
double totalWeight = 0.0;
// Step 2：贪心选边，跳过会形成环的边
for (const auto& e : edges) {
if (uf.unite(e.u, e.v)) { // 若成功合并（不形成环）
mstEdges.push_back(e); // 加入 MST
totalWeight += e.weight;
if ((int)mstEdges.size() == n - 1) break; // MST 恰好有 n-1 条边
}
}
return {mstEdges, totalWeight};
}
// ============================================================
// 模拟点的移动，每步重新计算 MST
// 简化策略：每步暴力重建完全图的边集 + 重跑 Kruskal
// 真实动态算法（KDS）会更高效，此处仅作教学演示
// ============================================================
int main() {
int n = 5; // 点的数量
// 初始位置（模拟 5 个移动传感器节点）
vector<Point> points = {
{0.0, 0.0},
{1.0, 0.0},
{0.5, 1.0},
{2.0, 1.5},
{3.0, 0.5}
};
// 移动速度（每步的位移向量，模拟匀速运动）
vector<Point> velocity = {
{0.1, 0.0},
{0.0, 0.1},
{-0.05, 0.05},
{0.1, -0.1},
{-0.1, 0.0}
};
int steps = 3; // 模拟步数
for (int step = 0; step <= steps; step++) {
cout << "========== 时刻 t = " << step << " ==========\n";
// 打印当前点的坐标
for (int i = 0; i < n; i++) {
printf(" 节点 %d: (%.2f, %.2f)\n", i, points[i].x, points[i].y);
}
// 构建完全图的边集（共 n*(n-1)/2 条边）
vector<Edge> edges;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
edges.push_back({i, j, points[i].dist(points[j])});
}
}
// 计算当前时刻的 MST
auto [mstEdges, totalW] = kruskalMST(n, edges);
// 打印 MST 结果
cout << " MST 边集：\n";
for (const auto& e : mstEdges) {
printf(" 节点%d -- 节点%d 权重=%.4f\n", e.u, e.v, e.weight);
}
printf(" MST 总权重 = %.4f\n\n", totalW);
// 更新点的位置（模拟运动：p = p + v * dt，dt=1）
for (int i = 0; i < n; i++) {
points[i].x += velocity[i].x;
points[i].y += velocity[i].y;
}
}
return 0;
}
运行效果（ASCII 演示）
========== 时刻 t = 0 ==========
节点 0: (0.00, 0.00)
节点 1: (1.00, 0.00)
节点 2: (0.50, 1.00)
节点 3: (2.00, 1.50)
节点 4: (3.00, 0.50)
MST 边集：
节点0 -- 节点1 权重=1.0000
节点0 -- 节点2 权重=1.1180
节点1 -- 节点3 权重=1.8028
节点3 -- 节点4 权重=1.1180
MST 总权重 = 5.0388
========== 时刻 t = 1 ==========
（点移动后，MST 结构可能发生变化...）
MST 结构示例（ASCII 树形）
时刻 t=0 的 MST 拓扑：
顶层（MST根）: 节点0
|-------------|
中层: 节点1 节点2
|
下层: 节点3
|
底层: 节点4
五、其他开放问题
除 MST 外，许多几何图上的优化问题在动态设置下仍是开放问题（Wide Open），例如：
- 最短路径（Shortest Paths）：移动点之间的最短路如何随时间演化？
- 其他图优化问题：匹配、覆盖、Steiner 树等
这些问题的动态版本目前几乎没有高效算法，是计算几何与动态图算法的前沿研究方向。
六、核心概念速查
| 概念 | 含义 |
|---|---|
| 连通分量 | 图中互相可达的最大节点集合 |
| MST | 连接所有节点、总边权最小的树 |
| KDS（Kinetic Data Structure） | 动态几何数据结构，追踪事件驱动的拓扑变化 |
| 事件（Event） | 导致 MST/连通性变化的几何临界时刻 |
| Minor-closed 图族 | 对图的子图运算封闭的图类（含平面图） |
| 参数化生成树 | 边权为参数函数时的生成树问题 |
24.5.6 可见性（Visibility）详解
一、问题背景：什么是可见性问题？
想象你站在一个充满建筑物的城市里，你只能看到没有被挡住的部分。
计算机图形学中，可见性问题就是：当观察者移动时，如何快速判断哪些物体是可见的，哪些被遮挡了。
这是计算机图形学中最经典的难题之一，催生了很多重要技术，比如：
- BSP 树（二叉空间分割树）：用于加速遮挡剔除
- 硬件深度缓冲（Z-buffer）：GPU 中判断像素深度的标准机制
当场景中的物体本身也在运动时，难度大幅提升——原来静态场景的加速结构，现在必须随着物体的运动实时更新。
二、BSP 树基础
2.1 什么是 BSP 树？
BSP（Binary Space Partition，二叉空间分割） 树是一种将空间递归地用平面切割成凸块（tiles） 的数据结构（详见第21章）。
切割过程如下：
整个空间
|
| 第一刀（用一个平面切开）
|
左半 ──── 右半
| |
再切 再切
| |
小凸块 ... 小凸块 ...
切割持续到每个凸块内部：
- 没有物体，或
- 只含有有限复杂度的几何体
2.2 BSP 树如何解决可见性问题？
一旦构建好 BSP 树，可以对所有几何片段确定一个正确的可见性排序（从前到后或从后到前）。
当观察者移动时，这个排序可以增量式地维护，无需从头重建。
三、运动场景下的动态 BSP 树
3.1 核心思想
当物体运动时，BSP 树需要实时更新。
关键洞察：
通过维护若干组合条件（combinatorial conditions） 来"认证" BSP 树的正确性。
当某个条件失效时，触发局部树调整，而不是全树重建。
⚠ 注意：大多数经典 BSP 构建算法不具备这种局部可更新性。
3.2 二维情形（ R 2 \mathbb{R}^2 R2）：运动线段的 BSP 维护
场景：平面上
n
n
n 条互不相交的运动线段
算法性质（随机化算法，文献[34]）：
| 性质 | 结论 |
|---|---|
| 事件总数 | O ( n 2 ) O(n^2) O(n2) |
| 每次树更新期望代价 | O ( log n ) O(\log n) O(logn) |
| 期望树大小 | O ( n log n ) O(n \log n) O(nlogn) |
3.3 三维情形（ R 3 \mathbb{R}^3 R3）：运动三角形的 BSP 维护
场景：三维空间中
n
n
n 个互不相交的运动三角形
维护代价（文献[35]）：
O
(
n
λ
s
+
2
(
n
)
log
2
n
)
O\!\left(n\lambda_{s+2}(n)\log^2 n\right)
O(nλs+2(n)log2n)
其中：
- λ s + 2 ( n ) \lambda_{s+2}(n) λs+2(n) 是 Davenport-Schinzel 序列中的近线性函数（几乎等于线性）
- s s s 是一个常数，取决于三角形的运动方式（例如直线平移、旋转等）
直觉理解： λ s + 2 ( n ) \lambda_{s+2}(n) λs+2(n) 增长极慢，比任何多项式都慢，可以粗略认为是 O ( n ⋅ 很慢增长的因子 ) O(n \cdot \text{很慢增长的因子}) O(n⋅很慢增长的因子)。
3.4 竖直分解的实践问题
上述两个算法都基于竖直分解（vertical decomposition） 的变体——大多数切割方向平行于某个固定方向。
这在实践中会产生**“薄片状（sliver-like）” BSP 块**，导致：
- 数值精度/鲁棒性问题（文献[36]）
- 实际工程中不稳定
四、可见性复合体与伪三角剖分
4.1 可见性复合体（Visibility Complex）
可见性复合体（文献[37]的开创性工作）是
R
2
\mathbb{R}^2
R2 中描述所有可见性关系的结构。
它表明，对于
R
2
\mathbb{R}^2
R2 中的可见性查询，伪三角剖分（pseudotriangulation） 是一种非常适合的结构。
4.2 什么是伪三角剖分？
伪三角形：有三个凸顶点和若干凹顶点的多边形。
普通三角形（三个角都凸）：
*
/ \
/ \
*-----*
伪三角形（一个凹角）：
*---------*
\ /
*-----*
\ /
\ /
*
（底部顶点是凹的）
伪三角剖分：将平面上的点集/凸多边形之间的自由空间划分为伪三角形的结构。
4.3 如何用于可见性？
问题：给定一个运动的观察者和若干凸的运动障碍物，维护观察者周围的可见多边形（visibility polygon）。
朴素方案：维护观察者周围的完整径向分解（radial decomposition）——代价太高。
改进方案（文献[38]）：
构建自由空间的伪三角剖分，使其在靠近观察者的区域越来越接近径向分解，在远离观察者的遮挡区域则保持简单稳定。
这样得到一个结构，能够：
- 紧凑地编码观察者周围随时间变化的可见多边形
- 在观察者看不到的远处区域非常稳定，变化少
用一个比喻理解：
观察者
[O]
近处：精细分解
/ / | | \ \
* * * * * * ← 伪三角形密集，接近径向分解
* * * * *
* * * ← 远处被遮挡，伪三角形稀疏稳定
障碍物 障碍物 障碍物
五、各结构的组合变化次数上界（图24.9）
下表总结了不同几何结构在运动时发生组合变化的次数上界：
| 结构 | 变化次数上界 | 来源 |
|---|---|---|
| 凸包（Convex hull） | O ( n 2 + ε ) O(n^{2+\varepsilon}) O(n2+ε) | [16] |
| 伪三角剖分（Pseudotriangulation） | O ( n 11 / 6 log 3 / 2 n ) O(n^{11/6} \log^{3/2} n) O(n11/6log3/2n) | [5] |
| 三角剖分（任意，Triangulation arb.） | O ~ ( n 7 / 3 ) \tilde{O}(n^{7/3}) O~(n7/3) | [5] |
| 最小生成树（MST） | O ( n 2 ) O(n^2) O(n2) | [6] |
| BSP | O ( n 2 ) O(n^2) O(n2) | [7, 11] |
说明： O ~ \tilde{O} O~ 表示忽略多项式对数因子的大 O O O，即 O ~ ( f ( n ) ) = O ( f ( n ) ⋅ polylog ( n ) ) \tilde{O}(f(n)) = O(f(n) \cdot \text{polylog}(n)) O~(f(n))=O(f(n)⋅polylog(n))
六、C++ 代码示例：BSP 树的简化实现（二维）
以下是一个简化的二维 BSP 树，演示其基本结构和插入/查询逻辑：
#include <iostream>
#include <vector>
#include <memory>
#include <cmath>
// ============================================================
// 二维点
// ============================================================
struct Point2D {
double x, y;
};
// ============================================================
// 二维线段（分割平面在2D退化为直线，这里用线段表示几何体）
// ============================================================
struct Segment {
Point2D a, b; // 线段两端点
};
// ============================================================
// 分割超平面（在2D中是一条直线 ax + by + c = 0）
// ============================================================
struct HalfPlane {
double a, b, c; // 直线方程：a*x + b*y + c = 0
// 计算点 p 在直线哪侧
// 返回值 > 0：正侧；< 0：负侧；= 0：在线上
double classify(const Point2D& p) const {
return a * p.x + b * p.y + c;
}
};
// ============================================================
// BSP 树节点
// ============================================================
struct BSPNode {
HalfPlane splitter; // 该节点使用的分割直线
std::vector<Segment> segments; // 位于该节点分割面上的线段
std::unique_ptr<BSPNode> front; // 正侧子树
std::unique_ptr<BSPNode> back; // 负侧子树
BSPNode() = default;
};
// ============================================================
// 判断线段在分割线的哪一侧
// 返回：1=正侧, -1=负侧, 0=跨越两侧
// ============================================================
int classifySegment(const Segment& seg, const HalfPlane& hp) {
double da = hp.classify(seg.a);
double db = hp.classify(seg.b);
const double EPS = 1e-9;
bool aFront = da > EPS;
bool aBack = da < -EPS;
bool bFront = db > EPS;
bool bBack = db < -EPS;
if ((aFront || (!aFront && !aBack)) && (bFront || (!bFront && !bBack)))
return 1; // 全在正侧或线上
if ((aBack || (!aFront && !aBack)) && (bBack || (!bFront && !bBack)))
return -1; // 全在负侧或线上
return 0; // 跨越
}
// ============================================================
// 简单的 BSP 树构建（随机选取第一条线段作为分割面）
// 注意：这是教学版，实际需要更智能的分割策略
// ============================================================
std::unique_ptr<BSPNode> buildBSP(std::vector<Segment> segs) {
if (segs.empty()) return nullptr;
auto node = std::make_unique<BSPNode>();
// 用第一条线段的方向构造分割直线
// 直线由 seg[0] 的两端点确定: 法向量 = (-(b.y-a.y), b.x-a.x)
const Segment& first = segs[0];
double dx = first.b.x - first.a.x;
double dy = first.b.y - first.a.y;
// 法向量 (ny, -nx) 使得 ny*(x-ax) + (-nx)*(y-ay) = 0
node->splitter = { -dy, dx, dy * first.a.x - dx * first.a.y };
node->segments.push_back(first);
std::vector<Segment> frontSegs, backSegs;
// 将其余线段分类
for (size_t i = 1; i < segs.size(); ++i) {
int side = classifySegment(segs[i], node->splitter);
if (side == 1) {
frontSegs.push_back(segs[i]); // 正侧
} else if (side == -1) {
backSegs.push_back(segs[i]); // 负侧
} else {
// 跨越：简化处理，放入正侧（实际需要分割线段）
frontSegs.push_back(segs[i]);
}
}
// 递归构建子树
node->front = buildBSP(frontSegs);
node->back = buildBSP(backSegs);
return node;
}
// ============================================================
// 从给定观察点出发，按从后到前顺序遍历 BSP 树（画家算法）
// 这正是 BSP 树用于可见性排序的核心操作
// ============================================================
void traverseBackToFront(const BSPNode* node, const Point2D& observer) {
if (!node) return;
double side = node->splitter.classify(observer);
if (side >= 0) {
// 观察者在正侧：先画负侧（背面），再画当前，再画正侧（前面）
traverseBackToFront(node->back.get(), observer);
for (const auto& seg : node->segments)
std::cout << " 渲染线段: (" << seg.a.x << "," << seg.a.y
<< ") -> (" << seg.b.x << "," << seg.b.y << ")\n";
traverseBackToFront(node->front.get(), observer);
} else {
// 观察者在负侧：顺序相反
traverseBackToFront(node->front.get(), observer);
for (const auto& seg : node->segments)
std::cout << " 渲染线段: (" << seg.a.x << "," << seg.a.y
<< ") -> (" << seg.b.x << "," << seg.b.y << ")\n";
traverseBackToFront(node->back.get(), observer);
}
}
// ============================================================
// 打印 BSP 树结构（ASCII 形式）
// ============================================================
void printBSP(const BSPNode* node, int depth = 0) {
if (!node) {
for (int i = 0; i < depth; ++i) std::cout << " ";
std::cout << "[空]\n";
return;
}
for (int i = 0; i < depth; ++i) std::cout << " ";
std::cout << "节点(分割线: "
<< node->splitter.a << "x + "
<< node->splitter.b << "y + "
<< node->splitter.c << " = 0, "
<< "线段数=" << node->segments.size() << ")\n";
printBSP(node->front.get(), depth + 1);
printBSP(node->back.get(), depth + 1);
}
// ============================================================
// 主函数演示
// ============================================================
int main() {
// 构造几条简单的线段
std::vector<Segment> scene = {
{{0, 0}, {4, 0}}, // 线段1：水平线
{{2, -2}, {2, 2}}, // 线段2：竖直线
{{1, 1}, {3, 3}}, // 线段3：斜线
{{-1, 1}, {1, 3}}, // 线段4
};
std::cout << "=== 构建 BSP 树 ===\n";
auto root = buildBSP(scene);
std::cout << "\n=== BSP 树结构 ===\n";
printBSP(root.get());
std::cout << "\n=== 从观察点 (5, 5) 进行从后到前遍历 ===\n";
Point2D observer = {5.0, 5.0};
traverseBackToFront(root.get(), observer);
return 0;
}
七、ASCII 演示：BSP 树构建过程
下面用一个简单的二维例子演示 BSP 树如何逐步切割空间：
初始场景（4条线段在平面上）：
y
^
| D
| /
| /
|/____C________
| \
| \
| B
+-----------> x
A（水平线）
第一刀（用线段 A 所在直线切割）：
顶层: 整个平面
|----------------|
第一层: A上方空间 A下方空间
(含B,C,D) (空)
第二刀（在"A上方"用线段C的直线切割）：
顶层: 整个平面
|------------------------|
第一层: A上方空间 A下方
|------------| [空]
第二层: C左侧空间 C右侧空间
(含D) (含B)
最终 BSP 树：
顶层: 根(A的分割线)
|----------------|
第一层: A上方 A下方
|--------| [空]
第二层: C左侧 C右侧
(有D) (有B)
八、总结
| 内容 | 要点 |
|---|---|
| 核心问题 | 观察者+物体都运动时，实时维护可见性 |
| BSP树 | 用平面递归切割空间，支持增量可见性排序 |
| 动态BSP（2D） | O ( n 2 ) O(n^2) O(n2) 事件，更新 O ( log n ) O(\log n) O(logn)，树大小 O ( n log n ) O(n\log n) O(nlogn) |
| 动态BSP（3D） | 维护代价 O ( n λ s + 2 ( n ) log 2 n ) O(n\lambda_{s+2}(n)\log^2 n) O(nλs+2(n)log2n) |
| 实践问题 | 竖直分解产生薄片块，鲁棒性差 |
| 伪三角剖分 | 对2D可见性更友好，靠近观察者处精细，远处稳定 |
24.5.8 开放问题（Open Problems）详解
一、背景回顾：什么是 KDS？
KDS（Kinetic Data Structure，运动数据结构） 是一类专门处理"运动中的几何对象"的数据结构。
评价一个 KDS 好不好，有四个标准：
| 标准 | 含义 |
|---|---|
| 高效（Efficient） | 处理的事件数接近实际发生的组合变化数（没有大量冗余事件） |
| 响应性（Responsive） | 每个事件处理时间短（更新快） |
| 局部性（Local） | 每个运动对象只参与少量的证书（certificate），结构不"牵一发动全身" |
| 紧凑性（Compact） | 维护的证书数量少，内存占用小 |
下面六个开放问题，都是目前没有同时满足上述四个标准的经典几何结构。
二、六大开放问题逐一解析
问题 1：高维凸包的运动维护
原文：Find an efficient (and responsive, local, and compact) KDS for maintaining the convex hull of points moving in dimensions d ≥ 3 d \geq 3 d≥3.
通俗理解
凸包是包裹所有点的最小凸多边形（二维）或凸多面体（三维及以上）。
想象用一根橡皮筋套住平面上所有的钉子，松开后橡皮筋的形状就是二维凸包。
二维凸包示意（* 是内部点，O 是凸包顶点）：
O
/ \
/ *\
O * O
\* * /
\ /
O
问题所在：
- 二维凸包的运动维护已有较好的算法
- 当维度 d ≥ 3 d \geq 3 d≥3 时，凸包的组合结构（面、棱、顶点）极为复杂
- 目前没有在三维或更高维度下同时满足四个 KDS 标准的算法
难点
高维凸包在点运动时，可能发生复杂的拓扑变化（面的合并、消失、新生），局部更新极难实现。
问题 2：最小包围圆/球的运动维护
原文：Find an efficient KDS for maintaining the smallest enclosing disk in d ≥ 2 d \geq 2 d≥2. For d = 2 d = 2 d=2, a goal would be an O ( n 2 + ε ) O(n^{2+\varepsilon}) O(n2+ε) algorithm.
通俗理解
最小包围圆（Smallest Enclosing Disk / Miniball）：找一个半径最小的圆（或球），使得所有点都在圆内或圆上。
最小包围圆示意：
.----.
/ * \
| * * |
| * |
\ * /
'----'
圆由最远的几个点决定（一般由2或3个点确定）
目标：对于 d = 2 d = 2 d=2（平面情形），希望设计一个事件数为 O ( n 2 + ε ) O(n^{2+\varepsilon}) O(n2+ε) 的算法（ ε \varepsilon ε 是任意小的正数，表示近似二次方）。
为什么难？
最小包围圆由少数几个极值点决定，这些点随运动可能反复切换，维护这种"谁是决定性点"的关系是主要挑战。目前连二维情形的近二次界都未被证明。
问题 3：Voronoi 图事件数的更紧界
原文：Establish tighter bounds on the number of Voronoi diagram events, narrowing the gap between quadratic and near-cubic.
通俗理解
Voronoi 图：给定平面上 n n n 个点（称为"站点"），将平面划分为 n n n 个区域，每个区域内的任意位置距离对应站点最近。
Voronoi 图示意（3个站点 A, B, C）：
+------------------+
| A | |
| | B |
|---------| |
| |--------|
| C | |
+------------------+
三个站点将平面分成三个区域
边界上的点到相邻两站点等距
问题所在：
当
n
n
n 个点运动时，Voronoi 图的组合结构（哪些区域相邻）会发生变化，每次变化称为一个事件。
- 当前已知下界： Ω ( n 2 ) \Omega(n^2) Ω(n2)（至少会有二次方级别的事件）
- 当前已知上界： O ( n 2 + 1 ) = O ( n 3 ) O(n^{2+1} ) = O(n^3) O(n2+1)=O(n3) 附近（接近三次方）
- 目标：缩小这个二次方到近三次方之间的巨大差距
Ω ( n 2 ) ≤ 事件数 ≤ O ( n 3 ) ← 需要收窄 \Omega(n^2) \leq \text{事件数} \leq O(n^3) \quad \leftarrow \text{需要收窄} Ω(n2)≤事件数≤O(n3)←需要收窄
问题 4：线性运动点的任意三角剖分——近二次界
原文：Obtain a near-quadratic bound on the number of events maintaining an arbitrary triangulation of linearly moving points.
通俗理解
三角剖分：将点集连成三角形，把整个区域铺满，相邻三角形共享边但不重叠。
5个点的一种三角剖分：
1---2
|\ /|
| X |
|/ \|
3---4
|
5
（三角形：1-2-4, 1-3-4, 3-4-5 等）
当所有点沿直线匀速运动时（线性运动），三角剖分的拓扑结构（哪些点相连）会变化，每次变化是一个事件。
- 目前最优界约为 O ( n 8 / 3 ) O(n^{8/3}) O(n8/3)（接近 n 2.67 n^{2.67} n2.67）
- 目标：证明
O
(
n
2
+
ε
)
O(n^{2+\varepsilon})
O(n2+ε)（近二次方）
这个问题标注了 * 号，说明这是作者认为尤其重要的问题。
目标： O ( n 2 + ε ) 当前最优： O ( n 8 / 3 ) ≈ O ( n 2.67 ) \text{目标}：O(n^{2+\varepsilon}) \quad \text{当前最优}：O(n^{8/3}) \approx O(n^{2.67}) 目标：O(n2+ε)当前最优：O(n8/3)≈O(n2.67)
问题 5：形状保证的运动三角剖分——次三次时间
原文：Maintain a kinetic triangulation with a guarantee on the shape of the triangles, in subcubic time.
通俗理解
问题 4 只要求"任意"三角剖分（不管三角形形状好不好）。在实际应用中，我们希望三角形形状规则（不要太扁、太细），例如 Delaunay 三角剖分保证没有"劣质"三角形。
好的三角形（接近等边）： 坏的三角形（很扁）：
* *
/ \ /|\
/ \ vs / | \
*-----* *--+--* ← 很扁，数值计算不稳定
Delaunay 三角剖分：满足"空圆性质"——任意三角形的外接圆内不含其他点。这能保证三角形形状尽量规则。
问题所在：维护带形状保证的运动三角剖分，目前最优算法需要
O
(
n
3
)
O(n^3)
O(n3) 甚至更高的时间，目标是降到次三次（
o
(
n
3
)
o(n^3)
o(n3)）。
目标：
o
(
n
3
)
（即严格小于三次方）
\text{目标}：o(n^3) \quad \text{（即严格小于三次方）}
目标：o(n3)（即严格小于三次方）
问题 6：欧氏距离下运动点 MST——次二次界
原文：Find a KDS to maintain the MST of moving points under the Euclidean metric achieving subquadratic bounds.
通俗理解
最小生成树（MST）：将 n n n 个点用 n − 1 n-1 n−1 条边连起来，使得总边长最小，且不形成环。
4个点的 MST 示意：
A---B A---B
| | → |
C---D C---D
（完全图） （MST，去掉最长边）
当点在运动时，MST 的结构（哪些点相连）会变化。
目标：设计事件数为次二次（
o
(
n
2
)
o(n^2)
o(n2)）的 KDS。
目前的算法需要处理
O
(
n
2
)
O(n^2)
O(n2) 个事件，而理想情况下希望能做到
O
(
n
2
−
δ
)
O(n^{2-\delta})
O(n2−δ)（
δ
>
0
\delta > 0
δ>0），即严格少于二次方。
三、六大问题对比总览
问题编号 结构 已知最优 目标
--------------------------------------------------------------
问题 1 凸包（d≥3） 无好算法 4个KDS标准全满足
问题 2 最小包围圆 无近二次算法 O(n^{2+ε})
问题 3 Voronoi图 O(n^3)附近 缩小到接近O(n^2)
问题 4* 任意三角剖分 O(n^{8/3}) O(n^{2+ε})
问题 5 形状保证三角剖分 O(n^3) o(n^3)
问题 6 欧氏MST O(n^2)事件 o(n^2)
四、C++ 示例代码：运动点集与 MST 的朴素实现
下面的代码演示了一个朴素的运动 MST 维护：每隔一个时间步重新计算整个 MST（非 KDS，仅作概念演示）。
真正的 KDS 目标是避免这种全局重算。
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cassert>
// ============================================================
// 二维运动点：位置 = 初始位置 + 速度 * 时间
// ============================================================
struct MovingPoint {
double x0, y0; // 初始位置
double vx, vy; // 速度向量
// 在时刻 t 的位置
double x(double t) const { return x0 + vx * t; }
double y(double t) const { return y0 + vy * t; }
};
// ============================================================
// 计算两点在时刻 t 的欧氏距离
// ============================================================
double dist(const MovingPoint& a, const MovingPoint& b, double t) {
double dx = a.x(t) - b.x(t);
double dy = a.y(t) - b.y(t);
return std::sqrt(dx * dx + dy * dy);
}
// ============================================================
// 并查集（Union-Find），用于 Kruskal 算法构建 MST
// ============================================================
struct UnionFind {
std::vector<int> parent, rank_;
explicit UnionFind(int n) : parent(n), rank_(n, 0) {
std::iota(parent.begin(), parent.end(), 0); // parent[i] = i
}
// 路径压缩查找根节点
int find(int x) {
if (parent[x] != x)
parent[x] = find(parent[x]);
return parent[x];
}
// 按秩合并两个集合，返回是否成功合并（原本不连通）
bool unite(int x, int y) {
int rx = find(x), ry = find(y);
if (rx == ry) return false; // 已在同一集合（会形成环）
if (rank_[rx] < rank_[ry]) std::swap(rx, ry);
parent[ry] = rx;
if (rank_[rx] == rank_[ry]) rank_[rx]++;
return true;
}
};
// ============================================================
// 边：连接两个点的边及其权重（长度）
// ============================================================
struct Edge {
int u, v; // 端点索引
double weight; // 边长
};
// ============================================================
// Kruskal 算法：在时刻 t 计算运动点集的 MST
// 这是朴素方法——每次全量重算
// KDS 的目标就是避免这种全量重算
// ============================================================
std::vector<Edge> computeMST(const std::vector<MovingPoint>& points, double t) {
int n = static_cast<int>(points.size());
// 枚举所有边（完全图，共 n*(n-1)/2 条边）
std::vector<Edge> edges;
edges.reserve(n * (n - 1) / 2);
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j)
edges.push_back({i, j, dist(points[i], points[j], t)});
// 按边长升序排列
std::sort(edges.begin(), edges.end(),
[](const Edge& a, const Edge& b) { return a.weight < b.weight; });
// Kruskal：贪心选边
UnionFind uf(n);
std::vector<Edge> mst;
mst.reserve(n - 1);
for (const auto& e : edges) {
if (uf.unite(e.u, e.v)) {
mst.push_back(e);
if (static_cast<int>(mst.size()) == n - 1)
break; // MST 已有 n-1 条边，完成
}
}
return mst;
}
// ============================================================
// 打印 MST 信息
// ============================================================
void printMST(const std::vector<Edge>& mst, double t) {
double total = 0.0;
std::cout << " 时刻 t=" << t << " 的 MST：\n";
for (const auto& e : mst) {
std::cout << " 点" << e.u << " -- 点" << e.v
<< " 长度=" << e.weight << "\n";
total += e.weight;
}
std::cout << " 总长度=" << total << "\n";
}
// ============================================================
// 检测 MST 拓扑结构是否发生变化（即是否出现 KDS 事件）
// 返回：true 表示结构变化（出现事件）
// ============================================================
bool topologyChanged(const std::vector<Edge>& mst1,
const std::vector<Edge>& mst2) {
if (mst1.size() != mst2.size()) return true;
for (size_t i = 0; i < mst1.size(); ++i) {
if (mst1[i].u != mst2[i].u || mst1[i].v != mst2[i].v)
return true;
}
return false;
}
int main() {
// 构造 5 个运动点
// 格式：初始位置 (x0, y0)，速度 (vx, vy)
std::vector<MovingPoint> points = {
{0.0, 0.0, 0.1, 0.2}, // 点0
{3.0, 0.0, -0.1, 0.1}, // 点1
{1.5, 2.5, 0.0, -0.2}, // 点2
{5.0, 2.0, -0.2, 0.0}, // 点3
{2.0, 4.0, 0.1, -0.1}, // 点4
};
std::cout << "=== 朴素运动 MST 演示 ===\n";
std::cout << "（模拟 KDS 事件检测：每步检查 MST 拓扑是否变化）\n\n";
int eventCount = 0;
double dt = 0.5; // 时间步长
// 初始 MST
auto prevMST = computeMST(points, 0.0);
printMST(prevMST, 0.0);
// 模拟运动，逐步检测事件
for (int step = 1; step <= 10; ++step) {
double t = step * dt;
auto currMST = computeMST(points, t);
if (topologyChanged(prevMST, currMST)) {
++eventCount;
std::cout << "\n[事件！] t=" << t << " MST 拓扑发生变化\n";
printMST(currMST, t);
prevMST = currMST;
} else {
std::cout << " t=" << t << " MST 拓扑未变\n";
}
}
std::cout << "\n共检测到 " << eventCount << " 次 MST 拓扑变化事件。\n";
std::cout << "注：真正的 KDS 目标是将事件处理总代价控制在 o(n^2)。\n";
return 0;
}
五、ASCII 演示：Delaunay 三角剖分的事件（Flip）
运动三角剖分中最常见的"事件"是边翻转（Edge Flip）：当四个点中某一点穿过对面三角形的外接圆时，两个三角形共享的边需要被翻转。
翻转前（点 D 在三角形 ABC 的外接圆内，违反 Delaunay 条件）：
B
/|\
/ | \
/ | \
A---+---C
\ | /
\ | /
\|/
D
对角线是 B-D，但 D 在 △ABC 外接圆内
→ 违反空圆性质，需要翻转
翻转后（将 BD 边换成 AC 边）：
B
/ \
/ \
/ \
A-------C
\ /
\ /
\ /
D
对角线换成 A-C
→ 现在满足空圆性质（Delaunay 条件）
事件发生的时刻：当 A、B、C、D 四点共圆时，此前合法的边变为非法，必须翻转。这就是一个 KDS 事件。
六、各问题的核心难点总结
问题 1（凸包 d≥3）
核心难点：高维凸包拓扑变化极复杂，局部更新代价难以控制
类比：3D 雕塑表面随顶点运动而变形，面的增减难以预测
问题 2（最小包围圆）
核心难点："决定性点"在少数极值点之间反复切换，证书设计困难
类比：橡皮筋套钉子，只有最外面少数几根钉子决定形状
问题 3（Voronoi 图）
核心难点：已知下界与上界之间有接近一次方的差距
差距：Ω(n²) vs O(n³)，相差一个 n 的因子
问题 4*（任意三角剖分）
核心难点：当前 O(n^{8/3}) 与目标 O(n^{2+ε}) 之间仍有差距
重要性：★★★ 作者特别标注
问题 5（形状保证三角剖分）
核心难点：形状约束（如 Delaunay）大幅增加了维护复杂度
类比：不只是铺砖，还要求每块砖尽量接近正方形
问题 6（欧氏 MST）
核心难点：MST 对点的微小运动很敏感，边的切换频繁
目标：严格少于 O(n²) 次事件
七、总结
这六个开放问题代表了运动数据结构领域最核心的挑战。它们的共同特点是：
- 静态版本已有高效算法（凸包、MST、Voronoi 图、三角剖分在静态场景下都有近线性算法）
- 动态/运动版本的复杂度界远未达到理想
- KDS 框架的四个标准（高效、响应、局部、紧凑）难以同时满足
解决这些问题不仅有理论意义，也直接推动计算机图形学、机器人运动规划、动态地图等实际应用的发展。
24.5.8.1 多重证书失效后的恢复（Recovery after Multiple Certificate Failures）
一、回顾：标准 KDS 的假设
标准 KDS（运动数据结构）有一个核心假设：
每次只有一个证书（certificate）失效，且我们能精确预测它何时失效。
证书是 KDS 用来保证当前结论仍然正确的"条件检查"。例如：
- “点 A 还在点 B 的左边” → 这是一个证书
- 证书失效 = 条件不再成立，需要更新结构
在标准 KDS 中，每次处理完一个失效事件后，结构被立即修复，再预测下一个失效时刻。
二、现实困难：无法精确预测失效时刻
在很多现实场景中，我们没有运动物体的精确运动描述（比如物理公式），只能周期性地采样系统状态。
典型场景：
- GPS 每秒更新一次位置（而不是连续轨迹）
- 传感器定时扫描场景（而不是实时监控）
- 物理模拟中每帧才能读取新位置
这时会出现什么问题？
时间轴：
t=0 t=1 t=2
[采样] ??? [采样] ??? [采样]
↑
这段时间内发生了什么？
可能有多个证书相继失效！
我们完全不知道。
核心挑战：两次采样之间，可能有多个证书同时失效，我们"错过"了中间的变化，醒来时面对的是一个已经"乱掉"的状态。
三、由此引出的研究方向
这引出了一个重要的研究问题：
如何在几何对象发生"小幅运动"后，高效地更新常见几何结构？
涉及的结构包括：
- 凸包（Convex Hull）
- Voronoi 图 / Delaunay 三角剖分
- 点排列（Arrangements）
- 等等
关键词是**“小幅运动”**——虽然我们错过了中间过程，但如果每次采样间隔不太长，点的移动量是有限的，理论上结构的变化也不会太剧烈，应该可以比从头重建更高效地修复。
四、核心案例：凸多边形的证书设计
4.1 问题设定
平面上有
n
n
n 个运动的点，按给定的圆形顺序排列，我们想维护"这些点构成的多边形始终是凸多边形"这一属性。
凸多边形的直观定义：从任意顶点出发沿边走，始终只往一个方向转弯（全部左转或全部右转）。
凸多边形（合法）： 非凸多边形（不合法）：
B B
/ \ / \
A C A C
\ / |X|
D D
所有内角 < 180° 有内角 > 180°
4.2 直觉上的证书选择：所有内角都是凸角
一个自然的想法：
证书集合 = “多边形的每个内角都是凸角（< 180°）”
如果共有 n n n 个顶点，就有 n n n 个证书（每个顶点一个角度检查）。
用叉积判断角度方向：对连续三点 P i − 1 , P i , P i + 1 P_{i-1}, P_i, P_{i+1} Pi−1,Pi,Pi+1，计算：
cross ( P i − 1 , P i , P i + 1 ) = ( P i − P i − 1 ) × ( P i + 1 − P i ) \text{cross}(P_{i-1}, P_i, P_{i+1}) = (P_i - P_{i-1}) \times (P_{i+1} - P_i) cross(Pi−1,Pi,Pi+1)=(Pi−Pi−1)×(Pi+1−Pi)
- > 0 > 0 >0：左转（凸角，合法）
- < 0 < 0 <0：右转（凹角，违反凸性）
- = 0 = 0 =0：三点共线
4.3 标准 KDS 中，这个证书集合够用吗？
够用！ 原因是：
只要初始时多边形是凸的，且我们能连续监控所有证书，那么任何一次从凸到非凸的转变，必然会先经历某个内角证书失效的时刻。
这是一个历史证明（historical proof）：
- 初始状态：凸 ✓
- 每次证书失效都被我们捕捉并处理
- → 当前证书全部有效 + 历史从未出错 → 当前一定是凸的
这就像一个安保系统：只要报警器一直开着，没报警就说明一直安全。
五、反例：证书全有效但多边形非凸！
5.1 令人惊讶的反例
看下面这个自交多边形（注意：顶点顺序固定，但边会相交）：
顶点顺序：A → B → C → D → A
正常凸四边形： 自交"蝴蝶形"多边形：
B-----C B C
| | \ /
| | \ /
A-----D / \
/ \
A D
左图：凸，所有内角 < 180°
右图：自交！但如果测量内角...
对于右图的蝴蝶形，在顶点
B
B
B 和
D
D
D 处，内角实际上是凸的（从多边形内部看）——因为自交之后，"内部"的定义变得模糊了。
结论：可以构造出所有内角都是凸角，但整体却是非凸甚至自交的多边形。
5.2 为什么标准 KDS 不受此影响？
关键在于连续运动的约束：
时间轴（连续监控）：
t=0（凸）──→ t=1 ──→ t=2 ──→ t=3
[正常] [正常] [某角证书失效！]
↑
我们立刻捕捉，
处理，多边形
从未"跳过"非凸状态
在连续运动下，多边形不可能在不经过某个角证书失效的情况下，从凸变成上面那种自交形状。物理上需要"穿越"，而穿越时必然有证书失效。
六、Oracle 模型：更强的对手
6.1 什么是 Oracle？
Oracle（神谕/对手） 是一个抽象概念：
想象有一个"捣蛋鬼"，他可以在我们不看的时候偷偷移动点的位置。
我们的视角：
[采样 t=0] ──→ 睡觉 ──→ [采样 t=1]
捣蛋鬼的操作（在我们睡觉时）：
把某些点悄悄移到了新位置！
而且他专门挑：移动后所有角证书仍然有效！
6.2 Oracle 模型下的问题
醒来后，我们检查所有角证书：全部有效！
但实际上，多边形已经变成了上面那个自交的蝴蝶形。
原因：捣蛋鬼绕过了所有证书，直接跳到了一个"证书全有效但结论错误"的状态。
状态空间示意：
合法凸多边形区域： ████████
自交但角证书有效： ░░░░
连续运动只能在 ████ 内移动（穿越边界必经过证书失效）
Oracle 可以直接跳到 ░░░░ 里！
6.3 解决方案：绝对证明
在 Oracle 模型（或周期性采样）下，必须使用绝对证明（absolute proof）：
证书集合在世界的任何状态下，只要全部有效，就能完全保证目标属性成立。
对于凸多边形：仅靠"所有内角是凸角"是不够的（如上所示），还需要额外的证书，比如：
- 确保多边形不自交（例如用线段相交检测）
- 或使用更强的凸性刻画（如所有点在某条参考线的同侧）
七、两种 KDS 模式对比
标准 KDS Oracle / 采样 KDS
---------------------------------------------------------
运动描述 精确的运动函数 只有离散时刻的采样
监控方式 连续监控 周期性采样
证书失效 每次只失效一个 两次采样间可能多个同时失效
证明类型 历史证明 绝对证明
证书要求 较弱（+历史保证即可） 较强（单独成立即可保证属性）
难度 较低 较高
八、C++ 示例代码：凸多边形证书检测（含历史证明 vs 绝对证明）
#include <iostream>
#include <vector>
#include <cmath>
#include <cassert>
// ============================================================
// 二维点
// ============================================================
struct Point {
double x, y;
};
// ============================================================
// 叉积：(B-A) × (C-B)
// > 0：左转（凸角）
// < 0：右转（凹角）
// = 0：共线
// ============================================================
double cross(const Point& A, const Point& B, const Point& C) {
return (B.x - A.x) * (C.y - B.y)
- (B.y - A.y) * (C.x - B.x);
}
// ============================================================
// 检查多边形所有内角是否都是凸角（叉积 >= 0）
// 这是"角度证书"——标准 KDS 中使用
// 注意：这是"弱证明"，在 Oracle 模型下不充分
// ============================================================
bool allAnglesConvex(const std::vector<Point>& poly) {
int n = static_cast<int>(poly.size());
for (int i = 0; i < n; ++i) {
const Point& A = poly[(i - 1 + n) % n]; // 前一个顶点
const Point& B = poly[i]; // 当前顶点
const Point& C = poly[(i + 1) % n]; // 后一个顶点
if (cross(A, B, C) < -1e-9) {
// 右转，存在凹角，角度证书失效
return false;
}
}
return true; // 所有内角都是凸角
}
// ============================================================
// 检查线段 (p1,p2) 和 (p3,p4) 是否相交
// 用于检测多边形是否自交
// ============================================================
bool segmentsIntersect(const Point& p1, const Point& p2,
const Point& p3, const Point& p4) {
// 使用叉积判断跨立关系
double d1 = cross(p3, p4, p1);
double d2 = cross(p3, p4, p2);
double d3 = cross(p1, p2, p3);
double d4 = cross(p1, p2, p4);
// 两线段跨立：一对端点分别在对方两侧
if (((d1 > 1e-9 && d2 < -1e-9) || (d1 < -1e-9 && d2 > 1e-9)) &&
((d3 > 1e-9 && d4 < -1e-9) || (d3 < -1e-9 && d4 > 1e-9)))
return true;
return false; // 忽略端点重合的退化情况
}
// ============================================================
// 检查多边形是否自交
// 枚举所有不相邻的边对，检查是否有相交
// ============================================================
bool isSelfIntersecting(const std::vector<Point>& poly) {
int n = static_cast<int>(poly.size());
for (int i = 0; i < n; ++i) {
for (int j = i + 2; j < n; ++j) {
// 排除首尾相邻的特殊情况
if (i == 0 && j == n - 1) continue;
if (segmentsIntersect(poly[i], poly[(i+1)%n],
poly[j], poly[(j+1)%n])) {
return true; // 发现相交边
}
}
}
return false;
}
// ============================================================
// 绝对证明的凸性检测：
// 条件1：所有内角为凸角
// 条件2：多边形不自交
// 两个条件同时满足 → 确保是真正的凸多边形
// 这在 Oracle 模型下也是正确的
// ============================================================
bool isConvexAbsolute(const std::vector<Point>& poly) {
return allAnglesConvex(poly) && !isSelfIntersecting(poly);
}
// ============================================================
// 打印多边形顶点
// ============================================================
void printPoly(const std::vector<Point>& poly, const std::string& name) {
std::cout << name << "：";
for (const auto& p : poly)
std::cout << "(" << p.x << "," << p.y << ") ";
std::cout << "\n";
}
int main() {
// --------------------------------------------------------
// 测试 1：正常凸四边形
// --------------------------------------------------------
std::vector<Point> convex = {
{0, 0}, {2, 0}, {2, 2}, {0, 2}
};
std::cout << "=== 测试1：正常凸四边形（正方形）===\n";
printPoly(convex, "顶点");
std::cout << "所有角度凸？ " << (allAnglesConvex(convex) ? "是" : "否") << "\n";
std::cout << "是否自交？ " << (isSelfIntersecting(convex) ? "是" : "否") << "\n";
std::cout << "绝对证明凸？ " << (isConvexAbsolute(convex) ? "是" : "否") << "\n\n";
// --------------------------------------------------------
// 测试 2：非凸多边形（有凹角）
// --------------------------------------------------------
std::vector<Point> concave = {
{0, 0}, {2, 0}, {1, 1}, {2, 2}, {0, 2}
};
std::cout << "=== 测试2：非凸多边形（中间有凹入）===\n";
printPoly(concave, "顶点");
std::cout << "所有角度凸？ " << (allAnglesConvex(concave) ? "是" : "否") << "\n";
std::cout << "是否自交？ " << (isSelfIntersecting(concave) ? "是" : "否") << "\n";
std::cout << "绝对证明凸？ " << (isConvexAbsolute(concave) ? "是" : "否") << "\n\n";
// --------------------------------------------------------
// 测试 3：自交"蝴蝶形"多边形（核心反例！）
// 顺序：A(0,0) → B(2,2) → C(2,0) → D(0,2)
//
// D(0,2)----B(2,2)
// \ /
// \ /
// \ / ← 边 AD 和 BC 在中心交叉
// / \
// / \
// A(0,0)----C(2,0)
//
// 这个多边形自交，但所有"内角"测量都是凸的（叉积 > 0）
// 正是文中提到的反例！
// --------------------------------------------------------
std::vector<Point> butterfly = {
{0, 0}, {2, 2}, {2, 0}, {0, 2}
};
std::cout << "=== 测试3：自交蝴蝶形（关键反例）===\n";
std::cout << "顶点顺序：A(0,0) → B(2,2) → C(2,0) → D(0,2)\n";
printPoly(butterfly, "顶点");
std::cout << "所有角度凸？ " << (allAnglesConvex(butterfly) ? "是" : "否") << "\n";
std::cout << " ↑ 仅靠角度证书会误判为凸！（Oracle 模型的危险）\n";
std::cout << "是否自交？ " << (isSelfIntersecting(butterfly) ? "是" : "否") << "\n";
std::cout << "绝对证明凸？ " << (isConvexAbsolute(butterfly) ? "是" : "否") << "\n";
std::cout << " ↑ 绝对证明正确地识别出这不是凸多边形\n\n";
// --------------------------------------------------------
// 演示：Oracle 攻击场景
// 初始合法凸多边形 → Oracle 偷偷修改 → 变成蝴蝶形
// 但角度证书仍然全部有效！
// --------------------------------------------------------
std::cout << "=== Oracle 攻击演示 ===\n";
std::cout << "初始状态（凸正方形）：\n";
printPoly(convex, " 顶点");
std::cout << " 角度证书：" << (allAnglesConvex(convex) ? "全部有效 ✓" : "有失效 ✗") << "\n\n";
std::cout << "Oracle 在我们'不看'时，偷偷把顶点移到蝴蝶形：\n";
printPoly(butterfly, " 顶点");
std::cout << " 角度证书：" << (allAnglesConvex(butterfly) ? "全部有效 ✓（被骗了！）" : "有失效 ✗") << "\n";
std::cout << " 自交检测：" << (isSelfIntersecting(butterfly) ? "自交 ✗（绝对证明揭露真相）" : "无自交") << "\n";
std::cout << " 绝对证明：" << (isConvexAbsolute(butterfly) ? "凸 ✓" : "非凸 ✗（正确结论）") << "\n";
return 0;
}
https://godbolt.org/z/G94Tc34n6
九、ASCII 演示：标准 KDS vs Oracle 模型下的状态转移
标准 KDS（连续监控）
状态变化过程：
t=0 t=1 t=2 t=3
[凸 ✓] → [凸 ✓] → [证书失效!] → [修复后凸 ✓]
↑
检测到角度证书失效
立刻处理，不会跳过
任何中间状态
结论：只要证书一直有效 + 初始是凸的 → 历史证明当前是凸的
Oracle 模型（采样监控）
状态变化过程：
t=0 t=1（采样）
[凸 ✓] → ??? → [蝴蝶形，角度证书全有效！]
↑
这段时间里，Oracle 偷偷移动了点
中间可能经历了非凸状态，但我们没看到
醒来时所有角度证书有效 → 如果用历史证明，会误判为凸！
结论：Oracle 模型下，必须用绝对证明（加上自交检测等）
两种证明方式的比较
历史证明：
[初始状态合法]
+
[证书连续有效，从未失效]
↓
[当前属性成立]
（依赖历史，不适用于 Oracle 模型）
绝对证明：
[证书当前全部有效]
↓
[当前属性成立]
（无需历史，任何时刻独立成立）
十、总结
| 概念 | 要点 |
|---|---|
| 多重证书失效 | 采样/无精确运动描述时，两次采样间可能多个证书同时失效 |
| 历史证明 | 依赖"初始正确 + 连续监控无失效"，在标准 KDS 中有效 |
| 绝对证明 | 证书集合在任何世界状态下独立保证属性，Oracle 模型必须用 |
| 核心反例 | 自交蝴蝶形多边形：所有内角凸，但整体非凸，角度证书不足以绝对证明凸性 |
| 应对策略 | Oracle 模型下需要更强的证书集合（如加入自交检测），代价更高 |
24.5.8.2 层次化运动描述（Hierarchical Motion Descriptions）
一、现实中的运动是有"结构"的
1.1 弹性小球的运动
考虑一个弹跳中的橡皮球。球上每个点的运动轨迹都不完全相同（因为球会变形），但它们有一个共同的规律：
整体运动 = 全局刚体运动（球心的抛物线轨迹 + 球整体旋转）
+ 局部变形（每个点相对于球心的微小抖动）
如果给 1000 个点分别描述轨迹，需要 1000 份数据。
但如果用"全局运动 + 局部偏差"来描述，只需要 1 份全局 + 1000 份很小的局部偏差——大量信息被共享，描述更经济。
1.2 关节人物的运动（人走路）
一个人走路时，身体各部分的运动可以这样描述：
顶层: 躯干（全局位置和朝向）
|------------------------|
再上层: 右上臂（相对躯干） 左上臂（相对躯干）
|---------| |---------|
上层: 右前臂 右手 左前臂 左手
（相对右上臂） （相对左上臂）
关键点：每一级只描述相对于父节点的运动，而不是在世界坐标系中的绝对轨迹。
- 右手的世界坐标 = 躯干运动 × 右上臂运动 × 右前臂运动 × 右手运动
- 如果躯干向前移动了 1 米，右手不需要单独记录"我也向前移了 1 米"——这个信息已经在躯干层级里了
二、层次化运动描述的核心思想
2.1 运动叠加（Superposition）
设物体
i
i
i 的世界坐标位置为
p
i
(
t
)
\mathbf{p}_i(t)
pi(t)，可以分解为：
p
i
(
t
)
=
M
global
(
t
)
⋅
M
group
(
t
)
⋅
M
local
,
i
(
t
)
⋅
p
i
(
0
)
\mathbf{p}_i(t) = \mathbf{M}_{\text{global}}(t) \cdot \mathbf{M}_{\text{group}}(t) \cdot \mathbf{M}_{\text{local},i}(t) \cdot \mathbf{p}_i^{(0)}
pi(t)=Mglobal(t)⋅Mgroup(t)⋅Mlocal,i(t)⋅pi(0)
其中：
- p i ( 0 ) \mathbf{p}_i^{(0)} pi(0)：物体的初始局部坐标（静止姿态）
- M local , i ( t ) \mathbf{M}_{\text{local},i}(t) Mlocal,i(t)：物体自身的局部运动（如手指弯曲）
- M group ( t ) \mathbf{M}_{\text{group}}(t) Mgroup(t)：所属群组的运动（如右臂整体摆动）
-
M
global
(
t
)
\mathbf{M}_{\text{global}}(t)
Mglobal(t)：全局运动（如整个人向前走）
越靠近根节点的变换，被越多对象共享。
2.2 经济性来自哪里？
朴素描述（每个对象独立）：
对象1：x₁(t) = 完整的世界坐标轨迹公式
对象2：x₂(t) = 完整的世界坐标轨迹公式
...
对象n：xₙ(t) = 完整的世界坐标轨迹公式
→ 每个公式都包含重复的全局运动信息
层次化描述：
全局：M_global(t) ← 所有对象共享
群组1：M_group1(t) ← 群组内对象共享
群组2：M_group2(t) ← 群组内对象共享
对象1（属于群组1）：M_local1(t) ← 仅对象1自用
对象2（属于群组1）：M_local2(t) ← 仅对象2自用
...
→ 全局运动只存储一次，被所有对象共享
三、对 KDS 证书评估的简化
3.1 什么是证书的局部性？
KDS 中的证书通常是局部断言，只涉及空间上相近的对象。
例如：
CCW
(
A
,
B
,
C
)
\text{CCW}(A, B, C)
CCW(A,B,C)（反时针方向）
这个证书断言：点
A
A
A、
B
B
B、
C
C
C 按逆时针顺序排列。
CCW
(
A
,
B
,
C
)
⟺
(
B
−
A
)
×
(
C
−
A
)
>
0
\text{CCW}(A, B, C) \iff (B-A) \times (C-A) > 0
CCW(A,B,C)⟺(B−A)×(C−A)>0
（这里
×
\times
× 是二维叉积）
3.2 关节手臂的例子
考虑一条手臂：
躯干(T) ──── 上臂(A) ──── 前臂(B) ──── 手(C)
我们想检测"手臂没有完全伸直"，即
A
A
A、
B
B
B、
C
C
C 三点不共线，用
CCW
(
A
,
B
,
C
)
\text{CCW}(A, B, C)
CCW(A,B,C) 来证书化。
世界坐标系下的证书计算：
CCW
(
A
world
,
B
world
,
C
world
)
\text{CCW}(A_{\text{world}}, B_{\text{world}}, C_{\text{world}})
CCW(Aworld,Bworld,Cworld)
其中每个点都需要：
A
world
=
M
torso
⋅
A
local
A_{\text{world}} = M_{\text{torso}} \cdot A_{\text{local}}
Aworld=Mtorso⋅Alocal
B
world
=
M
torso
⋅
M
upper_arm
⋅
B
local
B_{\text{world}} = M_{\text{torso}} \cdot M_{\text{upper\_arm}} \cdot B_{\text{local}}
Bworld=Mtorso⋅Mupper_arm⋅Blocal
C
world
=
M
torso
⋅
M
upper_arm
⋅
M
lower_arm
⋅
C
local
C_{\text{world}} = M_{\text{torso}} \cdot M_{\text{upper\_arm}} \cdot M_{\text{lower\_arm}} \cdot C_{\text{local}}
Cworld=Mtorso⋅Mupper_arm⋅Mlower_arm⋅Clocal
注意：
M
torso
M_{\text{torso}}
Mtorso（躯干的运动）出现在所有三个点的计算中。
局部坐标系下的证书计算：
由于叉积（和 CCW 判断）在刚体变换（旋转+平移）下保持不变，我们可以直接在上臂的局部坐标系中计算：
CCW
(
A
local
,
B
upper_arm
,
C
upper_arm
)
\text{CCW}(A_{\text{local}}, B_{\text{upper\_arm}}, C_{\text{upper\_arm}})
CCW(Alocal,Bupper_arm,Cupper_arm)
躯干的运动
M
torso
M_{\text{torso}}
Mtorso 对这个证书完全没有影响，可以直接忽略！
结论：层次化运动描述让我们能在最合适的局部坐标系中评估证书，自动过滤掉无关的上层运动。
四、层次化运动树的结构
顶层: 世界坐标系（World Frame）
|------------------------|
再上层: 人物A（全局位移） 人物B（全局位移）
|------------| |------------|
上层: 躯干A 头A 躯干B 头B
|------| |------|
中层: 右臂A 左臂A 右臂B 左臂B
|-----| |-----| |-----| |-----|
底层: 上臂 前臂 上臂 前臂 上臂 前臂 上臂 前臂
证书 CCW(上臂A末端, 前臂A末端, 手A) 只需在"右臂A"局部坐标系中计算
→ 人物A的全局位移、躯干A的运动，统统不需要管！
五、C++ 代码示例：层次化运动树与证书评估
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <memory>
// ============================================================
// 二维向量 / 点
// ============================================================
struct Vec2 {
double x, y;
Vec2(double x = 0, double y = 0) : x(x), y(y) {}
Vec2 operator+(const Vec2& o) const { return {x + o.x, y + o.y}; }
Vec2 operator-(const Vec2& o) const { return {x - o.x, y - o.y}; }
// 二维叉积（标量）
double cross(const Vec2& o) const { return x * o.y - y * o.x; }
void print() const {
std::cout << "(" << x << ", " << y << ")";
}
};
// ============================================================
// 二维刚体变换：旋转 + 平移
// 表示"在父坐标系中，本节点的位置和朝向"
// ============================================================
struct Transform2D {
double tx, ty; // 平移量
double angle; // 旋转角度（弧度）
Transform2D(double tx = 0, double ty = 0, double angle = 0)
: tx(tx), ty(ty), angle(angle) {}
// 将局部坐标点变换到父坐标系
Vec2 apply(const Vec2& p) const {
double cosA = std::cos(angle);
double sinA = std::sin(angle);
return {
cosA * p.x - sinA * p.y + tx,
sinA * p.x + cosA * p.y + ty
};
}
// 变换叠加：先应用 child，再应用 this（即 this ∘ child）
Transform2D compose(const Transform2D& child) const {
double cosA = std::cos(angle);
double sinA = std::sin(angle);
// child 的平移，经过 this 的旋转
double newTx = cosA * child.tx - sinA * child.ty + tx;
double newTy = sinA * child.tx + cosA * child.ty + ty;
return Transform2D(newTx, newTy, angle + child.angle);
}
};
// ============================================================
// 层次化运动树节点
// 每个节点代表一个关节或身体部件
// ============================================================
struct JointNode {
std::string name;
Transform2D localTransform; // 相对于父节点的变换
Vec2 localEndPoint; // 该部件在局部坐标系中的末端点位置
std::vector<std::shared_ptr<JointNode>> children;
JointNode(const std::string& name, const Transform2D& t, const Vec2& ep)
: name(name), localTransform(t), localEndPoint(ep) {}
void addChild(std::shared_ptr<JointNode> child) {
children.push_back(child);
}
};
// ============================================================
// 计算节点末端点的世界坐标
// parentWorldTransform：从父节点局部坐标到世界坐标的变换
// ============================================================
Vec2 getWorldPosition(const JointNode& node,
const Transform2D& parentWorldTransform) {
// 先将父变换与本节点局部变换叠加
Transform2D worldTransform = parentWorldTransform.compose(node.localTransform);
// 再将本节点局部末端点变换到世界坐标
return worldTransform.apply(node.localEndPoint);
}
// ============================================================
// CCW 判断：A、B、C 三点是否逆时针排列
// 叉积 > 0：逆时针（CCW）
// 叉积 < 0：顺时针（CW）
// 叉积 = 0：共线（手臂完全伸直！）
// ============================================================
double ccwValue(const Vec2& A, const Vec2& B, const Vec2& C) {
return (B - A).cross(C - A);
}
bool isCCW(const Vec2& A, const Vec2& B, const Vec2& C) {
return ccwValue(A, B, C) > 1e-9;
}
// ============================================================
// 打印层次树结构（ASCII 缩进形式）
// ============================================================
void printTree(const JointNode& node, const Transform2D& parentT,
int depth = 0) {
// 计算当前节点末端的世界坐标
Transform2D worldT = parentT.compose(node.localTransform);
Vec2 worldPos = worldT.apply(node.localEndPoint);
// 缩进
for (int i = 0; i < depth; ++i) std::cout << " ";
std::cout << "[" << node.name << "] 世界坐标=";
worldPos.print();
std::cout << " 局部偏移=(" << node.localTransform.tx
<< "," << node.localTransform.ty
<< ") 旋转=" << node.localTransform.angle * 180.0 / M_PI << "°\n";
for (const auto& child : node.children)
printTree(*child, worldT, depth + 1);
}
int main() {
// ============================================================
// 构建关节人物的层次运动树（简化版，只含右臂）
//
// 层次结构：
// 躯干(Torso)
// └── 上臂(UpperArm) [A点]
// └── 前臂(ForeArm) [B点]
// └── 手(Hand) [C点]
//
// 我们要验证的证书：CCW(A, B, C)（手臂未完全伸直）
// ============================================================
// 躯干：在世界坐标系中位于 (0,0)，朝向 0°
// 上臂从躯干肩部出发，肩部在局部坐标 (1, 2)
auto torso = std::make_shared<JointNode>(
"躯干(Torso)",
Transform2D(0, 0, 0), // 躯干在世界坐标系的位置
Vec2(0, 0) // 躯干自身末端（重心，无意义）
);
// 上臂：相对躯干，从肩部 (1, 2) 出发，向右上方倾斜 30°，长度 1.5
auto upperArm = std::make_shared<JointNode>(
"上臂(UpperArm)[A]",
Transform2D(1.0, 2.0, 30.0 * M_PI / 180.0), // 相对躯干
Vec2(1.5, 0) // 局部坐标中，上臂末端在 x=1.5 方向
);
// 前臂：相对上臂末端，再旋转 -40°（肘部弯曲），长度 1.2
auto foreArm = std::make_shared<JointNode>(
"前臂(ForeArm)[B]",
Transform2D(1.5, 0, -40.0 * M_PI / 180.0), // 相对上臂末端
Vec2(1.2, 0) // 前臂末端
);
// 手：相对前臂末端，再旋转 -10°，长度 0.5
auto hand = std::make_shared<JointNode>(
"手(Hand)[C]",
Transform2D(1.2, 0, -10.0 * M_PI / 180.0), // 相对前臂末端
Vec2(0.5, 0) // 手末端
);
// 构建树
foreArm->addChild(hand);
upperArm->addChild(foreArm);
torso->addChild(upperArm);
// ============================================================
// 打印层次树结构
// ============================================================
std::cout << "=== 关节人物层次运动树 ===\n\n";
Transform2D identity(0, 0, 0);
printTree(*torso, identity);
// ============================================================
// 计算 A、B、C 的世界坐标
// A = 上臂末端，B = 前臂末端，C = 手末端
// ============================================================
// 躯干变换（世界系）
Transform2D torsoWorld = identity.compose(torso->localTransform);
// 上臂变换（世界系）
Transform2D upperArmWorld = torsoWorld.compose(upperArm->localTransform);
// 前臂变换（世界系）
Transform2D foreArmWorld = upperArmWorld.compose(foreArm->localTransform);
// 手变换（世界系）
Transform2D handWorld = foreArmWorld.compose(hand->localTransform);
Vec2 A = upperArmWorld.apply(upperArm->localEndPoint); // 上臂末端（肘部）
Vec2 B = foreArmWorld.apply(foreArm->localEndPoint); // 前臂末端（腕部）
Vec2 C = handWorld.apply(hand->localEndPoint); // 手末端
std::cout << "\n=== 关键关节世界坐标 ===\n";
std::cout << "A（肘部）= "; A.print(); std::cout << "\n";
std::cout << "B（腕部）= "; B.print(); std::cout << "\n";
std::cout << "C（手末端）= "; C.print(); std::cout << "\n";
// ============================================================
// 在世界坐标系中评估证书 CCW(A, B, C)
// ============================================================
double ccvWorld = ccwValue(A, B, C);
std::cout << "\n=== 在世界坐标系中评估证书 CCW(A,B,C) ===\n";
std::cout << "叉积值 = " << ccvWorld << "\n";
std::cout << "结果：手臂" << (isCCW(A, B, C) ? "未完全伸直（CCW 成立 ✓）"
: "接近或完全伸直（CCW 失效 ✗）") << "\n";
// ============================================================
// 在上臂局部坐标系中评估同一证书
// 这里我们把 B 和 C 变换到上臂局部坐标系来评估
// A 在上臂局部坐标系中就是末端点 (1.5, 0)
//
// 核心：叉积（CCW）在刚体变换下不变，所以两种计算结果相同
// 但局部坐标系的计算不涉及躯干运动（已被"提取"到父节点）
// ============================================================
std::cout << "\n=== 在上臂局部坐标系中评估证书（层次化优化）===\n";
std::cout << "（躯干的全局运动被层次结构自动"
<< "屏蔽，无需参与计算）\n";
// 上臂末端在上臂局部坐标 = (1.5, 0)
Vec2 A_local = upperArm->localEndPoint;
// 前臂末端在上臂局部坐标
Vec2 B_local = foreArm->localTransform.apply(foreArm->localEndPoint);
// 手末端在上臂局部坐标
Transform2D foreToUpper = foreArm->localTransform;
Transform2D handToUpper = foreToUpper.compose(hand->localTransform);
Vec2 C_local = handToUpper.apply(hand->localEndPoint);
double ccvLocal = ccwValue(A_local, B_local, C_local);
std::cout << "A_local = "; A_local.print(); std::cout << "\n";
std::cout << "B_local = "; B_local.print(); std::cout << "\n";
std::cout << "C_local = "; C_local.print(); std::cout << "\n";
std::cout << "叉积值 = " << ccvLocal << "\n";
std::cout << "结果：手臂" << (ccvLocal > 1e-9 ? "未完全伸直（CCW 成立 ✓）"
: "接近或完全伸直（CCW 失效 ✗）") << "\n";
std::cout << "\n两种方法叉积符号一致？ "
<< ((ccvWorld > 0) == (ccvLocal > 0) ? "是 ✓（验证正确）" : "否 ✗")
<< "\n";
// ============================================================
// 模拟躯干平移：验证局部坐标系证书不受影响
// ============================================================
std::cout << "\n=== 模拟躯干大幅平移（+100, +100）后重新评估 ===\n";
Transform2D movedTorso(100, 100, 0);
Transform2D ua2 = movedTorso.compose(upperArm->localTransform);
Transform2D fa2 = ua2.compose(foreArm->localTransform);
Transform2D h2 = fa2.compose(hand->localTransform);
Vec2 A2 = ua2.apply(upperArm->localEndPoint);
Vec2 B2 = fa2.apply(foreArm->localEndPoint);
Vec2 C2 = h2.apply(hand->localEndPoint);
double ccv2 = ccwValue(A2, B2, C2);
std::cout << "躯干平移后，世界坐标叉积 = " << ccv2 << "\n";
std::cout << "与原来叉积值 " << ccvWorld << " 相同？ "
<< (std::abs(ccv2 - ccvWorld) < 1e-6 ? "是 ✓" : "否 ✗") << "\n";
std::cout << "→ 躯干（父节点）的平移完全不影响手臂弯曲证书的值！\n";
std::cout << "→ 层次化运动描述使证书评估只需关注局部，效率大幅提升。\n";
return 0;
}
六、ASCII 演示：层次化运动树的证书评估
关节人物的层次树
顶层: 世界坐标系
|----------------|
再上层: 躯干 T
|---------|
上层: 右臂根 左臂根
|--------|
中层: 上臂[A] （其他）
|
下层: 前臂[B]
|
底层: 手[C]
证书 CCW(A, B, C)：只与上臂、前臂、手有关
→ 躯干T的运动对此证书无影响
→ 只在"上臂局部坐标系"内计算，代价最小
运动叠加的直观图示
世界坐标系的手的位置：
手的世界坐标
= [躯干全局运动]
× [上臂相对躯干的运动]
× [前臂相对上臂的运动]
× [手相对前臂的运动]
× [手的初始局部位置]
朴素 KDS：每次检查证书，都要把所有层的变换都算一遍
层次化 KDS：证书是局部的，只需计算最近公共祖先以下的变换
世界系
/ \
T ...
|
上臂←─────────────────────────────────────────
| ↑
前臂 证书 CCW(A,B,C) 只需这一段的变换！ |
| |
手 已被
提取到上方共享
七、为什么层次化描述能提升 KDS 效率？
7.1 证书评估代价降低
设层次树深度为 d d d，每个节点的变换代价为 O ( 1 ) O(1) O(1)。
- 朴素方式：每次评估证书需要从根到叶完整变换，代价 O ( d ) O(d) O(d)
- 层次化方式：找到涉及节点的最近公共祖先（LCA），只计算 LCA 以下的变换
对于关节人物中相邻关节的证书：LCA 通常距离很近，代价接近 O ( 1 ) O(1) O(1)。
7.2 证书失效频率降低
- 全局运动（躯干平移、旋转）不会让手臂弯曲证书失效
- 只有局部运动（肘部弯曲角度变化）才影响手臂弯曲证书
- 层次化描述将共享运动"因子化"出去，使每个证书的失效条件更精确、更少触发
7.3 总结对比
方法 证书评估代价 冗余更新 适用场景
-------------------------------------------------------------
朴素 KDS O(d) 多（全局运动 独立运动物体
触发局部证书）
层次化 KDS O(局部深度) 少（共享运动 关节体、群体、
已被提取） 有层次结构的场景
八、总结
| 概念 | 要点 |
|---|---|
| 层次化运动描述 | 运动 = 各层局部运动的叠加，共享部分只存储一次 |
| 经济性来源 | 相近物体共享运动分量，减少重复描述 |
| 对 KDS 的好处 | 证书是局部的，在最合适的局部坐标系中评估，过滤掉无关的上层运动 |
| CCW 证书的例子 | CCW ( A , B , C ) \text{CCW}(A,B,C) CCW(A,B,C) 在上臂坐标系中评估，躯干的全局运动完全不参与计算 |
| 核心数学事实 | 叉积（CCW 判断）在刚体变换（旋转+平移）下保持不变，这是局部坐标系评估合法的根本原因 |
24.5.8.3 运动敏感性（Motion Sensitivity）
一、问题的出发点：现实中的运动是"有规律的"
1.1 最坏情况分析的局限
传统算法分析喜欢问：最坏情况下需要多少时间/空间？
对于 KDS 来说，"最坏情况"通常是：
n
n
n 个点完全随机地、独立地运动，彼此之间没有任何关联。
但现实中的运动根本不是这样的：
现实运动的例子：
鸟群飞行： 每只鸟的轨迹高度相似，整体朝同一方向
车流运动： 同一车道的车速度相近，方向完全一致
行星运动： 太阳系行星轨道平滑，变化极慢
布料模拟： 相邻布料点运动几乎相同，差异只在细节
最坏情况： 每个点独立随机跳动，与邻居毫无关联
→ 这种情况在实践中几乎不存在！
问题：如果我们把算法设计的目标对准"最坏情况"，可能会设计出理论上安全、但实践中完全用不上特殊结构的低效算法。
1.2 什么是运动相干性（Motion Coherence）？
运动相干性（Motion Coherence）是描述一组物体运动"有多相似/有多规律"的度量。
直觉上：
- 高相干性：所有点像一个整体一样运动，几乎同步
- 低相干性：每个点各自随机运动，完全无规律
相干性示意（箭头表示速度向量）：
高相干性： 低相干性：
→ → → → → ↑ ← ↓ → ↑
→ → → → → → ↑ ← ↓ →
→ → → → → ↓ → ↑ ← ↓
→ → → → → ← ↓ → ↑ ←
→ → → → → ↑ ← ↓ → ↑
像风吹麦田，整齐一致 像沸腾的水，杂乱无章
二、核心诉求：运动敏感算法
2.1 什么是"运动敏感算法"？
本节提出的研究目标是：
设计一类"运动敏感（motion-sensitive）"算法，其性能可以表示为底层物体运动相干程度的函数。
具体来说，设 κ \kappa κ 是某种刻画运动相干性的参数：
- 当 κ = 0 \kappa = 0 κ=0（完全随机、无相干）：算法退化为一般情况，代价为 O ( f ( n ) ) O(f(n)) O(f(n))
- 当
κ
\kappa
κ 很大（高度相干）：算法代价应该显著降低，例如
O
(
g
(
n
,
κ
)
)
O(g(n, \kappa))
O(g(n,κ))，其中
g
≪
f
g \ll f
g≪f
算法代价 = O ( g ( n , κ ) ) , κ 越大代价越低 \text{算法代价} = O\!\left(g(n,\, \kappa)\right), \quad \kappa \text{ 越大代价越低} 算法代价=O(g(n,κ)),κ 越大代价越低
这就像排序算法中的"自适应排序"：Timsort 等算法在输入接近有序时比纯随机输入快得多。
2.2 为什么需要这类算法？
当前状况：
算法设计 → 针对最坏情况 → 理论上安全
↓
实践中浪费资源
（因为现实运动很有规律）
理想状况：
算法设计 → 针对"运动相干性参数化"的情况
↓
高相干性输入 → 快！
低相干性输入 → 仍然正确（只是慢一点）
三、如何量化运动相干性？
本节没有给出具体的数学定义，但可以从文献和相关工作中归纳出几种常见思路：
3.1 速度差异（Velocity Variance）
最直接的方式：测量所有物体速度向量的"分散程度"。
设
n
n
n 个点的速度为
v
1
,
v
2
,
…
,
v
n
\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_n
v1,v2,…,vn，均值为
v
ˉ
\bar{\mathbf{v}}
vˉ，则速度方差：
σ
2
=
1
n
∑
i
=
1
n
∥
v
i
−
v
ˉ
∥
2
\sigma^2 = \frac{1}{n} \sum_{i=1}^{n} \|\mathbf{v}_i - \bar{\mathbf{v}}\|^2
σ2=n1i=1∑n∥vi−vˉ∥2
- σ 2 = 0 \sigma^2 = 0 σ2=0：所有点速度完全相同（最高相干性）
- σ 2 \sigma^2 σ2 很大：速度高度分散（低相干性）
3.2 事件密度（Event Density）
另一种思路：用实际发生的 KDS 事件数
E
E
E 来描述运动的"复杂程度"。
算法代价
=
O
(
E
⋅
log
n
)
\text{算法代价} = O\!\left(E \cdot \log n\right)
算法代价=O(E⋅logn)
当运动高度相干时，
E
≪
n
2
E \ll n^2
E≪n2，算法比最坏情况快得多。
3.3 最大位移（Maximum Displacement）
在采样模型中，用两次采样之间每个点的最大位移
δ
\delta
δ 作为参数：
δ
=
max
i
∥
p
i
(
t
1
)
−
p
i
(
t
0
)
∥
\delta = \max_{i} \|\mathbf{p}_i(t_1) - \mathbf{p}_i(t_0)\|
δ=imax∥pi(t1)−pi(t0)∥
δ
\delta
δ 小 → “小幅运动” → 几何结构变化少 → 更新代价低：
更新代价
=
O
(
f
(
n
,
δ
)
)
,
f
→
0
当
δ
→
0
\text{更新代价} = O\!\left(f(n, \delta)\right), \quad f \to 0 \text{ 当 } \delta \to 0
更新代价=O(f(n,δ)),f→0 当 δ→0
四、具体例子：相干性对 KDS 事件数的影响
4.1 整体平移（完全相干）
n n n 个点整体平移（所有点速度相同 v i = v \mathbf{v}_i = \mathbf{v} vi=v）：
t=0： t=1：
* * * * * *
* * * →→→ * * *
* * * * * *
点之间的相对位置完全不变！
KDS 事件数 = 0（凸包、Delaunay 三角剖分、MST 的拓扑结构全部不变）
这是相干性最高的情形，算法代价最低。
4.2 整体旋转（高度相干）
n n n 个点绕公共中心旋转（所有点角速度相同）：
t=0： t=1：
* *
* * * → * * * （整体旋转）
* *
相对距离不变，但相对方向会变化
某些几何属性（如凸包形状）不变，但排列顺序相关的属性可能变化。
KDS 事件数远少于最坏情况。
4.3 随机独立运动（零相干性）
每个点独立随机运动：
t=0： t=1：
* * * * (乱)
* * * → 乱乱乱
* * * (乱) *
几乎所有几何关系都在变化！
KDS 事件数 = O ( n 2 ) O(n^2) O(n2) 甚至更高，最坏情况。
五、C++ 示例代码：运动相干性度量与事件敏感统计
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <random>
#include <cassert>
// ============================================================
// 二维运动点
// ============================================================
struct Point {
double x, y;
double vx, vy; // 速度
// 在时刻 t 的位置
double px(double t) const { return x + vx * t; }
double py(double t) const { return y + vy * t; }
};
// ============================================================
// 计算速度相干性：所有点速度向量的方差（越小越相干）
// 返回速度方差 σ²
// ============================================================
double velocityVariance(const std::vector<Point>& pts) {
int n = static_cast<int>(pts.size());
if (n == 0) return 0.0;
// 计算速度均值
double meanVx = 0, meanVy = 0;
for (const auto& p : pts) { meanVx += p.vx; meanVy += p.vy; }
meanVx /= n; meanVy /= n;
// 计算方差
double var = 0;
for (const auto& p : pts) {
double dvx = p.vx - meanVx;
double dvy = p.vy - meanVy;
var += dvx * dvx + dvy * dvy;
}
return var / n; // 速度方差 σ²
}
// ============================================================
// 计算相干性系数 κ（越大越相干）
// κ = 1 / (1 + σ²)，范围 (0, 1]
// σ² = 0 时 κ = 1（完全相干）
// σ² → ∞ 时 κ → 0（完全随机）
// ============================================================
double coherenceKappa(const std::vector<Point>& pts) {
double var = velocityVariance(pts);
return 1.0 / (1.0 + var);
}
// ============================================================
// 叉积，用于 CCW 判断
// ============================================================
double cross2D(double ax, double ay,
double bx, double by,
double cx, double cy) {
return (bx - ax) * (cy - ay) - (by - ay) * (cx - ax);
}
// ============================================================
// 检测相邻三点的 CCW 顺序是否发生改变（即是否发生 KDS 事件）
// 对所有相邻三点组合进行检测
// 这是一个简化的"事件检测器"
// ============================================================
int countTopologyChanges(const std::vector<Point>& pts,
double t0, double t1, int steps) {
int n = static_cast<int>(pts.size());
if (n < 3) return 0;
int eventCount = 0;
double dt = (t1 - t0) / steps;
// 记录上一时刻所有相邻三元组的 CCW 符号
// 这里简化：只检查顺序相邻的三元组 (i, i+1, i+2)
std::vector<int> prevSign(n - 2);
for (int i = 0; i < n - 2; ++i) {
double cv = cross2D(
pts[i].px(t0), pts[i].py(t0),
pts[i+1].px(t0), pts[i+1].py(t0),
pts[i+2].px(t0), pts[i+2].py(t0)
);
prevSign[i] = (cv > 1e-12) ? 1 : (cv < -1e-12 ? -1 : 0);
}
// 逐步推进时间，检测符号变化
for (int step = 1; step <= steps; ++step) {
double t = t0 + step * dt;
for (int i = 0; i < n - 2; ++i) {
double cv = cross2D(
pts[i].px(t), pts[i].py(t),
pts[i+1].px(t), pts[i+1].py(t),
pts[i+2].px(t), pts[i+2].py(t)
);
int curSign = (cv > 1e-12) ? 1 : (cv < -1e-12 ? -1 : 0);
if (curSign != prevSign[i] && curSign != 0) {
++eventCount; // 符号发生改变，视为一次 KDS 事件
prevSign[i] = curSign;
}
}
}
return eventCount;
}
// ============================================================
// 生成不同相干性的点集
// mode=0：完全相干（所有点速度相同）
// mode=1：部分相干（速度有小扰动）
// mode=2：完全随机（速度完全随机）
// ============================================================
std::vector<Point> generatePoints(int n, int mode, unsigned seed = 42) {
std::mt19937 rng(seed);
std::uniform_real_distribution<double> posDist(-5.0, 5.0);
std::uniform_real_distribution<double> perturbDist(-0.1, 0.1); // 小扰动
std::uniform_real_distribution<double> randVel(-2.0, 2.0); // 随机速度
std::vector<Point> pts(n);
// 基础速度（所有点共享）
double baseVx = 1.0, baseVy = 0.5;
for (auto& p : pts) {
p.x = posDist(rng);
p.y = posDist(rng);
if (mode == 0) {
// 完全相干：所有点速度完全相同
p.vx = baseVx;
p.vy = baseVy;
} else if (mode == 1) {
// 部分相干：基础速度 + 小扰动
p.vx = baseVx + perturbDist(rng);
p.vy = baseVy + perturbDist(rng);
} else {
// 完全随机：速度完全随机
p.vx = randVel(rng);
p.vy = randVel(rng);
}
}
return pts;
}
// ============================================================
// 运行一次完整的"运动敏感性"分析
// ============================================================
void analyzeMotionSensitivity(const std::string& label,
const std::vector<Point>& pts,
double t0, double t1, int steps) {
double kappa = coherenceKappa(pts);
double var = velocityVariance(pts);
int events = countTopologyChanges(pts, t0, t1, steps);
std::cout << "--- " << label << " ---\n";
std::cout << " 速度方差 σ² = " << var << "\n";
std::cout << " 相干系数 κ = " << kappa << " （越接近1越相干）\n";
std::cout << " 检测到事件数 = " << events
<< " （κ越大事件越少）\n\n";
}
int main() {
const int N = 20; // 点数
const double T0 = 0.0;
const double T1 = 5.0;
const int STEPS = 1000; // 时间步数（模拟精度）
std::cout << "=== 运动敏感性分析演示 ===\n\n";
std::cout << "点数 n=" << N << "，时间区间 [" << T0 << ", " << T1
<< "]，步数=" << STEPS << "\n\n";
// 三种相干性场景
auto pts0 = generatePoints(N, 0); // 完全相干
auto pts1 = generatePoints(N, 1); // 部分相干
auto pts2 = generatePoints(N, 2); // 完全随机
analyzeMotionSensitivity("场景1：完全相干（整体平移）",
pts0, T0, T1, STEPS);
analyzeMotionSensitivity("场景2：部分相干（加小扰动）",
pts1, T0, T1, STEPS);
analyzeMotionSensitivity("场景3：完全随机（无相干性）",
pts2, T0, T1, STEPS);
// ============================================================
// 演示：相干性参数 κ 与事件数的关系
// 逐步增加扰动幅度，观察 κ 与事件数的变化趋势
// ============================================================
std::cout << "=== 相干性 κ 与事件数的关系（逐步增加扰动）===\n\n";
std::cout << "扰动幅度 κ 事件数\n";
std::cout << "----------- ---------- --------\n";
std::mt19937 rng(42);
std::uniform_real_distribution<double> posDist(-5.0, 5.0);
// 从很小的扰动到很大的扰动
std::vector<double> perturbLevels = {0.0, 0.05, 0.2, 0.5, 1.0, 2.0, 5.0};
for (double perturb : perturbLevels) {
std::vector<Point> pts(N);
std::uniform_real_distribution<double> pd(-perturb, perturb);
for (auto& p : pts) {
p.x = posDist(rng);
p.y = posDist(rng);
p.vx = 1.0 + (perturb > 0 ? pd(rng) : 0.0);
p.vy = 0.5 + (perturb > 0 ? pd(rng) : 0.0);
}
double kappa = coherenceKappa(pts);
int events = countTopologyChanges(pts, T0, T1, STEPS);
// 格式化输出
std::cout << " " << perturb;
// 对齐填充
std::string ps = std::to_string(perturb);
for (int s = ps.size(); s < 10; ++s) std::cout << " ";
std::cout << kappa;
std::string ks = std::to_string(kappa).substr(0, 8);
for (int s = ks.size(); s < 10; ++s) std::cout << " ";
std::cout << events << "\n";
}
std::cout << "\n结论：扰动越大 → κ 越小 → 事件数越多 → 算法代价越高\n";
std::cout << "运动敏感算法的目标：用 κ 来参数化算法代价，\n";
std::cout << "使得高相干性输入（κ ≈ 1）时代价接近最优。\n";
return 0;
}
六、ASCII 演示：相干性谱系
相干性从高到低：
κ ≈ 1.0 完全相干（整体平移/旋转）
│
│ → → → → →
│ → → → → → 所有点速度完全相同
│ → → → → → KDS 事件数 = 0
│
│
κ ≈ 0.9 高度相干（群体运动，小扰动）
│
│ → → ↗ → →
│ ↗ → → → ↗ 速度基本一致，有微小差异
│ → ↗ → → → KDS 事件数很少
│
│
κ ≈ 0.5 中等相干（部分关联）
│
│ → ↑ → ↓ →
│ ↑ → ↑ → ↑ 速度方向分散，有一定规律
│ → ↑ ↓ → → KDS 事件数中等
│
│
κ ≈ 0.1 低相干（近似随机）
│
│ ↑ ← ↓ → ↑
│ → ↑ ← ↓ → 速度完全随机
│ ↓ → ↑ ← ↓ KDS 事件数接近最坏情况 O(n²)
│
κ ≈ 0.0 完全随机
七、与自适应算法的类比
运动敏感算法的思想与算法领域中的自适应算法（Adaptive Algorithm） 高度相似：
排序领域：
输入逆序度 = 0（已排序）→ Timsort 代价 O(n)
输入逆序度 = 最大值 → Timsort 代价 O(n log n)
参数化：代价 = O(n + n·log(逆序度/n))
运动KDS领域（类比）：
运动相干性 κ = 1（完全相干）→ 算法代价接近 O(n)
运动相干性 κ ≈ 0（完全随机）→ 算法代价 O(n²) 或更高
参数化：代价 = O(g(n, κ))，κ 越大代价越小
两者的共同点：
√ 在特殊结构（有序 / 相干）时远快于最坏情况
√ 在最坏情况下仍然正确（只是慢一点）
√ 用一个参数刻画输入的"规律程度"
八、总结
| 概念 | 要点 |
|---|---|
| 问题根源 | 现实运动高度相干，但传统 KDS 分析针对最坏情况，无法利用这一结构 |
| 运动相干性 | 刻画一组物体运动"有多相似"的度量，高相干 = 速度方差小 |
| 相干性参数 κ \kappa κ | 由运动的速度方差等导出， κ → 1 \kappa \to 1 κ→1 表示高度相干， κ → 0 \kappa \to 0 κ→0 表示随机 |
| 运动敏感算法 | 性能表示为 O ( g ( n , κ ) ) O(g(n, \kappa)) O(g(n,κ))， κ \kappa κ 越大代价越低 |
| 研究意义 | 避免算法设计被不现实的最坏情况主导，从实际数据的特殊结构中获益 |
| 类比 | 类似排序中的自适应算法（Timsort），在"接近有序"时远快于一般情况 |
24.5.8.4 非规范结构（Non-Canonical Structures）
一、规范结构 vs 非规范结构
1.1 什么是规范结构（Canonical Structure）？
规范结构是指：给定一组点的位置，结构的形态被唯一确定，与算法无关、与历史无关。
常见的规范结构：
给定 5 个点： 无论用什么算法，结果唯一
* * 凸包： 最小包围凸多边形
*----------*
* | * | ← 唯一
* * *----------*
Delaunay 三角剖分：
满足空圆性质的唯一三角剖分
（退化情形除外）
最近点对：
距离最小的两个点 → 唯一确定
关键性质：外部事件（External Event）= 结构发生变化的时刻，与维护算法无关，只取决于点的位置变化。
例如，Delaunay 三角剖分的外部事件 = 四点共圆的时刻，这是纯粹的几何条件，任何算法都一样。
1.2 什么是非规范结构（Non-Canonical Structure）？
非规范结构是指：给定同样一组点，可能存在多种合法形态，具体是哪一种取决于算法和历史。
最典型的例子：一般三角剖分（arbitrary triangulation）
同样 4 个点，有两种合法三角剖分：
A-------B A-------B
| \ | | / |
| \ | 或 | / |
| \| |/ |
D-------C D-------C
对角线 AC 对角线 BD
两种都是合法三角剖分，没有哪个"更正确"！
既然同样的点可以对应多种三角剖分，那么：
- "三角剖分发生变化"的时刻取决于当前维护的是哪种三角剖分
- 而当前是哪种，又取决于我们用的算法和历史演化路径
二、这对 KDS 分析造成了什么困难？
2.1 外部事件的定义变得模糊
对于规范结构，外部事件有客观的定义：
外部事件
=
纯粹由点的位置决定的结构变化时刻
\text{外部事件} = \text{纯粹由点的位置决定的结构变化时刻}
外部事件=纯粹由点的位置决定的结构变化时刻
对于非规范结构，"外部事件"的定义依赖算法：
算法 A 维护的三角剖分： 算法 B 维护的三角剖分：
对角线 AC 对角线 BD
点移动时，AC 变成非法 点移动同样的距离，BD 还合法
→ 算法 A 触发事件 → 算法 B 不触发事件
同样的点运动，不同算法的事件数完全不同！
→ 无法公平比较算法之间的效率
2.2 效率分析失去基准
对于规范结构，我们可以定义：
算法效率
=
算法处理的事件数
外部事件数（最优下界）
\text{算法效率} = \frac{\text{算法处理的事件数}}{\text{外部事件数（最优下界）}}
算法效率=外部事件数（最优下界）算法处理的事件数
这个比值是算法无关的基准，可以用来公平评价算法质量。
对于非规范结构，分母（外部事件数）本身就取决于算法，比值失去意义：
算法A的事件数
算法A的"外部"事件数
vs
算法B的事件数
算法B的"外部"事件数
\frac{\text{算法A的事件数}}{\text{算法A的"外部"事件数}} \quad \text{vs} \quad \frac{\text{算法B的事件数}}{\text{算法B的"外部"事件数}}
算法A的"外部"事件数算法A的事件数vs算法B的"外部"事件数算法B的事件数
两个分母不同，无法比较。
三、当前的主流解决方案：人为施加规范性
3.1 强制选择一种规范结构
最常见的做法：从所有合法三角剖分中人为选定一种，将其升格为"规范的"，然后维护这个规范结构。
最典型的例子就是 Delaunay 三角剖分：
所有合法三角剖分中，选"空圆性质"作为规范条件：
非 Delaunay： Delaunay（规范）：
A-------B A-------B
| \ | | / |
| \ | → | / |
| \| |/ |
D-------C D-------C
D 在 △ABC 外接圆内 空圆性质满足，唯一确定
（违反 Delaunay）
优点：结构唯一确定，外部事件有客观定义，可以公平分析算法效率。
缺点：增加了事件数量！
3.2 为什么规范化会增加事件数？
直觉解释：
非规范三角剖分（懒惰维护）：
点在运动 → 当前三角剖分还"凑合合法" → 不翻转边 → 0 事件
规范 Delaunay 三角剖分（严格维护）：
点在运动 → 空圆条件稍微违反 → 立刻翻转边 → 1 个事件
同样的点运动，规范化触发了更多事件！
换句话说，规范结构对点的运动"更敏感"，会捕捉到更多微小变化。
形式上，Delaunay 三角剖分的事件数上界约为：
O
(
n
2
)
到
O
(
n
8
/
3
)
O\!\left(n^2\right) \text{ 到 } O\!\left(n^{8/3}\right)
O(n2) 到 O(n8/3)
而某些非规范三角剖分可能只需要处理
O
(
n
2
)
O(n^2)
O(n2) 甚至更少的事件——如果我们允许结构依赖历史的话。
四、历史依赖结构（History-Dependent Structures）
4.1 什么是历史依赖结构？
历史依赖结构：当前结构的具体形态，不仅取决于点的当前位置，还取决于结构的历史演化路径。
时间轴：
t=0 t=1 t=2
初始三角剖分 点稍微移动 点再移动
↓ ↓ ↓
形态 T₀ T₀ 还合法？ 仍合法？
是 → 保持 T₀ 是 → 保持 T₀
否 → 最小修改 否 → 最小修改
当前结构 = T₀ + 历史中所有必要的最小修改
→ 两条从 T₀ 出发的不同运动路径，即使最终点位置相同，
也可能得到不同的当前结构！
4.2 为什么历史依赖结构可能更高效？
关键洞察：如果我们采用"能不改就不改"的策略，只在当前结构真正无法维持时才做最小修改，那么：
- 事件数 = 实际必须修改的次数（往往远少于规范结构）
- 每次修改代价低（局部翻转，
O
(
log
n
)
O(\log n)
O(logn) 级别）
代价： - 很难分析这类算法的理论性能（因为最优事件数不再有客观基准）
- 分析需要依赖历史路径，而历史可以是任意的
本节的核心结论：
我们目前缺乏分析历史依赖结构的数学工具。这是 KDS 领域一个重要的开放问题。
五、两种策略的对比
策略 规范化（强制唯一） 历史依赖（懒惰维护）
---------------------------------------------------------------------
结构唯一性 唯一确定 依赖历史，不唯一
外部事件定义 客观、与算法无关 依赖算法，无客观基准
事件数量 较多（对运动更敏感） 较少（能不改就不改）
算法分析 成熟，有完善理论工具 困难，缺乏数学工具
典型例子 Delaunay 三角剖分 任意合法三角剖分
当前研究状态 主流，已有较好结果 开放问题，待研究
六、C++ 示例代码：规范 vs 非规范三角剖分的事件数对比
#include <iostream>
#include <vector>
#include <cmath>
#include <array>
#include <cassert>
// ============================================================
// 二维点（支持随时间线性运动）
// ============================================================
struct Point {
double x, y; // 当前位置
double vx, vy; // 速度（线性运动）
double px(double t) const { return x + vx * t; }
double py(double t) const { return y + vy * t; }
};
// ============================================================
// 叉积：判断 C 在有向线段 AB 的哪一侧
// > 0：左侧（逆时针）
// < 0：右侧（顺时针）
// = 0：共线
// ============================================================
double cross2D(double ax, double ay,
double bx, double by,
double cx, double cy) {
return (bx - ax) * (cy - ay) - (by - ay) * (cx - ax);
}
// ============================================================
// 空圆测试（In-Circle Test）：
// 检验点 D 是否在三角形 ABC 的外接圆内部
// 返回 > 0：D 在圆内（违反 Delaunay 条件，需要翻转）
// 返回 < 0：D 在圆外（Delaunay 条件满足）
// 返回 = 0：D 恰好在圆上（退化情形，即外部事件时刻）
//
// 数学原理：计算如下行列式
// | ax-dx ay-dy (ax-dx)²+(ay-dy)² |
// | bx-dx by-dy (bx-dx)²+(by-dy)² |
// | cx-dx cy-dy (cx-dx)²+(cy-dy)² |
// ============================================================
double inCircle(double ax, double ay,
double bx, double by,
double cx, double cy,
double dx, double dy) {
double adx = ax - dx, ady = ay - dy;
double bdx = bx - dx, bdy = by - dy;
double cdx = cx - dx, cdy = cy - dy;
return adx * (bdy * (cdx*cdx + cdy*cdy) - cdy * (bdx*bdx + bdy*bdy))
- ady * (bdx * (cdx*cdx + cdy*cdy) - cdx * (bdx*bdx + bdy*bdy))
+ (adx*adx + ady*ady) * (bdx * cdy - bdy * cdx);
}
// ============================================================
// 四边形（由两个共享对角线的三角形构成）
// 顶点顺序：A, B, C, D 构成凸四边形
// 当前对角线：AC（即三角形 ABC 和 ACD）
// 备选对角线：BD（即三角形 ABD 和 BCD）
// ============================================================
struct Quad {
int a, b, c, d; // 四个顶点的索引（逆时针顺序）
bool useAC; // true=使用对角线AC，false=使用对角线BD
};
// ============================================================
// 检查四边形当前对角线是否需要翻转（Delaunay 规范化检查）
// 如果 D 在 △ABC 的外接圆内，则对角线 AC 不满足 Delaunay，需翻转
// ============================================================
bool needsFlip(const std::vector<Point>& pts, const Quad& q, double t) {
double ax = pts[q.a].px(t), ay = pts[q.a].py(t);
double bx = pts[q.b].px(t), by = pts[q.b].py(t);
double cx = pts[q.c].px(t), cy = pts[q.c].py(t);
double dx = pts[q.d].px(t), dy = pts[q.d].py(t);
if (q.useAC) {
// 当前对角线是 AC，检查 D 是否在 △ABC 外接圆内
return inCircle(ax, ay, bx, by, cx, cy, dx, dy) > 1e-9;
} else {
// 当前对角线是 BD，检查 A 是否在 △BCD 外接圆内
return inCircle(bx, by, cx, cy, dx, dy, ax, ay) > 1e-9;
}
}
// ============================================================
// 检查四边形的任意对角线是否合法
// （非规范策略：只要当前对角线"没有明显问题"就不翻转）
// 这里"没有明显问题"的宽松条件：对角线的两个三角形都不退化
// ============================================================
bool isDegenerate(const std::vector<Point>& pts,
int i, int j, int k, double t) {
// 检查三点是否接近共线（面积接近 0）
double area = cross2D(
pts[i].px(t), pts[i].py(t),
pts[j].px(t), pts[j].py(t),
pts[k].px(t), pts[k].py(t)
);
return std::abs(area) < 1e-9;
}
bool currentDiagStillValid(const std::vector<Point>& pts,
const Quad& q, double t) {
if (q.useAC) {
// 对角线 AC：检查 △ABC 和 △ACD 都不退化
return !isDegenerate(pts, q.a, q.b, q.c, t)
&& !isDegenerate(pts, q.a, q.c, q.d, t);
} else {
// 对角线 BD：检查 △ABD 和 △BCD 都不退化
return !isDegenerate(pts, q.a, q.b, q.d, t)
&& !isDegenerate(pts, q.b, q.c, q.d, t);
}
}
// ============================================================
// 主模拟：对比规范 Delaunay 策略 vs 非规范懒惰策略的事件数
// ============================================================
int main() {
// 构造 4 个运动点（一个凸四边形，逐渐变形）
// A(0,0)→右移, B(2,0)→右移慢, C(2,2)→左移, D(0,2)→不动
std::vector<Point> pts = {
{0.0, 0.0, 0.3, 0.0}, // A：向右
{2.0, 0.0, 0.1, 0.0}, // B：向右（慢）
{2.0, 2.0, -0.2, 0.1}, // C：向左上
{0.0, 2.0, 0.0, 0.0}, // D：静止
};
// 四边形：A=0, B=1, C=2, D=3
// 初始对角线：AC（即 useAC = true）
Quad q_delaunay = {0, 1, 2, 3, true}; // 规范（Delaunay）策略
Quad q_lazy = {0, 1, 2, 3, true}; // 非规范（懒惰）策略
int events_delaunay = 0; // 规范策略的翻转事件数
int events_lazy = 0; // 非规范策略的翻转事件数
double dt = 0.01;
double tEnd = 5.0;
std::cout << "=== 规范 vs 非规范三角剖分事件数对比 ===\n\n";
std::cout << "四个运动点构成一个凸四边形，模拟时间 [0, "
<< tEnd << "]，步长 " << dt << "\n\n";
for (double t = dt; t <= tEnd; t += dt) {
// ---- 规范（Delaunay）策略：只要违反空圆条件立刻翻转 ----
if (needsFlip(pts, q_delaunay, t)) {
q_delaunay.useAC = !q_delaunay.useAC; // 翻转对角线
++events_delaunay;
}
// ---- 非规范（懒惰）策略：只有当前对角线完全失效才翻转 ----
// "失效"的宽松条件：当前对角线产生退化三角形
if (!currentDiagStillValid(pts, q_lazy, t)) {
q_lazy.useAC = !q_lazy.useAC; // 翻转对角线
++events_lazy;
}
}
std::cout << "规范 Delaunay 策略：翻转事件数 = " << events_delaunay << "\n";
std::cout << "非规范懒惰策略： 翻转事件数 = " << events_lazy << "\n\n";
if (events_delaunay > events_lazy) {
std::cout << "结论：规范化增加了 "
<< (events_delaunay - events_lazy)
<< " 次额外事件（"
<< 100.0 * (events_delaunay - events_lazy) / std::max(1, events_lazy)
<< "% 的开销）\n";
} else {
std::cout << "结论：在此场景下两者事件数相近。\n";
}
std::cout << "\n说明：\n";
std::cout << " 规范策略：只要空圆条件被轻微违反就翻转，对运动极敏感\n";
std::cout << " 懒惰策略：只在结构真正退化时才翻转，事件数更少\n";
std::cout << " 但懒惰策略依赖历史，理论分析极困难——这正是本节的开放问题！\n";
return 0;
}
七、ASCII 演示：规范化如何增加事件数
场景：四个点的两种三角剖分策略
初始状态（t=0）：
A(0,0)--------B(2,0)
| / |
| / |
| / |
| / |
| / |
D(0,2)--------C(2,2)
当前对角线：AC（△ABC + △ACD）
两种策略都从这里出发
点稍微移动后（t=1）：
A'-------B'
| \ |
| \ | ← D' 刚好进入 △AB'C' 的外接圆
| \| （轻微违反 Delaunay）
D'--------C'
规范（Delaunay）策略：
检测到 D' 在外接圆内 → 立刻翻转！→ 事件数 +1
新对角线：BD
非规范（懒惰）策略：
当前三角剖分还合法（只是不那么"优质"）→ 不翻转！→ 事件数不变
再移动一段后（t=2）：
A''------B''
| |
| | ← 此时 AC 对角线产生退化三角形
| | 两种策略都必须翻转
D''------C''
两种策略都翻转 → 各自事件数 +1
统计对比：
时间段 规范策略 懒惰策略
t=0 ~ t=1 翻转（+1） 不翻转（0）
t=1 ~ t=2 翻转（+1） 翻转（+1）
t=2 ~ t=3 翻转（+1） 不翻转（0）
...
总计： N 次 < N 次
规范化引入了额外的事件，但获得了可分析性（理论工具成熟）
懒惰维护事件更少，但无法分析（缺乏数学工具）——开放问题！
八、核心矛盾总结
可分析性
↑
强 | 规范结构（Delaunay 等）
| 事件多，但可以用成熟理论分析
| 外部事件有客观定义
|
|
弱 | 历史依赖结构（懒惰维护）
| 事件少，实践中可能更高效
| 但缺乏数学分析工具
| 外部事件无客观基准
+--------------------------------→
事件少 事件多
这个矛盾是 KDS 领域目前尚未解决的根本性困难之一。
九、总结
| 概念 | 要点 |
|---|---|
| 规范结构 | 由点的位置唯一确定（凸包、Delaunay），外部事件有客观定义 |
| 非规范结构 | 同样的点对应多种合法形态（任意三角剖分），外部事件依赖算法 |
| 规范化代价 | 人为施加规范性（如强制 Delaunay）→ 增加事件数，但获得可分析性 |
| 历史依赖结构 | 当前形态取决于历史演化路径，可能更高效但无法分析 |
| 开放问题 | 缺乏分析历史依赖结构的数学工具，这是 KDS 领域的重要研究方向 |
24.6 移动对象查询（Querying Moving Objects）
一、核心问题：我们并不总是需要"全程跟踪"
1.1 从"全程监控"到"按需查询"
想象你是一个城市交通管理员，管理着
n
n
n 辆出租车（它们在二维平面
R
2
\mathbb{R}^2
R2 上移动）。
你有两种工作模式：
模式A：全程跟踪（Kinetic方法）
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
时间轴: ──────────────────────────────>
车辆1: ●→→→●→→→●→→→●→→→●→→→●→→→●
车辆2: ●→→→●→→→●→→→●→→→●→→→●→→→●
车辆3: ●→→→●→→→●→→→●→→→●→→→●→→→●
↑ ↑ ↑ ↑ ↑ ↑ ↑
每一刻都在维护所有车辆的位置信息
代价：很高！但信息最完整
模式B：按需查询（本节讨论的方法）
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
时间轴: ──────────────────────────────>
车辆们: ... ... ... ... ...
↑ ↑
查询1 查询2
"此刻谁在区域R里？" "t时刻谁在区域R'里？"
代价：只在需要时付出，更经济
关键洞察：很多应用场景下，我们不需要知道物体的全部运动历史，只需要在特定时刻回答特定问题。
1.2 典型查询示例
给定 n n n 个在 R 2 \mathbb{R}^2 R2 中移动的点，典型的查询包括：
查询类型1：时刻查询
"在时刻 t，矩形 R 内有哪些点？"
y
↑
│ ┌─────────┐
│ │ R │ ●P3
│ │ ●P1 │
│ │ ●P2│
│ └─────────┘
│ ●P4
└──────────────────→ x
回答：P1 和 P2 在矩形 R 内
查询类型2：时间区间查询
"在时间段 [t1, t2] 内，哪些点曾经进入过矩形 R？"
时刻t1 时刻t2
●P1 ●P1→→→→→进入R
●P2 ●P2（一直在R内）
●P3 ●P3→→离开R
回答：P1、P2、P3 都在某个时刻位于 R 内
查询类型3：带变化的R和t
"对于不同的矩形 R 和时刻 t，反复查询"
（R 和 t 都是查询参数，每次可以不同）
二、解决思路：动静结合
2.1 两种极端策略
处理移动对象查询，有两种极端策略：
策略 优点 缺点
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
纯 Kinetic 随时能回答 维护成本高
(全程维护索引) 查询速度快 大部分维护可能用不上
纯 Static 不用维护 每次查询从头建索引
(每次查询重建) 简单 查询速度慢
最佳方案：混合使用动态（kinetic）技术和静态（static）技术。
2.2 混合方法的核心思想
混合策略的时间线:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
时间: ─────────────────────────────────────→
Kinetic索引: [===维护中===] [===维护中===]
↑ 停止维护（这段时间没有查询需求）
Static快照: ★ 查询来了！
快速建立当前时刻的静态快照
用静态数据结构回答
关键权衡:
┌──────────────────────────────────────────────┐
│ 频繁查询的时间段 → 维护 Kinetic 索引更划算 │
│ 偶尔查询的时间段 → 用 Static 快照更划算 │
└──────────────────────────────────────────────┘
2.3 使用的标准工具
论文提到两种经典的范围搜索（range searching）数据结构：
分区树（Partition Tree）
分区树的思想：将空间递归划分
整个空间
|----------------|
左半区域 右半区域
|-------| |-------|
左下 左上 右下 右上
|---| |---| |---| |---|
点群1 点群2 点群3 点群4 点群5 点群6 点群7 点群8
每个叶节点存储一小群点
查询时：只访问与查询矩形 R 有交集的节点
范围树（Range Tree）
范围树是一种多层结构，专门用于多维范围查询：
范围树（二维情况）：
第一层：按 x 坐标排序的平衡二叉搜索树
每个节点关联一棵按 y 坐标排序的子树
按x排序
|----------------|
x<5 x>=5
|-------| |-------|
x<2 x<4 x<7 x<9
对于每个x范围节点，内部有一棵按y排序的树
→ 先用x坐标缩小范围，再用y坐标进一步过滤
三、"近未来快、远未来慢"的查询
3.1 问题描述
论文特别提到一个有趣的特殊情况：
我们希望关于近未来的查询比远未来的查询更快。
这在实时应用中非常自然：
应用场景示例：自动驾驶
━━━━━━━━━━━━━━━━━━━━━
当前时刻 1秒后 10秒后 1分钟后
↓ ↓ ↓ ↓
─────────────────────────────────────────────────→ 时间
需要响应: 极快(毫秒级) 较快 可以慢一些
精度要求: 极高 高 可以粗略
重要程度: ★★★★★ ★★★ ★★
原因：1秒后会发生碰撞 → 必须立刻知道！
1分钟后的情况 → 可以慢慢算
3.2 实现思路
近未来优先的索引结构:
━━━━━━━━━━━━━━━━━━━
时间维度的分层：
┌─────────────────────────────────────────┐
│ 近未来层（精细索引，查询很快） │
│ ├── 下1秒: 完整的空间索引 │
│ ├── 下2秒: 完整的空间索引 │
│ └── 下5秒: 完整的空间索引 │
├─────────────────────────────────────────┤
│ 中期层（中等索引，查询适中） │
│ ├── 下10秒: 粗略的空间索引 │
│ └── 下30秒: 粗略的空间索引 │
├─────────────────────────────────────────┤
│ 远期层（简单索引，查询较慢） │
│ └── 下1分钟+: 需要时现算 │
└─────────────────────────────────────────┘
核心权衡:
- 近未来：预先建好精细索引 → 查询快
- 远未来：不预建索引 → 节省维护成本，查询时再算
四、k-d 树和 R-树用于移动对象
4.1 k-d 树处理移动对象
k-d 树是一种按不同维度交替划分空间的二叉树：
k-d 树（二维空间）示例:
━━━━━━━━━━━━━━━━━━━━
空间划分过程:
步骤1: 按x坐标划分 步骤2: 按y坐标划分
┌──────────┐ ┌──────────┐
│ │ │ │ B │ │
│ A │ B │ ├─────│ D │
│ │ │ │ C │ │
└──────────┘ └──────────┘
x=5 y=4
对应的树结构:
x=5
|------------|
y=3 y=7
|-----| |-----|
P1 P2 P3 P4
移动对象的挑战:
当点 P1 移动越过 x=5 这条分界线时，
需要将 P1 从左子树删除，插入右子树
→ 频繁的结构变化！
4.2 R-树处理移动对象
R-树用最小外接矩形（MBR）来组织空间对象：
R-树示意:
━━━━━━━━
空间中的点和它们的 MBR 分组:
┌─────────────────────────────────────┐
│ │
│ ┌───────────┐ ┌────────────┐ │
│ │ R1 │ │ R2 │ │
│ │ ●a ●b │ │ ●e ●f │ │
│ │ ●c │ │ ●g │ │
│ │ ●d │ │ │ │
│ └───────────┘ └────────────┘ │
│ │
└─────────────────────────────────────┘
R_root
对应的树:
R_root
|------------|
R1 R2
|---|--| | |---|---|
a b c d e f g
移动对象的挑战:
当点 a 移出 R1 的边界时:
方案1: 扩大 R1 → 但 R1 可能变得太大，降低查询效率
方案2: 把 a 移到 R2 → 但可能引起连锁调整
方案3: 定期重建整棵树 → 简单但代价大
五、完整代码示例
以下是一个完整的 C++ 程序，演示移动对象查询的核心概念：用 k-d 树对移动点做矩形范围查询。
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <sstream>
// ============================================================
// 移动对象查询演示
// 核心功能：
// 1. 用 k-d 树组织二维空间中的点
// 2. 支持矩形范围查询（给定矩形 R，找出其中的所有点）
// 3. 模拟点的运动：每个点有速度，位置随时间线性变化
// 4. 支持"在指定时刻 t 查询矩形 R 内的点"
// ============================================================
// ---------- 基本数据结构 ----------
// 二维点，带有速度信息（线性运动模型）
// 位置公式: pos(t) = pos(0) + vel * t
// 即 x(t) = x0 + vx * t, y(t) = y0 + vy * t
struct MovingPoint {
int id; // 点的唯一标识
double x0, y0; // 初始位置（t=0 时）
double vx, vy; // 速度（单位时间的位移）
// 计算在时刻 t 的位置
// 公式: $x(t) = x_0 + v_x \cdot t$
// $y(t) = y_0 + v_y \cdot t$
double x_at(double t) const { return x0 + vx * t; }
double y_at(double t) const { return y0 + vy * t; }
};
// 轴对齐矩形（查询区域）
// 表示区域: $[x_{lo}, x_{hi}] \times [y_{lo}, y_{hi}]$
struct Rectangle {
double x_lo, y_lo; // 左下角
double x_hi, y_hi; // 右上角
// 判断点 (px, py) 是否在矩形内
bool contains(double px, double py) const {
return px >= x_lo && px <= x_hi &&
py >= y_lo && py <= y_hi;
}
};
// ---------- k-d 树节点 ----------
// k-d 树：二维空间的划分结构
// 偶数层按 x 坐标划分，奇数层按 y 坐标划分
// 每个叶节点存储一个点的索引
struct KdNode {
int point_idx; // 如果是叶节点，存储点的索引；否则为 -1
int split_dim; // 划分维度: 0 = x, 1 = y
double split_val; // 划分值
KdNode* left; // 左子树（坐标 < split_val 的点）
KdNode* right; // 右子树（坐标 >= split_val 的点）
KdNode()
: point_idx(-1), split_dim(0), split_val(0.0),
left(nullptr), right(nullptr) {}
bool is_leaf() const { return left == nullptr && right == nullptr; }
};
// ---------- k-d 树实现 ----------
class KdTree {
public:
KdTree() : root_(nullptr) {}
~KdTree() {
destroy(root_);
}
// 构建 k-d 树
// points: 所有点在某一时刻的坐标快照
// 时间复杂度: $O(n \log n)$
void build(const std::vector<std::pair<double, double>>& points) {
destroy(root_);
indices_.resize(points.size());
for (int i = 0; i < static_cast<int>(points.size()); i++) {
indices_[i] = i;
}
points_snapshot_ = points;
root_ = build_recursive(indices_.data(),
static_cast<int>(indices_.size()), 0);
}
// 矩形范围查询：找出矩形 R 内的所有点
// 返回点的索引列表
// 平均时间复杂度: $O(\sqrt{n} + k)$，其中 $k$ 是结果数量
std::vector<int> range_query(const Rectangle& rect) const {
std::vector<int> result;
query_recursive(root_, rect, result);
return result;
}
private:
KdNode* root_;
std::vector<int> indices_;
std::vector<std::pair<double, double>> points_snapshot_;
// 递归构建 k-d 树
// depth 决定按哪个维度划分：depth % 2 == 0 → x，depth % 2 == 1 → y
KdNode* build_recursive(int* idx_arr, int count, int depth) {
if (count <= 0) return nullptr;
KdNode* node = new KdNode();
node->split_dim = depth % 2; // 交替使用 x 和 y 维度
if (count == 1) {
// 叶节点：直接存储点
node->point_idx = idx_arr[0];
return node;
}
// 按当前维度排序，取中位数作为划分值
int dim = node->split_dim;
std::sort(idx_arr, idx_arr + count,
[&](int a, int b) {
if (dim == 0)
return points_snapshot_[a].first
< points_snapshot_[b].first;
else
return points_snapshot_[a].second
< points_snapshot_[b].second;
});
int mid = count / 2;
node->point_idx = idx_arr[mid];
if (dim == 0)
node->split_val = points_snapshot_[idx_arr[mid]].first;
else
node->split_val = points_snapshot_[idx_arr[mid]].second;
// 递归构建左右子树
node->left = build_recursive(idx_arr, mid, depth + 1);
node->right = build_recursive(idx_arr + mid + 1,
count - mid - 1, depth + 1);
return node;
}
// 递归范围查询
// 关键优化：如果查询矩形与当前子树的划分不相交，直接跳过
void query_recursive(KdNode* node, const Rectangle& rect,
std::vector<int>& result) const {
if (node == nullptr) return;
// 检查当前节点的点是否在查询矩形内
if (node->point_idx >= 0) {
double px = points_snapshot_[node->point_idx].first;
double py = points_snapshot_[node->point_idx].second;
if (rect.contains(px, py)) {
result.push_back(node->point_idx);
}
}
if (node->is_leaf()) return;
// 利用划分维度进行剪枝
// 如果查询矩形完全在划分值的一侧，只需要搜索那一侧
double lo = (node->split_dim == 0) ? rect.x_lo : rect.y_lo;
double hi = (node->split_dim == 0) ? rect.x_hi : rect.y_hi;
if (lo < node->split_val) {
// 查询矩形的低端在划分值左侧 → 搜索左子树
query_recursive(node->left, rect, result);
}
if (hi >= node->split_val) {
// 查询矩形的高端在划分值右侧 → 搜索右子树
query_recursive(node->right, rect, result);
}
}
// 释放树节点
void destroy(KdNode* node) {
if (node == nullptr) return;
destroy(node->left);
destroy(node->right);
delete node;
}
};
// ---------- 移动对象查询系统 ----------
// 核心类：管理移动点，支持"在时刻 t 对矩形 R 的范围查询"
class MovingObjectQuerySystem {
public:
// 添加一个移动点
void add_point(int id, double x0, double y0, double vx, double vy) {
MovingPoint p;
p.id = id;
p.x0 = x0;
p.y0 = y0;
p.vx = vx;
p.vy = vy;
points_.push_back(p);
}
// 查询：在时刻 t，矩形 R 内有哪些点？
//
// 工作流程：
// 1. 计算所有点在时刻 t 的位置快照
// $x_i(t) = x_{i,0} + v_{x,i} \cdot t$
// $y_i(t) = y_{i,0} + v_{y,i} \cdot t$
// 2. 用快照构建 k-d 树（静态方法）
// 3. 在 k-d 树上做矩形范围查询
//
// 这就是"静态快照"方法——每次查询时重建索引
std::vector<int> query_at_time(const Rectangle& rect, double t) {
// 步骤1: 生成时刻 t 的位置快照
std::vector<std::pair<double, double>> snapshot(points_.size());
for (int i = 0; i < static_cast<int>(points_.size()); i++) {
snapshot[i] = {points_[i].x_at(t), points_[i].y_at(t)};
}
// 步骤2: 建立 k-d 树
KdTree tree;
tree.build(snapshot);
// 步骤3: 范围查询
std::vector<int> idx_results = tree.range_query(rect);
// 将索引转换为点的 ID
std::vector<int> id_results;
for (int idx : idx_results) {
id_results.push_back(points_[idx].id);
}
return id_results;
}
// 暴力查询（用于对比验证）
// 直接遍历所有点，检查是否在矩形内
// 时间复杂度: $O(n)$
std::vector<int> brute_force_query(const Rectangle& rect, double t) {
std::vector<int> result;
for (const auto& p : points_) {
double px = p.x_at(t);
double py = p.y_at(t);
if (rect.contains(px, py)) {
result.push_back(p.id);
}
}
return result;
}
// 打印所有点在时刻 t 的位置
void print_positions(double t) const {
std::cout << "时刻 t=" << t << " 各点位置:" << std::endl;
for (const auto& p : points_) {
std::cout << " 点" << p.id << ": ("
<< p.x_at(t) << ", " << p.y_at(t) << ")"
<< " 速度=(" << p.vx << ", " << p.vy << ")"
<< std::endl;
}
}
// ASCII 可视化：显示点在时刻 t 的位置和查询矩形
void visualize(const Rectangle& rect, double t,
const std::vector<int>& results) const {
// 画布大小
const int W = 40;
const int H = 20;
// 坐标范围
const double xmin = -2.0, xmax = 22.0;
const double ymin = -2.0, ymax = 22.0;
// 初始化画布
std::vector<std::string> canvas(H, std::string(W, ' '));
// 坐标转换函数
auto to_col = [&](double x) -> int {
return static_cast<int>((x - xmin) / (xmax - xmin) * (W - 1));
};
auto to_row = [&](double y) -> int {
// y 轴向上，行号向下，所以取反
return H - 1 - static_cast<int>(
(y - ymin) / (ymax - ymin) * (H - 1));
};
// 绘制查询矩形边框
int r_c1 = to_col(rect.x_lo), r_c2 = to_col(rect.x_hi);
int r_r1 = to_row(rect.y_hi), r_r2 = to_row(rect.y_lo);
for (int c = r_c1; c <= r_c2 && c < W; c++) {
if (r_r1 >= 0 && r_r1 < H) canvas[r_r1][c] = '-';
if (r_r2 >= 0 && r_r2 < H) canvas[r_r2][c] = '-';
}
for (int r = r_r1; r <= r_r2 && r < H; r++) {
if (r_c1 >= 0 && r_c1 < W) canvas[r][r_c1] = '|';
if (r_c2 >= 0 && r_c2 < W) canvas[r][r_c2] = '|';
}
// 角点
auto set_corner = [&](int r, int c) {
if (r >= 0 && r < H && c >= 0 && c < W) canvas[r][c] = '+';
};
set_corner(r_r1, r_c1);
set_corner(r_r1, r_c2);
set_corner(r_r2, r_c1);
set_corner(r_r2, r_c2);
// 绘制点
// 在查询结果中的点用 '*' 标记，不在结果中的用 '.' 标记
for (const auto& p : points_) {
double px = p.x_at(t);
double py = p.y_at(t);
int col = to_col(px);
int row = to_row(py);
if (row >= 0 && row < H && col >= 0 && col < W) {
bool in_result = false;
for (int rid : results) {
if (rid == p.id) { in_result = true; break; }
}
// 结果内的点用 '*'，结果外的用 'o'
canvas[row][col] = in_result ? '*' : 'o';
}
}
// 输出画布
std::cout << "\n ASCII 可视化 (t=" << t
<< ", '*'=在矩形内, 'o'=在矩形外):" << std::endl;
std::cout << " +" << std::string(W, '-') << "+" << std::endl;
for (int r = 0; r < H; r++) {
std::cout << " |" << canvas[r] << "|" << std::endl;
}
std::cout << " +" << std::string(W, '-') << "+" << std::endl;
}
private:
std::vector<MovingPoint> points_;
};
// ---------- 主程序 ----------
int main() {
std::cout << "==================================================="
<< std::endl;
std::cout << " 移动对象查询 (Querying Moving Objects) 演示"
<< std::endl;
std::cout << "==================================================="
<< std::endl;
MovingObjectQuerySystem system;
// 添加 8 个移动点
// add_point(id, x初始, y初始, x速度, y速度)
system.add_point(0, 2.0, 3.0, 1.0, 0.5); // 向右上移动
system.add_point(1, 8.0, 2.0, -0.5, 1.0); // 向左上移动
system.add_point(2, 15.0, 10.0, -1.0, 0.0); // 向左水平移动
system.add_point(3, 5.0, 15.0, 0.5, -1.0); // 向右下移动
system.add_point(4, 10.0, 8.0, 0.0, 0.5); // 向上移动
system.add_point(5, 18.0, 18.0, -0.5, -0.5); // 向左下移动
system.add_point(6, 1.0, 12.0, 1.5, 0.0); // 向右水平移动
system.add_point(7, 12.0, 5.0, 0.3, 0.8); // 向右上移动
// 定义查询矩形 R: [5, 15] x [5, 15]
Rectangle query_rect;
query_rect.x_lo = 5.0;
query_rect.y_lo = 5.0;
query_rect.x_hi = 15.0;
query_rect.y_hi = 15.0;
std::cout << "\n查询矩形 R: x=[" << query_rect.x_lo << ", "
<< query_rect.x_hi << "], y=["
<< query_rect.y_lo << ", " << query_rect.y_hi << "]"
<< std::endl;
// 在三个不同时刻查询
double query_times[] = {0.0, 5.0, 10.0};
for (double t : query_times) {
std::cout << "\n==========================================="
<< std::endl;
std::cout << "查询时刻 t = " << t << std::endl;
std::cout << "==========================================="
<< std::endl;
// 显示各点位置
system.print_positions(t);
// k-d 树查询
std::vector<int> kd_result =
system.query_at_time(query_rect, t);
// 暴力查询（验证）
std::vector<int> bf_result =
system.brute_force_query(query_rect, t);
// 排序以便对比
std::sort(kd_result.begin(), kd_result.end());
std::sort(bf_result.begin(), bf_result.end());
// 输出查询结果
std::cout << "\nk-d树查询结果: { ";
for (int id : kd_result) std::cout << "点" << id << " ";
std::cout << "}" << std::endl;
std::cout << "暴力验证结果: { ";
for (int id : bf_result) std::cout << "点" << id << " ";
std::cout << "}" << std::endl;
// 验证两种方法结果一致
bool match = (kd_result == bf_result);
std::cout << "结果一致: " << (match ? "是" : "否") << std::endl;
// ASCII 可视化
system.visualize(query_rect, t, kd_result);
}
// ---------- 演示"近未来优先"的概念 ----------
std::cout << "\n\n==========================================="
<< std::endl;
std::cout << " '近未来快、远未来慢' 概念演示" << std::endl;
std::cout << "==========================================="
<< std::endl;
std::cout << "\n查询响应时间与未来距离的关系：" << std::endl;
std::cout << std::endl;
std::cout << " 响应时间" << std::endl;
std::cout << " |" << std::endl;
std::cout << " | ...." << std::endl;
std::cout << " | ...." << std::endl;
std::cout << " | ...." << std::endl;
std::cout << " | ....." << std::endl;
std::cout << " | ...." << std::endl;
std::cout << " | .." << std::endl;
std::cout << " | ." << std::endl;
std::cout << " +──────────────────────────────→ 查询的未来距离"
<< std::endl;
std::cout << " 近未来 远未来" << std::endl;
std::cout << " (快速响应) (慢速响应)" << std::endl;
std::cout << std::endl;
std::cout << " 实现方式:" << std::endl;
std::cout << " - 近未来: 预建精细索引(k-d树/R-树)"
<< "，查询 O(sqrt(n)+k)" << std::endl;
std::cout << " - 远未来: 按需重建或暴力扫描"
<< "，查询 O(n)" << std::endl;
return 0;
}
六、复杂度总结
| 操作 | 方法 | 时间复杂度 |
|---|---|---|
| 构建 k-d 树 | 静态快照 | O ( n log n ) O(n \log n) O(nlogn) |
| 矩形范围查询（k-d 树） | 剪枝搜索 | O ( n + k ) O(\sqrt{n} + k) O(n+k) |
| 构建范围树 | 多层排序 | O ( n log d − 1 n ) O(n \log^{d-1} n) O(nlogd−1n) |
| 矩形范围查询（范围树） | 层级搜索 | O ( log d n + k ) O(\log^d n + k) O(logdn+k) |
| 暴力查询 | 遍历所有点 | O ( n ) O(n) O(n) |
其中 n n n 是点的数量， k k k 是查询结果的数量， d d d 是空间维度。
七、核心要点总结
移动对象查询的三个关键思想：
━━━━━━━━━━━━━━━━━━━━━━━━━━━
1. 动静结合
不必一直维护索引（纯 kinetic），
也不必每次从头算（纯 static），
根据查询频率选择最优策略。
2. 经典工具的复用
k-d 树、R-树、分区树、范围树
这些经典数据结构稍加改造就能处理移动对象。
3. 近未来优先
在实时应用中，近未来的查询需要更快。
可以为不同的时间范围维护不同精度的索引。
开源鸿蒙跨平台开发社区汇聚开发者与厂商，共建“一次开发，多端部署”的开源生态，致力于降低跨端开发门槛，推动万物智联创新。
更多推荐
10
0- 0
已为社区贡献17条内容
所有评论(0)