计算机辅助设计与图形学学报
計算機輔助設計與圖形學學報
계산궤보조설계여도형학학보
JOURNAL OF COMPUTER-AIDED DESIGN & COMPUTER GRAPHICS
2005年
4期
689-693
,共5页
计算几何%多边形%Voronoi图
計算幾何%多邊形%Voronoi圖
계산궤하%다변형%Voronoi도
在对多边形P的外部Voronoi图的性质进行研究的基础上,将其表示成树结构并利用树结构的性质给出了其所含Voronoi顶点和边数的上界:n+s+2×h-r-t-2和2×n+2×s+3×h-r-t-3,其中,h,n和s分别是P的边界、边和凸顶点的数目;t和r分别是位于P的凸包上的顶点和边数.同时,给出了每一个Voronoi区域所包含顶点和边数的平均值估计.文中工作在基于多边形外部Voronoi图的碰撞检测算法的复杂度分析方面有着重要作用.
在對多邊形P的外部Voronoi圖的性質進行研究的基礎上,將其錶示成樹結構併利用樹結構的性質給齣瞭其所含Voronoi頂點和邊數的上界:n+s+2×h-r-t-2和2×n+2×s+3×h-r-t-3,其中,h,n和s分彆是P的邊界、邊和凸頂點的數目;t和r分彆是位于P的凸包上的頂點和邊數.同時,給齣瞭每一箇Voronoi區域所包含頂點和邊數的平均值估計.文中工作在基于多邊形外部Voronoi圖的踫撞檢測算法的複雜度分析方麵有著重要作用.
재대다변형P적외부Voronoi도적성질진행연구적기출상,장기표시성수결구병이용수결구적성질급출료기소함Voronoi정점화변수적상계:n+s+2×h-r-t-2화2×n+2×s+3×h-r-t-3,기중,h,n화s분별시P적변계、변화철정점적수목;t화r분별시위우P적철포상적정점화변수.동시,급출료매일개Voronoi구역소포함정점화변수적평균치고계.문중공작재기우다변형외부Voronoi도적팽당검측산법적복잡도분석방면유착중요작용.
