基于Voronoi理論判別剛體運(yùn)動軌跡的方法

張鐵強(qiáng)

遼寧對外經(jīng)貿(mào)學(xué)院，遼寧大連 116052

基于Voronoi理論判別剛體運(yùn)動軌跡的方法

張鐵強(qiáng)

遼寧對外經(jīng)貿(mào)學(xué)院，遼寧大連 116052

基于平面點集的 Voronoi 圖提出一種定性判別剛體運(yùn)動軌跡的方法。通過物體點與背景點組成的Voronoi 圖的點集與邊集的變化來定性判別物體運(yùn)動的軌跡。實驗結(jié)果表明，該算法能準(zhǔn)確地描述物體運(yùn)動軌跡，結(jié)果精確。

空間推理；Voronoi圖；Voronoi邊；運(yùn)動軌跡

空間推理（spatial reasoning）是人工智能學(xué)科處理常識性空間知識的一種方法[1]。剛體隨時間運(yùn)動的問題屬于空間推理[2]的范疇，已經(jīng)應(yīng)用在很多領(lǐng)域，例如：運(yùn)動規(guī)劃、幾何建模、物理系統(tǒng)以及虛擬現(xiàn)實系統(tǒng)的計算機(jī)模擬、機(jī)器人、模式識別[3]等方面。在這些應(yīng)用中，選擇一個有效的數(shù)據(jù)結(jié)構(gòu)是解決這些大型系統(tǒng)的關(guān)鍵。Voronoi 圖則常用于這種數(shù)據(jù)結(jié)構(gòu)，它是計算幾何學(xué)科中的一個重要結(jié)構(gòu)，能準(zhǔn)確描述空間方向關(guān)系[4-5]，已廣泛應(yīng)用于上述各領(lǐng)域[6]。

本文正是利用Voronoi圖來描述背景點與剛體點的拓?fù)浣Y(jié)構(gòu)，并根據(jù)這一拓?fù)浣Y(jié)構(gòu)的變化來定性描述物體運(yùn)動軌跡的。在余下的篇幅中，將詳細(xì)地闡述該方法的特點：剛體點與背景點構(gòu)成voronoi圖，剛體點在平面上運(yùn)動，將會使voronoi圖發(fā)生改變，當(dāng)剛體點與某背景點消失voronoi邊時，剛體點遠(yuǎn)離該背景點，反之，當(dāng)剛體點與某背景點生成voronoi邊時，剛體點靠近該背景點。當(dāng)voronoi圖的狀態(tài)未發(fā)生改變時，剛體點的運(yùn)動狀態(tài)也視為未發(fā)生變化。

1 Voronoi圖理論基礎(chǔ)

1.1 Voronoi圖的定義

設(shè)P={p1,p2,…,pn}?R2，R2是二維歐氏空間上的點集，d(·，·)為歐氏距離。稱為 Voronoi區(qū)域。其中，由點集P生成的Voronoi圖可定義為：

Voronoi圖區(qū)域的邊被稱為Voronoi圖的邊，Voronoi圖區(qū)域的頂點被稱為Voronoi圖的頂點。

1.2 Voronoi圖的生成算法

Voronoi圖的平面點集構(gòu)造算法有3類：平面掃描法、分治法和增量算法。其中的增量算法不但可以適用于靜態(tài)點集，而且可以適用于動態(tài)點集，本文中選取增量算法構(gòu)造平面點集(包括背景點與剛體點)的Voronoi圖。

1.2.1 翼邊數(shù)據(jù)結(jié)構(gòu)

首先介紹Voronoi圖的存儲結(jié)構(gòu)——翼邊數(shù)據(jù)結(jié)構(gòu)。

1）將Voronoi圖擴(kuò)充為幾何圖(平面圖)。用足夠大的閉合曲線圍繞Voronoi圖的頂點，無限邊相交在此曲線，將此曲線分割成若干個曲線段，稱為Voronoi邊，此圖稱為擴(kuò)充幾何圖。令G=(V，E)，其中，，。

2）首先對每一條邊任選并且固定方向，然后，命名頂點序號1，2，…，nv與邊的序號1，2，…，ne，并稱為生成子pi的Voronoi多邊形為i(i=1，2，…，n，∞)。

利用已有的多邊形數(shù)組描述Voronoi圖的翼邊數(shù)據(jù)結(jié)構(gòu)。

1.2.2 增量算法

在增量算法的設(shè)計階段，首先做出3個點的Voronoi圖，其余各點都位于單位正方形中，附加3點的坐標(biāo)為：

輸入：點集P，l，Vl-1

輸出：翼邊數(shù)據(jù)結(jié)構(gòu)（Vl）

過程：

1）找出pl的Voronoi區(qū)域；

2）假設(shè)pl與Voronoi區(qū)域所在生成子pi的垂直平分線與V(pi)的邊界交于ω1和ω2兩個點，而且pl在有向線段ω1ω2區(qū)域的左側(cè)，可生成V(pl)的一條邊，從這條邊進(jìn)入相鄰的Voronoi多邊形。用同樣方法，找到pl與鄰接的Voronoi區(qū)域多邊形的生成子的垂直平分線的所有線段序列，直到起點ω1；

3）刪除圖Vl-1中在圖V(pl)中的數(shù)據(jù)構(gòu)造，同時修改對應(yīng)的翼邊數(shù)據(jù)結(jié)構(gòu)。

1.3 Delauny三角剖分與凸包、最大空圓

Delauny三角剖分是Voronoi圖相對于點集的對偶圖，其中任意三角形的外接圓都不包含點集中的所有點。所以，在構(gòu)造點集對應(yīng)的Voronoi圖后，作它的對偶圖，即對每條Voronoi邊分別做通過點集中任意兩點的垂線，便得到Delauny三角剖分。

