FM / polygon

/usr/include/boost/polygon

Name	Size	Mode	Actions
detail/	-	0755	rm
gmp_override.hpp	3245	0644	edit dl rm
gtl.hpp	696	0644	edit dl rm
interval_concept.hpp	25993	0644	edit dl rm
interval_data.hpp	2701	0644	edit dl rm
interval_traits.hpp	1364	0644	edit dl rm
isotropy.hpp	17571	0644	edit dl rm
point_concept.hpp	12743	0644	edit dl rm
point_data.hpp	3252	0644	edit dl rm
point_traits.hpp	1328	0644	edit dl rm
polygon.hpp	2418	0644	edit dl rm
polygon_45_data.hpp	2330	0644	edit dl rm
polygon_45_set_concept.hpp	19393	0644	edit dl rm
polygon_45_set_data.hpp	78330	0644	edit dl rm
polygon_45_set_traits.hpp	6216	0644	edit dl rm
polygon_45_with_holes_data.hpp	3510	0644	edit dl rm
polygon_90_data.hpp	2888	0644	edit dl rm
polygon_90_set_concept.hpp	26923	0644	edit dl rm
polygon_90_set_data.hpp	44501	0644	edit dl rm
polygon_90_set_traits.hpp	16451	0644	edit dl rm
polygon_90_with_holes_data.hpp	3994	0644	edit dl rm
polygon_data.hpp	2218	0644	edit dl rm
polygon_set_concept.hpp	26570	0644	edit dl rm
polygon_set_data.hpp	40251	0644	edit dl rm
polygon_set_traits.hpp	5385	0644	edit dl rm
polygon_traits.hpp	74180	0644	edit dl rm
polygon_with_holes_data.hpp	3458	0644	edit dl rm
rectangle_concept.hpp	50898	0644	edit dl rm
rectangle_data.hpp	2120	0644	edit dl rm
rectangle_traits.hpp	1349	0644	edit dl rm
segment_concept.hpp	20086	0644	edit dl rm
segment_data.hpp	2772	0644	edit dl rm
segment_traits.hpp	1463	0644	edit dl rm
segment_utils.hpp	4963	0644	edit dl rm
transform.hpp	15004	0644	edit dl rm
voronoi.hpp	4511	0644	edit dl rm
voronoi_builder.hpp	19672	0644	edit dl rm
voronoi_diagram.hpp	19489	0644	edit dl rm
voronoi_geometry_type.hpp	1407	0644	edit dl rm

Edit: /usr/include/boost/polygon/isotropy.hpp (17571B)

/*
  Copyright 2008 Intel Corporation

Use, modification and distribution are subject to the Boost Software License,
  Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  http://www.boost.org/LICENSE_1_0.txt).
*/

#ifndef BOOST_POLYGON_ISOTROPY_HPP
#define BOOST_POLYGON_ISOTROPY_HPP

//external
#include <cmath>
#include <cstddef>
#include <cstdlib>
#include <vector>
#include <deque>
#include <map>
#include <set>
#include <list>
//#include <iostream>
#include <algorithm>
#include <limits>
#include <iterator>
#include <string>

#ifndef BOOST_POLYGON_NO_DEPS

#include <boost/config.hpp>
#ifdef BOOST_MSVC
#define BOOST_POLYGON_MSVC
#endif
#ifdef BOOST_INTEL
#define BOOST_POLYGON_ICC
#endif
#ifdef BOOST_HAS_LONG_LONG
#define BOOST_POLYGON_USE_LONG_LONG
typedef boost::long_long_type polygon_long_long_type;
typedef boost::ulong_long_type polygon_ulong_long_type;
//typedef long long polygon_long_long_type;
//typedef unsigned long long polygon_ulong_long_type;
#endif
#else

#ifdef _WIN32
#define BOOST_POLYGON_MSVC
#endif
#ifdef __ICC
#define BOOST_POLYGON_ICC
#endif
#define BOOST_POLYGON_USE_LONG_LONG
typedef long long polygon_long_long_type;
typedef unsigned long long polygon_ulong_long_type;
#endif

