 |
 |
 |
 |
 |
 |
 |
 |
|
 |
|
 |
|
| 第四节 包含与重叠 | ||||
 凸多边形重叠计算
两个凸多边形的重叠问题,这也就是对两个凸多边形求相交部分的问题。 现在约定凸多边形指它的边界和内部,凸多边形仍用顶点坐标的逆时针方向序列确定。 设给出的两个凸多边形P和Q的顶点序列分别是  和 。为说明简便,假设P的边界上不包含Q的项点,Q的边界也不包含P的顶点。
有两个问题需要解决,一个是如何有次序地求出各边的所有交点,一个是如何排列求出交点和原凸多边形的顶点,形成交得凸多边形的顶点序列。 为了有次序地求出交点,可以在两个多边形边上交替地前进,原则是在哪个多边形的边上可能有交点就等待,在另一个多边形的边上前进。初始从对边  与 的求交开始,注意所有求交是线段的求交。这里规定了 。
|
||||
 |
||||
 第一节
线段的交点计算第二节
多边形表面的交线计算第三节
平面中的凸壳算法第四节
包含与重叠第五节
简单多边形的三角剖分 |
