/**
 * @file
 * $Id$
 * $Revision$
 * $Author$
 * $Date$
 *
 * This file is part of The iWear Framework.
 *
 * The iWear Framework is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by the
 * Free Software Foundation as in version 2 of the License.

 * 
 * The iWear Framework is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
 * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
 * more details.
 * 
 * You should have received a copy of the GNU General Public License along with
 * The iWear Framework; if not, write to the Free Software Foundation, Inc., 59
 * Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */

#ifndef __IWEAR_POLYGON_H
#define __IWEAR_POLYGON_H

#ifndef __IWEAR_POINT_H
#include <iwear/point.h>
#endif

#ifndef __IWEAR_IWM_H
#include <iwear/iwm.h>
#endif

#include <vector>

namespace iwear
{
    namespace math
    {

template<class T>
class Polygon2D : public std::vector<Point2D<T> >
{
private:
protected:
public:
    typedef typename std::vector<Point2D<T> >::size_type size_type;
    /**
     * @return true if the passed point is within the polygon
     */
    bool within( const Point2D<T>& ) const;

    /**
     * Check whether no lines are crossing each other in the polygon and it has
     * some area.
     */
    bool check( void ) const;

    /**
     * Returns a rectangular bounding box of the polygon, while .first is the
     * lower left corner (minimum y and minimum x values) and .second is the
     * upper right corner (maximum y and maximum x values)
     */
    std::pair<Point2D<T>,Point2D<T> > box( void ) const;

    std::vector<Point2D<T> >& vector( void ) {  return *this; }
    const std::vector<Point2D<T> >& vector( void ) const {  return *this; }

