 |
 |
 |
 |
 |
 |
 |
 |
|
 |
|
 |
|
| 第四节 包含与重叠 | ||||
 两个凸多边形求交的完整算法:CONVEX POLYGON INTERSECTION 1.〔准备〕i←1,j←1,k←1,  ;2.〔交替前进求交〕若k≤2*(l+m)并且所求出当前交点不是第一次求得交点  ,则做2.1—2.3循环: 2.1 若线段   与  相交,则调用Output; 2.2 调用Advance; 2.3 k←k+1; 3.〔结束判断〕若在步2找到过交点,则交得凸多边形顶点序列已在调用Output过程中输出,算法结束; 否则,做如下检查: 若  包含于多边形Q中,则输出P包含于Q中,算法结束;若  包含于多边形P中,则输出Q包含于P中,算法结束;若上述两个检查都不成功,输出交为空,两多边形分离,算法结束; |
||||
 |
||||
| 交点个数最多为2(l+m)个 | ||||
 第一节
线段的交点计算第二节
多边形表面的交线计算第三节
平面中的凸壳算法第四节
包含与重叠第五节
简单多边形的三角剖分 |
