#include #include #include #include #include #include #include using namespace std; const int MAXD = 10000; // max value for |x|, |y| const int MAXSECTORS = 100; const int NUMSECTIONS = 800; // how many segments used to model a circle double TOL = 0.01; 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 cx, cy, r; // center and radius of sector polygon() : nsegs(0) {} void add(segment s) { s.order(); segs.push_back(s); nsegs++; } 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[4*n]; prevXHigh = -2*MAXD; } void print() { for(int i=0; i 0 && 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] = {0}; double xlow = nodes[0].x; double ylow1 = 2*MAXD; // artificially high double ylow2 = 2*MAXD; double yhigh1 = -2*MAXD; // artificially low double yhigh2 = -2*MAXD; int count = 0; // number of polygons in current // vertical section of scan line for(int i=0; i