 |
 |
 |
 |
 |
 |
 |
 |
|
 |
|
 |
|
| 第一节 线段的交点计算 | ||||
 算法:
1.〔事件点进度表E初始化〕将输入待求交点的n条线段的2n个端点按x,y字典式排序后存放于表E中; 2.〔准备收集交点〕  ;{A是一集合,初为空,准备存入找到的交点;}3.〔平面扫描〕若表E不为空,则进行(1)~(3)循环。直到表E为空时算法结束。 3.1〔取出当前事件点〕P←MIN(E)； 3.2〔当前事件点处理〕考查当前事件点P,分三种情况: (1) 若P是边S的左端点,则做：INSERT(S,L); 
=ABOVE(S,L);
=BELOW(S,L);若S和 相交,则求出的交点送入集和A中;若S和 相交,则求出的交点送入集和A中;(2) 若P是边S的右端点,则做：
=ABOVE(S,L);
=BELOW(S,L);若 和相交于点P的右边,则求出的交点送入集和A中；DELETE(S,L)； (3) 若P是边 和的交点,且在P的左边=ABOVE(),则做S3=ABOVE( ,L);S4=BELOW( ,L);若  和相交，则求出的交点送入集合A中；若  和相交，则求出的交点送入集合A中；在L中交换 和的位置；3.3 〔处理找到的交点〕若集合A不为空，做下面循环，直至A为空： 取出集合A中一个交点，其横坐标是x； 若MEMBER(x,E)为FALSE,则输出此交点，并做 INSERT(x,E); |
||||
 第一节
线段的交点计算第二节
多边形表面的交线计算第三节
平面中的凸壳算法第四节
包含与重叠第五节
简单多边形的三角剖分 |
