src/tools/tCoord.h

Go to the documentation of this file.

/*

*************************************************************************

ArmageTron -- Just another Tron Lightcycle Game in 3D.
Copyright (C) 2000  Manuel Moos (manuel@moosnet.de)

**************************************************************************

This program 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; either version 2
of the License, or (at your option) any later version.

This program 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 this program; if not, write to the Free Software
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
  
***************************************************************************

*/

#ifndef ArmageTron_tCOORD_H
#define ArmageTron_tCOORD_H

//#include <iostream>
#include "defs.h"
#include "tError.h"
#include <iterator>
#include <algorithm>
#include <map>
#include <vector>

class tCoord{
public:
    REAL x,y; 
    explicit tCoord(REAL X=0,REAL Y=0):x(X),y(Y){}; 

    // Calculations:
    inline bool operator==(const tCoord &a) const; 
    bool operator!=(const tCoord &a) const{return !operator==(a);} 
    tCoord operator-(const tCoord &a) const{return tCoord(x-a.x,y-a.y);} 
    tCoord operator-() const{return tCoord(-x,-y);} 
    tCoord operator+(const tCoord &a) const{return tCoord(x+a.x,y+a.y);} 
    const tCoord& operator+=(tCoord const &other)    { x+=other.x; y+=other.y; return *this;} 
    const tCoord& operator-=(tCoord const &other)    { x-=other.x; y-=other.y; return *this;} 
    tCoord operator*(REAL a) const      {return tCoord(x*a,y*a);} 
    const tCoord& operator*=(REAL a)    { x*=a; y*=a; return *this;} 
    const tCoord& operator*=(tCoord const &other)    { x*=other.x; y*=other.y; return *this;} 
    REAL NormSquared()          const   {return x*x+y*y;} 
    REAL Norm()                 const   {return sqrt(NormSquared());} 
    void Normalize()                    { *this *= 1/Norm(); } 
    const tCoord &operator=(const tCoord &a){ x=a.x;y=a.y; return *this;  } 

    static REAL F(const tCoord &a,const tCoord &b){
        return(a.x*b.x+a.y*b.y);
    }

    static REAL V(const tCoord &a,const tCoord &b,const tCoord &c){
        tCoord ab=b-a;
        tCoord ac=c-a;
        return(F(ab,ac)/F(ac,ac));
    }

    static REAL CrossProduct(tCoord const &a, tCoord const &b, tCoord const &c) {
        return (b.x - a.x)*(c.y - a.y) - (c.x - a.x)*(b.y - a.y);
    }

    static REAL Tangent(tCoord const &a, tCoord const &b) {
        return (b.y - a.y)/(b.x-a.x);
    }

private:
    class GrahamComparator {
        tCoord const &m_reference;
    public:
        GrahamComparator(tCoord const &reference) : m_reference(reference) {}
        bool operator()(tCoord const &a, tCoord const &b) {
            REAL ta = Tangent(m_reference, a), tb = Tangent(m_reference, b);

            //check for 90 degree angles...
            if(ta == NAN && tb == NAN) return fabs((m_reference-a).NormSquared()) < fabs((m_reference-b).NormSquared());
            if(ta == NAN) return tb<0;
            if(tb == NAN) return ta>0;

            //check for opposite sides
            if(ta>0 && tb<0) return true;
            if(tb>0 && ta<0) return false;

            return (ta<tb-EPS) || ((fabs(ta-tb)<EPS) && fabs((m_reference-a).NormSquared()) < fabs((m_reference-b).NormSquared()));
        }
    };
public:

    template<typename T> static void GrahamScan(T &in, T &out);

REAL   operator*(const tCoord &a) const{return -x*a.y+y*a.x;}


    tCoord Turn(const tCoord &a) const{return tCoord(x*a.x-y*a.y,y*a.x+x*a.y);}
    tCoord Turn(REAL x,REAL y) const{return Turn(tCoord(x,y));}
    tCoord Conj() const{return tCoord(x,-y);}

