#include #include #include #include #include #include #include using namespace std; const int MAXD = 10000; // max value for |x|, |y| const int MAXPOLYGONS = 100; const int MAXSEGS = 20; const double PI = 4*atan(1.0); set xxvals; // scan line positions bool equals(double a, double b) { return (fabs(a-b) < 0.000001); } class point { public: double x, y; point() : x(0.0), y(0.0) {} point(double xx, double yy) : x(xx), y(yy) {} bool operator==(const point &rhs) const { return (equals(x, rhs.x) && equals(y, rhs.y)); } void print() const { cout << '(' << x << ',' << y << ')'; } }; class segment { public: point p1, p2; double ang; // angle from point with lowest x to point with highest x segment() {} segment(point pp1, point pp2) : p1(pp1), p2(pp2) {} void order() { if ((!equals(p2.x, p1.x) && p2.x < p1.x) || (equals(p2.x, p1.x) && p2.y < p1.y)) { point tmp = p1; p1 = p2; p2 = tmp; } ang = atan2(p2.y-p1.y, p2.x-p1.x); } }; class polygon { public: vector segs; int nsegs; double xmin, xmax, ymin, ymax; double area; polygon() : nsegs(0) {} void add(segment s) { area += (s.p2.x - s.p1.x)*(s.p2.y+s.p1.y); s.order(); segs.push_back(s); nsegs++; } double getArea() { return area/2.0; } void print() { for(int i=0; i rhs.x; } }; class scanLine { public: int n; // number of polygons int size; // number of nodes on scan line scanLineNode *nodes; // the scan line double prevXHigh; // used by getArea scanLine(int nn) { n = nn; size = 0; nodes = new scanLineNode[2*MAXSEGS*n]; prevXHigh = -2*MAXD; } void print() { for(int i=0; i 0 && !equals(nodes[i-1].y, node.y) && nodes[i-1].y > node.y) { nodes[i] = nodes[i-1]; i--; } segment s = polygons[node.ipoly].segs[node.iseg]; while(i > 0 && equals(nodes[i-1].y, node.y) && polygons[nodes[i-1].ipoly].segs[nodes[i-1].iseg].ang > s.ang) { nodes[i] = nodes[i-1]; i--; } nodes[i] = node; size++; } double getArea(double xhigh) { if (equals(xhigh, prevXHigh)) return 0.0; //cout << "next x = " << xhigh << endl; double area = 0.0; bool present[n]; for(int i=0; i