namespace boost { namespace polygon{

enum GEOMETRY_CONCEPT_ID {
    COORDINATE_CONCEPT,
    INTERVAL_CONCEPT,
    POINT_CONCEPT,
    POINT_3D_CONCEPT,
    RECTANGLE_CONCEPT,
    POLYGON_90_CONCEPT,
    POLYGON_90_WITH_HOLES_CONCEPT,
    POLYGON_45_CONCEPT,
    POLYGON_45_WITH_HOLES_CONCEPT,
    POLYGON_CONCEPT,
    POLYGON_WITH_HOLES_CONCEPT,
    POLYGON_90_SET_CONCEPT,
    POLYGON_45_SET_CONCEPT,
    POLYGON_SET_CONCEPT
  };

struct undefined_concept {};

template <typename T>
  struct geometry_concept { typedef undefined_concept type; };

template <typename GCT, typename T>
  struct view_of {};

template <typename T1, typename T2>
  view_of<T1, T2> view_as(const T2& obj) { return view_of<T1, T2>(obj); }

template <typename T, bool /*enable*/ = true>
  struct coordinate_traits {};

//used to override long double with an infinite precision datatype
  template <typename T>
  struct high_precision_type {
    typedef long double type;
  };

template <typename T>
  T convert_high_precision_type(const typename high_precision_type<T>::type& v) {
    return T(v);
  }

//used to override std::sort with an alternative (parallel) algorithm
  template <typename iter_type>
  void polygon_sort(iter_type _b_, iter_type _e_);

template <typename iter_type, typename pred_type>
  void polygon_sort(iter_type _b_, iter_type _e_, const pred_type& _pred_);

template <>
  struct coordinate_traits<int> {
    typedef int coordinate_type;
    typedef long double area_type;
#ifdef BOOST_POLYGON_USE_LONG_LONG
    typedef polygon_long_long_type manhattan_area_type;
    typedef polygon_ulong_long_type unsigned_area_type;
    typedef polygon_long_long_type coordinate_difference;
#else
    typedef long manhattan_area_type;
    typedef unsigned long unsigned_area_type;
    typedef long coordinate_difference;
#endif
    typedef long double coordinate_distance;
  };

template<>
  struct coordinate_traits<long, sizeof(long) == sizeof(int)> {
    typedef coordinate_traits<int> cT_;
    typedef cT_::coordinate_type coordinate_type;
    typedef cT_::area_type area_type;
    typedef cT_::manhattan_area_type manhattan_area_type;
    typedef cT_::unsigned_area_type unsigned_area_type;
    typedef cT_::coordinate_difference coordinate_difference;
    typedef cT_::coordinate_distance coordinate_distance;
  };

#ifdef BOOST_POLYGON_USE_LONG_LONG
  template <>
  struct coordinate_traits<polygon_long_long_type> {
    typedef polygon_long_long_type coordinate_type;
    typedef long double area_type;
    typedef polygon_long_long_type manhattan_area_type;
    typedef polygon_ulong_long_type unsigned_area_type;
    typedef polygon_long_long_type coordinate_difference;
    typedef long double coordinate_distance;
  };

template<>
  struct coordinate_traits<long, sizeof(long) == sizeof(polygon_long_long_type)> {
    typedef coordinate_traits<polygon_long_long_type> cT_;
    typedef cT_::coordinate_type coordinate_type;
    typedef cT_::area_type area_type;
    typedef cT_::manhattan_area_type manhattan_area_type;
    typedef cT_::unsigned_area_type unsigned_area_type;
    typedef cT_::coordinate_difference coordinate_difference;
    typedef cT_::coordinate_distance coordinate_distance;
  };
#endif

template <>
  struct coordinate_traits<float> {
    typedef float coordinate_type;
    typedef float area_type;
    typedef float manhattan_area_type;
    typedef float unsigned_area_type;
    typedef float coordinate_difference;
    typedef float coordinate_distance;
  };

template <>
  struct coordinate_traits<double> {
    typedef double coordinate_type;
    typedef double area_type;
    typedef double manhattan_area_type;
    typedef double unsigned_area_type;
    typedef double coordinate_difference;
    typedef double coordinate_distance;
  };

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

template <typename T>
  struct scaling_policy {
    template <typename T2>
    static inline T round(T2 t2) {
      return (T)std::floor(t2+0.5);
    }

static inline T round(T t2) {
      return t2;
    }
  };

struct coordinate_concept {};

template <>
  struct geometry_concept<int> { typedef coordinate_concept type; };
#ifdef BOOST_POLYGON_USE_LONG_LONG
  template <>
  struct geometry_concept<polygon_long_long_type> { typedef coordinate_concept type; };
#endif
  template <>
  struct geometry_concept<float> { typedef coordinate_concept type; };
  template <>
  struct geometry_concept<double> { typedef coordinate_concept type; };
  template <>
  struct geometry_concept<long double> { typedef coordinate_concept type; };

struct gtl_no { static const bool value = false; };
  struct gtl_yes { typedef gtl_yes type;
    static const bool value = true; };

template <bool T, bool T2>
  struct gtl_and_c { typedef gtl_no type; };
  template <>
  struct gtl_and_c<true, true> { typedef gtl_yes type; };

template <typename T, typename T2>
  struct gtl_and : gtl_and_c<T::value, T2::value> {};
  template <typename T, typename T2, typename T3>
  struct gtl_and_3 { typedef typename gtl_and<
                       T, typename gtl_and<T2, T3>::type>::type type; };

template <typename T, typename T2, typename T3, typename T4>
  struct gtl_and_4 { typedef typename gtl_and_3<
                       T, T2, typename gtl_and<T3, T4>::type>::type type; };
  template <typename T, typename T2>
  struct gtl_or { typedef gtl_yes type; };
  template <typename T>
  struct gtl_or<T, T> { typedef T type; };

template <typename T, typename T2, typename T3>
  struct gtl_or_3 { typedef typename gtl_or<
                      T, typename gtl_or<T2, T3>::type>::type type; };

template <typename T, typename T2, typename T3, typename T4>
  struct gtl_or_4 { typedef typename gtl_or<
                      T, typename gtl_or_3<T2, T3, T4>::type>::type type; };

template <typename T>
  struct gtl_not { typedef gtl_no type; };
  template <>
  struct gtl_not<gtl_no> { typedef gtl_yes type; };

template <typename T>
  struct gtl_if {
#ifdef BOOST_POLYGON_MSVC
    typedef gtl_no type;
#endif
  };
  template <>
  struct gtl_if<gtl_yes> { typedef gtl_yes type; };

template <typename T, typename T2>
  struct gtl_same_type { typedef gtl_no type; };
  template <typename T>
  struct gtl_same_type<T, T> { typedef gtl_yes type; };
  template <typename T, typename T2>
  struct gtl_different_type { typedef typename gtl_not<typename gtl_same_type<T, T2>::type>::type type; };

struct manhattan_domain {};
  struct forty_five_domain {};
  struct general_domain {};

template <typename T>
  struct geometry_domain { typedef general_domain type; };

template <typename domain_type, typename coordinate_type>
  struct area_type_by_domain { typedef typename coordinate_traits<coordinate_type>::area_type type; };
  template <typename coordinate_type>
  struct area_type_by_domain<manhattan_domain, coordinate_type> {
    typedef typename coordinate_traits<coordinate_type>::manhattan_area_type type; };

template<bool E, class R = void>
  struct enable_if_ {
      typedef R type;
  };

template<class R>
  struct enable_if_<false, R> { };

template<class E, class R = void>
  struct enable_if
      : enable_if_<E::value, R> { };

struct y_c_edist : gtl_yes {};

template <typename coordinate_type_1, typename coordinate_type_2>
    typename enable_if<
    typename gtl_and_3<y_c_edist, typename gtl_same_type<typename geometry_concept<coordinate_type_1>::type, coordinate_concept>::type,
                       typename gtl_same_type<typename geometry_concept<coordinate_type_1>::type, coordinate_concept>::type>::type,
    typename coordinate_traits<coordinate_type_1>::coordinate_difference>::type
  euclidean_distance(const coordinate_type_1& lvalue, const coordinate_type_2& rvalue) {
    typedef typename coordinate_traits<coordinate_type_1>::coordinate_difference Unit;
    return (lvalue < rvalue) ? (Unit)rvalue - (Unit)lvalue : (Unit)lvalue - (Unit)rvalue;
  }

// predicated_swap swaps a and b if pred is true

// predicated_swap is guarenteed to behave the same as
  // if(pred){
  //   T tmp = a;
  //   a = b;
  //   b = tmp;
  // }
  // but will not generate a branch instruction.
  // predicated_swap always creates a temp copy of a, but does not
  // create more than one temp copy of an input.
  // predicated_swap can be used to optimize away branch instructions in C++
  template <class T>
  inline bool predicated_swap(const bool& pred,
                              T& a,
                              T& b) {
    const T tmp = a;
    const T* input[2] = {&b, &tmp};
    a = *input[!pred];
    b = *input[pred];
    return pred;
  }

enum direction_1d_enum { LOW = 0, HIGH = 1,
                           LEFT = 0, RIGHT = 1,
                           CLOCKWISE = 0, COUNTERCLOCKWISE = 1,
                           REVERSE = 0, FORWARD = 1,
                           NEGATIVE = 0, POSITIVE = 1 };
  enum orientation_2d_enum { HORIZONTAL = 0, VERTICAL = 1 };
  enum direction_2d_enum { WEST = 0, EAST = 1, SOUTH = 2, NORTH = 3 };
  enum orientation_3d_enum { PROXIMAL = 2 };
  enum direction_3d_enum { DOWN = 4, UP = 5 };
  enum winding_direction {
    clockwise_winding = 0,
    counterclockwise_winding = 1,
    unknown_winding = 2
  };

class direction_2d;
  class direction_3d;
  class orientation_2d;

class direction_1d {
  private:
    unsigned int val_;
    explicit direction_1d(int d);
  public:
    inline direction_1d() : val_(LOW) {}
    inline direction_1d(const direction_1d& that) : val_(that.val_) {}
    inline direction_1d(const direction_1d_enum val) : val_(val) {}
    explicit inline direction_1d(const direction_2d& that);
    explicit inline direction_1d(const direction_3d& that);
    inline direction_1d& operator = (const direction_1d& d) {
      val_ = d.val_; return * this; }
    inline bool operator==(direction_1d d) const { return (val_ == d.val_); }
    inline bool operator!=(direction_1d d) const { return !((*this) == d); }
    inline unsigned int to_int(void) const { return val_; }
    inline direction_1d& backward() { val_ ^= 1; return *this; }
    inline int get_sign() const { return val_ * 2 - 1; }
  };

class direction_2d;

class orientation_2d {
  private:
    unsigned int val_;
    explicit inline orientation_2d(int o);
  public:
    inline orientation_2d() : val_(HORIZONTAL) {}
    inline orientation_2d(const orientation_2d& ori) : val_(ori.val_) {}
    inline orientation_2d(const orientation_2d_enum val) : val_(val) {}
    explicit inline orientation_2d(const direction_2d& that);
    inline orientation_2d& operator=(const orientation_2d& ori) {
      val_ = ori.val_; return * this; }
    inline bool operator==(orientation_2d that) const { return (val_ == that.val_); }
    inline bool operator!=(orientation_2d that) const { return (val_ != that.val_); }
    inline unsigned int to_int() const { return (val_); }
    inline void turn_90() { val_ = val_^ 1; }
    inline orientation_2d get_perpendicular() const {
      orientation_2d retval = *this;
      retval.turn_90();
      return retval;
    }
    inline direction_2d get_direction(direction_1d dir) const;
  };

class direction_2d {
  private:
    int val_;

public:

inline direction_2d() : val_(WEST) {}

inline direction_2d(const direction_2d& that) : val_(that.val_) {}

inline direction_2d(const direction_2d_enum val) : val_(val) {}

inline direction_2d& operator=(const direction_2d& d) {
      val_ = d.val_;
      return * this;
    }

inline ~direction_2d() { }

inline bool operator==(direction_2d d) const { return (val_ == d.val_); }
    inline bool operator!=(direction_2d d) const { return !((*this) == d); }
    inline bool operator< (direction_2d d) const { return (val_ < d.val_); }
    inline bool operator<=(direction_2d d) const { return (val_ <= d.val_); }
    inline bool operator> (direction_2d d) const { return (val_ > d.val_); }
    inline bool operator>=(direction_2d d) const { return (val_ >= d.val_); }

// Casting to int
    inline unsigned int to_int(void) const { return val_; }

inline direction_2d backward() const {
      // flip the LSB, toggles 0 - 1   and 2 - 3
      return direction_2d(direction_2d_enum(val_ ^ 1));
    }

// Returns a direction 90 degree left (LOW) or right(HIGH) to this one
    inline direction_2d turn(direction_1d t) const {
      return direction_2d(direction_2d_enum(val_ ^ 3 ^ (val_ >> 1) ^ t.to_int()));
    }

// Returns a direction 90 degree left to this one
    inline direction_2d left() const {return turn(HIGH);}

// Returns a direction 90 degree right to this one
    inline direction_2d right() const {return turn(LOW);}

// N, E are positive, S, W are negative
    inline bool is_positive() const {return (val_ & 1);}
    inline bool is_negative() const {return !is_positive();}
    inline int get_sign() const {return ((is_positive()) << 1) -1;}

};

direction_1d::direction_1d(const direction_2d& that) : val_(that.to_int() & 1) {}

orientation_2d::orientation_2d(const direction_2d& that) : val_(that.to_int() >> 1) {}

direction_2d orientation_2d::get_direction(direction_1d dir) const {
    return direction_2d(direction_2d_enum((val_ << 1) + dir.to_int()));
  }

class orientation_3d {
  private:
    unsigned int val_;
    explicit inline orientation_3d(int o);
  public:
    inline orientation_3d() : val_((int)HORIZONTAL) {}
    inline orientation_3d(const orientation_3d& ori) : val_(ori.val_) {}
    inline orientation_3d(orientation_2d ori) : val_(ori.to_int()) {}
    inline orientation_3d(const orientation_3d_enum val) : val_(val) {}
    explicit inline orientation_3d(const direction_2d& that);
    explicit inline orientation_3d(const direction_3d& that);
    inline ~orientation_3d() {  }
    inline orientation_3d& operator=(const orientation_3d& ori) {
      val_ = ori.val_; return * this; }
    inline bool operator==(orientation_3d that) const { return (val_ == that.val_); }
    inline bool operator!=(orientation_3d that) const { return (val_ != that.val_); }
    inline unsigned int to_int() const { return (val_); }
    inline direction_3d get_direction(direction_1d dir) const;
  };

class direction_3d {
  private:
    int val_;

public:

inline direction_3d() : val_(WEST) {}

inline direction_3d(direction_2d that) : val_(that.to_int()) {}
    inline direction_3d(const direction_3d& that) : val_(that.val_) {}

inline direction_3d(const direction_2d_enum val) : val_(val) {}
    inline direction_3d(const direction_3d_enum val) : val_(val) {}

inline direction_3d& operator=(direction_3d d) {
      val_ = d.val_;
      return * this;
    }

inline ~direction_3d() { }

inline bool operator==(direction_3d d) const { return (val_ == d.val_); }
    inline bool operator!=(direction_3d d) const { return !((*this) == d); }
    inline bool operator< (direction_3d d) const { return (val_ < d.val_); }
    inline bool operator<=(direction_3d d) const { return (val_ <= d.val_); }
    inline bool operator> (direction_3d d) const { return (val_ > d.val_); }
    inline bool operator>=(direction_3d d) const { return (val_ >= d.val_); }

// Casting to int
    inline unsigned int to_int(void) const { return val_; }

inline direction_3d backward() const {
      // flip the LSB, toggles 0 - 1   and 2 - 3 and 4 - 5
      return direction_2d(direction_2d_enum(val_ ^ 1));
    }

// N, E, U are positive, S, W, D are negative
    inline bool is_positive() const {return (val_ & 1);}
    inline bool is_negative() const {return !is_positive();}
    inline int get_sign() const {return ((is_positive()) << 1) -1;}

};

direction_1d::direction_1d(const direction_3d& that) : val_(that.to_int() & 1) {}
  orientation_3d::orientation_3d(const direction_3d& that) : val_(that.to_int() >> 1) {}
  orientation_3d::orientation_3d(const direction_2d& that) : val_(that.to_int() >> 1) {}

direction_3d orientation_3d::get_direction(direction_1d dir) const {
    return direction_3d(direction_3d_enum((val_ << 1) + dir.to_int()));
  }

}
}
#endif

