#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 { const Line d1(-1, -1, 1, 1); const Line d2(-1, 1, 1, -1); int d = 0; int q, ql, q2; 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.setVertex1(((it == begin()) ? back() : *(it-1)) - v); l.setVertex2(v2); if(q == 1 || q == 3) { if(!(l.intersects(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(!(l.intersects(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.setVertex1(*it); line.setVertex2(*it2); if(l.intersects(line, NULL) == INTERSECTION_SEGMENT_SEGMENT) return true; } return false; }