平面點集S的凸包是包含S中所有點的最小凸集，亦即所有Delauny三角形的并集。

平面點集S的最大空圓，給定平面上n個點的點集S，尋找一個不包含S中點的最大圓，即為S的最大空圓。

2 定性判定剛體運(yùn)動軌跡

判定過程：

[1.輸入背景點] 在平面上隨意確定一個點集，作為背景點集。

[2.輸入剛體點] 在平面上確定一個點集作為剛體點。由于是剛體，可用平均值法將剛體點集歸結(jié)為一點進(jìn)行處理。

[3.生成voronoi圖] 利用增量算法生成背景點集與剛體點構(gòu)成的平面點集的voronoi 圖。

[4.記錄剛體點初始狀態(tài)] 記錄剛體點與背景點集的voronoi邊狀態(tài)。

[5.移動剛體點] 在平面上移動剛體點。

[6.記錄voronoi邊的變化]

剛體點與背景點生成的voronoi圖中，voronoi邊的變化情況可定性反映出剛體點與背景點之間的位置關(guān)系和方向關(guān)系：

1）設(shè)剛體點4與背景點1、2、3的初始空間關(guān)系如圖1所示。

圖1 4個點的原始狀態(tài)

2）點與某背景點之間有voronoi邊生成，則可定性表示為剛體點靠近該背景點。（如圖2）

圖2 剛體點4與背景點2生成voronoi邊

圖3 剛體點4與背景點1消失voronoi邊

3 實驗與結(jié)論

3.1 實驗結(jié)果

1）輸入背景點1-8，輸入物體點9。（圖4）

2）沿圖示軌跡拖動物體點。對物體點運(yùn)動做定性分析。（圖5）

當(dāng)剛體點9沿著圖5中的軌跡運(yùn)動時，它與背景點集的voronoi邊的變化序列如下。

點9與背景點5之間生成邊，點9與背景點2之間消失邊，點9與背景點8之間生成邊，點9與背景點3之間消失邊，點9與背景點4之間生成邊，點9與背景點6之間消失邊，點9與背景點1之間生成邊，點9與背景點7之間消失邊，點9與背景點8之間消失邊。

因此，點9的運(yùn)動軌跡可以用自然語言序列定性表示：

點9靠近背景點5，點9遠(yuǎn)離背景點2，點9靠近背景點8，點9遠(yuǎn)離背景點3，點9靠近背景點4，點9遠(yuǎn)離背景點6，點9靠近背景點1，點9遠(yuǎn)離背景點7，點9遠(yuǎn)離背景點8。

圖4

3.2 結(jié)論

實驗證明，本文提出的方法可以基本準(zhǔn)確的定性描述剛體點的運(yùn)動軌跡。

圖5

[1]廖士中，石純一.定性空間推理的研究與發(fā)展[J].計算機(jī)科學(xué)，1998，25（4）：11-13.

[2]石純一，廖士中.定性推理方法[M].北京：清華大學(xué)出版社，2002.

[3]邊肇祺，等.模式識別[M].北京：清華大學(xué)出版社，2000.

[4]閆浩文，郭仁忠.用Voronoi圖描述空間方向關(guān)系的理論依據(jù)[J].武漢大學(xué)學(xué)報（自然科學(xué)版），2002.

[5]閆浩文，郭仁忠.基于Voronoi圖的空間方向關(guān)系形式化描述模型[J].武漢大學(xué)學(xué)報（自然科學(xué)版），2003.

[6]周培德.計算幾何—算法分析與設(shè)計[M].北京：清華大學(xué)出版社，1999.

[7]王嘵東，廖士中.一個基于桶技術(shù)的平面點集Voronoi圖增量算法[J].遼寧師范大學(xué)學(xué)報（自然科學(xué)版），2002.

圖3 管理員子系統(tǒng)

3 結(jié)論

總之，該統(tǒng)計學(xué)立體化教學(xué)平臺的設(shè)計充分考慮了教學(xué)過程中的學(xué)生需求和教師需求。本文主要研究了統(tǒng)計學(xué)立體化教學(xué)平臺的設(shè)計，為統(tǒng)計學(xué)傳統(tǒng)教學(xué)和互聯(lián)網(wǎng)融合指引了方向，該平臺的設(shè)計主要為提高統(tǒng)計學(xué)的教學(xué)質(zhì)量提供良好的輔助功能。有了該平臺能使統(tǒng)計學(xué)教學(xué)質(zhì)量更上一層樓[5]。

參考文獻(xiàn)

[1]劉貴富.信息環(huán)境下高校立體化教學(xué)資源建設(shè)研究[J].黑龍江高教研究，2009，8：138-140.

[2]劉立群.立體化教學(xué)資源建設(shè)及其模型研究[J].沈陽師范大學(xué)學(xué)報(自然科學(xué)版).2010，4：571-573.

[3]余朝文.基于網(wǎng)絡(luò)學(xué)習(xí)型社會的立體化教學(xué)資源建設(shè)研究[J].中國電化教育，2011，6：70-91.

[4]劉媚.概率論與數(shù)理統(tǒng)計課程立體化教學(xué)改革初探[J].寧夏師范學(xué)院學(xué)報，2013，6：85-87.

[5]翟成景.網(wǎng)絡(luò)立體化教學(xué)資源交互平臺的設(shè)計與實現(xiàn)[D].山東：山東大學(xué)，2013：2-5.

TP3

A

1674-6708（2015）149-0148-03

張鐵強(qiáng)，副教授，研究方向：計算機(jī)應(yīng)用、教學(xué)管理