9 #ifndef _LIMBO_GEOMETRY_GEOMETRY_H
10 #define _LIMBO_GEOMETRY_GEOMETRY_H
41 HORIZONTAL_SLICING = 1,
53 switch (slicing_orient)
55 case HORIZONTAL_SLICING:
56 return "HORIZONTAL_SLICING";
57 case VERTICAL_SLICING:
58 return "VERTICAL_SLICING";
60 return "HOR_VER_SLICING";
62 return "HOR_VER_SA_SLICING";
64 return "HOR_VER_AR_SLICING";
145 template <
typename T>
153 typedef int coordinate_type;
154 typedef long area_type;
156 typedef long manhattan_area_type;
157 typedef unsigned long unsigned_area_type;
158 typedef long coordinate_difference;
160 typedef long coordinate_distance;
167 template <
typename Po
intType>
171 typedef PointType point_type;
172 typedef typename point_type::coordinate_type coordinate_type;
179 static coordinate_type
get(
const point_type& point,
orientation_2d const& orient)
180 {
return point.
get(orient);}
186 {point.set(orient, value);}
191 static point_type
construct(coordinate_type
const& x, coordinate_type
const& y)
192 {
return point_type(x, y);}
198 template <
typename RectType>
202 typedef RectType rectangle_type;
203 typedef typename rectangle_type::coordinate_type coordinate_type;
210 static inline coordinate_type
get(rectangle_type
const& rectangle,
direction_2d const& direct)
211 {
return rectangle.
get(direct);}
216 static inline void set(rectangle_type& rectangle,
direction_2d const& direct, coordinate_type
const& v)
217 {rectangle.set(direct, v);}
221 static inline rectangle_type
construct(coordinate_type
const& xl, coordinate_type
const& yl,
222 coordinate_type
const& xh, coordinate_type
const& yh)
223 {
return rectangle_type(xl, yl, xh, yh);}
227 template <
typename PolygonType>
229 struct polygon_90_traits
231 typedef PolygonType polygon_type;
232 typedef typename polygon_type::point_type point_type;
233 typedef typename point_type::coordinate_type coordinate_type;
234 typedef typename polygon_type::vertex_iterator_type vertex_iterator_type;
237 static inline vertex_iterator_type begin_vertex(polygon_type
const& p)
238 {
return p.begin_vertex();}
241 static inline vertex_iterator_type end_vertex(polygon_type
const& p)
242 {
return p.end_vertex();}
246 {
return UNKNOWN_WINDING;}
253 template <
typename ContainerType>
257 typedef ContainerType container_type;
258 typedef typename container_type::value_type value_type;
259 typedef typename container_type::const_iterator const_iterator_type;
260 typedef typename container_type::iterator iterator_type;
264 static void insert(container_type& container, value_type
const& v) {container.insert(v);}
266 static void insert(container_type& container, iterator_type it, value_type
const& v) {container.insert(it, v);}
268 static void erase(container_type& container, value_type
const& v) {container.erase(v);}
270 static void erase(container_type& container, iterator_type it) {container.erase(it);}
272 template <
typename Po
intCompareType>
273 static container_type
construct(PointCompareType
const& comp)
274 {
return container_type(comp);}
279 template <
typename T>
283 typedef std::vector<T> container_type;
284 typedef typename container_type::value_type value_type;
285 typedef typename container_type::const_iterator const_iterator_type;
286 typedef typename container_type::iterator iterator_type;
290 static void insert(container_type& container, value_type
const& v) {container.push_back(v);}
292 static void insert(container_type& container, iterator_type it, value_type
const& v) {container.insert(it, v);}
294 static void erase(container_type& container, iterator_type it) {container.erase(it);}
297 template <
typename Po
intCompareType>
298 static container_type
construct(PointCompareType
const&)
299 {
return container_type();}
303 template <
typename T>
307 typedef std::list<T> container_type;
308 typedef typename container_type::value_type value_type;
309 typedef typename container_type::const_iterator const_iterator_type;
310 typedef typename container_type::iterator iterator_type;
314 static void insert(container_type& container, value_type
const& v) {container.push_back(v);}
316 static void insert(container_type& container, iterator_type it, value_type
const& v) {container.insert(it, v);}
318 static void erase(container_type& container, iterator_type it) {container.erase(it);}
321 template <
typename Po
intCompareType>
322 static container_type
construct(PointCompareType
const&)
323 {
return container_type();}
328 template <
typename Po
intSet>
329 inline coordinate_traits<typename point_traits<typename container_traits<PointSet>::value_type>::area_type>
332 typedef typename container_traits<PointSet>::const_iterator_type const_iterator_type;
333 typedef typename container_traits<PointSet>::value_type point_type;
334 typedef typename point_traits<point_type>::coordinate_type coordinate_type;
338 for (const_iterator_type itCur = vPoint.begin(); itCur != vPoint.end(); ++itCur)
340 const_iterator_type itNext = itCur;
342 if (itNext == vPoint.end()) itNext = vPoint.begin();
static rectangle_type construct(coordinate_type const &xl, coordinate_type const &yl, coordinate_type const &xh, coordinate_type const &yh)
construct rectangle from coordinates
static coordinate_type get(const point_type &point, orientation_2d const &orient)
get coordinate from point
int to_int() const
convert orientation to integer
static point_type construct(coordinate_type const &x, coordinate_type const &y)
construct point from coordinates
static void set(rectangle_type &rectangle, direction_2d const &direct, coordinate_type const &v)
set coordinate for rectangle
void turn_90()
turn 90 degree
int m_orient
enum type of orientation in integer representation
bool valid() const
check whether the orientation is valid
static void insert(container_type &container, value_type const &v)
insert value to container
static void set(point_type &point, orientation_2d const &orient, coordinate_type const &value)
set coordinate for point
static void erase(container_type &container, iterator_type it)
erase an element from container with iterator
direction_2d
direction type for rectangles
horizontal/vertical slicing and choose rectangle with smaller area every time
orientation_2d_enum
orientation type for lines
static void insert(container_type &container, iterator_type it, value_type const &v)
insert value to container with hint of iterator
static container_type construct(PointCompareType const &comp)
a default construct function is necessary, because std::set needs a compare function, but vector does not
bool operator!=(orientation_2d const &rhs) const
inequality operator
orientation_2d()
constructor
bool operator==(orientation_2d const &rhs) const
equality operator
slicing_orientation_2d
orientation type for slicing
type traits for containers such as vector, list, multiset
static void erase(container_type &container, iterator_type it)
erase an element from container with iterator
winding_direction
winding direction type CLOCKWISE and COUNTERCLOCKWISE refers to winding direction of a polygon ...
coordinate_traits< typename point_traits< typename container_traits< PointSet >::value_type >::area_type > area(PointSet const &vPoint)
calculate signed area of a polygon, the result is positive if its winding is CLOCKWISE ...
static container_type construct(PointCompareType const &)
a default construct function
static coordinate_type get(rectangle_type const &rectangle, direction_2d const &direct)
get coordinate from rectangle
horizontal/vertical slicing and choose rectangle with better aspect ratio every time ...
std::string to_string(slicing_orientation_2d slicing_orient)
convert enum type of slicing orientation to string
orientation_2d get_perpendicular() const
get perpendicular orientation
orientation_2d(const orientation_2d &ori)
copy constructor
type traits for rectangle
static void insert(container_type &container, iterator_type it, value_type const &v)
insert value to container with hint of iterator
friend bool operator<(orientation_2d const &ori1, orientation_2d const &ori2)
less than operator
type traits for coordinates
static container_type construct(PointCompareType const &)
a default construct function
static void erase(container_type &container, iterator_type it)
erase an element from container with iterator
orientation_2d(orientation_2d_enum const &ori)
constructor
static void insert(container_type &container, value_type const &v)
insert value to container
static void insert(container_type &container, value_type const &v)
endnowarn
horizontal/vertical slicing and choose rectangle with larger area every time
static void erase(container_type &container, value_type const &v)
erase value from iterator
orientation_2d & operator=(const orientation_2d &ori)
assignment
a class denoting orientation of lines
static void insert(container_type &container, iterator_type it, value_type const &v)
insert value to container with hint of iterator