计算机工程与科学
計算機工程與科學
계산궤공정여과학
COMPUTER ENGINEERING & SCIENCE
2007年
12期
85-86
,共2页
多边形%交集面积%并集面积%算法
多邊形%交集麵積%併集麵積%算法
다변형%교집면적%병집면적%산법
平面多边形交集与并集面积的计算机算法可以利用多边形裁剪算法来实现.本文提出的算法思想是利用Weiler-Atherton多边形裁剪算法中的多边形链表,在遍历链表时遇到交点就改变跟踪方向,这样可以求出并集顶点表,求交集时只要从入点开始跟踪遇到交点再改变跟踪方向;最后,通过交集和并集表求出它们的面积.多边形可以是凸的或凹的、甚至是带孔的.
平麵多邊形交集與併集麵積的計算機算法可以利用多邊形裁剪算法來實現.本文提齣的算法思想是利用Weiler-Atherton多邊形裁剪算法中的多邊形鏈錶,在遍歷鏈錶時遇到交點就改變跟蹤方嚮,這樣可以求齣併集頂點錶,求交集時隻要從入點開始跟蹤遇到交點再改變跟蹤方嚮;最後,通過交集和併集錶求齣它們的麵積.多邊形可以是凸的或凹的、甚至是帶孔的.
평면다변형교집여병집면적적계산궤산법가이이용다변형재전산법래실현.본문제출적산법사상시이용Weiler-Atherton다변형재전산법중적다변형련표,재편력련표시우도교점취개변근종방향,저양가이구출병집정점표,구교집시지요종입점개시근종우도교점재개변근종방향;최후,통과교집화병집표구출타문적면적.다변형가이시철적혹요적、심지시대공적.
