運動學資料結構

基本概念

運動學資料結構定義為一種用於跟蹤連續移動的幾何系統的屬性的資料結構。例如，運動學凸包資料結構跟蹤 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 次瀏覽

啟動你的 職業生涯

透過完成課程獲得認證

開始