运动学数据结构

基本概念

运动学数据结构定义为一种用于跟踪连续移动的几何系统的属性的数据结构。例如，运动学凸包数据结构跟踪 n 个移动点的凸包。

运动学数据结构的开发受到涉及连续运动的物理对象的计算几何问题的启发，例如机器人、动画或计算机图形学中的碰撞或可见性检测。

概述

运动学数据结构在系统上实现，其中有一组值作为时间的函数而变化，以一种称为的方式。因此，系统具有一些值，并且对于每个系统值 v，它表示 v=f(t)。运动学数据结构允许在当前虚拟时间 t 对系统进行查询，以及另外两个操作

• advance(t)：系统推进到时间 t。
• change(v,f(t))：从当前时间起，将值 v 的轨迹更改为 f(t)。

可以支持其他操作。例如，运动学数据结构通常使用一组点来实现。在这种情况下，该结构通常允许插入和删除点。

与传统数据结构的对比

运动学数据结构允许其中存储的值随时间连续变化。原则上，这可以通过以固定的时间间隔对点的位 置进行采样，并将每个点删除并重新插入到“静态”（传统）数据结构中来近似。但是，这种方法容易出现过采样或欠采样，具体取决于实现的时间间隔，并且也可能浪费计算资源。

证书方法

可以实现以下通用方法来构建运动学数据结构

• 存储当前时间 t 下系统的某个数据结构。此数据结构允许对当前虚拟时间下的系统进行查询。
• 使用证书增强数据结构。证书被视为数据结构准确的条件。这些证书现在都为真，并且只有当其中一个证书不再为真时，数据结构才会停止变得完美或准确。
• 计算每个证书的失效时间，即它将不再为真的时间。
• 将证书存储在优先级队列中，并以其失效时间为键。
• 要前进到时间 t，请查看优先级队列中失效时间最小的证书。如果证书在时间 t 之前失效，则将其从队列中删除或弹出，并修复数据结构使其在失效时完美或准确，然后更新证书。重复此操作，直到优先级队列中失效时间最小的证书在时间 t 之后失效为止。如果优先级队列中失效时间最小的证书在时间 t 之后失效，则声明所有证书在时间 t 时为真，因此数据结构可以正确地回答时间 t 时的查询。

事件类型

证书失效被称为“事件”。如果运动学数据结构维护的属性在事件发生时不发生变化，则将事件声明为内部事件。如果数据结构维护的属性在事件发生时发生变化，则将事件声明为外部事件。

性能

在实现证书方法时，有四种性能衡量标准。如果某个量是 n 的多对数函数，或者对于随机的小 € 为 O(n€) ，则称该量为小量，其中 n 被视为对象的个数。

Arnab Chakraborty

更新时间： 2020年1月8日

565 次浏览

启动你的 职业生涯

通过完成课程获得认证

开始