·凸多边形重叠计算 两个凸多边形的重叠问题，这也就是对 两个凸多边形求相文部分的问题。 现在约定凸多边形指它的边界和内部， 凸多边形仍用顶点坐标的逆时针方向序列 确定。 设给出的两个凸多边形卯和Q的顶点序列 分别是P1,P2,,P和Q1,Q2,,Qm。为说明 简便，假设P的边界上不包含Q的项点，Q的边 界也不包含P的顶点
• 凸多边形重叠计算 两个凸多边形的重叠问题,这也就是对 两个凸多边形求相交部分的问题。 现在约定凸多边形指它的边界和内部, 凸多边形仍用顶点坐标的逆时针方向序列 确定。 设给出的两个凸多边形P和Q的顶点序列 分别是P1 ,P2 ,…,PL和Q1 ,Q2 ,…,Qm。为说明 简便,假设P的边界上不包含Q的项点,Q的边 界也不包含P的顶点
有两个问题需要解决，一个是如何有次 序地求出各边的所有交点，一个是如何排列 求出交点和原凸多边形的顶点，形成交得凸 多边形的顶点序列。 为了有次序地求出交点，可以在两个多 边形边上交替地前进，原则是在哪个多边形 的边上可能有交点就等待，在另一个多边形 的边上前进。初始从对边PP,与QQ的求交 开始，注意所有求交是线段的求交。这里规 定了PoP,Q0Qm
有两个问题需要解决,一个是如何有次 序地求出各边的所有交点,一个是如何排列 求出交点和原凸多边形的顶点,形成交得凸 多边形的顶点序列。 为了有次序地求出交点,可以在两个多 边形边上交替地前进,原则是在哪个多边形 的边上可能有交点就等待,在另一个多边形 的边上前进。初始从对边P0 P1与Q0 Q1的求交 开始,注意所有求交是线段的求交。这里规 定了P0 =PL ,Q0 =Qm
前进 前进 出 前进 Q
情形 (1) (2) (3) (4) (5) (6) (7) (8) P在Qj-1Qj 左 左 右 右 右 左 右 左 Qj在Pi-1Pi 右 左 右 左 左 左 右 右 前进的多边 形 区分前四种情形还是后四种情形 求矢量积P-P,×Q:Q;的z分量，若该分量 大于等于0，是前四种情形，小于0是后四种情形
情形 (1) (2) (3) (4) (5) (6) (7) (8) Pi在Qj-1Qj 左 左 右 右 右 左 右 左 Qj在Pi-1Pi 右 左 右 左 左 左 右 右 前进的多边 形 Q P Q P P Q P Q 区分前四种情形还是后四种情形 求矢量积Pi-1 Pi×Qj-1 Qj的z分量,若该分量 大于等于0,是前四种情形,小于0是后四种情形
·Advance S←PP:XQQ的z分量；分二种情况处 理，然后算法就结束； 1.若S≥0，则做 若P在Q1Q左并且Q在yP左，或者P在Q 1Q,右并且Q在pP左，则前进1，否则j前进 2.若S<0,则做 若P在Q1Q右并且Q在PP左，或者P在Q Q右并直Q在PP右，则前进1，否则j前进1； 算法中"前进1"，指若i<l,则前进1是+1；若 i=L,则前进1是1。这因为多边形P是首尾相接 的。类似地"'j前进1"，j<m时是j+1;j=m时是1。 总在多边形P上前进，在Q上前进
• Advance S←Pi-1Pi×Qj-1Qj的z分量;分二种情况处 理,然后算法就结束; 1. 若S≥0,则做 若Pi在Qj-1Qj左并且Qj在Pi-1Pi左,或者Pi在Qj- 1Qj右并且Qj在pi-1Pi左,则i前进1,否则j前进1; 2. 若S<0,则做 若Pi在Qj-1Qj右并且Q在Pi-lPi左,或者Pi在Qj- 1Qj右并且Qj在Pi-1Pi右,则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上前进
为了正确排列求出的交点并加入原两个 凸多边形部分顶点以形成相交的凸多边形， 可以在每求出一个交点时进行一次输出。 求出的第一个交点可只做一下记录，如 果在以后交替前进求交点的过程中再次求出 与第一次求得相同的交点，就知道整个求交 过程已经结束了。 求得一个不是第一个的其它任何一个交 点时，为形成交得凸多边形顶点序列，要区分 边P-P是进入多边形0，还是走出Q两种情况
为了正确排列求出的交点并加入原两个 凸多边形部分顶点以形成相交的凸多边形, 可以在每求出一个交点时进行一次输出。 求出的第一个交点可只做一下记录,如 果在以后交替前进求交点的过程中再次求出 与第一次求得相同的交点,就知道整个求交 过程已经结束了。 求得一个不是第一个的其它任何一个交 点时,为形成交得凸多边形顶点序列,要区分 边Pi-l Pi是进入多边形Q,还是走出Q两种情况
P 05 Q-1 Q P-1 P P-1 Q-1 (1) (2) P-1P正进入多边形0，此时应输出本次 求出交点前，上次求得交点后的多边形0上 的各顶点，然后再输出本次交点，因为这 些点是交得凸多边形的顶点
Pi-1 Pi正进入多边形Q,此时应输出本次 求出交点前，上次求得交点后的多边形Q上 的各顶点，然后再输出本次交点，因为这 些点是交得凸多边形的顶点
P-P:是走出Q,这时应输出本次求出交 点前，上次求得交点后的多边形柳上的各顶 点，再输出本次交点。 这两种情况区分，可通过检查P在直线 Q;-Q;的左侧还是右侧来确定。 Output 若本过程是第一次被调用，则做： R←第一次求得的交点，若P在Q-Q左则 t←i,否则t←j; 否则做： 若P在Q-Q左，则做： 输出多边形0上t至j-1各顶点，输出当前交点 ,tfi;
Pi-1 Pi是走出Q,这时应输出本次求出交 点前，上次求得交点后的多边形P上的各顶 点, 再输出本次交点。 这两种情况区分,可通过检查Pi在直线 Qj-1 Qj的左侧还是右侧来确定。 Output 若本过程是第一次被调用,则做: R0←第一次求得的交点,若Pi在Qj-1 Qj左则 t←i,否则t←j； 否则做: 若Pi在Qj-1 Qj左,则做: 输出多边形Q上t至j-1各顶点,输出当前交点 ,t←i;
否则做：输出多边形柳上t至i-1各顶点，输 出当前交点，t←j; 两个凸多边形求交的完整算法： CONVEX POLYGON INTERSECT ION 1.〔准备)i←1，j1,k←1，PoPL,02-0m: 2.〔交替前进求交)若k≤2*(+m)并直所求出 当前交点不是第一次求得交点R,则做 2.12.3循环： 2.1 若线段P-1p;与Q-Q相交，则调用 Output; 2.2 调用Advance; 2.3 k←k+1;
否则做: 输出多边形P上t至i-1各顶点,输 出当前交点,t←j; 两个凸多边形求交的完整算法: CONVEX POLYGON INTERSECTION 1.〔准备〕i←1,j←1,k←1,P0←PL ,Q0←Qm ; 2.〔交替前进求交〕若k≤2*(l+m)并且所求出 当前交点不是第一次求得交点R0 ,则做 2.1~2.3循环: 2.1 若线段Pi-1Pi与Qj-1 Qj相交,则调用 Output; 2.2 调用Advance; 2.3 k←k+1;
3.〔结束判断)若在步2找到过交点，则 交得凸多边形顶点序列已在调用 0 utput:过程中输出，算法结束； 否则，做如下检查： 若P,包含于多边形Q中，则输出P 包含于Q中，算法结束； 若Q1包含于多边形P中，则输出Q 包含于P中，算法结束； 若上述两个检查都不成功，输出 交为空，两多边形分离，算法结束；
3.〔结束判断〕若在步2找到过交点,则 交得凸多边形顶点序列已在调用 Output过程中输出,算法结束; 否则,做如下检查: 若P1包含于多边形Q中,则输出P 包含于Q中,算法结束; 若Q1包含于多边形P中,则输出Q 包含于P中,算法结束; 若上述两个检查都不成功,输出 交为空,两多边形分离,算法结束;