/* Copyright 2008 Intel Corporation Use, modification and distribution are subject to the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt). */ #ifndef BOOST_POLYGON_ISOTROPY_HPP #define BOOST_POLYGON_ISOTROPY_HPP //external #include #include #include #include #include #include #include #include //#include #include #include #include #include #ifndef BOOST_POLYGON_NO_DEPS #include #ifdef BOOST_MSVC #define BOOST_POLYGON_MSVC #endif #ifdef BOOST_INTEL #define BOOST_POLYGON_ICC #endif #ifdef BOOST_HAS_LONG_LONG #define BOOST_POLYGON_USE_LONG_LONG typedef boost::long_long_type polygon_long_long_type; typedef boost::ulong_long_type polygon_ulong_long_type; //typedef long long polygon_long_long_type; //typedef unsigned long long polygon_ulong_long_type; #endif #else #ifdef _WIN32 #define BOOST_POLYGON_MSVC #endif #ifdef __ICC #define BOOST_POLYGON_ICC #endif #define BOOST_POLYGON_USE_LONG_LONG typedef long long polygon_long_long_type; typedef unsigned long long polygon_ulong_long_type; #endif namespace boost { namespace polygon{ enum GEOMETRY_CONCEPT_ID { COORDINATE_CONCEPT, INTERVAL_CONCEPT, POINT_CONCEPT, POINT_3D_CONCEPT, RECTANGLE_CONCEPT, POLYGON_90_CONCEPT, POLYGON_90_WITH_HOLES_CONCEPT, POLYGON_45_CONCEPT, POLYGON_45_WITH_HOLES_CONCEPT, POLYGON_CONCEPT, POLYGON_WITH_HOLES_CONCEPT, POLYGON_90_SET_CONCEPT, POLYGON_45_SET_CONCEPT, POLYGON_SET_CONCEPT }; struct undefined_concept {}; template struct geometry_concept { typedef undefined_concept type; }; template struct view_of {}; template view_of view_as(const T2& obj) { return view_of(obj); } template struct coordinate_traits {}; //used to override long double with an infinite precision datatype template struct high_precision_type { typedef long double type; }; template T convert_high_precision_type(const typename high_precision_type::type& v) { return T(v); } //used to override std::sort with an alternative (parallel) algorithm template void polygon_sort(iter_type _b_, iter_type _e_); template void polygon_sort(iter_type _b_, iter_type _e_, const pred_type& _pred_); template <> struct coordinate_traits { typedef int coordinate_type; typedef long double area_type; #ifdef BOOST_POLYGON_USE_LONG_LONG typedef polygon_long_long_type manhattan_area_type; typedef polygon_ulong_long_type unsigned_area_type; typedef polygon_long_long_type coordinate_difference; #else typedef long manhattan_area_type; typedef unsigned long unsigned_area_type; typedef long coordinate_difference; #endif typedef long double coordinate_distance; }; template<> struct coordinate_traits { typedef coordinate_traits cT_; typedef cT_::coordinate_type coordinate_type; typedef cT_::area_type area_type; typedef cT_::manhattan_area_type manhattan_area_type; typedef cT_::unsigned_area_type unsigned_area_type; typedef cT_::coordinate_difference coordinate_difference; typedef cT_::coordinate_distance coordinate_distance; }; #ifdef BOOST_POLYGON_USE_LONG_LONG template <> struct coordinate_traits { typedef polygon_long_long_type coordinate_type; typedef long double area_type; typedef polygon_long_long_type manhattan_area_type; typedef polygon_ulong_long_type unsigned_area_type; typedef polygon_long_long_type coordinate_difference; typedef long double coordinate_distance; }; template<> struct coordinate_traits { typedef coordinate_traits cT_; typedef cT_::coordinate_type coordinate_type; typedef cT_::area_type area_type; typedef cT_::manhattan_area_type manhattan_area_type; typedef cT_::unsigned_area_type unsigned_area_type; typedef cT_::coordinate_difference coordinate_difference; typedef cT_::coordinate_distance coordinate_distance; }; #endif template <> struct coordinate_traits { typedef float coordinate_type; typedef float area_type; typedef float manhattan_area_type; typedef float unsigned_area_type; typedef float coordinate_difference; typedef float coordinate_distance; }; template <> struct coordinate_traits { typedef double coordinate_type; typedef double area_type; typedef double manhattan_area_type; typedef double unsigned_area_type; typedef double coordinate_difference; typedef double coordinate_distance; }; template <> struct coordinate_traits { typedef long double coordinate_type; typedef long double area_type; typedef long double manhattan_area_type; typedef long double unsigned_area_type; typedef long double coordinate_difference; typedef long double coordinate_distance; }; template struct scaling_policy { template static inline T round(T2 t2) { return (T)std::floor(t2+0.5); } static inline T round(T t2) { return t2; } }; struct coordinate_concept {}; template <> struct geometry_concept { typedef coordinate_concept type; }; #ifdef BOOST_POLYGON_USE_LONG_LONG template <> struct geometry_concept { typedef coordinate_concept type; }; #endif template <> struct geometry_concept { typedef coordinate_concept type; }; template <> struct geometry_concept { typedef coordinate_concept type; }; template <> struct geometry_concept { typedef coordinate_concept type; }; struct gtl_no { static const bool value = false; }; struct gtl_yes { typedef gtl_yes type; static const bool value = true; }; template struct gtl_and_c { typedef gtl_no type; }; template <> struct gtl_and_c { typedef gtl_yes type; }; template struct gtl_and : gtl_and_c {}; template struct gtl_and_3 { typedef typename gtl_and< T, typename gtl_and::type>::type type; }; template struct gtl_and_4 { typedef typename gtl_and_3< T, T2, typename gtl_and::type>::type type; }; template struct gtl_or { typedef gtl_yes type; }; template struct gtl_or { typedef T type; }; template struct gtl_or_3 { typedef typename gtl_or< T, typename gtl_or::type>::type type; }; template struct gtl_or_4 { typedef typename gtl_or< T, typename gtl_or_3::type>::type type; }; template struct gtl_not { typedef gtl_no type; }; template <> struct gtl_not { typedef gtl_yes type; }; template struct gtl_if { #ifdef BOOST_POLYGON_MSVC typedef gtl_no type; #endif }; template <> struct gtl_if { typedef gtl_yes type; }; template struct gtl_same_type { typedef gtl_no type; }; template struct gtl_same_type { typedef gtl_yes type; }; template struct gtl_different_type { typedef typename gtl_not::type>::type type; }; struct manhattan_domain {}; struct forty_five_domain {}; struct general_domain {}; template struct geometry_domain { typedef general_domain type; }; template struct area_type_by_domain { typedef typename coordinate_traits::area_type type; }; template struct area_type_by_domain { typedef typename coordinate_traits::manhattan_area_type type; }; template struct enable_if_ { typedef R type; }; template struct enable_if_ { }; template struct enable_if : enable_if_ { }; struct y_c_edist : gtl_yes {}; template typename enable_if< typename gtl_and_3::type, coordinate_concept>::type, typename gtl_same_type::type, coordinate_concept>::type>::type, typename coordinate_traits::coordinate_difference>::type euclidean_distance(const coordinate_type_1& lvalue, const coordinate_type_2& rvalue) { typedef typename coordinate_traits::coordinate_difference Unit; return (lvalue < rvalue) ? (Unit)rvalue - (Unit)lvalue : (Unit)lvalue - (Unit)rvalue; } // predicated_swap swaps a and b if pred is true // predicated_swap is guarenteed to behave the same as // if(pred){ // T tmp = a; // a = b; // b = tmp; // } // but will not generate a branch instruction. // predicated_swap always creates a temp copy of a, but does not // create more than one temp copy of an input. // predicated_swap can be used to optimize away branch instructions in C++ template inline bool predicated_swap(const bool& pred, T& a, T& b) { const T tmp = a; const T* input[2] = {&b, &tmp}; a = *input[!pred]; b = *input[pred]; return pred; } enum direction_1d_enum { LOW = 0, HIGH = 1, LEFT = 0, RIGHT = 1, CLOCKWISE = 0, COUNTERCLOCKWISE = 1, REVERSE = 0, FORWARD = 1, NEGATIVE = 0, POSITIVE = 1 }; enum orientation_2d_enum { HORIZONTAL = 0, VERTICAL = 1 }; enum direction_2d_enum { WEST = 0, EAST = 1, SOUTH = 2, NORTH = 3 }; enum orientation_3d_enum { PROXIMAL = 2 }; enum direction_3d_enum { DOWN = 4, UP = 5 }; enum winding_direction { clockwise_winding = 0, counterclockwise_winding = 1, unknown_winding = 2 }; class direction_2d; class direction_3d; class orientation_2d; class direction_1d { private: unsigned int val_; explicit direction_1d(int d); public: inline direction_1d() : val_(LOW) {} inline direction_1d(const direction_1d& that) : val_(that.val_) {} inline direction_1d(const direction_1d_enum val) : val_(val) {} explicit inline direction_1d(const direction_2d& that); explicit inline direction_1d(const direction_3d& that); inline direction_1d& operator = (const direction_1d& d) { val_ = d.val_; return * this; } inline bool operator==(direction_1d d) const { return (val_ == d.val_); } inline bool operator!=(direction_1d d) const { return !((*this) == d); } inline unsigned int to_int(void) const { return val_; } inline direction_1d& backward() { val_ ^= 1; return *this; } inline int get_sign() const { return val_ * 2 - 1; } }; class direction_2d; class orientation_2d { private: unsigned int val_; explicit inline orientation_2d(int o); public: inline orientation_2d() : val_(HORIZONTAL) {} inline orientation_2d(const orientation_2d& ori) : val_(ori.val_) {} inline orientation_2d(const orientation_2d_enum val) : val_(val) {} explicit inline orientation_2d(const direction_2d& that); inline orientation_2d& operator=(const orientation_2d& ori) { val_ = ori.val_; return * this; } inline bool operator==(orientation_2d that) const { return (val_ == that.val_); } inline bool operator!=(orientation_2d that) const { return (val_ != that.val_); } inline unsigned int to_int() const { return (val_); } inline void turn_90() { val_ = val_^ 1; } inline orientation_2d get_perpendicular() const { orientation_2d retval = *this; retval.turn_90(); return retval; } inline direction_2d get_direction(direction_1d dir) const; }; class direction_2d { private: int val_; public: inline direction_2d() : val_(WEST) {} inline direction_2d(const direction_2d& that) : val_(that.val_) {} inline direction_2d(const direction_2d_enum val) : val_(val) {} inline direction_2d& operator=(const direction_2d& d) { val_ = d.val_; return * this; } inline ~direction_2d() { } inline bool operator==(direction_2d d) const { return (val_ == d.val_); } inline bool operator!=(direction_2d d) const { return !((*this) == d); } inline bool operator< (direction_2d d) const { return (val_ < d.val_); } inline bool operator<=(direction_2d d) const { return (val_ <= d.val_); } inline bool operator> (direction_2d d) const { return (val_ > d.val_); } inline bool operator>=(direction_2d d) const { return (val_ >= d.val_); } // Casting to int inline unsigned int to_int(void) const { return val_; } inline direction_2d backward() const { // flip the LSB, toggles 0 - 1 and 2 - 3 return direction_2d(direction_2d_enum(val_ ^ 1)); } // Returns a direction 90 degree left (LOW) or right(HIGH) to this one inline direction_2d turn(direction_1d t) const { return direction_2d(direction_2d_enum(val_ ^ 3 ^ (val_ >> 1) ^ t.to_int())); } // Returns a direction 90 degree left to this one inline direction_2d left() const {return turn(HIGH);} // Returns a direction 90 degree right to this one inline direction_2d right() const {return turn(LOW);} // N, E are positive, S, W are negative inline bool is_positive() const {return (val_ & 1);} inline bool is_negative() const {return !is_positive();} inline int get_sign() const {return ((is_positive()) << 1) -1;} }; direction_1d::direction_1d(const direction_2d& that) : val_(that.to_int() & 1) {} orientation_2d::orientation_2d(const direction_2d& that) : val_(that.to_int() >> 1) {} direction_2d orientation_2d::get_direction(direction_1d dir) const { return direction_2d(direction_2d_enum((val_ << 1) + dir.to_int())); } class orientation_3d { private: unsigned int val_; explicit inline orientation_3d(int o); public: inline orientation_3d() : val_((int)HORIZONTAL) {} inline orientation_3d(const orientation_3d& ori) : val_(ori.val_) {} inline orientation_3d(orientation_2d ori) : val_(ori.to_int()) {} inline orientation_3d(const orientation_3d_enum val) : val_(val) {} explicit inline orientation_3d(const direction_2d& that); explicit inline orientation_3d(const direction_3d& that); inline ~orientation_3d() { } inline orientation_3d& operator=(const orientation_3d& ori) { val_ = ori.val_; return * this; } inline bool operator==(orientation_3d that) const { return (val_ == that.val_); } inline bool operator!=(orientation_3d that) const { return (val_ != that.val_); } inline unsigned int to_int() const { return (val_); } inline direction_3d get_direction(direction_1d dir) const; }; class direction_3d { private: int val_; public: inline direction_3d() : val_(WEST) {} inline direction_3d(direction_2d that) : val_(that.to_int()) {} inline direction_3d(const direction_3d& that) : val_(that.val_) {} inline direction_3d(const direction_2d_enum val) : val_(val) {} inline direction_3d(const direction_3d_enum val) : val_(val) {} inline direction_3d& operator=(direction_3d d) { val_ = d.val_; return * this; } inline ~direction_3d() { } inline bool operator==(direction_3d d) const { return (val_ == d.val_); } inline bool operator!=(direction_3d d) const { return !((*this) == d); } inline bool operator< (direction_3d d) const { return (val_ < d.val_); } inline bool operator<=(direction_3d d) const { return (val_ <= d.val_); } inline bool operator> (direction_3d d) const { return (val_ > d.val_); } inline bool operator>=(direction_3d d) const { return (val_ >= d.val_); } // Casting to int inline unsigned int to_int(void) const { return val_; } inline direction_3d backward() const { // flip the LSB, toggles 0 - 1 and 2 - 3 and 4 - 5 return direction_2d(direction_2d_enum(val_ ^ 1)); } // N, E, U are positive, S, W, D are negative inline bool is_positive() const {return (val_ & 1);} inline bool is_negative() const {return !is_positive();} inline int get_sign() const {return ((is_positive()) << 1) -1;} }; direction_1d::direction_1d(const direction_3d& that) : val_(that.to_int() & 1) {} orientation_3d::orientation_3d(const direction_3d& that) : val_(that.to_int() >> 1) {} orientation_3d::orientation_3d(const direction_2d& that) : val_(that.to_int() >> 1) {} direction_3d orientation_3d::get_direction(direction_1d dir) const { return direction_3d(direction_3d_enum((val_ << 1) + dir.to_int())); } } } #endif