張鐵強

遼寧對外經貿學院，遼寧大連 116052

基于Voronoi理論判別剛體運動軌跡的方法

張鐵強

遼寧對外經貿學院，遼寧大連 116052

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

空間推理；Voronoi圖；Voronoi邊；運動軌跡

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

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

1 Voronoi圖理論基礎

1.1 Voronoi圖的定義

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

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

1.2 Voronoi圖的生成算法

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

1.2.1 翼邊數據結構

首先介紹Voronoi圖的存儲結構——翼邊數據結構。

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

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

利用已有的多邊形數組描述Voronoi圖的翼邊數據結構。

1.2.2 增量算法

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

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

輸出：翼邊數據結構（Vl）

過程：

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

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

3）刪除圖Vl-1中在圖V(pl)中的數據構造，同時修改對應的翼邊數據結構。

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

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

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

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

2 定性判定剛體運動軌跡

判定過程：

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

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

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

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

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

[6.記錄voronoi邊的變化]

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

1）設剛體點4與背景點1、2、3的初始空間關系如圖1所示。

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

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

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

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

3 實驗與結論

3.1 實驗結果

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

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

當剛體點9沿著圖5中的軌跡運動時，它與背景點集的voronoi邊的變化序列如下。

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

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

點9靠近背景點5，點9遠離背景點2，點9靠近背景點8，點9遠離背景點3，點9靠近背景點4，點9遠離背景點6，點9靠近背景點1，點9遠離背景點7，點9遠離背景點8。

圖4

3.2 結論

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

圖5

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

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

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

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

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

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

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

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

3 結論

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

參考文獻

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

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

[3]余朝文.基于網絡學習型社會的立體化教學資源建設研究[J].中國電化教育，2011，6：70-91.

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

[5]翟成景.網絡立體化教學資源交互平臺的設計與實現[D].山東：山東大學，2013：2-5.

TP3

A

1674-6708（2015）149-0148-03

張鐵強，副教授，研究方向：計算機應用、教學管理