计算机工程与设计
計算機工程與設計
계산궤공정여설계
COMPUTER ENGINEERING AND DESIGN
2014年
1期
192-197
,共6页
宋树华%濮国梁%罗旭%陈东%陈润强
宋樹華%濮國樑%囉旭%陳東%陳潤彊
송수화%복국량%라욱%진동%진윤강
多边形裁剪%交点%前驱%后继%矢量数组
多邊形裁剪%交點%前驅%後繼%矢量數組
다변형재전%교점%전구%후계%시량수조
polygon clipping%intersection points%predecessor%successor%vector
为了尽量降低任意多边形裁剪复杂度,提出了一种基于多边形顶点遍历的简单多边形裁剪算法.该算法将多边形交点插入到裁剪多边形和被裁减多边形顶点矢量数组中,通过记录交点及其前驱、后继信息,可快速生成结果多边形.其中,时间复杂度为O((m+k)×k),m是两多边形中顶点数较大者,k是两多边形的交点数.该算法简化了交点的数据结构,节省了存储空间,降低了算法的时间复杂度,具有简单、易于编程实现、运行效率高的特点.
為瞭儘量降低任意多邊形裁剪複雜度,提齣瞭一種基于多邊形頂點遍歷的簡單多邊形裁剪算法.該算法將多邊形交點插入到裁剪多邊形和被裁減多邊形頂點矢量數組中,通過記錄交點及其前驅、後繼信息,可快速生成結果多邊形.其中,時間複雜度為O((m+k)×k),m是兩多邊形中頂點數較大者,k是兩多邊形的交點數.該算法簡化瞭交點的數據結構,節省瞭存儲空間,降低瞭算法的時間複雜度,具有簡單、易于編程實現、運行效率高的特點.
위료진량강저임의다변형재전복잡도,제출료일충기우다변형정점편력적간단다변형재전산법.해산법장다변형교점삽입도재전다변형화피재감다변형정점시량수조중,통과기록교점급기전구、후계신식,가쾌속생성결과다변형.기중,시간복잡도위O((m+k)×k),m시량다변형중정점수교대자,k시량다변형적교점수.해산법간화료교점적수거결구,절성료존저공간,강저료산법적시간복잡도,구유간단、역우편정실현、운행효솔고적특점.
