工程图学学报
工程圖學學報
공정도학학보
JOURNAL OF ENGINEERING GRAPHICS
2000年
2期
52-58
,共7页
凸多边形%支撑线%凸壳%可移动方向
凸多邊形%支撐線%凸殼%可移動方嚮
철다변형%지탱선%철각%가이동방향
设P与Q为平面上两个互不相交的凸多边形,则在P与Q之间必存在两条正支撑线和两条斜支撑线,确定它们就可以确定P与Q的凸壳和P与Q的全部可移动方向,这在机器人学、几何布局及VLSI设计等领域具有重要实用意义.本文给出统一确定这些支撑线的快速算法,其时间复杂度为O(logm· logn) ,其中m与n分别为P与Q的顶点数.
設P與Q為平麵上兩箇互不相交的凸多邊形,則在P與Q之間必存在兩條正支撐線和兩條斜支撐線,確定它們就可以確定P與Q的凸殼和P與Q的全部可移動方嚮,這在機器人學、幾何佈跼及VLSI設計等領域具有重要實用意義.本文給齣統一確定這些支撐線的快速算法,其時間複雜度為O(logm· logn) ,其中m與n分彆為P與Q的頂點數.
설P여Q위평면상량개호불상교적철다변형,칙재P여Q지간필존재량조정지탱선화량조사지탱선,학정타문취가이학정P여Q적철각화P여Q적전부가이동방향,저재궤기인학、궤하포국급VLSI설계등영역구유중요실용의의.본문급출통일학정저사지탱선적쾌속산법,기시간복잡도위O(logm· logn) ,기중m여n분별위P여Q적정점수.
