Geometry.h

Go to the documentation of this file.

 
#ifndef _LIMBO_GEOMETRY_GEOMETRY_H
#define _LIMBO_GEOMETRY_GEOMETRY_H
 
#include <vector>
#include <list>
#include <ostream>

namespace limbo 
{
namespace geometry 
{
 
using std::cout;
using std::endl;
using std::ifstream;
using std::ofstream;
using std::string;

enum orientation_2d_enum
{
    HORIZONTAL = 0, 
    VERTICAL = 1
};

enum slicing_orientation_2d
{
    HORIZONTAL_SLICING = 1,
    VERTICAL_SLICING = 2,
    HOR_VER_SLICING = 3, 
    HOR_VER_SA_SLICING = 4, 
    HOR_VER_AR_SLICING = 5 
};

inline std::string to_string(slicing_orientation_2d slicing_orient)
{
    switch (slicing_orient)
    {
        case HORIZONTAL_SLICING:
            return "HORIZONTAL_SLICING"; 
        case VERTICAL_SLICING:
            return "VERTICAL_SLICING"; 
        case HOR_VER_SLICING:
            return "HOR_VER_SLICING"; 
        case HOR_VER_SA_SLICING:
            return "HOR_VER_SA_SLICING"; 
        case HOR_VER_AR_SLICING:
            return "HOR_VER_AR_SLICING"; 
        default:
            return "UNKNOWN";
    }
}

enum direction_2d
{
    LEFT = 0, 
    BOTTOM = 1, 
    RIGHT = 2, 
    TOP = 3
};

enum winding_direction
{
    CLOCKWISE = 0, 
    COUNTERCLOCKWISE = 1, 
    UNKNOWN_WINDING = 2 
};

class orientation_2d
{
    public:
        orientation_2d() {m_orient = -1;}
        orientation_2d(orientation_2d_enum const& ori)
            : m_orient(ori) {}

        inline orientation_2d(const orientation_2d& ori) : m_orient(ori.m_orient) {}
        inline orientation_2d& operator=(const orientation_2d& ori) 
        {m_orient = ori.m_orient; return * this; }

        inline bool operator==(orientation_2d const& rhs) const { return (m_orient == rhs.m_orient); }
        inline bool operator!=(orientation_2d const& rhs) const { return (m_orient != rhs.m_orient); }
        inline int to_int() const { return m_orient; }
        inline void turn_90() { m_orient = m_orient^ 1; }
        inline orientation_2d get_perpendicular() const 
        {
            orientation_2d retval = *this;
            retval.turn_90();
            return retval;
        }

        inline bool valid() const {return m_orient == 0 || m_orient == 1;}
        friend bool operator<(orientation_2d const& ori1, orientation_2d const& ori2) 
        {return ori1.m_orient < ori2.m_orient;}
    protected:
        int m_orient; 
};

template <typename T>
struct coordinate_traits; 

template <>
struct coordinate_traits<int> 
{
    typedef int coordinate_type;
    typedef long area_type;
 
    typedef long manhattan_area_type;
    typedef unsigned long unsigned_area_type;
    typedef long coordinate_difference;
 
    typedef long coordinate_distance;
};

#define LIMBO_GEOMETRY_COORDINATE_TRAITS(T, AREA_T, UNSIGNED_AREA_T) \
template <> \
struct coordinate_traits<T> \
{ \
    typedef T coordinate_type; \
    typedef AREA_T area_type; \
    typedef AREA_T manhattan_area_type; \
    typedef UNSIGNED_AREA_T unsigned_area_type; \
    typedef AREA_T coordinate_difference; \
    typedef AREA_T coordinate_distance; \
};
 
#ifdef __SIZEOF_INT128__
LIMBO_GEOMETRY_COORDINATE_TRAITS(long, __int128_t, __uint128_t)
LIMBO_GEOMETRY_COORDINATE_TRAITS(unsigned long, __int128_t, __uint128_t)
LIMBO_GEOMETRY_COORDINATE_TRAITS(long long, __int128_t, __uint128_t)
LIMBO_GEOMETRY_COORDINATE_TRAITS(unsigned long long, __int128_t, __uint128_t)
#else 
LIMBO_GEOMETRY_COORDINATE_TRAITS(long, long long, unsigned long long)
LIMBO_GEOMETRY_COORDINATE_TRAITS(unsigned long, long long, unsigned long long)
LIMBO_GEOMETRY_COORDINATE_TRAITS(long long, long long, unsigned long long)
LIMBO_GEOMETRY_COORDINATE_TRAITS(unsigned long long, long long, unsigned long long)
#endif 
 
#undef LIMBO_GEOMETRY_COORDINATE_TRAITS

template <typename PointType>
struct point_traits 
{
    typedef PointType point_type;
    typedef typename point_type::coordinate_type coordinate_type;

