计算机工程与应用
計算機工程與應用
계산궤공정여응용
COMPUTER ENGINEERING AND APPLICATIONS
2002年
20期
48-49,406
,共3页
凸包%格网%平面点集%计算几何
凸包%格網%平麵點集%計算幾何
철포%격망%평면점집%계산궤하
文章提出了一种提高构建凸包速度的新方法.该算法生成一个网格来管理离散点,在淘汰明显不位于凸包上的点时,将对离散点的取舍转换为对格的取舍,计算工作量只与离散点的范围及网格的密度有关,与离散点的数目无关;同时对点集也进行了初略的排序.在求取剩余点集的凸包时,采用了一种先分段求取凸包边界,最后将这些边界合并成凸包的方法,该方法充分利用了剩余点集所具有的有序性.
文章提齣瞭一種提高構建凸包速度的新方法.該算法生成一箇網格來管理離散點,在淘汰明顯不位于凸包上的點時,將對離散點的取捨轉換為對格的取捨,計算工作量隻與離散點的範圍及網格的密度有關,與離散點的數目無關;同時對點集也進行瞭初略的排序.在求取剩餘點集的凸包時,採用瞭一種先分段求取凸包邊界,最後將這些邊界閤併成凸包的方法,該方法充分利用瞭剩餘點集所具有的有序性.
문장제출료일충제고구건철포속도적신방법.해산법생성일개망격래관리리산점,재도태명현불위우철포상적점시,장대리산점적취사전환위대격적취사,계산공작량지여리산점적범위급망격적밀도유관,여리산점적수목무관;동시대점집야진행료초략적배서.재구취잉여점집적철포시,채용료일충선분단구취철포변계,최후장저사변계합병성철포적방법,해방법충분이용료잉여점집소구유적유서성.