兵工学报
兵工學報
병공학보
ACTA ARMAMENTARII
2008年
3期
379-384
,共6页
几何学%多边形%孔%凸划分%单调链%单调多边形
幾何學%多邊形%孔%凸劃分%單調鏈%單調多邊形
궤하학%다변형%공%철화분%단조련%단조다변형
该算法利用单调链对有内孔的多边形进行凸划分,包括3个步骤:首先将有孔多边形分解为有序单调链;其次通过组合和分裂单调链,逐次拆分出单调多边形;最后将单调多边形划分为凸多边形.每个步骤都给出了证明和复杂性分析.实验和分析说明算法平均复杂性接近O(nlg(n)).
該算法利用單調鏈對有內孔的多邊形進行凸劃分,包括3箇步驟:首先將有孔多邊形分解為有序單調鏈;其次通過組閤和分裂單調鏈,逐次拆分齣單調多邊形;最後將單調多邊形劃分為凸多邊形.每箇步驟都給齣瞭證明和複雜性分析.實驗和分析說明算法平均複雜性接近O(nlg(n)).
해산법이용단조련대유내공적다변형진행철화분,포괄3개보취:수선장유공다변형분해위유서단조련;기차통과조합화분렬단조련,축차탁분출단조다변형;최후장단조다변형화분위철다변형.매개보취도급출료증명화복잡성분석.실험화분석설명산법평균복잡성접근O(nlg(n)).
