#include "Polygon.h" #include double Polygon::area() const { double d = 0.0; for(const_iterator it = begin(); it != end(); it++) { const_iterator it2 = it+1; if(it2 == end()) it2 = begin(); d += (it2->getX()+it->getX())*(it2->getY()-it->getY()); } return fabs(d/2); } double Polygon::perimeter() const { double d = 0.0; for(const_iterator it = begin(); it != end(); it++) { const_iterator it2 = it+1; if(it2 == end()) it2 = begin(); d += it->distance(*it2); } return d; } int Polygon::quadrant(const Vertex &v) const { if(v.getX() > 0 && v.getY() >= 0) return 1; if(v.getX() >= 0 && v.getY() < 0) return 2; if(v.getX() < 0 && v.getY() <= 0) return 3; if(v.getX() <= 0 && v.getY() > 0) return 4; return 0; } bool Polygon::contains(const Vertex &v) const { int d = 0; int q, ql, q2; LINE d1 = {Vertex(-1, -1), Vertex(1, 1)}; LINE d2 = {Vertex(-1, 1), Vertex(1, -1)}; LINE l; Vertex v2; if(empty()) return false; v2 = back() - v; q = quadrant(v2); if(q == 0) return true; for(const_iterator it = begin(); it != end(); it++) { ql = q; v2 = *it - v; q = quadrant(v2); if(q == 0) return true; switch(q-ql) { case 0: break; case 1: case -3: d++; break; case 3: case -1: d--; break; default: l.v1 = ((it == begin()) ? back() : *(it-1)) - v; l.v2 = v2; if(q == 1 || q == 3) { if(!(lineIntersection(&l, &d2, &v2) & INTERSECTION_LINE)) return false; q2 = quadrant(v2); if(q2 == 0) return true; if((q == 1 && q2 == 2) || (q == 3 && q2 == 4)) d -= 2; else d += 2; } else { if(!(lineIntersection(&l, &d1, &v2) & INTERSECTION_LINE)) return false; q2 = quadrant(v2); if(q2 == 0) return true; if((q == 2 && q2 == 3) || (q == 4 && q2 == 1)) d -= 2; else d += 2; } } } return (d != 0); } bool Polygon::intersects(const LINE *l) const { LINE line; for(Polygon::const_iterator it = begin(); it != end(); it++) { Polygon::const_iterator it2 = it+1; if(it2 == end()) it2 = begin(); line.v1 = *it; line.v2 = *it2; if(lineIntersection(l, &line, NULL) == INTERSECTION_SEGMENT_SEGMENT) return true; } return false; }