    Polygon2D<T>& operator=( const std::vector<Point2D<T> >& p /*Polygon2D<T>& p*/ ) 
    {
	std::vector<Point2D<T> >::operator=(p);
	return *this;
    }
};

template<class T>
std::pair<Point2D<T>,Point2D<T> > Polygon2D<T>::box( void ) const/*{{{*/
{
    
    std::pair<Point2D<T>,Point2D<T> > ret;
    size_t n = this->size();
    if ( n <= 1 )
    {
	return ret;
    }
     
    T& minx = ret.first.x;
    T& miny = ret.first.y;
    T& maxx = ret.second.x;
    T& maxy = ret.second.y;


    const Point2D<T>& p = this->operator[](0);
    
    minx = p.x;
    miny = p.y;
    maxx = p.x;
    maxy = p.y;

    for( size_t i = 1; i < n; ++i )
    {
	const Point2D<T>& P = this->operator[](i);

	if ( minx > P.x )
	{
	    minx = P.x;
	}

	if ( miny > P.y )
	{
	    miny = P.y;
	}

	if ( maxx < P.x )
	{
	    maxx = P.x;
	}

	if ( maxy < P.y )
	{
	    maxy = P.y;
	}
    }
    return ret;
}/*}}}*/

template<class T>
bool Polygon2D<T>::check( void ) const/*{{{*/
{
    if( this->size() < 3 ) return false; // Point or line or nothing.

    // Go through the points and, hm, yes, do what ?
    // Look into sedgewicks algorithms, there is some intersection between
    // lines algorithm we might be able to use here to speed things up, maybe
    // for the within function too ?
    return false;
    return true;
}/*}}}*/

template<class T>
inline int32_t ccw( const Point2D<T>& p0, const Point2D<T>& p1, const Point2D<T>& p2 )/*{{{*/
{
    T dx1;
    T dx2;
    T dy1;
    T dy2;
    dx1 = p1.x - p0.x;
    dy1 = p1.y - p0.y;
    dx2 = p2.x - p0.x;
    dy2 = p2.y - p0.y;

    T a = dx1 * dy2;
    T b = dy1 * dx2;
    if ( a > b )
    {
	return 1;
    }
    if ( a < b )
    {
	return -1;
    }
    if ( a == b )
    {
	if (( dx1 * dx2 < 0 ) || (dy1 * dy2 < 0))
	{
	    return -1;
	}
	if ((dx1*dx1+dy1*dy1) >= (dx2*dx2+dy2*dy2))
	{
	    return 0;
	}
    }
    return 1;
}/*}}}*/

template<class T>
inline int32_t rccw( const Point2D<T>& p0, const Point2D<T>& p1, const Point2D<T>& p2 )/*{{{*/
{
    int32_t ret = ccw(p0,p1,p2);
//    cout << "ccw = " << ret << endl;
    return ret;
}/*}}}*/

template<class T>
inline bool intersect( const std::pair<Point2D<T>,Point2D<T> >& l1, const std::pair<Point2D<T>,Point2D<T> >& l2 )/*{{{*/
{
    return ( (ccw(l1.first,l1.second,l2.first) * ccw(l1.first,l1.second,l2.second)) <= math::Help<T>::neutral_addition(l1.first.x)) 
	&& ( (ccw(l2.first,l2.second,l1.first) * ccw(l2.first,l2.second,l1.second)) <= math::Help<T>::neutral_addition(l1.first.x));
}/*}}}*/
	
template<class T>
inline bool Polygon2D<T>::within( const Point2D<T>& t) const/*{{{*/
{
    if( this->size() < 3 ) return false; // Point or line or nothing.

    std::pair<Point2D<T>,Point2D<T> > lt;
    std::pair<Point2D<T>,Point2D<T> > lp;
    // Quelle : Algorithmen, Robert Sedgewick (Pascal) 2nd Edition, p406f
    // Eine möglicherweise schnellere lösung für grosse polygone ist im
    // kapitel27 angegeben, wobei man dort die menge alle schnitte einer
    // streckenmenge ermittelt, davon könnte man die menge der polygonseiten
    // abziehen und hat die menge aller schnitte der teststrecke mit dem
    // polygon, woraus man wiederrum die seite des punktes ermitteln kann...
    //
    // Möglicherweise braucht man das sowieso für die check methode die
    // ermitteln kann ob ein polygon sich nirgends selbst schneidet.
    lt.first = t;
    lt.second = t;
//    lt.second.x = 5000;
    lt.second.x = numeric_limits<float>::max();
    // lt is our "test line" for intersect test.

    int N = this->size();
    int j = 0;
    int count = 0;
 //   cout << "N = " << N << endl;
    for( int i = 1; i <= N; ++i )
    {
	if ( i == N )
	{
	    N = 0;
	    i = 0;
	}
	lp.first = (*this)[i];
	lp.second = (*this)[i];
	if ( ! intersect(lp,lt) )
	{
//	    cout << "Does not intersect point itself" << endl;
	    lp.second = (*this)[j];
	    if ( intersect(lp,lt) )
	    {
		count++;
	    }
	}
//	cout << "j = " << j << endl;
//	cout << "i = " << i << endl;
	j = i;
    }
//    cout << "COUNT = " << count << endl;
    return (count % 2);
}/*}}}*/

template<class T>
inline std::istream& operator>>( std::istream& i, iwear::math::Polygon2D<T>& p ) /*{{{*/
{
    iwear::math::Polygon2D<T> po;

    if( i.peek() == EOF )
    {
	i.clear();
	return i;
    }

    skipws(i);
    if( i.get() != '(' )
    {
	i.setstate(i.failbit);
	return i;
    }

    Point2D<T> pn;
    while(true)
    {
	i >> pn;
	if( !i ) return i;
	po.push_back(pn);
	char c = i.get();
	if( c == ',' )
	{
	    continue;
	}
	else if( c == ')' )
	{
	    break;
	}
	else
	{
	    i.setstate(i.failbit);
	    return i;
	}
    }
    p.swap(po);
    return i;
}/*}}}*/

template<class T>
inline std::ostream& operator<<( std::ostream& o, const iwear::math::Polygon2D<T>& p )
{
    o << "(";

    typename iwear::math::Polygon2D<T>::size_type i;
    for(i= 0; i < p.size(); ++i )
    {
	if( i != 0 )
	{
	    o << ",";
	}
	o << p[i];
    }

    o << ")";
    return o;
}

}// namespace math
}// namespace iwear

#endif