#include <iostream>
#include <vector>


class point
{
    public:
		point (int a, int b): x(a), y(b) {};
		~point () {};

		int getX() {return x;}
		int getY() {return y;}

	private:
		int x;
		int y;
};


class side
{
	public:
		side(point f, point s): first(f), second(s) {};
		~side() {};
		point getFirst() {return first;}
		point getSecond() {return second;}

	private:
		point first;
		point second;
};


class boundingBox
{
	public:
		boundingBox(std::vector <point> p);
		~boundingBox() {};

		std::vector <side> getSides() {return boundingSides;}

	private:
		std::vector <point> boundingPoints;
		std::vector <side> boundingSides;
};


boundingBox::boundingBox(std::vector <point> p)
{
	boundingPoints = p;

	// in the constructor, create a vector of sides from the points
	for (std::vector <point>::iterator i = boundingPoints.begin(); i != boundingPoints.end()-1; i++)
	{
		boundingSides.push_back( side(*i, *(i+1)) );
	}

	boundingSides.push_back( side (*(boundingPoints.end()-1), *(boundingPoints.begin()) ) );
}






bool collisionCheck(std::vector <side> s, point p)
{
	std::vector <side> nodeSides;

	int toleft = 0;
	int toright = 0;

	for (std::vector <side>::iterator i = s.begin(); i != s.end(); i++)
	{
		//if the Y value of the point being tested is between the Y values of a side, add a node
		if (p.getY() > (*i).getFirst().getY() && p.getY() < (*i).getSecond().getY() ||
		    p.getY() < (*i).getFirst().getY() && p.getY() > (*i).getSecond().getY() )
		{
			nodeSides.push_back( side ( (*i).getFirst(), (*i).getSecond() ) );
		}

		
		// if the Y value of the point being tested is also the Y of the second point of the side...
		if (p.getY() == (*i).getSecond().getY())
		{
			//if it isn't the last side, and this side and the next strattle that y value, add a node
			if (i != s.end()-1)
			{
				if ((*i).getFirst().getY() < p.getY() && (*(i+1)).getSecond().getY() > p.getY() ||
			   	    (*i).getFirst().getY() > p.getY() && (*(i+1)).getSecond().getY() < p.getY() )
				{
					nodeSides.push_back( side ( (*i).getFirst(), (*i).getSecond() ) );
				}	
			}	

			//if it is the last side, and this side and the first side strattle that y value, add a node
			else if ((*i).getFirst().getY() < p.getY() && s.front().getSecond().getY() > p.getY() ||
			   	 (*i).getFirst().getY() > p.getY() && s.front().getSecond().getY() < p.getY() )
			{
				nodeSides.push_back( side ( (*i).getFirst(), (*i).getSecond() ) );
			}
		}
	}

	for (std::vector <side>::iterator i = nodeSides.begin(); i != nodeSides.end(); i++)
	{
		double deltaY = (*i).getSecond().getY() - (*i).getFirst().getY();
		double deltaX = (*i).getSecond().getX() - (*i).getFirst().getX();

		double slope = deltaX - deltaY;
	
		double x = ( p.getY() - (*i).getSecond().getY() + (slope * (*i).getSecond().getX()) ) / slope;

		if (x < p.getX()) 
		{
			toleft++;
		}

		else
		{
			toright++;
		}
	}


	std::cout << "Analysis: " << toleft << " nodes to the left, " << toright << " nodes to the right." << std::endl;
	
	if (toleft % 2 == 0)
	{
		std::cout << "return false, does not hit" << std::endl;
		return false;
	}

	else
	{
		std::cout << "return true, hits" << std::endl;
		return true;
	}
}
			





int main ()
{
	std::vector <point> points;

	points.push_back(point(3, 5));
	points.push_back(point(1, 13));
	points.push_back(point(7, 16));
	points.push_back(point(14, 14));
	points.push_back(point(8, 13));
	points.push_back(point(9, 11));
	points.push_back(point(17, 13));
	points.push_back(point(16, 18));
	points.push_back(point(21, 15));
	points.push_back(point(17, 9));
	points.push_back(point(9, 7));
	points.push_back(point(12, 5));
	points.push_back(point(14, 7));
	points.push_back(point(15, 2));
	points.push_back(point(6, 3));

	boundingBox enemy(points);

	point hitSimp(13, 4);
	point hitComp(19, 15);
	point missNear(10, 12);
	point missFar(100,100);

	collisionCheck(enemy.getSides(), hitSimp);

	collisionCheck(enemy.getSides(), hitComp);

	collisionCheck(enemy.getSides(), missNear);

	collisionCheck(enemy.getSides(), missFar);

	return 0;
}