    // I/O:
    void Print(std::ostream &s) const; 
    void Read(std::istream &s); 
};

REAL se_EstimatedRangeOfMult(const tCoord &a,const tCoord &b);

REAL st_GetDifference( const tCoord & a, const tCoord & b );

inline bool tCoord::operator==(const tCoord &a) const{
    return ((*this-a).NormSquared()<=(EPS*EPS)*se_EstimatedRangeOfMult(*this,a));
}

inline std::ostream &operator<< (std::ostream &s,const tCoord &c){
    c.Print(s);
    return s;
}

inline std::istream &operator>> (std::istream &s,tCoord &c){
    c.Read(s);
    return s;
}

inline tCoord operator*(REAL a, tCoord const &c) {
    return c*a;
}

template<typename T> void tCoord::GrahamScan(T &in, T &out) {
    tASSERT(!in.empty());
    out.clear();

    // find the point that's closest to the bottom, preferring points to the left
    tCoord P=in.front();
    typename T::iterator iter(in.begin()+1);
    for(; iter != in.end(); ++iter) {
        if(iter->y < P.y || iter->y == P.y && iter->x < P.x) {
            P = *iter;
        }
    }

    std::sort(in.begin(), in.end(), GrahamComparator(P));

    //std::cerr << "P: " << P << std::endl;

    out.push_back(P);
    for(typename T::iterator iter = in.begin()+1; iter != in.end(); ++iter) {
        if(*iter != P) {
            out.push_back(*iter);
            break;
        }
    }
    if(out.size()<2) return; //all points equeal P, kinda boring...

    //std::copy(in.begin(), in.end(), std::ostream_iterator<tCoord>(std::cerr, " "));
    //std::cerr << std::endl;
    for(typename T::iterator iter = in.begin(); iter != in.end(); ++iter) {
        //std::cerr << "New point: " << *iter << "; angle=" << (atanf(Tangent(P, *iter))*180/M_PI) << std::endl;
    }

    for(typename T::iterator iter = in.begin()+2; iter != in.end(); ++iter) {
        if(*iter == P) continue;
        if(*iter == *(iter - 1)) continue; //duplicate or near- duplicate point; We don't want that mess.
        //std::cerr << "New point: " << *iter << "; angle=" << Tangent(P, *iter) << std::endl;
        //if(iter->y > 200) std::cerr << "==================\n";
        float product = CrossProduct(out[out.size()-2], out.back(), *iter);
        if (product < 0 || fabs(product) < EPS) {
            //the last three points are concave, remove points until they're not
            while((product < 0 || fabs(product) < EPS) && out.size() > 2) {
                //std::cerr << "concave: " << *(iter-2) << " " << *(iter-1) << " " << *iter << std::endl;
                //std::copy(out.begin(), out.end(), std::ostream_iterator<tCoord>(std::cerr, " "));
                //std::cerr << std::endl;
                out.pop_back();
                product = CrossProduct(out[out.size()-2], out.back(), *iter);
            }
        } else {
            //std::cerr << "Passed point: " << *iter << std::endl;
        }
        out.push_back(*iter);
        //std::copy(out.begin(), out.end(), std::ostream_iterator<tCoord>(std::cerr, " "));
        //std::cerr << std::endl;
    }
    float product = CrossProduct(out[out.size()-2], out.back(), P);
    while((product < 0 || fabs(product) < EPS) && out.size() > 2) {
        //std::cerr << "concave: " << *(iter-2) << " " << *(iter-1) << " " << *iter << std::endl;
        //std::copy(out.begin(), out.end(), std::ostream_iterator<tCoord>(std::cerr, " "));
        //std::cerr << std::endl;
        out.pop_back();
        product = CrossProduct(out[out.size()-2], out.back(), P);
    }
    //std::cerr << "=====\n";
    //for(typename T::iterator iter = out.begin(); iter != out.end(); ++iter) {
    //  std::cerr << *iter << std::endl;
    //}

}

extern const tCoord se_zeroCoord;
#endif

---