计算机工程与应用
計算機工程與應用
계산궤공정여응용
COMPUTER ENGINEERING AND APPLICATIONS
2011年
1期
205-207,233
,共4页
凸壳%简单多边形%极值点%多边形集
凸殼%簡單多邊形%極值點%多邊形集
철각%간단다변형%겁치점%다변형집
提出一种计算平面多边形集凸壳的快速算法.将多边形集的凸壳根据极值点划分为右上、左上、左下、右下四段,同时对集合中多边形利用其极值点提取右上、左上、左下、右下四个点列段,凸壳的每一段仅受多边形同一类点列段的影响.根据多边形集合的极值点确定四个矩形区域对四类点列段进行筛选,再按给定规则在矩形区域中进行初始找点,可求出四段凸壳初始点列,它们按顺序可确定一平面多边形,求出到此多边形的凸壳即为所求多边形集的凸壳.算法通过分段、分类、筛选等措施提高了计算效率,并且易于实现,其时间复杂度为O(N).
提齣一種計算平麵多邊形集凸殼的快速算法.將多邊形集的凸殼根據極值點劃分為右上、左上、左下、右下四段,同時對集閤中多邊形利用其極值點提取右上、左上、左下、右下四箇點列段,凸殼的每一段僅受多邊形同一類點列段的影響.根據多邊形集閤的極值點確定四箇矩形區域對四類點列段進行篩選,再按給定規則在矩形區域中進行初始找點,可求齣四段凸殼初始點列,它們按順序可確定一平麵多邊形,求齣到此多邊形的凸殼即為所求多邊形集的凸殼.算法通過分段、分類、篩選等措施提高瞭計算效率,併且易于實現,其時間複雜度為O(N).
제출일충계산평면다변형집철각적쾌속산법.장다변형집적철각근거겁치점화분위우상、좌상、좌하、우하사단,동시대집합중다변형이용기겁치점제취우상、좌상、좌하、우하사개점렬단,철각적매일단부수다변형동일류점렬단적영향.근거다변형집합적겁치점학정사개구형구역대사류점렬단진행사선,재안급정규칙재구형구역중진행초시조점,가구출사단철각초시점렬,타문안순서가학정일평면다변형,구출도차다변형적철각즉위소구다변형집적철각.산법통과분단、분류、사선등조시제고료계산효솔,병차역우실현,기시간복잡도위O(N).
