 |
 |
 |
 |
 |
 |
 |
 |
|
 |
|
 |
|
| 第四节 包含与重叠 | ||||
 |
||||
| 区分前四种情形还是后四种情形 求矢量积  的z分量,若该分量大于等于0,是前四种情形,小于0是后四种情形。
 Advance
的z分量;分二种情况处理,然后算法就结束;1. 若S≥0,则做 若  在  左并且在 左,或者在右并且在左,则i前进1,否则j前进1;2. 若S<0,则做 若 在右并且Q在左,或者在右并且在右,则i前进1,否则j前进1;算法中"i前进1",指若i<l,则前进1是i+1;若i=L,则前进1是1。这因为多边形P是首尾相接的。类似地"j前进1",j<m时是j+1;j=m时是1。i总在多边形P上前进,j在Q上前进。 为了正确排列求出的交点并加入原两个凸多边形部分顶点以形成相交的凸多边形,可以在每求出一个交点时进行一次输出。 求出的第一个交点可只做一下记录,如果在以后交替前进求交点的过程中再次求出与第一次求得相同的交点,就知道整个求交过程已经结束了。 求得一个不是第一个的其它任何一个交点时,为形成交得凸多边形顶点序列,要区分边 是进入多边形Q,还是走出Q两种情况。
|
||||
 第一节
线段的交点计算第二节
多边形表面的交线计算第三节
平面中的凸壳算法第四节
包含与重叠第五节
简单多边形的三角剖分 |
