// ********************************************************** // File: Polygon.cpp // Description: Implementation of class Polygon // // Author: Carlos Moreno // ********************************************************** #include "Polygon.h" #include "Segment.h" #include "Triangle.h" Polygon::iterator Polygon::begin() { return iterator (vertices.begin(), vertices.end()); } Polygon::const_iterator Polygon::begin() const { return const_iterator (vertices.begin(), vertices.end()); } void Polygon::push_back (const Point & p) { vertices.push_back (p); } void Polygon::push_front (const Point & p) { vertices.push_front (p); } void Polygon::insert (const iterator & i, const Point & p) { vertices.insert (i.get_i(), p); } Polygon::iterator Polygon::remove (const iterator & target) { if (!(vertices.empty())) { list<Point>::iterator ret_value; ret_value = vertices.erase (target.get_i()); if (ret_value == vertices.end()) { return iterator (vertices.begin(), vertices.end()); } else { return iterator (ret_value, vertices.end()); } } else { return iterator(); // return "null" iterator } } bool Polygon::contains (const Point & p) const { // Find a point outside the polygon //(point with max x + (1,0)) const_iterator current = begin(); Point p_max_x = *current++; do { if ((*current).get_x() > p_max_x.get_x()) { p_max_x = *current; } current++; } while (current != begin()); Point outside = p_max_x + Point (1,0); Segment line (p, outside); // Now check the number of intersections of segment // p - outside with the edges of the polygon // The loop must start in a vertex that is not exactly // on the segment 'line'. int intersections = 0; current = begin(); while ((*current).is_on (line)) current++; Polygon::const_iterator first_point = current; do { Point v = *current++; if (Segment (v, *current).intersects (line)) { intersections++; } if ((*current).is_on (line)) { while ((*++current).is_on (line)); // Skip all the vertices that are on the line if (turn(line.get_p1(), line.get_p2(), v) == turn (line.get_p1(), line.get_p2(), *current)) { intersections--; } // If previous and next points are on the same // side of line, then line doesn't intersect the // polygon;  it merely touches it at the vertex. // Since one intersection was counted by the test // with the first edge, decrement the count. } } while (current != first_point); if (intersections % 2) // if odd number of intersections { return true; } else { return false; } } void Polygon::draw (bool draw_vs, int v_radius) const { const_iterator current = begin(); if (draw_vs) { (*current).draw (2 * v_radius); } do { if (draw_vs) { (*current).draw (v_radius); } Point p = *current++; Segment (p, *current).draw(); } while (current != begin()); } Polygon Polygon::convex_hull() const { Polygon hull; Polygon::const_iterator input_iter = begin(); Polygon::iterator hull_iter; // The first three points go directly to the output Point p1 = *input_iter++; Point p2 = *input_iter++; Point p3 = *input_iter; // Make sure the output is in counter-clockwise sense if (turn (p1, p2, p3) == left_turn) { hull.push_back (p1); hull.push_back (p2); hull.push_back (p3); hull.push_front (p3); } else { hull.push_back (p2); hull.push_back (p1); hull.push_back (p3); hull.push_front (p3); } // The last point has to be always inserted at both ends do { Polygon::iterator first = hull.begin(); Polygon::iterator last = first - 1; // The list is circular Point p = *input_iter++; if (turn (*(first+1), *first, p) == left_turn || turn (*(last-1), *last, p) == right_turn) { hull.push_back (p); hull.push_front (p); // Now fix the possible concavities after insertion // of new point (on both ends of the output list) first = hull.begin(); last = first-1; while (turn (*first, *(first+1), *(first+2)) == right_turn) { hull.remove (first+1); } while (turn (*last, *(last-1), *(last-2)) == left_turn) { hull.remove (last-1); } } } while (input_iter != begin()); hull.remove (hull.begin()); // Remove repeated point (1st pt. = last pt.) return hull; } int Polygon::orientation() const { const_iterator current = begin(); bool empty_triangle_found = false; Triangle t; // Find a triangle (three consecutive vertices of // the polygon) that doesn't contain any other // vertex of the polygon. do { t = Triangle (*(current-1), *current, *(current+1)); bool t_is_empty = true; const_iterator i = begin(); do { if ((*i).is_inside (t)) { t_is_empty = false; break; } i++; } while (i != begin()); if (t_is_empty) { empty_triangle_found = true; } else { current++; } } while (!empty_triangle_found); // Now we know that either all the points inside the // triangle are inside the polygon, are all are // outside the polygon. // Given the orientation of t, and checking if a // point inside t is also inside the polygon, we // determine the orientation of the polygon. Point p = (*(current-1) + *current + *(current+1)) / 3; if (p.is_inside (*this)) // if inside the polygon { if (t.orientation () == counter_clockwise) { return counter_clockwise; } else { return clockwise; } } else { if (t.orientation () == counter_clockwise) { return clockwise; } else { return counter_clockwise; } } }

Return to article