#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();
}
}
bool Polygon::contains (const Point & p) const
{
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);
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));
if (turn(line.get_p1(), line.get_p2(), v) ==
turn (line.get_p1(), line.get_p2(), *current))
{
intersections--;
}
}
}
while (current != first_point);
if (intersections % 2)
{
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;
Point p1 = *input_iter++;
Point p2 = *input_iter++;
Point p3 = *input_iter;
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);
}
do
{
Polygon::iterator first = hull.begin();
Polygon::iterator last = first - 1;
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);
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());
return hull;
}
int Polygon::orientation() const
{
const_iterator current = begin();
bool empty_triangle_found = false;
Triangle t;
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);
Point p = (*(current-1) + *current + *(current+1)) / 3;
if (p.is_inside (*this))
{
if (t.orientation () == counter_clockwise)
{
return counter_clockwise;
}
else
{
return clockwise;
}
}
else
{
if (t.orientation () == counter_clockwise)
{
return clockwise;
}
else
{
return counter_clockwise;
}
}
}