算法问题实战策略——15.6　多边形

以计算几何方式表现现实世界时，多边形（polygon）是必不可少的因素。因此，有关多边形的问题也经常出现在程序设计竞赛中。 多边形的种类 首先简单介绍本节将要用到的名词。  凸多边形（convex polygon）指的是每个内角都在180度以内的多边形。例如，正方形就是凸多边形。凸多边形具有几个非常有用的性质，所以会经常应用于解题过程。例如，两个凸多边形的交集也是凸多边形，连接凸多边形内部任意两点的线段绝不会与凸多边形的边相交。  反之，内角超过180度的多边形就是凹多边形（concave polygon）。  简单多边形（simple polygon）是边不相交的多边形。 求面积 给出三角形的3个顶点时，利用向量的叉积就能求出其面积。将其延伸后，就能很容易地求出凸多边形的面积。如图15-8(a)所示，在多边形内部选择一点，就能以将该点作为顶点的三角形分割此多边形。求出各三角形的面积就能求出多边形的面积，那么，该如何求出凹多边形的面积呢？ 向量的叉积会根据不同方向而发生符号变化，利用此性质就能把前面使用的算法应用于求凹多边形面积的问题。假设多边形的各个顶点p0、p1、•••、pn1已按逆时针方向排列，接下来选择一个点q后，分别计算将多边形的两个相邻顶点pi、p(i+1)%n和q视为顶点的各三角形的面积(piq)×(p(i+1)%nq)/2。此时需注意，没有对向量的叉积取绝对值，所以相加的三角形面积中会存在负值。要想让两个向量的叉积满足条件a×b>0，那么向量b必须在a的逆时针方向。因此，要想使面积为正数，连接qpip(i+1)%n的线段就必须在pi向左旋转。 图15-8　求多边形的面积 图15-8(b)和(c)分别表示示例多边形中具有正值面积和负值面积的三角形。不对这些面积取绝对值而直接相加，结果会如何呢？中空部分的面积相互抵消会变成0，最终会得到整个多边形的面积。无论q在什么位置，只要多边形是简单多边形，这种性质就总是成立。如果把q视为坐标空间的原点，对这种方法稍加整理即可得到更简单的公式。原点与相邻两顶点构成的三角形面积之和可定义为如下形式。 设pi=(xi, yi)，就会变成如下形式。 这个公式中，相加的项都是xiy(i+1)%n的形式，而相减的项都是x(i+1)%nyi的形式。那么，可以按照如下形式归纳整个多边形的面积。 此处对结果取了绝对值，因为叉积的和会根据多边形顶点的排列顺序是顺时针还是逆时针而取不同符号。代码15-10是实现这种公式的算法源代码。 代码15-10　求简单多边形面积的area()函数 // 求给定简单多边形p的面积。 // p是各顶点的位置向量的集合。 double area(const vector<vector2>& p) { double ret = 0; for(int i = 0; i < p.size(); ++i) { int j = (i + 1) % p.size(); ret += p[i].x * p[j].y - p[j].x * p[i].y; } return fabs(ret) / 2.0; } 内部/外部判断 给出简单多边形和不在此多边形边上的点q时，编写函数判断q在多边形的内部还是外部。编写这种函数的比较常用的方法是，画出一条从q起始向右伸展的射线，并算出射线与多边形的边共相交几次。图15-9(a)表示从给出的几个点画出的射线与多边形相交的次数。从多边形内部的点起始的射线会与多边形的边发生奇数次数的相交，而从多边形外部起始的射线会与多边形的边发生偶数次数的相交。这种方法实现起来似乎比较简单，不过需要处理较多的异常情况，所以还是比较麻烦。下面看看图15-9(b)。从a起始的射线经过多边形的顶点，所以此射线不会与多边形的任何一边相交。因此，算法会误判此点在多边形外部。那么，将多边形的边与射线发生接触的情况也视为相交，是否能解决这个问题呢？此射线在顶点处与两个边发生接触，所以这种方法也不是很适当。从b起始的射线与多边形的边完全重叠，此时应当将射线与边发生的相交次数算成1次，而1次未相交。那么，怎样才能编写出能够处理所有这些异常的算法呢？ 图15-9　解决多边形内部/外部的判断问题 可以将射线向上“略微”移动。假如射线与多边形的边(pi, p(i+1)%n)相互接触，那么，移动后的射线会与此边相交，或者根本不发生任何接触。这取决于此边的两个顶点中，与原射线没有发生接触的顶点处于移动后射线的上方还是下方。如果此顶点在射线上方，那么此边会与射线相交；如果此顶点在射线下方，那么此边不会与射线有任何接触。使用这种方法时需要注意，并不是真的上移射线，而只是进行假设。为了避免与顶点发生重叠，只将射线的y坐标增加一个很微小的值。因此，这种变化不会改变与其他边相交的情况。 代码15-11是实现这种算法的isInside()函数。算法并没有直接使用以前编写的线段相交函数，而是首先找出了能够把射线纵向分割的边，然后确认交点是否在q的右方。这种操作中，找出纵向分割边的代码就显得尤为重要。因为，某个边的顶点与射线重叠时，根据另一顶点所处位置的不同，其结果也会发生变化。另外，代码中完全忽略了与射线相互平行的边。 代码15-11　能够判断给定的点是否包含于简单多边形内部的isInside()函数 // 点q包含在多边形p内部时，返回真，否则返回假。 // 没有定义q在多边形的边上时的返回值。 bool isInside(vector2 q, const vector<vector2>& p) { int crosses = 0; for(int i = 0; i < p.size(); ++i) { int j = (i + 1) % p.size(); // (p[i], p[j])会纵向分割射线吗？ if((p[i].y > q.y) != (p[j].y > q.y)) { // 计算交点的x坐标。 double atX = (p[j].x - p[i].x) * (q.y - p[i].y) / (p[j].y - p[i].y) + p[i].x; if(q.x < atX) ++crosses; } } return crosses % 2 > 0; }