计算机工程与科学
計算機工程與科學
계산궤공정여과학
COMPUTER ENGINEERING & SCIENCE
2011年
2期
129-132
,共4页
三维凸包%二次极值%增量算法
三維凸包%二次極值%增量算法
삼유철포%이차겁치%증량산법
本文阐述一种快速的三维凸包构造新算法,算法吸收了QuickHull方法中每次选用凸包的极值点(Extremal-Point)来构造新凸包的思想,在此基础上改进为选用二次极值点的方法来构造新凸包,并结合"冲突图"(Conflict-Graph)来更新凸包外的点和当前凸包的拓扑结构关系,从而取得了快速排除凸包的内部点、缩小问题规模、实现高效构建凸包的效果.本文算法的时间复杂度为O(nlgr),通过实验证明本文算法与QuickHull算法相比平均执行消耗时间减少20%,因此本算法具有理论和实际应用价值.
本文闡述一種快速的三維凸包構造新算法,算法吸收瞭QuickHull方法中每次選用凸包的極值點(Extremal-Point)來構造新凸包的思想,在此基礎上改進為選用二次極值點的方法來構造新凸包,併結閤"遲突圖"(Conflict-Graph)來更新凸包外的點和噹前凸包的拓撲結構關繫,從而取得瞭快速排除凸包的內部點、縮小問題規模、實現高效構建凸包的效果.本文算法的時間複雜度為O(nlgr),通過實驗證明本文算法與QuickHull算法相比平均執行消耗時間減少20%,因此本算法具有理論和實際應用價值.
본문천술일충쾌속적삼유철포구조신산법,산법흡수료QuickHull방법중매차선용철포적겁치점(Extremal-Point)래구조신철포적사상,재차기출상개진위선용이차겁치점적방법래구조신철포,병결합"충돌도"(Conflict-Graph)래경신철포외적점화당전철포적탁복결구관계,종이취득료쾌속배제철포적내부점、축소문제규모、실현고효구건철포적효과.본문산법적시간복잡도위O(nlgr),통과실험증명본문산법여QuickHull산법상비평균집행소모시간감소20%,인차본산법구유이론화실제응용개치.