    static coordinate_type get(const point_type& point, orientation_2d const& orient) 
    {return point.get(orient);}

    static void set(point_type& point, orientation_2d const& orient, coordinate_type const& value) 
    {point.set(orient, value);}

    static point_type construct(coordinate_type const& x, coordinate_type const& y) 
    {return point_type(x, y);}
};

template <typename RectType>
struct rectangle_traits 
{
    typedef RectType rectangle_type;
    typedef typename rectangle_type::coordinate_type coordinate_type;

    static inline coordinate_type get(rectangle_type const& rectangle, direction_2d const& direct) 
    {return rectangle.get(direct);}

    static inline void set(rectangle_type& rectangle, direction_2d const& direct, coordinate_type const& v)
    {rectangle.set(direct, v);}

    static inline rectangle_type construct(coordinate_type const& xl, coordinate_type const& yl, 
            coordinate_type const& xh, coordinate_type const& yh)
    {return rectangle_type(xl, yl, xh, yh);}
};
 
#if 0
template <typename PolygonType>
struct polygon_90_traits 
{
    typedef PolygonType polygon_type;
    typedef typename polygon_type::point_type point_type;
    typedef typename point_type::coordinate_type coordinate_type;
    typedef typename polygon_type::vertex_iterator_type vertex_iterator_type;
 
    // Get the begin iterator
    static inline vertex_iterator_type begin_vertex(polygon_type const& p)
    {return p.begin_vertex();}
 
    // Get the end iterator
    static inline vertex_iterator_type end_vertex(polygon_type const& p) 
    {return p.end_vertex();}
 
    // Get the winding direction of the polygon
    static inline winding_direction winding(polygon_type const&) 
    {return UNKNOWN_WINDING;}
};
#endif 

template <typename ContainerType>
struct container_traits
{
    typedef ContainerType container_type;
    typedef typename container_type::value_type value_type;
    typedef typename container_type::const_iterator const_iterator_type;
    typedef typename container_type::iterator iterator_type;

    static void insert(container_type& container, value_type const& v) {container.insert(v);}
    static void insert(container_type& container, iterator_type it, value_type const& v) {container.insert(it, v);}
    static void erase(container_type& container, value_type const& v) {container.erase(v);}
    static void erase(container_type& container, iterator_type it) {container.erase(it);}
    template <typename PointCompareType>
    static container_type construct(PointCompareType const& comp)
    {return container_type(comp);}
};

template <typename T>
struct container_traits<std::vector<T> >
{
    typedef std::vector<T> container_type;
    typedef typename container_type::value_type value_type;
    typedef typename container_type::const_iterator const_iterator_type;
    typedef typename container_type::iterator iterator_type;

    static void insert(container_type& container, value_type const& v) {container.push_back(v);}
    static void insert(container_type& container, iterator_type it, value_type const& v) {container.insert(it, v);}
    static void erase(container_type& container, iterator_type it) {container.erase(it);}
    template <typename PointCompareType>
    static container_type construct(PointCompareType const&)
    {return container_type();}
};

template <typename T>
struct container_traits<std::list<T> >
{
    typedef std::list<T> container_type;
    typedef typename container_type::value_type value_type;
    typedef typename container_type::const_iterator const_iterator_type;
    typedef typename container_type::iterator iterator_type;

    static void insert(container_type& container, value_type const& v) {container.push_back(v);}
    static void insert(container_type& container, iterator_type it, value_type const& v) {container.insert(it, v);}
    static void erase(container_type& container, iterator_type it) {container.erase(it);}
    template <typename PointCompareType>
    static container_type construct(PointCompareType const&)
    {return container_type();}
};

template <typename PointSet>
inline typename coordinate_traits<typename point_traits<typename container_traits<PointSet>::value_type>::coordinate_type>::area_type
area(PointSet const& vPoint)
{
    typedef typename container_traits<PointSet>::const_iterator_type const_iterator_type;
    typedef typename container_traits<PointSet>::value_type point_type;
    typedef typename point_traits<point_type>::coordinate_type coordinate_type;
    typedef typename coordinate_traits<coordinate_type>::area_type area_type;
 
    area_type a = 0;
    for (const_iterator_type itCur = vPoint.begin(); itCur != vPoint.end(); ++itCur)
    {
        const_iterator_type itNext = itCur;
        ++itNext;
        if (itNext == vPoint.end()) itNext = vPoint.begin();
 
        a += (area_type)(point_traits<point_type>::get(*itNext, HORIZONTAL) - point_traits<point_type>::get(*itCur, HORIZONTAL)) * 
            (area_type)(point_traits<point_type>::get(*itNext, VERTICAL) + point_traits<point_type>::get(*itCur, VERTICAL)); 
    }
    return a/2;
}
 
} // namespace geometry
} // namespace limbo
 
#endif