多边形的交集 解决此问题的最直观的方法是,先求出两个简单多边形的交集,然后求交集面积。两个多边形都是凸多边形时,最容易求出多边形的交集,因为两个凸多边形的交集也是凸多边形。不过此题中,小岛的轮廓是任意简单多边形,所以此性质并不成立。所幸第二个多边形是矩形,所以是凸多边形,问题也就变得简单了。 图15-10 利用半平面的交集生成凸多边形 我们要利用的凸多边形重要特性之一是,可以通过多个半平面(half plane)的交集求出凸多边形。将凸多边形的各边按照逆时针方向遍历,并求出包含各边的直线左侧半平面。那么,这些半平面的交集就等于当前凸多边形。图15-10表示包含一个凸多边形4边的几条直线及其定义的半平面,图中深色部分的交集就是四边形内部的多边形。 求给定多边形和四边形的交集时可利用此性质。如图15-11所示,先设计函数求多边形和半平面的交集。此函数在给出多边形P和向量a、b时,用包含a、b的直线分割多边形,然后返回其中一部分。图中从a看向b时,返回b左侧的部分。如果给出图15-11形状的多边形,函数会返回图中深色的部分。 图15-11 利用包含向量的直线分割多边形 利用直线分割多边形 下面从图15-11中找出想要得到的深色多边形的顶点。可知如下性质。 多边形的顶点中,直线左侧的点都将成为分割后多边形的顶点。 多边形的边横穿直线时,边与直线的交点也将成为分割后多边形的顶点。 利用这些性质就可以编写算法,按照逆时针方向遍历所有点以找出顶点。此算法遍历所有点后,按照相遇顺序将顶点添加到分割后的多边形上。代码15-12的cutPoly()实现了该算法,ccw()函数判断各点属于哪个平面。如果有cutPoly()函数,就可以将其调用4次以求出四边形和P的交集。代码15-12的intersection()函数实现这种操作。请注意,代码按照逆时针方向遍历四边形的各边。cutPoly()函数会根据两点的输入顺序返回不同多边形,因此,输入顺序有误就会得到意想不到的交集。 代码15-12 解决金银岛问题的裁剪多边形算法 typedef vector<vector2> polygon; // 求半平面与简单多边形的交集。 // 用包含(a, b)的直线分割多边形p后,返回(a, b)左侧的部分。 polygon cutPoly(const polygon& p, const vector2& a, const vector2& b) { int n = p.size(); // 查看各点是否在半平面内。 vector<bool> inside(n); for(int i = 0; i < n; ++i) inside[i] = ccw(a, b, p[i]) >= 0; polygon ret; // 遍历多边形的边并找出分割后多边形的各个顶点。 for(int i = 0; i < n; ++i) { int j = (i + 1) % n; // 半平面内的点p[i]总是包含于分割后的多边形。 if(inside[i]) ret.push_back(p[i]); // 如果边p[i]-p[j]与直线相交,就把交点包含到分割后的多边形中。 if(inside[i] != inside[j]) { vector2 cross; assert(lineIntersection(p[i], p[j], a, b, cross)); ret.push_back(cross); } } return ret; } // 利用萨瑟兰德-霍奇曼(Sutherland-Hodgman)算法的多边形裁剪。 polygon intersection(const polygon& p, double x1, double y1, double x2, double y2) { vector2 a(x1, y1), b(x2, y1), c(x2, y2), d(x1, y2); polygon ret = cutPoly(p, a, b); ret = cutPoly(ret, b, c); ret = cutPoly(ret, c, d); ret = cutPoly(ret, d, a); return ret; } 从代码注释中可以看出,此算法名为萨瑟兰德-霍奇曼算法。在利用一个多边形裁剪另一个多边形的多边形裁剪(polygon clipping)算法中,萨瑟兰德-霍奇曼算法是最基础且最悠久的算法。 注意事项 第二个示例的图形如图15-12所示。从图中可以看出,如果小岛的轮廓是凹多边形,通过交集有可能得到两个以上的多边形。但代码15-12完全没有考虑这种情况!这究竟是为什么呢? 萨瑟兰德霍奇曼算法会把多边形的边越过直线的点和越过来的点相互连接,因此,向代码15-12输入第二个示例时,会返回一个“上面的多边形和下面的多边形被一个重叠的边相互连接”的多边形。重叠部分的面积是0,所以此题中可以忽略这部分。不过,有些问题需要另外处理这种多边形,所以应当对分割后的多边形进行适当后处理。此时就需要分割两个多边形,或者使用其他算法。 图15-12 金银岛问题的第二个示例数据