Date view Thread view Subject view Author view

From: lucanus.j.simonson_at_[hidden]
Date: 2008-06-03 19:56:59

Author: ljsimons
Date: 2008-06-03 19:56:56 EDT (Tue, 03 Jun 2008)
New Revision: 46107
URL: http://svn.boost.org/trac/boost/changeset/46107

Log:
adding 45 and aribtrary angle polygons, fleshing out API for basic types
Added:
   sandbox/gtl/gtl/geometry_concept.hpp
      - copied, changed from r45926, /sandbox/gtl/gtl/geometry_traits.hpp
   sandbox/gtl/gtl/polygon_45_concept.hpp (contents, props changed)
   sandbox/gtl/gtl/polygon_45_data.hpp (contents, props changed)
   sandbox/gtl/gtl/polygon_45_with_holes_concept.hpp (contents, props changed)
   sandbox/gtl/gtl/polygon_45_with_holes_data.hpp (contents, props changed)
   sandbox/gtl/gtl/polygon_90_concept.hpp (contents, props changed)
   sandbox/gtl/gtl/polygon_90_data.hpp (contents, props changed)
   sandbox/gtl/gtl/polygon_90_with_holes_concept.hpp (contents, props changed)
   sandbox/gtl/gtl/polygon_90_with_holes_data.hpp (contents, props changed)
Removed:
   sandbox/gtl/gtl/geometry_traits.hpp
Text files modified:
   sandbox/gtl/gtl/geometry_concept.hpp | 146 ++++------
   sandbox/gtl/gtl/gtl.hpp | 437 ++++++++++++++++++++++++++++++---
   sandbox/gtl/gtl/interval_concept.hpp | 290 ++++++++++++++++++++++
   sandbox/gtl/gtl/isotropy.hpp | 14
   sandbox/gtl/gtl/iterator_compact_to_points.hpp | 6
   sandbox/gtl/gtl/iterator_geometry_to_set.hpp | 43 +-
   sandbox/gtl/gtl/iterator_points_to_compact.hpp | 8
   sandbox/gtl/gtl/point_3d_concept.hpp | 2
   sandbox/gtl/gtl/point_concept.hpp | 7
   sandbox/gtl/gtl/point_data.hpp | 5
   sandbox/gtl/gtl/polygon_concept.hpp | 315 ------------------------
   sandbox/gtl/gtl/polygon_data.hpp | 44 ---
   sandbox/gtl/gtl/polygon_formation.hpp | 26 +
   sandbox/gtl/gtl/polygon_set_wrapper.hpp | 12
   sandbox/gtl/gtl/polygon_traits.hpp | 22 +
   sandbox/gtl/gtl/polygon_with_holes_concept.hpp | 177 -------------
   sandbox/gtl/gtl/polygon_with_holes_data.hpp | 74 -----
   sandbox/gtl/gtl/polygon_with_holes_traits.hpp | 3
   sandbox/gtl/gtl/post_concept_definitions.hpp | 10
   sandbox/gtl/gtl/post_geometry_traits_definitions.hpp | 14 +
   sandbox/gtl/gtl/rectangle_concept.hpp | 517 +++++++++++++++++++++++++++++++++++++++
   sandbox/gtl/gtl/rectangle_data.hpp | 10
   22 files changed, 1391 insertions(+), 791 deletions(-)

Copied: sandbox/gtl/gtl/geometry_concept.hpp (from r45926, /sandbox/gtl/gtl/geometry_traits.hpp)
==============================================================================
--- /sandbox/gtl/gtl/geometry_traits.hpp (original)
+++ sandbox/gtl/gtl/geometry_concept.hpp 2008-06-03 19:56:56 EDT (Tue, 03 Jun 2008)
@@ -5,91 +5,71 @@
   Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   http://www.boost.org/LICENSE_1_0.txt).
 */
-struct no_type {};
 
 template <typename T>
-struct geometry_traits {
- typedef no_type geometry_concept;
+struct geometry_concept {
+ typedef no_type type;
 };
 
-template <>
-struct geometry_traits<point_data<int> > {
- typedef point_concept geometry_concept;
-};
-template <>
-struct geometry_traits<point_data<long long> > {
- typedef point_concept geometry_concept;
-};
-template <>
-struct geometry_traits<rectangle_data<int> > {
- typedef rectangle_concept geometry_concept;
-};
-template <>
-struct geometry_traits<rectangle_data<long long> > {
- typedef rectangle_concept geometry_concept;
-};
-template <>
-struct geometry_traits<interval_data<int> > {
- typedef interval_concept geometry_concept;
-};
-template <>
-struct geometry_traits<interval_data<long long> > {
- typedef interval_concept geometry_concept;
-};
-template <>
-struct geometry_traits<point_3d_data<int> > {
- typedef point_3d_concept geometry_concept;
-};
-template <>
-struct geometry_traits<point_3d_data<long long> > {
- typedef point_3d_concept geometry_concept;
-};
-template <>
-struct geometry_traits<polygon_data<int> > {
- typedef polygon_concept geometry_concept;
-};
-template <>
-struct geometry_traits<polygon_data<long long> > {
- typedef polygon_concept geometry_concept;
-};
-template <>
-struct geometry_traits<polygon_with_holes_data<int> > {
- typedef polygon_with_holes_concept geometry_concept;
-};
-template <>
-struct geometry_traits<polygon_with_holes_data<long long> > {
- typedef polygon_with_holes_concept geometry_concept;
-};
-template<>
-struct geometry_traits<polygon_formation::PolyLinePolygonData<true, int> > {
- typedef polygon_with_holes_concept geometry_concept;
-};
-template<>
-struct geometry_traits<polygon_formation::PolyLinePolygonData<false, int> > {
- typedef polygon_with_holes_concept geometry_concept;
-};
-template<>
-struct geometry_traits<polygon_formation::PolyLinePolygonData<true, long long> > {
- typedef polygon_with_holes_concept geometry_concept;
-};
-template<>
-struct geometry_traits<polygon_formation::PolyLinePolygonData<false, long long> > {
- typedef polygon_with_holes_concept geometry_concept;
-};
-template <>
-struct geometry_traits<polygon_formation::PolyLineHoleData<true, int> > {
- typedef polygon_concept geometry_concept;
-};
-template <>
-struct geometry_traits<polygon_formation::PolyLineHoleData<false, int> > {
- typedef polygon_concept geometry_concept;
-};
-template <>
-struct geometry_traits<polygon_formation::PolyLineHoleData<true, long long> > {
- typedef polygon_concept geometry_concept;
-};
-template <>
-struct geometry_traits<polygon_formation::PolyLineHoleData<false, long long> > {
- typedef polygon_concept geometry_concept;
-};
+#define GTL_REGISTER_GEOMETRY_TRAITS(coordinate_type) \
+template <>\
+struct geometry_concept<point_data<coordinate_type> > {\
+ typedef point_concept type;\
+};\
+template <>\
+struct geometry_concept<rectangle_data<coordinate_type> > {\
+ typedef rectangle_concept type;\
+};\
+template <>\
+struct geometry_concept<interval_data<coordinate_type> > {\
+ typedef interval_concept type;\
+};\
+template <>\
+struct geometry_concept<point_3d_data<coordinate_type> > {\
+ typedef point_3d_concept type;\
+};\
+template <>\
+struct geometry_concept<polygon_90_data<coordinate_type> > {\
+ typedef polygon_90_concept type;\
+};\
+template <>\
+struct geometry_concept<polygon_90_with_holes_data<coordinate_type> > {\
+ typedef polygon_90_with_holes_concept type;\
+};\
+template<>\
+struct geometry_concept<polygon_formation::PolyLinePolygonData<true, coordinate_type> > {\
+ typedef polygon_90_with_holes_concept type;\
+};\
+template<>\
+struct geometry_concept<polygon_formation::PolyLinePolygonData<false, coordinate_type> > {\
+ typedef polygon_90_with_holes_concept type;\
+};\
+template <>\
+struct geometry_concept<polygon_formation::PolyLineHoleData<true, coordinate_type> > {\
+ typedef polygon_90_concept type;\
+};\
+template <>\
+struct geometry_concept<polygon_formation::PolyLineHoleData<false, coordinate_type> > {\
+ typedef polygon_90_concept type;\
+};\
+template <>\
+struct geometry_concept<polygon_45_data<coordinate_type> > {\
+ typedef polygon_45_concept type;\
+};\
+template <>\
+struct geometry_concept<polygon_45_with_holes_data<coordinate_type> > {\
+ typedef polygon_45_with_holes_concept type;\
+};\
+template <>\
+struct geometry_concept<polygon_data<coordinate_type> > {\
+ typedef polygon_concept type;\
+};\
+template <>\
+struct geometry_concept<polygon_with_holes_data<coordinate_type> > {\
+ typedef polygon_with_holes_concept type;\
+};\
+
+//end of GTL_REGISTER_GEOMETRY_TRAITS macro
 
+GTL_REGISTER_GEOMETRY_TRAITS(int)
+GTL_REGISTER_GEOMETRY_TRAITS(long long)

Deleted: sandbox/gtl/gtl/geometry_traits.hpp
==============================================================================
--- sandbox/gtl/gtl/geometry_traits.hpp 2008-06-03 19:56:56 EDT (Tue, 03 Jun 2008)
+++ (empty file)
@@ -1,95 +0,0 @@
-/*
- 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).
-*/
-struct no_type {};
-
-template <typename T>
-struct geometry_traits {
- typedef no_type geometry_concept;
-};
-
-template <>
-struct geometry_traits<point_data<int> > {
- typedef point_concept geometry_concept;
-};
-template <>
-struct geometry_traits<point_data<long long> > {
- typedef point_concept geometry_concept;
-};
-template <>
-struct geometry_traits<rectangle_data<int> > {
- typedef rectangle_concept geometry_concept;
-};
-template <>
-struct geometry_traits<rectangle_data<long long> > {
- typedef rectangle_concept geometry_concept;
-};
-template <>
-struct geometry_traits<interval_data<int> > {
- typedef interval_concept geometry_concept;
-};
-template <>
-struct geometry_traits<interval_data<long long> > {
- typedef interval_concept geometry_concept;
-};
-template <>
-struct geometry_traits<point_3d_data<int> > {
- typedef point_3d_concept geometry_concept;
-};
-template <>
-struct geometry_traits<point_3d_data<long long> > {
- typedef point_3d_concept geometry_concept;
-};
-template <>
-struct geometry_traits<polygon_data<int> > {
- typedef polygon_concept geometry_concept;
-};
-template <>
-struct geometry_traits<polygon_data<long long> > {
- typedef polygon_concept geometry_concept;
-};
-template <>
-struct geometry_traits<polygon_with_holes_data<int> > {
- typedef polygon_with_holes_concept geometry_concept;
-};
-template <>
-struct geometry_traits<polygon_with_holes_data<long long> > {
- typedef polygon_with_holes_concept geometry_concept;
-};
-template<>
-struct geometry_traits<polygon_formation::PolyLinePolygonData<true, int> > {
- typedef polygon_with_holes_concept geometry_concept;
-};
-template<>
-struct geometry_traits<polygon_formation::PolyLinePolygonData<false, int> > {
- typedef polygon_with_holes_concept geometry_concept;
-};
-template<>
-struct geometry_traits<polygon_formation::PolyLinePolygonData<true, long long> > {
- typedef polygon_with_holes_concept geometry_concept;
-};
-template<>
-struct geometry_traits<polygon_formation::PolyLinePolygonData<false, long long> > {
- typedef polygon_with_holes_concept geometry_concept;
-};
-template <>
-struct geometry_traits<polygon_formation::PolyLineHoleData<true, int> > {
- typedef polygon_concept geometry_concept;
-};
-template <>
-struct geometry_traits<polygon_formation::PolyLineHoleData<false, int> > {
- typedef polygon_concept geometry_concept;
-};
-template <>
-struct geometry_traits<polygon_formation::PolyLineHoleData<true, long long> > {
- typedef polygon_concept geometry_concept;
-};
-template <>
-struct geometry_traits<polygon_formation::PolyLineHoleData<false, long long> > {
- typedef polygon_concept geometry_concept;
-};
-

Modified: sandbox/gtl/gtl/gtl.hpp
==============================================================================
--- sandbox/gtl/gtl/gtl.hpp (original)
+++ sandbox/gtl/gtl/gtl.hpp 2008-06-03 19:56:56 EDT (Tue, 03 Jun 2008)
@@ -17,95 +17,438 @@
 #include <iterator>
 
 //isotropy types
-#include "isotropy.h"
+#include "isotropy.hpp"
 
 //data types
-#include "point_data.h"
-#include "interval_data.h"
-#include "rectangle_data.h"
-#include "point_3d_data.h"
-#include "polygon_data.h"
-#include "polygon_with_holes_data.h"
+#include "point_data.hpp"
+#include "interval_data.hpp"
+#include "rectangle_data.hpp"
+#include "point_3d_data.hpp"
 
 //traits types
-#include "point_traits.h"
-#include "interval_traits.h"
-#include "rectangle_traits.h"
-#include "point_3d_traits.h"
-#include "polygon_traits.h"
-#include "polygon_with_holes_traits.h"
+#include "point_traits.hpp"
+#include "interval_traits.hpp"
+#include "rectangle_traits.hpp"
+#include "point_3d_traits.hpp"
+#include "polygon_traits.hpp"
+#include "polygon_with_holes_traits.hpp"
 
 //concept types
-#include "point_concept.h"
-#include "interval_concept.h"
-#include "rectangle_concept.h"
-#include "point_3d_concept.h"
-
-//algorithms needed by polygon concepts
-#include "iterator_points_to_compact.h"
-#include "iterator_compact_to_points.h"
+#include "point_concept.hpp"
+#include "interval_concept.hpp"
+#include "rectangle_concept.hpp"
+#include "point_3d_concept.hpp"
+
+//algorithms needed by polygon types
+#include "iterator_points_to_compact.hpp"
+#include "iterator_compact_to_points.hpp"
+
+#include "polygon_90_data.hpp"
+#include "polygon_90_with_holes_data.hpp"
+#include "polygon_45_data.hpp"
+#include "polygon_45_with_holes_data.hpp"
+#include "polygon_data.hpp"
+#include "polygon_with_holes_data.hpp"
 
 //polygon concept types
-#include "polygon_concept.h"
-#include "polygon_with_holes_concept.h"
+#include "polygon_90_concept.hpp"
+#include "polygon_90_with_holes_concept.hpp"
+#include "polygon_45_concept.hpp"
+#include "polygon_45_with_holes_concept.hpp"
+#include "polygon_concept.hpp"
+#include "polygon_with_holes_concept.hpp"
 
 //definitions
-#include "post_concept_definitions.h"
+#include "post_concept_definitions.hpp"
 
 //manhattan boolean op algorithms
-#include "boolean_op.h"
-#include "polygon_formation.h"
-#include "rectangle_formation.h"
-#include "iterator_vertex_orient_conversion.h"
-#include "iterator_geometry_to_set.h"
+#include "boolean_op.hpp"
+#include "polygon_formation.hpp"
+#include "rectangle_formation.hpp"
+#include "iterator_vertex_orient_conversion.hpp"
+#include "iterator_geometry_to_set.hpp"
 
 //polygon set data types
-#include "polygon_set_data.h"
+#include "polygon_set_data.hpp"
 //polygon set trait types
-#include "polygon_set_traits.h"
+#include "polygon_set_traits.hpp"
 //polygon set concepts
-#include "polygon_set_view.h"
+#include "polygon_set_view.hpp"
 //geometry traits
-#include "geometry_traits.h"
+#include "geometry_concept.hpp"
 
-#include "polygon_set_wrapper.h"
+#include "polygon_set_wrapper.hpp"
 
 //defintions
-#include "post_geometry_traits_definitions.h"
+#include "post_geometry_traits_definitions.hpp"
 
 
+//immutable unary functions
 
+//accepts: point rectangle point_3d prism
+template <typename geometry_type>
+typename component_type<geometry_type>::type
+get(const geometry_type& geometry_object, orientation_2d orient) {
+ return geometry_concept<geometry_type>::type::get(geometry_object, orient);
+}
+
+//accepts: point_3d prism
+template <typename geometry_type>
+typename component_type<geometry_type>::type
+get(const geometry_type& geometry_object, orientation_3d orient) {
+ return geometry_concept<geometry_type>::type::get(geometry_object, orient);
+}
+
+//accepts: interval
+template <typename geometry_type>
+typename component_type<geometry_type>::type
+get(const geometry_type& geometry_object, direction_1d dir) {
+ return geometry_concept<geometry_type>::type::get(geometry_object, dir);
+}
+
+//accepts: interval
+template <typename geometry_type>
+typename component_type<geometry_type>::type
+high(const geometry_type& geometry_object) {
+ return geometry_concept<geometry_type>::type::high(geometry_object);
+}
+
+//accepts: interval
+template <typename geometry_type>
+typename component_type<geometry_type>::type
+low(const geometry_type& geometry_object) {
+ return geometry_concept<geometry_type>::type::low(geometry_object);
+}
+
+//accepts: rectangle prism
+template <typename geometry_type>
+typename component_type<geometry_type>::type
+horizontal(const geometry_type& geometry_object) {
+ return geometry_concept<geometry_type>::type::horizontal(geometry_object);
+}
+
+//accepts: rectangle prism
+template <typename geometry_type>
+typename component_type<geometry_type>::type
+vertical(const geometry_type& geometry_object) {
+ return geometry_concept<geometry_type>::type::vertical(geometry_object);
+}
+
+//accepts: rectangle prism
+template <typename geometry_type>
+typename coordinate_type<geometry_type>::type
+xl(const geometry_type& geometry_object) {
+ return geometry_concept<geometry_type>::type::xl(geometry_object);
+}
+
+//accepts: rectangle prism
+template <typename geometry_type>
+typename coordinate_type<geometry_type>::type
+yl(const geometry_type& geometry_object) {
+ return geometry_concept<geometry_type>::type::yl(geometry_object);
+}
+
+//accepts: rectangle prism
+template <typename geometry_type>
+typename coordinate_type<geometry_type>::type
+xh(const geometry_type& geometry_object) {
+ return geometry_concept<geometry_type>::type::xh(geometry_object);
+}
+
+//accepts: rectangle prism
+template <typename geometry_type>
+typename coordinate_type<geometry_type>::type
+yh(const geometry_type& geometry_object) {
+ return geometry_concept<geometry_type>::type::yh(geometry_object);
+}
+
+//accepts: interval
+template <typename geometry_type>
+typename center_type<geometry_type>::type
+center(const geometry_type& geometry_object) {
+ return geometry_concept<geometry_type>::type::center(geometry_object);
+}
+
+//accepts: interval
+template <typename geometry_type>
+typename coordinate_type<geometry_type>::type
+delta(const geometry_type& geometry_object) {
+ return geometry_concept<geometry_type>::type::delta(geometry_object);
+}
+
+//accepts: rectangle prism
+template <typename geometry_type>
+typename coordinate_type<geometry_type>::type
+delta(const geometry_type& geometry_object, orientation_2d orient) {
+ return geometry_concept<geometry_type>::type::delta(geometry_object, orient);
+}
+
+//accepts: prism
+template <typename geometry_type>
+typename coordinate_type<geometry_type>::type
+delta(const geometry_type& geometry_object, orientation_3d orient) {
+ return geometry_concept<geometry_type>::type::delta(geometry_object, orient);
+}
+
+//accepts: rectangle, polygon
+template <typename geometry_type>
+typename coordinate_type<geometry_type>::type
+area(const geometry_type& geometry_object) {
+ return geometry_concept<geometry_type>::type::area(geometry_object);
+}
+
+//accepts: rectangle
+template <typename geometry_type>
+typename coordinate_type<geometry_type>::type
+half_perimeter(const geometry_type& geometry_object) {
+ return geometry_concept<geometry_type>::type::half_perimeter(geometry_object);
+}
+
+//accepts: rectangle
+template <typename geometry_type>
+typename coordinate_type<geometry_type>::type
+perimeter(const geometry_type& geometry_object) {
+ return geometry_concept<geometry_type>::type::perimeter(geometry_object);
+}
+
+template <typename geometry_type>
+orientation_2d guess_orientation(const geometry_type& geometry_object) {
+ return geometry_concept<geometry_type>::type::guess_orientation(geometry_object);
+}
+
+
+//mutable unary functions
+
+template <typename geometry_type>
+void set(geometry_type& geometry_object, direction_1d dir, typename component_type<geometry_type>::type value) {
+ geometry_concept<geometry_type>::type::set(geometry_object, dir, value);
+}
+
+//accepts: point,coordinate point_3d,coordinate rectangle,interval prism,interval
+template <typename geometry_type_1, typename geometry_type_2>
+void set(geometry_type_1& geometry_object, orientation_2d orient, const geometry_type_2& value) {
+ geometry_concept<geometry_type_1>::type::set(geometry_object, orient, value);
+}
+
+//accepts: point_3d,coordinate prism,interval
+template <typename geometry_type_1, typename geometry_type_2>
+void set(geometry_type_1& geometry_object, orientation_3d orient, const geometry_type_2& value) {
+ geometry_concept<geometry_type_1>::type::set(geometry_object, orient, value);
+}
+
+template <typename geometry_type, typename point_type_1, typename point_type_2>
+geometry_type& set_points(geometry_type& geometry_object, const point_type_1& point1, const point_type_2& point2) {
+ return geometry_concept<geometry_type>::type::set_points(geometry_object, point1, point2);
+}
+
+template <typename geometry_type>
+void high(geometry_type& geometry_object, typename component_type<geometry_type>::type value) {
+ geometry_concept<geometry_type>::type::high(geometry_object, value);
+}
+
+template <typename geometry_type>
+void low(geometry_type& geometry_object, typename component_type<geometry_type>::type value) {
+ geometry_concept<geometry_type>::type::low(geometry_object, value);
+}
+
+//accepts: rectangle prism
+template <typename geometry_type>
+void xl(geometry_type& geometry_object, typename coordinate_type<geometry_type>::type value) {
+ geometry_concept<geometry_type>::type::xl(geometry_object, value);
+}
+
+//accepts: rectangle prism
+template <typename geometry_type>
+void xh(geometry_type& geometry_object, typename coordinate_type<geometry_type>::type value) {
+ geometry_concept<geometry_type>::type::xh(geometry_object, value);
+}
+
+//accepts: rectangle prism
+template <typename geometry_type>
+void yl(geometry_type& geometry_object, typename coordinate_type<geometry_type>::type value) {
+ geometry_concept<geometry_type>::type::yl(geometry_object, value);
+}
+
+//accepts: rectangle prism
+template <typename geometry_type>
+void yh(geometry_type& geometry_object, typename coordinate_type<geometry_type>::type value) {
+ geometry_concept<geometry_type>::type::yh(geometry_object, value);
+}
+
+//accepts: rectangle prism
+template <typename geometry_type_1, typename geometry_type_2>
+void horizontal(geometry_type_1& geometry_object, const geometry_type_2& value) {
+ geometry_concept<geometry_type_1>::type::horizontal(geometry_object, value);
+}
+
+//accepts: rectangle prism
+template <typename geometry_type_1, typename geometry_type_2>
+void vertical(geometry_type_1& geometry_object, const geometry_type_2& value) {
+ geometry_concept<geometry_type_1>::type::vertical(geometry_object, value);
+}
+
+//immutable binary functions
 
 template <typename geometry_type_1, typename geometry_type_2>
 bool contains(const geometry_type_1& geometry_object, const geometry_type_2& contained_geometry_object,
               bool consider_touch = true) {
- return typename geometry_traits<geometry_type_1>::geometry_concept().contains(geometry_object, contained_geometry_object,
- consider_touch, typename geometry_traits<geometry_type_2>::geometry_concept());
+ return typename geometry_concept<geometry_type_1>::type().contains(geometry_object, contained_geometry_object,
+ consider_touch, typename geometry_concept<geometry_type_2>::type());
 }
 
 template <typename geometry_type_1, typename geometry_type_2>
 bool equivalence(const geometry_type_1& lvalue, const geometry_type_2& rvalue) {
- typename geometry_traits<geometry_type_1>::geometry_concept concept_instantiation;
+ typename geometry_concept<geometry_type_1>::type concept_instantiation;
   return concept_instantiation.equivalence(lvalue, rvalue);
 }
 
-template <typename geometry_type>
-typename component_type<geometry_type>::type
-get(const geometry_type& geometry_object, orientation_2d orient) {
- return geometry_traits<geometry_type>::geometry_concept::get(geometry_object, orient);
+template <typename geometry_type_1, typename geometry_type_2>
+bool intersects(geometry_type_1& lvalue, geometry_type_2& rvalue, bool consider_touch = true) {
+ return geometry_concept<geometry_type_1>::type::intersects(lvalue, rvalue, consider_touch, typename geometry_concept<geometry_type_2>::type());
+}
+
+template <typename geometry_type_1, typename geometry_type_2>
+bool boundaries_intersect(geometry_type_1& lvalue, const geometry_type_2& rvalue, bool consider_touch = true) {
+ return geometry_concept<geometry_type_1>::type::boundaries_intersect(lvalue, rvalue, consider_touch, typename geometry_concept<geometry_type_2>::type());
+}
+
+template <typename geometry_type_1, typename geometry_type_2>
+bool abuts(geometry_type_1& lvalue, const geometry_type_2& rvalue) {
+ return geometry_concept<geometry_type_1>::type::abuts(lvalue, rvalue, typename geometry_concept<geometry_type_2>::type());
+}
+
+template <typename geometry_type_1, typename geometry_type_2>
+bool abuts(geometry_type_1& lvalue, const geometry_type_2& rvalue, direction_1d dir) {
+ return geometry_concept<geometry_type_1>::type::abuts(lvalue, rvalue, dir, typename geometry_concept<geometry_type_2>::type());
 }
 
 template <typename geometry_type>
-typename component_type<geometry_type>::type
-get(const geometry_type& geometry_object, orientation_3d orient) {
- return geometry_traits<geometry_type>::geometry_concept::get(geometry_object, orient);
+geometry_type get_half(const geometry_type& geometry_object, direction_1d dir) {
+ return geometry_concept<geometry_type>::type::get_half(geometry_object, dir);
+}
+
+//mutable binary functions
+
+template <typename geometry_type_1, typename geometry_type_2>
+geometry_type_1& assign(geometry_type_1& lvalue, const geometry_type_2& rvalue) {
+ return geometry_concept<geometry_type_1>::type::assign(lvalue, rvalue);
+}
+
+template <typename geometry_type_1, typename geometry_type_2>
+geometry_type_1& convolve(geometry_type_1& lvalue, const geometry_type_2& rvalue) {
+ return geometry_concept<geometry_type_1>::type::convolve(lvalue, rvalue, typename geometry_concept<geometry_type_2>::type());
+}
+
+template <typename geometry_type_1, typename geometry_type_2>
+geometry_type_1& deconvolve(geometry_type_1& lvalue, const geometry_type_2& rvalue) {
+ return geometry_concept<geometry_type_1>::type::deconvolve(lvalue, rvalue, typename geometry_concept<geometry_type_2>::type());
+}
+
+template <typename geometry_type_1, typename geometry_type_2>
+geometry_type_1& reflected_convolve(geometry_type_1& lvalue, const geometry_type_2& rvalue) {
+ return geometry_concept<geometry_type_1>::type::reflected_convolve(lvalue, rvalue, typename geometry_concept<geometry_type_2>::type());
+}
+
+template <typename geometry_type_1, typename geometry_type_2>
+geometry_type_1& reflected_deconvolve(geometry_type_1& lvalue, const geometry_type_2& rvalue) {
+ return geometry_concept<geometry_type_1>::type::reflected_deconvolve(lvalue, rvalue, typename geometry_concept<geometry_type_2>::type());
+}
+
+template <typename geometry_type_1, typename geometry_type_2>
+typename coordinate_type<geometry_type_1>::type distance(geometry_type_1& lvalue, const geometry_type_2& rvalue) {
+ return geometry_concept<geometry_type_1>::type::distance(lvalue, rvalue, typename geometry_concept<geometry_type_2>::type());
+}
+
+template <typename geometry_type_1, typename geometry_type_2>
+bool encompass(geometry_type_1& lvalue, const geometry_type_2& rvalue) {
+ return geometry_concept<geometry_type_1>::type::encompass(lvalue, rvalue, typename geometry_concept<geometry_type_2>::type());
+}
+
+template <typename geometry_type_1, typename geometry_type_2>
+bool intersect(geometry_type_1& lvalue, geometry_type_2& rvalue, bool consider_touch = true) {
+ return geometry_concept<geometry_type_1>::type::intersect(lvalue, rvalue, consider_touch, typename geometry_concept<geometry_type_2>::type());
+}
+
+template <typename geometry_type_1, typename geometry_type_2>
+geometry_type_1& generalized_intersect(geometry_type_1& lvalue, const geometry_type_2& rvalue) {
+ return geometry_concept<geometry_type_1>::type::generalized_intersect(lvalue, rvalue, typename geometry_concept<geometry_type_2>::type());
 }
 
 template <typename geometry_type_1, typename geometry_type_2>
-geometry_type_1& assign(geometry_type_1& lvalue, geometry_type_2& rvalue) {
- return geometry_traits<geometry_type_1>::geometry_concept::assign(lvalue, rvalue);
+bool join_with(geometry_type_1& lvalue, const geometry_type_2& rvalue) {
+ return geometry_concept<geometry_type_1>::type::join_with(lvalue, rvalue);
 }
 
+template <typename geometry_type>
+geometry_type& flip(geometry_type& geometry_object, typename center_type<geometry_type>::type pivot) {
+ return geometry_concept<geometry_type>::type::flip(geometry_object, pivot);
+}
+
+template <typename geometry_type>
+geometry_type& scale(geometry_type& geometry_object, double factor) {
+ return geometry_concept<geometry_type>::type::scale(geometry_object, factor);
+}
+
+template <typename geometry_type>
+geometry_type& move(geometry_type& geometry_object, typename coordinate_type<geometry_type>::type displacement) {
+ return geometry_concept<geometry_type>::type::move(geometry_object, displacement);
+}
+
+//accepts: point point_3d rectangle prism
+template <typename geometry_type>
+geometry_type& move(geometry_type& geometry_object, orientation_2d orient,
+ typename coordinate_type<geometry_type>::type displacement) {
+ return geometry_concept<geometry_type>::type::move(geometry_object, orient, displacement);
+}
+
+//accepts: point_3d prism
+template <typename geometry_type>
+geometry_type& move(geometry_type& geometry_object, orientation_3d orient,
+ typename coordinate_type<geometry_type>::type displacement) {
+ int untested = 0;
+ return geometry_concept<geometry_type>::type::move(geometry_object, orient, displacement);
+}
+
+template <typename geometry_type>
+geometry_type& bloat(geometry_type& geometry_object, typename coordinate_type<geometry_type>::type bloating) {
+ return geometry_concept<geometry_type>::type::bloat(geometry_object, bloating);
+}
+
+template <typename geometry_type>
+geometry_type& shrink(geometry_type& geometry_object, typename coordinate_type<geometry_type>::type shrinking) {
+ return geometry_concept<geometry_type>::type::shrink(geometry_object, shrinking);
+}
+
+//polygonal functions
+
+template <typename geometry_type>
+rectangle_data<typename coordinate_type<geometry_type>::type>
+bounding_box(const geometry_type& geometry_object) {
+ return geometry_concept<geometry_type>::type::bounding_box(geometry_object);
+}
+
+template <typename geometry_type>
+direction_1d winding(const geometry_type& geometry_object) {
+ return geometry_concept<geometry_type>::type::winding(geometry_object);
+}
+
+template <typename geometry_type, typename rectangle_type>
+void set_rectangle(geometry_type& geometry_object, const rectangle_type& rectangle) {
+ geometry_concept<geometry_type>::type::set_rectangle(geometry_object, rectangle);
+}
+
+template <typename geometry_type, typename iterator_type>
+void set_vertices(geometry_type& geometry_object, iterator_type input_begin, iterator_type input_end) {
+ geometry_concept<geometry_type>::type::set(geometry_object, input_begin, input_end);
+}
+
+template <typename geometry_type, typename iterator_type>
+void set_compact(geometry_type& geometry_object, iterator_type input_begin, iterator_type input_end) {
+ geometry_concept<geometry_type>::type::set_compact(geometry_object, input_begin, input_end);
+}
+
+//boolean operator functions
+
 template <typename geometry_type_1, typename geometry_type_2>
 polygon_set_view<typename geometry_type_1::operator_arg_type,
                  typename geometry_type_2::operator_arg_type,

Modified: sandbox/gtl/gtl/interval_concept.hpp
==============================================================================
--- sandbox/gtl/gtl/interval_concept.hpp (original)
+++ sandbox/gtl/gtl/interval_concept.hpp 2008-06-03 19:56:56 EDT (Tue, 03 Jun 2008)
@@ -8,6 +8,13 @@
 struct interval_concept {
   interval_concept() {}
 
+ template <typename interval_type>
+ struct registration {
+ typedef typename interval_traits<interval_type>::coordinate_type coordinate_type;
+ typedef typename interval_traits<interval_type>::coordinate_type component_type;
+ typedef typename interval_traits<interval_type>::coordinate_type center_type;
+ };
+
   template <direction_1d_enum dir, typename T>
   static inline typename interval_traits<T>::coordinate_type
   get(const T& interval) {
@@ -62,7 +69,8 @@
 
   template <typename interval_type>
   static bool contains(const interval_type& interval,
- typename interval_traits<interval_type>::coordinate_type value, bool consider_touch) {
+ typename interval_traits<interval_type>::coordinate_type value,
+ bool consider_touch, no_type tag) {
     if(consider_touch) {
       return value <= get<HIGH>(interval) && value >= get<LOW>(interval);
     } else {
@@ -73,10 +81,286 @@
   template <typename interval_type, typename interval_type_2>
   static bool contains(const interval_type& interval,
                        const interval_type_2& value, bool consider_touch, interval_concept tag) {
- return contains(interval, get(value, LOW), consider_touch) &&
- contains(interval, get(value, HIGH), consider_touch);
+ return contains(interval, get(value, LOW), consider_touch, no_type()) &&
+ contains(interval, get(value, HIGH), consider_touch, no_type());
+ }
+
+ /// get the low coordinate
+ template <typename interval_type>
+ static inline typename interval_traits<interval_type>::coordinate_type
+ low(const interval_type& interval) { return get(interval, LOW); }
+
+ /// get the high coordinate
+ template <typename interval_type>
+ static inline typename interval_traits<interval_type>::coordinate_type
+ high(const interval_type& interval) { return get(interval, HIGH); }
+
+ /// get the center coordinate
+ template <typename interval_type>
+ static inline typename interval_traits<interval_type>::coordinate_type
+ center(const interval_type& interval) { return (high(interval) + low(interval))/2; }
+
+ /// set the low coordinate to v
+ template <typename interval_type>
+ static interval_type& low(interval_type& interval,
+ typename interval_traits<interval_type>::coordinate_type v) {
+ set(interval, LOW, v); return interval; }
+
+ /// set the high coordinate to v
+ template <typename interval_type>
+ static interval_type& high(interval_type& interval,
+ typename interval_traits<interval_type>::coordinate_type v) {
+ set(interval, HIGH, v); return interval; }
+
+ /// get the magnitude of the interval
+ template <typename interval_type>
+ static inline typename interval_traits<interval_type>::coordinate_type
+ delta(const interval_type& interval) { return high(interval) - low(interval); }
+
+ /// flip this about coordinate
+ template <typename interval_type>
+ static interval_type& flip(interval_type& interval,
+ typename interval_traits<interval_type>::coordinate_type axis = 0) {
+ typename interval_traits<interval_type>::coordinate_type newLow, newHigh;
+ newLow = axis - high(interval);
+ newHigh = axis - low(interval);
+ low(interval, newLow);
+ high(interval, newHigh);
+ return interval;
+ }
+
+ /// scale interval by factor
+ template <typename interval_type>
+ static interval_type& scale(interval_type& interval,
+ double factor) {
+ typedef typename interval_traits<interval_type>::coordinate_type Unit;
+ Unit newHigh = (Unit)(high(interval) * factor);
+ low(interval, (Unit)(low(interval)*factor));
+ high(interval, (Unit)(newHigh));
+ return interval;
+ }
+
+ /// move interval by delta
+ template <typename interval_type>
+ static interval_type& move(interval_type& interval,
+ typename interval_traits<interval_type>::coordinate_type delta) {
+ typedef typename interval_traits<interval_type>::coordinate_type Unit;
+ Unit len = high(interval) - low(interval);
+ low(interval, low(interval) + delta);
+ high(interval, low(interval) + len);
+ return interval;
+ }
+
+ /// convolve this with b
+ template <typename interval_type>
+ static interval_type& convolve(interval_type& interval,
+ typename interval_traits<interval_type>::coordinate_type b, no_type tag) {
+ typedef typename interval_traits<interval_type>::coordinate_type Unit;
+ Unit newLow = low(interval) + b;
+ Unit newHigh = high(interval) + b;
+ low(interval, newLow);
+ high(interval, newHigh);
+ return interval;
+ }
+
+ /// deconvolve this with b
+ template <typename interval_type>
+ static interval_type& deconvolve(interval_type& interval,
+ typename interval_traits<interval_type>::coordinate_type b, no_type tag) {
+ typedef typename interval_traits<interval_type>::coordinate_type Unit;
+ Unit newLow = low(interval) - b;
+ Unit newHigh = high(interval) - b;
+ low(interval, newLow);
+ high(interval, newHigh);
+ return interval;
+ }
+
+ /// convolve this with b
+ template <typename interval_type, typename interval_type_2>
+ static interval_type& convolve(interval_type& interval,
+ const interval_type_2& b, interval_concept tag) {
+ typedef typename interval_traits<interval_type>::coordinate_type Unit;
+ Unit newLow = low(interval) + low(b);
+ Unit newHigh = high(interval) + high(b);
+ low(interval, newLow);
+ high(interval, newHigh);
+ return interval;
+ }
+
+ /// deconvolve this with b
+ template <typename interval_type, typename interval_type_2>
+ static interval_type& deconvolve(interval_type& interval,
+ const interval_type_2& b, interval_concept tag) {
+ typedef typename interval_traits<interval_type>::coordinate_type Unit;
+ Unit newLow = low(interval) - low(b);
+ Unit newHigh = high(interval) - high(b);
+ low(interval, newLow);
+ high(interval, newHigh);
+ return interval;
+ }
+
+ /// reflected convolve this with b
+ template <typename interval_type, typename interval_type_2>
+ static interval_type& reflected_convolve(interval_type& interval,
+ const interval_type_2& b, interval_concept tag) {
+ typedef typename interval_traits<interval_type>::coordinate_type Unit;
+ Unit newLow = low(interval) - high(b);
+ Unit newHigh = high(interval) - low(b);
+ low(interval, newLow);
+ high(interval, newHigh);
+ return interval;
+ }
+
+ /// reflected deconvolve this with b
+ template <typename interval_type, typename interval_type_2>
+ static interval_type& reflected_deconvolve(interval_type& interval,
+ const interval_type_2& b, interval_concept tag) {
+ typedef typename interval_traits<interval_type>::coordinate_type Unit;
+ Unit newLow = low(interval) + high(b);
+ Unit newHigh = high(interval) + low(b);
+ low(interval, newLow);
+ high(interval, newHigh);
+ return interval;
+ }
+
+ /// distance from a coordinate to an interval
+ template <typename interval_type>
+ static inline typename interval_traits<interval_type>::coordinate_type
+ distance(const interval_type& interval,
+ typename interval_traits<interval_type>::coordinate_type position, no_type tag) {
+ typedef typename interval_traits<interval_type>::coordinate_type Unit;
+ Unit dist[3] = {0, low(interval) - position, position - high(interval)};
+ return dist[ (dist[1] > 0) + ((dist[2] > 0) << 1) ];
+ }
+
+
+ /// distance between two intervals
+ template <typename interval_type, typename interval_type_2>
+ static inline typename interval_traits<interval_type>::coordinate_type
+ distance(const interval_type& interval,
+ const interval_type_2& b, interval_concept tag) {
+ typedef typename interval_traits<interval_type>::coordinate_type Unit;
+ Unit dist[3] = {0, low(interval) - high(b), low(b) - high(interval)};
+ return dist[ (dist[1] > 0) + ((dist[2] > 0) << 1) ];
+ }
+
+ /// check if Interval b intersects `this` Interval
+ template <typename interval_type, typename interval_type_2>
+ static bool intersects(const interval_type& interval, const interval_type_2& b,
+ bool consider_touch, interval_concept tag) {
+ return consider_touch ?
+ (low(interval) <= high(b)) & (high(interval) >= low(b)) :
+ (low(interval) < high(b)) & (high(interval) > low(b));
+ }
+
+ /// check if Interval b partially overlaps `this` Interval
+ template <typename interval_type, typename interval_type_2>
+ static bool boundaries_intersect(const interval_type& interval, const interval_type_2& b,
+ bool consider_touch, interval_concept tag) {
+ return (contains(interval, low(b), consider_touch, no_type()) ||
+ contains(interval, high(b), consider_touch, no_type())) &&
+ (contains(b, low(interval), consider_touch, no_type()) ||
+ contains(b, high(interval), consider_touch, no_type()));
+ }
+
+ /// check if they are end to end
+ template <typename interval_type, typename interval_type_2>
+ static bool abuts(const interval_type& interval, const interval_type_2& b, direction_1d dir, interval_concept tag) {
+ return dir.to_int() ? low(b) == high(interval) : low(interval) == high(b);
+ }
+
+ /// check if they are end to end
+ template <typename interval_type, typename interval_type_2>
+ static bool abuts(const interval_type& interval, const interval_type_2& b, interval_concept tag) {
+ return abuts(interval, b, HIGH, interval_concept()) || abuts(interval, b, LOW, interval_concept());
+ }
+
+
+ /// set 'this' interval to the intersection of 'this' and b
+ template <typename interval_type, typename interval_type_2>
+ static bool intersect(interval_type& interval, const interval_type_2& b, bool consider_touch, interval_concept tag) {
+ typedef typename interval_traits<interval_type>::coordinate_type Unit;
+ Unit lowVal = std::max(low(interval), low(b));
+ Unit highVal = std::min(high(interval), high(b));
+ bool valid = consider_touch ?
+ lowVal <= highVal :
+ lowVal < highVal;
+ if(valid) {
+ low(interval, lowVal);
+ high(interval, highVal);
+ }
+ return valid;
+ }
+
+ /// set 'this' interval to the generalized intersection of 'this' and b
+ template <typename interval_type, typename interval_type_2>
+ static interval_type& generalized_intersect(interval_type& interval, const interval_type_2& b, interval_concept tag) {
+ typedef typename interval_traits<interval_type>::coordinate_type Unit;
+ Unit coords[4] = {low(interval), high(interval), low(b), high(b)};
+ //consider implementing faster sorting of small fixed length range
+ std::sort(coords, coords+4);
+ low(interval, coords[1]);
+ high(interval, coords[2]);
+ return interval;
   }
 
+ /// bloat the Interval
+ template <typename interval_type>
+ static interval_type& bloat(interval_type& interval, typename interval_traits<interval_type>::coordinate_type bloating) {
+ low(interval, low(interval)-bloating);
+ high(interval, high(interval)+bloating);
+ return interval;
+ }
+
+ /// bloat the specified side of `this` Interval
+ template <typename interval_type>
+ static interval_type& bloat(interval_type& interval, direction_1d dir, typename interval_traits<interval_type>::coordinate_type bloating) {
+ set(interval, dir, get(interval, dir) + dir.get_sign() * bloating);
+ return interval;
+ }
+
+
+ /// shrink the Interval
+ template <typename interval_type>
+ static interval_type& shrink(interval_type& interval, typename interval_traits<interval_type>::coordinate_type shrinking) {
+ return bloat(interval, -shrinking);
+ }
+
+ /// shrink the specified side of `this` Interval
+ template <typename interval_type>
+ static interval_type& shrink(interval_type& interval, direction_1d dir, typename interval_traits<interval_type>::coordinate_type shrinking) {
+ return bloat(interval, dir, -shrinking);
+ }
+
+ /// Enlarge `this` Interval to encompass the specified Interval
+ template <typename interval_type, typename interval_type_2>
+ static bool encompass(interval_type& interval, const interval_type_2& b, interval_concept tag) {
+ bool retval = !contains(interval, b, true, interval_concept());
+ low(interval, std::min(low(interval), low(b)));
+ high(interval, std::max(high(interval), high(b)));
+ return retval;
+ }
+
+ /// gets the half of the interval as an interval
+ template <typename interval_type>
+ static interval_type get_half(const interval_type& interval, direction_1d d1d) {
+ typedef typename interval_traits<interval_type>::coordinate_type Unit;
+ Unit c = (get(interval, LOW) + get(interval, HIGH)) / 2;
+ return construct<interval_type>((d1d == LOW) ? get(interval, LOW) : c,
+ (d1d == LOW) ? c : get(interval, HIGH));
+ }
+
+ /// returns true if the 2 intervals exactly touch at one value, like in l1 <= h1 == l2 <= h2
+ /// sets the argument to the joined interval
+ template <typename interval_type, typename interval_type_2>
+ static bool join_with(interval_type& interval, const interval_type_2& b) {
+ if(abuts(interval, b, interval_concept())) {
+ encompass(interval, b, interval_concept());
+ return true;
+ }
+ return false;
+ }
+
 };
 
 

Modified: sandbox/gtl/gtl/isotropy.hpp
==============================================================================
--- sandbox/gtl/gtl/isotropy.hpp (original)
+++ sandbox/gtl/gtl/isotropy.hpp 2008-06-03 19:56:56 EDT (Tue, 03 Jun 2008)
@@ -5,13 +5,20 @@
   Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   http://www.boost.org/LICENSE_1_0.txt).
 */
-enum direction_1d_enum { LOW = 0, HIGH = 1 };
+
+struct no_type {};
+
+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 winding_direction {
- counterclockwise_winding = 0,
- clockwise_winding = 1,
+ clockwise_winding = 0,
+ counterclockwise_winding = 1,
   unknown_winding = 2
 };
 
@@ -33,6 +40,7 @@
   bool operator!=(direction_1d d) const { return !((*this) == d); }
   unsigned int to_int(void) const { return val_; }
   direction_1d& backward() { val_ ^= 1; return *this; }
+ int get_sign() const { return val_ * 2 - 1; }
 };
 
 class direction_2d;

Modified: sandbox/gtl/gtl/iterator_compact_to_points.hpp
==============================================================================
--- sandbox/gtl/gtl/iterator_compact_to_points.hpp (original)
+++ sandbox/gtl/gtl/iterator_compact_to_points.hpp 2008-06-03 19:56:56 EDT (Tue, 03 Jun 2008)
@@ -5,7 +5,7 @@
   Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   http://www.boost.org/LICENSE_1_0.txt).
 */
-template <class iterator_type, class point_type>
+template <typename iterator_type, typename point_type>
 class iterator_compact_to_points {
 private:
   iterator_type iter_;
@@ -34,10 +34,11 @@
   }
   //use bitwise copy and assign provided by the compiler
   inline iterator_compact_to_points& operator++() {
+ iterator_type prev_iter = iter_;
     ++iter_;
     if(iter_ == iter_end_) {
       if(point_concept::get<HORIZONTAL>(pt_) != firstX_) {
- --iter_;
+ iter_ = prev_iter;
         point_concept::set<HORIZONTAL>(pt_, firstX_);
       }
     } else {
@@ -59,3 +60,4 @@
   }
   inline reference operator*() const { return pt_; }
 };
+

Modified: sandbox/gtl/gtl/iterator_geometry_to_set.hpp
==============================================================================
--- sandbox/gtl/gtl/iterator_geometry_to_set.hpp (original)
+++ sandbox/gtl/gtl/iterator_geometry_to_set.hpp 2008-06-03 19:56:56 EDT (Tue, 03 Jun 2008)
@@ -118,7 +118,7 @@
 };
 
 template <typename polygon_type>
-class iterator_geometry_to_set<polygon_concept, polygon_type> {
+class iterator_geometry_to_set<polygon_90_concept, polygon_type> {
 public:
   typedef typename polygon_traits<polygon_type>::coordinate_type coordinate_type;
   typedef std::forward_iterator_tag iterator_category;
@@ -129,8 +129,7 @@
   typedef typename polygon_traits<polygon_type>::iterator_type coord_iterator_type;
 private:
   value_type vertex_;
- iterator_compact_to_points<typename polygon_traits<polygon_type>::iterator_type,
- point_data<typename polygon_traits<polygon_type>::coordinate_type> > itrb, itre;
+ typename polygon_traits<polygon_type>::iterator_type itrb, itre;
   bool last_vertex_;
   bool is_hole_;
   int multiplier_;
@@ -142,13 +141,13 @@
   iterator_geometry_to_set() : polygon_index(-1) {}
   iterator_geometry_to_set(const polygon_type& polygon, direction_1d dir, orientation_2d orient = HORIZONTAL, bool is_hole = false) :
     is_hole_(is_hole), orient_(orient), polygon_index(0) {
- itrb = polygon_concept::begin_points(polygon);
- itre = polygon_concept::end_points(polygon);
+ itrb = polygon_90_concept::begin(polygon);
+ itre = polygon_90_concept::end(polygon);
     use_wrap = false;
- if(itrb == itre || dir == HIGH || polygon_concept::size(polygon) < 4) {
+ if(itrb == itre || dir == HIGH || polygon_90_concept::size(polygon) < 4) {
       polygon_index = -1;
     } else {
- direction_1d wdir = polygon_concept::winding(polygon);
+ direction_1d wdir = polygon_90_concept::winding(polygon);
       multiplier_ = wdir == LOW ? -1 : 1;
       if(is_hole_) multiplier_ *= -1;
       first_pt = pts[0] = *itrb;
@@ -218,7 +217,7 @@
 };
 
 template <typename polygon_with_holes_type>
-class iterator_geometry_to_set<polygon_with_holes_concept, polygon_with_holes_type> {
+class iterator_geometry_to_set<polygon_90_with_holes_concept, polygon_with_holes_type> {
 public:
   typedef typename rectangle_traits<polygon_with_holes_type>::coordinate_type coordinate_type;
   typedef std::forward_iterator_tag iterator_category;
@@ -227,8 +226,8 @@
   typedef const value_type* pointer; //immutable
   typedef const value_type& reference; //immutable
 private:
- iterator_geometry_to_set<polygon_concept, polygon_with_holes_type> itrb, itre;
- iterator_geometry_to_set<polygon_concept, typename polygon_with_holes_traits<polygon_with_holes_type>::hole_type> itrhib, itrhie;
+ iterator_geometry_to_set<polygon_90_concept, polygon_with_holes_type> itrb, itre;
+ iterator_geometry_to_set<polygon_90_concept, typename polygon_with_holes_traits<polygon_with_holes_type>::hole_type> itrhib, itrhie;
   typename polygon_with_holes_traits<polygon_with_holes_type>::iterator_holes_type itrhb, itrhe;
   orientation_2d orient_;
   bool started_holes;
@@ -236,15 +235,15 @@
   iterator_geometry_to_set() {}
   iterator_geometry_to_set(const polygon_with_holes_type& polygon, direction_1d dir,
                            orientation_2d orient = HORIZONTAL) : orient_(orient) {
- itre = iterator_geometry_to_set<polygon_concept, polygon_with_holes_type>(polygon, HIGH, orient);
- itrhe = polygon_with_holes_concept::end_holes(polygon);
+ itre = iterator_geometry_to_set<polygon_90_concept, polygon_with_holes_type>(polygon, HIGH, orient);
+ itrhe = polygon_90_with_holes_concept::end_holes(polygon);
     if(dir == HIGH) {
       itrb = itre;
       itrhb = itrhe;
       started_holes = true;
     } else {
- itrb = iterator_geometry_to_set<polygon_concept, polygon_with_holes_type>(polygon, LOW, orient);
- itrhb = polygon_with_holes_concept::begin_holes(polygon);
+ itrb = iterator_geometry_to_set<polygon_90_concept, polygon_with_holes_type>(polygon, LOW, orient);
+ itrhb = polygon_90_with_holes_concept::begin_holes(polygon);
       started_holes = false;
     }
   }
@@ -253,26 +252,26 @@
     if(itrb == itre) {
       if(itrhib == itrhie) {
         if(itrhb != itrhe) {
- itrhib = iterator_geometry_to_set<polygon_concept,
+ itrhib = iterator_geometry_to_set<polygon_90_concept,
             typename polygon_with_holes_traits<polygon_with_holes_type>::hole_type>(*itrhb, LOW, orient_, true);
- itrhie = iterator_geometry_to_set<polygon_concept,
+ itrhie = iterator_geometry_to_set<polygon_90_concept,
             typename polygon_with_holes_traits<polygon_with_holes_type>::hole_type>(*itrhb, HIGH, orient_, true);
           ++itrhb;
         } else {
- itrhib = itrhie = iterator_geometry_to_set<polygon_concept,
+ itrhib = itrhie = iterator_geometry_to_set<polygon_90_concept,
             typename polygon_with_holes_traits<polygon_with_holes_type>::hole_type>();
         }
       } else {
         ++itrhib;
         if(itrhib == itrhie) {
           if(itrhb != itrhe) {
- itrhib = iterator_geometry_to_set<polygon_concept,
+ itrhib = iterator_geometry_to_set<polygon_90_concept,
               typename polygon_with_holes_traits<polygon_with_holes_type>::hole_type>(*itrhb, LOW, orient_, true);
- itrhie = iterator_geometry_to_set<polygon_concept,
+ itrhie = iterator_geometry_to_set<polygon_90_concept,
               typename polygon_with_holes_traits<polygon_with_holes_type>::hole_type>(*itrhb, HIGH, orient_, true);
             ++itrhb;
           } else {
- itrhib = itrhie = iterator_geometry_to_set<polygon_concept,
+ itrhib = itrhie = iterator_geometry_to_set<polygon_90_concept,
               typename polygon_with_holes_traits<polygon_with_holes_type>::hole_type>();
           }
         }
@@ -281,9 +280,9 @@
       ++itrb;
       if(itrb == itre) {
         if(itrhb != itrhe) {
- itrhib = iterator_geometry_to_set<polygon_concept,
+ itrhib = iterator_geometry_to_set<polygon_90_concept,
             typename polygon_with_holes_traits<polygon_with_holes_type>::hole_type>(*itrhb, LOW, orient_, true);
- itrhie = iterator_geometry_to_set<polygon_concept,
+ itrhie = iterator_geometry_to_set<polygon_90_concept,
             typename polygon_with_holes_traits<polygon_with_holes_type>::hole_type>(*itrhb, HIGH, orient_, true);
           ++itrhb;
         }

Modified: sandbox/gtl/gtl/iterator_points_to_compact.hpp
==============================================================================
--- sandbox/gtl/gtl/iterator_points_to_compact.hpp (original)
+++ sandbox/gtl/gtl/iterator_points_to_compact.hpp 2008-06-03 19:56:56 EDT (Tue, 03 Jun 2008)
@@ -5,11 +5,12 @@
   Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   http://www.boost.org/LICENSE_1_0.txt).
 */
-template <class iT, typename point_type>
+template <typename iT, typename point_type>
 class iterator_points_to_compact {
 private:
   iT iter_;
   orientation_2d orient_;
+ mutable typename point_traits<point_type>::coordinate_type coord_;
 public:
   typedef typename point_traits<point_type>::coordinate_type coordinate_type;
   typedef std::forward_iterator_tag iterator_category;
@@ -19,11 +20,12 @@
   typedef const coordinate_type& reference; //immutable
 
   inline iterator_points_to_compact() {}
- inline iterator_points_to_compact(iT iter) : iter_(iter), orient_(HORIZONTAL) {}
+ explicit inline iterator_points_to_compact(iT iter) : iter_(iter), orient_(HORIZONTAL) {}
   inline iterator_points_to_compact(const iterator_points_to_compact& that) :
     iter_(that.iter_), orient_(that.orient_) {}
   //use bitwise copy and assign provided by the compiler
   inline iterator_points_to_compact& operator++() {
+ //consider adding assert/excpetion for non-manhattan case
     ++iter_;
     orient_.turn_90();
     return *this;
@@ -39,5 +41,5 @@
   inline bool operator!=(const iterator_points_to_compact& that) const {
     return (iter_ != that.iter_);
   }
- inline reference operator*() const { return point_concept::get(*iter_, orient_); }
+ inline reference operator*() const { return coord_ = point_concept::get(*iter_, orient_); }
 };

Modified: sandbox/gtl/gtl/point_3d_concept.hpp
==============================================================================
--- sandbox/gtl/gtl/point_3d_concept.hpp (original)
+++ sandbox/gtl/gtl/point_3d_concept.hpp 2008-06-03 19:56:56 EDT (Tue, 03 Jun 2008)
@@ -26,7 +26,7 @@
     point_traits<T>::set(point, orient, value); }
   template <typename T, typename coordinate_type>
   static inline void set(T& point, orientation_3d orient, coordinate_type value) {
- point_traits<T>::set(point, orient, value); }
+ point_3d_traits<T>::set(point, orient, value); }
 
   template <typename T, typename coordinate_type1, typename coordinate_type2, typename coordinate_type3>
   static inline T construct(coordinate_type1 x_value,

Modified: sandbox/gtl/gtl/point_concept.hpp
==============================================================================
--- sandbox/gtl/gtl/point_concept.hpp (original)
+++ sandbox/gtl/gtl/point_concept.hpp 2008-06-03 19:56:56 EDT (Tue, 03 Jun 2008)
@@ -11,6 +11,7 @@
   template <typename point_type>
   struct registration {
     typedef typename point_traits<point_type>::coordinate_type component_type;
+ typedef typename point_traits<point_type>::coordinate_type coordinate_type;
   };
 
   template <typename T>
@@ -34,12 +35,14 @@
   }
 
   template <typename point_type>
- static void x(point_type& point) {
+ static typename point_traits<point_type>::coordinate_type
+ x(point_type& point) {
     return get<HORIZONTAL>(point);
   }
 
   template <typename point_type>
- static void y(point_type& point) {
+ static typename point_traits<point_type>::coordinate_type
+ y(point_type& point) {
     return get<VERTICAL>(point);
   }
 

Modified: sandbox/gtl/gtl/point_data.hpp
==============================================================================
--- sandbox/gtl/gtl/point_data.hpp (original)
+++ sandbox/gtl/gtl/point_data.hpp 2008-06-03 19:56:56 EDT (Tue, 03 Jun 2008)
@@ -35,3 +35,8 @@
   coordinate_type coords_[2];
 };
 
+template <class T>
+std::ostream& operator << (std::ostream& o, const point_data<T>& r)
+{
+ return o << r.get(HORIZONTAL) << ' ' << r.get(VERTICAL);
+}

Added: sandbox/gtl/gtl/polygon_45_concept.hpp
==============================================================================
--- (empty file)
+++ sandbox/gtl/gtl/polygon_45_concept.hpp 2008-06-03 19:56:56 EDT (Tue, 03 Jun 2008)
@@ -0,0 +1,167 @@
+/*
+ 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).
+*/
+
+template <typename iterator_type>
+typename point_traits<typename iterator_type::value_type>::coordinate_type
+polygon_point_sequence_area(iterator_type begin_range, iterator_type end_range) {
+ typedef typename iterator_type::value_type point_type;
+ typedef typename point_traits<point_type>::coordinate_type Unit;
+ if(begin_range == end_range) return Unit(0);
+ point_type first = *begin_range;
+ ++begin_range;
+ if(begin_range == end_range) return Unit(0); //throw bad polygon?
+ point_type previous = *begin_range;
+ ++begin_range;
+ // Initialize trapezoid base line
+ Unit y_base = point_concept::y(first);
+ // Initialize area accumulator
+
+ Unit area(0);
+ while (begin_range != end_range) {
+ Unit x1 = point_concept::x(previous);
+ Unit x2 = point_concept::x(*begin_range);
+ if(x1 != x2) {
+ // do trapezoid area accumulation
+ area += (x2 - x1) * ((point_concept::y(*begin_range) - y_base) +
+ (point_concept::y(previous) - y_base)) / 2;
+ }
+ previous = *begin_range;
+ // go to next point
+ ++begin_range;
+ }
+ Unit x1 = point_concept::x(previous);
+ Unit x2 = point_concept::x(first);
+ area += (x2 - x1) * ((point_concept::y(first) - y_base) +
+ (point_concept::y(previous) - y_base)) / 2;
+ return area;
+}
+
+struct polygon_45_concept : polygon_90_concept {
+ inline polygon_45_concept() {}
+
+ template <typename polygon_type_1, typename polygon_type_2>
+ static polygon_type_1& assign(polygon_type_1& lvalue, const polygon_type_2& rvalue) {
+ set(lvalue, begin(rvalue), end(rvalue));
+ return lvalue;
+ }
+
+ template <typename polygon_type>
+ static direction_1d winding(const polygon_type& polygon){
+ //rewrite winding algorithm for non-manhattan
+ winding_direction wd = polygon_traits<polygon_type>::winding(polygon);
+ if(wd != unknown_winding) {
+ return wd == clockwise_winding ? CLOCKWISE: COUNTERCLOCKWISE;
+ }
+ return polygon_point_sequence_area(begin(polygon), end(polygon)) < 0 ? COUNTERCLOCKWISE : CLOCKWISE;
+ }
+
+ template <typename polygon_type>
+ static rectangle_data<typename polygon_traits<polygon_type>::coordinate_type>
+ bounding_box(const polygon_type& polygon) {
+ typedef typename polygon_traits<polygon_type>::coordinate_type coordinate_type;
+ typedef typename polygon_traits<polygon_type>::iterator_type iterator;
+ coordinate_type xmin = 0;
+ coordinate_type ymin = 0;
+ coordinate_type xmax = 0;
+ coordinate_type ymax = 0;
+ bool first_iteration = true;
+ iterator itr_end = end(polygon);
+ for(iterator itr = begin(polygon); itr != itr_end; ++itr) {
+ coordinate_type x = point_concept::x(*itr);
+ coordinate_type y = point_concept::y(*itr);
+ if(first_iteration) {
+ xmin = xmax = x;
+ ymin = ymax = x;
+ first_iteration = false;
+ }
+ xmin = std::min(xmin, x);
+ xmax = std::max(xmax, x);
+ ymin = std::min(ymin, y);
+ ymax = std::max(ymax, y);
+ }
+ typedef rectangle_data<coordinate_type> rectangle_type;
+ rectangle_type return_value = rectangle_concept::construct<rectangle_type>(xmin, ymin, xmax, ymax);
+ return return_value;
+ }
+
+ template <typename polygon_type>
+ static typename registration<polygon_type>::center_type
+ center(const polygon_type& polygon) {
+ return rectangle_concept::center(bounding_box(polygon));
+ }
+
+ template <typename polygon_type>
+ static typename polygon_traits<polygon_type>::coordinate_type
+ area(const polygon_type& polygon) {
+ //rewrite for non-manhattan
+ typename polygon_traits<polygon_type>::coordinate_type result =
+ polygon_point_sequence_area(begin(polygon), end(polygon));
+ if(result < 0) result *= -1;
+ return result;
+ }
+
+ /// get the perimeter of the polygon
+ template <typename polygon_type>
+ static typename polygon_traits<polygon_type>::coordinate_type
+ perimeter(const polygon_type& polygon) {
+ typedef typename polygon_traits<polygon_type>::coordinate_type coordinate_type;
+ typedef typename polygon_traits<polygon_type>::iterator_type iterator;
+ typedef typename iterator::value_type point_type;
+ coordinate_type return_value = 0;
+ point_type previous_point, first_point;
+ iterator itr = begin(polygon);
+ iterator itr_end = end(polygon);
+ if(itr == itr_end) return return_value;
+ previous_point = first_point = *itr;
+ ++itr;
+ for( ; itr != itr_end; ++itr) {
+ point_type current_point = *itr;
+ return_value += point_concept::distance(current_point, previous_point);
+ previous_point = current_point;
+ }
+ return_value += point_concept::distance(previous_point, first_point);
+ return return_value;
+ }
+
+ /// check if point is inside polygon
+ template <typename polygon_type, typename point_type>
+ static bool contains(const polygon_type& polygon, const point_type& point,
+ bool consider_touch, point_concept pc) {
+ throw(std::string("function not yet implemented\n"));
+ return false;
+ }
+
+ template <typename polygon_type, typename coordinate_type_1, typename coordinate_type_2>
+ static polygon_type& move(polygon_type& polygon, coordinate_type_1 x_displacement, coordinate_type_2 y_displacement) {
+ std::vector<typename polygon_traits<polygon_type>::iterator_type::value_type> points;
+ points.reserve(size(polygon));
+ for(typename polygon_traits<polygon_type>::iterator_type iter = begin(polygon);
+ iter != end(polygon); ++iter) {
+ typename polygon_traits<polygon_type>::iterator_type::value_type vertex = *iter;
+ point_concept::x(vertex, point_concept::x(vertex) + x_displacement);
+ point_concept::y(vertex, point_concept::y(vertex) + y_displacement);
+ points.push_back(vertex);
+ }
+ set(polygon, points.begin(), points.end());
+ return polygon;
+ }
+
+ /// move polygon by delta in orient
+ template <typename polygon_type, typename coordinate_type_1>
+ static polygon_type& move(polygon_type& polygon, orientation_2d orient, coordinate_type_1 displacement) {
+ if(orient == HORIZONTAL) {
+ move(polygon, displacement, 0);
+ } else {
+ move(polygon, 0, displacement);
+ }
+ return polygon;
+ }
+
+};
+
+

Added: sandbox/gtl/gtl/polygon_45_data.hpp
==============================================================================
--- (empty file)
+++ sandbox/gtl/gtl/polygon_45_data.hpp 2008-06-03 19:56:56 EDT (Tue, 03 Jun 2008)
@@ -0,0 +1,59 @@
+/*
+ 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).
+*/
+template <typename T>
+class polygon_45_data {
+public:
+ typedef T coordinate_type;
+ typedef typename std::vector<point_data<coordinate_type> >::const_iterator iterator_type;
+ typedef iterator_points_to_compact<iterator_type, point_data<coordinate_type> > compact_iterator_type;
+
+ inline polygon_45_data(){;} //do nothing default constructor
+
+ template<class iT>
+ inline polygon_45_data& set(iT input_begin, iT input_end) {
+ coords_.clear(); //just in case there was some old data there
+ coords_.insert(coords_.end(), input_begin, input_end);
+ return *this;
+ }
+
+ template<typename iT>
+ inline polygon_45_data& set_compact(iT input_begin, iT input_end) {
+ typedef iterator_compact_to_points<iT, point_data<coordinate_type> > iTC;
+ return set(iTC(input_begin, input_end), iTC(input_end, input_end));
+ }
+
+ /// copy constructor (since we have dynamic memory)
+ inline polygon_45_data(const polygon_45_data& that) : coords_(that.coords_) {}
+
+ /// assignment operator (since we have dynamic memory do a deep copy)
+ inline polygon_45_data& operator=(const polygon_45_data& that) {
+ coords_ = that.coords_;
+ return *this;
+ }
+
+ template <typename T2>
+ inline polygon_45_data& operator=(const T2& rvalue);
+
+ /// get begin iterator, returns a pointer to a const Unit
+ inline iterator_type begin() const { return coords_.begin(); }
+
+ /// get end iterator, returns a pointer to a const Unit
+ inline iterator_type end() const { return coords_.end(); }
+
+ /// get begin iterator, returns a pointer to a const Unit
+ inline compact_iterator_type begin_compact() const { return compact_iterator_type(begin()); }
+
+ /// get end iterator, returns a pointer to a const Unit
+ inline compact_iterator_type end_compact() const { return compact_iterator_type(begin()); }
+
+ inline std::size_t size() const { return coords_.size(); }
+
+private:
+ std::vector<point_data<coordinate_type> > coords_;
+};
+

Added: sandbox/gtl/gtl/polygon_45_with_holes_concept.hpp
==============================================================================
--- (empty file)
+++ sandbox/gtl/gtl/polygon_45_with_holes_concept.hpp 2008-06-03 19:56:56 EDT (Tue, 03 Jun 2008)
@@ -0,0 +1,86 @@
+/*
+ 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).
+*/
+
+struct polygon_45_with_holes_concept : virtual polygon_45_concept, polygon_90_with_holes_concept {
+public:
+ inline polygon_45_with_holes_concept() {}
+
+ template <typename polygon_with_holes_type_1, typename polygon_with_holes_type_2>
+ static polygon_with_holes_type_1& assign(polygon_with_holes_type_1& lvalue, const polygon_with_holes_type_2& rvalue) {
+ polygon_45_concept::assign(lvalue, rvalue);
+ set_holes(lvalue, begin_holes(rvalue), end_holes(rvalue));
+ return lvalue;
+ }
+
+ template <typename polygon_with_holes_type>
+ static typename polygon_with_holes_traits<polygon_with_holes_type>::coordinate_type
+ area(const polygon_with_holes_type& polygon) {
+ typename polygon_traits<polygon_with_holes_type>::coordinate_type retval = polygon_45_concept::area(polygon);
+ typename polygon_with_holes_traits<polygon_with_holes_type>::iterator_holes_type b, e;
+ e = end_holes(polygon);
+ for(b = begin_holes(polygon); b != e; ++b) {
+ retval -= polygon_45_concept::area(*b);
+ }
+ }
+
+ /// check if point is inside polygon
+ template <typename polygon_with_holes_type, typename point_type>
+ static bool contains(const polygon_with_holes_type& polygon, const point_type& point,
+ bool consider_touch, point_concept pc) {
+ typename polygon_with_holes_traits<polygon_with_holes_type>::iterator_holes_type b, e;
+ e = end_holes(polygon);
+ for(b = begin_holes(polygon); b != e; ++b) {
+ if(polygon_45_concept::contains(*b, point, !consider_touch, pc)) {
+ return false;
+ }
+ }
+ return polygon_45_concept::contains(polygon, point, consider_touch, pc);
+ }
+
+ /// get the perimeter of the polygon
+ template <typename polygon_with_holes_type>
+ static typename polygon_traits<polygon_with_holes_type>::coordinate_type
+ perimeter(const polygon_with_holes_type& polygon) {
+ typename polygon_traits<polygon_with_holes_type>::coordinate_type retval = polygon_45_concept::perimeter(polygon);
+ typename polygon_with_holes_traits<polygon_with_holes_type>::iterator_holes_type b, e;
+ e = end_holes(polygon);
+ for(b = begin_holes(polygon); b != e; ++b) {
+ retval -= polygon_45_concept::perimeter(*b);
+ }
+ }
+
+ template <typename polygon_with_holes_type, typename coordinate_type_1, typename coordinate_type_2>
+ static polygon_with_holes_type& move(polygon_with_holes_type& polygon,
+ coordinate_type_1 x_displacement, coordinate_type_2 y_displacement) {
+ typedef typename polygon_with_holes_traits<polygon_with_holes_type>::hole_type hole_type;
+ std::vector<hole_type> holes;
+ holes.resize(size_holes(polygon));
+ typename polygon_with_holes_traits<polygon_with_holes_type>::iterator_holes_type b, e;
+ e = end_holes(polygon);
+ for(b = begin_holes(polygon); b != e; ++b) {
+ holes.push_back(*b);
+ polygon_45_concept::move(holes.back(), x_displacement, y_displacement);
+ }
+ set_holes(polygon, holes.begin(), holes.end());
+ polygon_45_concept::move(polygon, x_displacement, y_displacement);
+ return polygon;
+ }
+
+ /// move polygon by delta in orient
+ template <typename polygon_with_holes_type, typename coordinate_type_1>
+ static polygon_with_holes_type& move(polygon_with_holes_type& polygon,
+ orientation_2d orient, coordinate_type_1 displacement) {
+ if(orient == HORIZONTAL) {
+ move(polygon, displacement, 0);
+ } else {
+ move(polygon, 0, displacement);
+ }
+ return polygon;
+ }
+};
+

Added: sandbox/gtl/gtl/polygon_45_with_holes_data.hpp
==============================================================================
--- (empty file)
+++ sandbox/gtl/gtl/polygon_45_with_holes_data.hpp 2008-06-03 19:56:56 EDT (Tue, 03 Jun 2008)
@@ -0,0 +1,97 @@
+/*
+ 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).
+*/
+
+template <typename T>
+class polygon_45_with_holes_data {
+public:
+ typedef T coordinate_type;
+ typedef typename polygon_45_data<T>::iterator_type iterator_type;
+ typedef typename polygon_45_data<T>::compact_iterator_type compact_iterator_type;
+ typedef typename std::list<polygon_45_data<coordinate_type> >::const_iterator iterator_holes_type;
+ typedef polygon_45_data<coordinate_type> hole_type;
+
+ /// default constructor of point does not initialize x and y
+ inline polygon_45_with_holes_data(){;} //do nothing default constructor
+
+ template<class iT>
+ inline polygon_45_with_holes_data& set(iT input_begin, iT input_end) {
+ self_.set(input_begin, input_end);
+ return *this;
+ }
+
+ template<class iT>
+ inline polygon_45_with_holes_data& set_compact(iT input_begin, iT input_end) {
+ self_.set_compact(input_begin, input_end);
+ return *this;
+ }
+
+ /// initialize a polygon from x,y values, it is assumed that the first is an x
+ /// and that the input is a well behaved polygon
+ template<class iT>
+ inline polygon_45_with_holes_data& set_holes(iT input_begin, iT input_end) {
+ holes_.clear(); //just in case there was some old data there
+ for( ; input_begin != input_end; ++ input_begin) {
+ holes_.push_back(hole_type());
+ holes_.back().set((*input_begin).begin(), (*input_begin).end());
+ }
+ return *this;
+ }
+
+ /// copy constructor (since we have dynamic memory)
+ inline polygon_45_with_holes_data(const polygon_45_with_holes_data& that) : self_(that.self_),
+ holes_(that.holes_) {}
+
+ /// assignment operator (since we have dynamic memory do a deep copy)
+ inline polygon_45_with_holes_data& operator=(const polygon_45_with_holes_data& that) {
+ self_ = that.self_;
+ holes_ = that.holes_;
+ return *this;
+ }
+
+ /// get begin iterator, returns a pointer to a const coordinate_type
+ inline const iterator_type begin() const {
+ return self_.begin();
+ }
+
+ /// get end iterator, returns a pointer to a const coordinate_type
+ inline const iterator_type end() const {
+ return self_.end();
+ }
+
+ /// get begin iterator, returns a pointer to a const coordinate_type
+ inline const compact_iterator_type begin_compact() const {
+ return self_.begin_compact();
+ }
+
+ /// get end iterator, returns a pointer to a const coordinate_type
+ inline const compact_iterator_type end_compact() const {
+ return self_.end_compact();
+ }
+
+ inline unsigned int size() const {
+ return self_.size();
+ }
+
+ /// get begin iterator, returns a pointer to a const polygon
+ inline const iterator_holes_type begin_holes() const {
+ return holes_.begin();
+ }
+
+ /// get end iterator, returns a pointer to a const polygon
+ inline const iterator_holes_type end_holes() const {
+ return holes_.end();
+ }
+
+ inline unsigned int size_holes() const {
+ return holes_.size();
+ }
+
+private:
+ polygon_45_data<coordinate_type> self_;
+ std::list<hole_type> holes_;
+};

Added: sandbox/gtl/gtl/polygon_90_concept.hpp
==============================================================================
--- (empty file)
+++ sandbox/gtl/gtl/polygon_90_concept.hpp 2008-06-03 19:56:56 EDT (Tue, 03 Jun 2008)
@@ -0,0 +1,330 @@
+/*
+ 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).
+*/
+struct polygon_90_concept {
+ inline polygon_90_concept() {}
+
+ template <typename polygon_type>
+ struct registration {
+ typedef typename polygon_traits<polygon_type>::coordinate_type coordinate_type;
+ typedef point_data<coordinate_type> center_type;
+ };
+
+
+ template<typename polygon_type, typename compact_iterator_type>
+ static void set_compact(polygon_type& polygon, compact_iterator_type input_begin, compact_iterator_type input_end) {
+ polygon_traits<polygon_type>::set_compact(polygon, input_begin, input_end);
+ }
+
+ template<typename polygon_type, typename rectangle_type>
+ static void set_rectangle(polygon_type& polygon, const rectangle_type& rect) {
+ typename polygon_traits<polygon_type>::coordinate_type coords[4] =
+ {rectangle_concept::xl(rect), rectangle_concept::yl(rect),
+ rectangle_concept::xh(rect), rectangle_concept::yh(rect)};
+ set_compact(polygon, coords, coords+4);
+ }
+
+ template<typename polygon_type, typename point_iterator_type>
+ static void set(polygon_type& polygon, point_iterator_type begin_point, point_iterator_type end_point) {
+ polygon_traits<polygon_type>::set(polygon, begin_point, end_point);
+ }
+
+ template <typename polygon_type>
+ static typename polygon_traits<polygon_type>::iterator_type
+ begin(const polygon_type& polygon) {
+ return polygon_traits<polygon_type>::begin(polygon);
+ }
+
+ template <typename polygon_type>
+ static typename polygon_traits<polygon_type>::iterator_type
+ end(const polygon_type& polygon) {
+ return polygon_traits<polygon_type>::end(polygon);
+ }
+
+ template <typename polygon_type>
+ static typename polygon_traits<polygon_type>::compact_iterator_type
+ begin_compact(const polygon_type& polygon) {
+ return polygon_traits<polygon_type>::begin_compact(polygon);
+ }
+
+ template <typename polygon_type>
+ static typename polygon_traits<polygon_type>::compact_iterator_type
+ end_compact(const polygon_type& polygon) {
+ return polygon_traits<polygon_type>::end_compact(polygon);
+ }
+
+ template<typename T, class iT>
+ static T construct(iT inputBegin, iT inputEnd) { return polygon_traits<T>::construct(inputBegin, inputEnd); }
+
+ template<typename polygon_type, typename rectangle_type>
+ static polygon_type construct_from_rectangle(const rectangle_type& rect) {
+ polygon_type poly;
+ set_rectangle(poly, rect);
+ return poly;
+ }
+
+ template <typename polygon_type, typename polygon_type2>
+ static polygon_type copy_construct(const polygon_type2& polygon) {
+ return construct(begin(polygon), end(polygon));
+ }
+
+ template <typename polygon_type>
+ static std::size_t size(const polygon_type& polygon) {
+ return polygon_traits<polygon_type>::size(polygon);
+ }
+
+ template <typename polygon_type_1, typename polygon_type_2>
+ static polygon_type_1& assign(polygon_type_1& lvalue, const polygon_type_2& rvalue) {
+ set_compact(lvalue, begin_compact(rvalue), end_compact(rvalue));
+ return lvalue;
+ }
+
+ template <typename polygon_type>
+ static direction_1d winding(const polygon_type& polygon){
+ winding_direction wd = polygon_traits<polygon_type>::winding(polygon);
+ if(wd != unknown_winding) {
+ return wd == clockwise_winding ? LOW: HIGH;
+ }
+ direction_1d dir = HIGH;
+ typedef typename polygon_traits<polygon_type>::coordinate_type coordinate_type;
+ typedef typename polygon_traits<polygon_type>::compact_iterator_type iterator;
+ iterator itr = begin_compact(polygon);
+ coordinate_type firstx = *itr;
+ coordinate_type minX = firstx;
+ ++itr;
+ iterator end_itr = end_compact(polygon);
+ if(itr == end_itr) return dir;
+ coordinate_type prevy = *itr;
+ coordinate_type firsty = *itr;
+ ++itr;
+ for( ; itr != end_itr; ++itr) {
+ coordinate_type x = *itr;
+ ++itr;
+ if(itr == end_itr) break;
+ coordinate_type y = *itr;
+ if(x <= minX) {
+ minX = x;
+ //edge directed downward on left side of figure is counterclockwise
+ dir = y < prevy ? HIGH : LOW;
+ }
+ prevy = y;
+ }
+ if(firstx <= minX) {
+ dir = firsty < prevy ? HIGH : LOW;
+ }
+ return dir;
+ }
+
+ template <typename polygon_type>
+ static rectangle_data<typename polygon_traits<polygon_type>::coordinate_type>
+ bounding_box(const polygon_type& polygon) {
+ typedef typename polygon_traits<polygon_type>::coordinate_type coordinate_type;
+ typedef typename polygon_traits<polygon_type>::compact_iterator_type iterator;
+ coordinate_type xmin = 0;
+ coordinate_type ymin = 0;
+ coordinate_type xmax = 0;
+ coordinate_type ymax = 0;
+ bool first_iteration = true;
+ iterator itr_end = end_compact(polygon);
+ for(iterator itr = begin_compact(polygon); itr != itr_end; ++itr) {
+ coordinate_type x = *itr;
+ ++itr;
+ if(itr == itr_end) break;
+ coordinate_type y = *itr;
+ if(first_iteration) {
+ xmin = xmax = x;
+ ymin = ymax = x;
+ first_iteration = false;
+ }
+ xmin = std::min(xmin, x);
+ xmax = std::max(xmax, x);
+ ymin = std::min(ymin, y);
+ ymax = std::max(ymax, y);
+ }
+ typedef rectangle_data<coordinate_type> rectangle_type;
+ rectangle_type return_value = rectangle_concept::construct<rectangle_type>(xmin, ymin, xmax, ymax);
+ return return_value;
+ }
+
+ template <typename polygon_type>
+ static typename registration<polygon_type>::center_type
+ center(const polygon_type& polygon) {
+ return rectangle_concept::center(bounding_box(polygon));
+ }
+
+ template <typename polygon_type>
+ static typename polygon_traits<polygon_type>::coordinate_type
+ area(const polygon_type& polygon) {
+ //for (long i = 2; i < _size; i += 2) res += ((double)_vertex[i-1])*((double)(_vertex[i-2] - _vertex[i]));
+ typedef typename polygon_traits<polygon_type>::coordinate_type coordinate_type;
+ typedef typename polygon_traits<polygon_type>::compact_iterator_type iterator;
+ coordinate_type retval = 0;
+ iterator itr = begin_compact(polygon);
+ iterator end_itr = end_compact(polygon);
+ coordinate_type firstx = *itr;
+ coordinate_type prevx = *itr;
+ ++itr;
+ if(itr == end_itr) return 0;
+ coordinate_type prevy = *itr;
+ ++itr;
+ for( ; itr != end_itr; ++itr) {
+ coordinate_type x = *itr;
+ ++itr;
+ if(itr == end_itr) break;
+ coordinate_type y = *itr;
+ retval += (prevy * (prevx - x));
+ prevy = y;
+ prevx = x;
+ }
+ retval += (prevy * (prevx - firstx));
+ return retval >= 0 ? retval : -retval;
+ }
+
+ /// get the perimeter of the polygon
+ template <typename polygon_type>
+ static typename polygon_traits<polygon_type>::coordinate_type
+ perimeter(const polygon_type& polygon) {
+ typedef typename polygon_traits<polygon_type>::coordinate_type coordinate_type;
+ typedef typename polygon_traits<polygon_type>::iterator_type iterator;
+ typedef typename iterator::value_type point_type;
+ coordinate_type return_value = 0;
+ point_type previous_point, first_point;
+ iterator itr = begin(polygon);
+ iterator itr_end = end(polygon);
+ if(itr == itr_end) return return_value;
+ previous_point = first_point = *itr;
+ ++itr;
+ for( ; itr != itr_end; ++itr) {
+ ++itr;
+ if(itr == itr_end) break;
+ point_type current_point = *itr;
+ return_value += point_concept::manhattan_distance(current_point, previous_point);
+ previous_point = current_point;
+ }
+ return_value += point_concept::manhattan_distance(previous_point, first_point);
+ return return_value;
+ }
+
+ /// check if point is inside polygon
+ template <typename polygon_type, typename point_type>
+ static bool contains(const polygon_type& polygon, const point_type& point,
+ bool consider_touch, point_concept pc) {
+ typedef typename polygon_traits<polygon_type>::coordinate_type coordinate_type;
+ typedef typename polygon_traits<polygon_type>::iterator_type iterator;
+ typedef typename iterator::value_type point_type;
+ iterator iter, iter_end;
+ iter_end = end(polygon);
+ iter = begin(polygon);
+ point_type prev_pt = *iter;
+ unsigned int num = size(polygon);
+ unsigned int counts[2] = {0, 0};
+ for(unsigned int i = 0; i < num; ++i) {
+ if(i == num-1) iter = begin(polygon);
+ else ++iter;
+ point_type current_pt = *iter;
+ if(point_concept::get<HORIZONTAL>(current_pt) ==
+ point_concept::get<HORIZONTAL>(prev_pt)) {
+ unsigned int index = point_concept::get<HORIZONTAL>(current_pt) >
+ point_concept::get<HORIZONTAL>(point);
+ unsigned int increment = 0;
+ interval_data<coordinate_type> ivl =
+ interval_concept::construct<interval_data<coordinate_type> >(point_concept::get<VERTICAL>(current_pt),
+ point_concept::get<VERTICAL>(prev_pt));
+ if(interval_concept::contains(ivl, point_concept::get<VERTICAL>(point), true, no_type())) {
+ if(point_concept::get<HORIZONTAL>(current_pt) ==
+ point_concept::get<HORIZONTAL>(point)) return consider_touch;
+ ++increment;
+ if(point_concept::get<VERTICAL>(current_pt) !=
+ point_concept::get<VERTICAL>(point) &&
+ point_concept::get<VERTICAL>(prev_pt) !=
+ point_concept::get<VERTICAL>(point)) {
+ ++increment;
+ }
+ counts[index] += increment;
+ }
+ }
+ prev_pt = current_pt;
+ }
+ //odd count implies boundary condition
+ if(counts[0] % 2 || counts[1] % 2) return consider_touch;
+ //an odd number of edges to the left implies interior pt
+ return counts[0] % 4;
+ }
+
+// //awaiting re-implementation of iterator_edges and edge concept
+// template <typename polygon_type, typename point_type>
+// static point_type project(const polygon_type& polygon, const point_type& point) const {
+// point_type return_value;
+// typedef iterator_edges<typename polygon_traits<polygon_type>::iterator_type,
+// edge_data<typename polygon_traits<polygon_type>::coordinate_type> > iterator;
+// iterator iter = begin_edges();
+// iterator iter_end = end_edges();
+// double dist = 0;
+// bool first_segment = true;
+// for( ; iter != iter_end; ++iter) {
+// point_type segement_point = segment_concept::project_point(*iter, point);
+// double seg_dist = point_concept::euclidian_distance(point, segment_point);
+// if(first_segment || seg_dist < dist) {
+// dist = seg_dist;
+// return_value = segment_point;
+// }
+// }
+// return return_value;
+// }
+
+// //awaiting re-implementation of iterator_edges and edge concept
+// template <typename polygon_type, typename point_type>
+// static point_type project(point_type& result, const polygon_type& polygon,
+// const point_type& point, direction_2d dir) {
+// typedef iterator_edges<typename polygon_traits<polygon_type>::iterator_type,
+// edge_data<typename polygon_traits<polygon_type>::coordinate_type> > iterator;
+// iterator iter = begin_edges();
+// iterator iter_end = end_edges();
+// double dist = 0;
+// bool found = false;
+// bool first_segment = true;
+// for( ; iter != iter_end; ++iter) {
+// point_type segement_point;
+// if(segment_concept::project_point(segment_point, *iter, point, dir)) {
+// found = true;
+// double seg_dist = point_concept::euclidian_distance(point, segment_point);
+// if(first_segment || seg_dist < dist) {
+// dist = seg_dist;
+// result = segment_point;
+// }
+// }
+// return found;
+// }
+
+ template <typename polygon_type, typename coordinate_type_1, typename coordinate_type_2>
+ static polygon_type& move(polygon_type& polygon, coordinate_type_1 x_displacement, coordinate_type_2 y_displacement) {
+ std::vector<typename polygon_traits<polygon_type>::coordinate_type> coords;
+ coords.reserve(size(polygon));
+ bool pingpong = true;
+ for(typename polygon_traits<polygon_type>::compact_iterator_type iter = begin_compact(polygon);
+ iter != end_compact(polygon); ++iter) {
+ coords.push_back((*iter) + (pingpong ? x_displacement : y_displacement));
+ pingpong = !pingpong;
+ }
+ set_compact(polygon, coords.begin(), coords.end());
+ return polygon;
+ }
+
+ /// move polygon by delta in orient
+ template <typename polygon_type, typename coordinate_type_1>
+ static polygon_type& move(polygon_type& polygon, orientation_2d orient, coordinate_type_1 displacement) {
+ if(orient == HORIZONTAL) {
+ move(displacement, 0);
+ } else {
+ move(0, displacement);
+ }
+ return polygon;
+ }
+
+};
+
+

Added: sandbox/gtl/gtl/polygon_90_data.hpp
==============================================================================
--- (empty file)
+++ sandbox/gtl/gtl/polygon_90_data.hpp 2008-06-03 19:56:56 EDT (Tue, 03 Jun 2008)
@@ -0,0 +1,64 @@
+/*
+ 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).
+*/
+template <typename T>
+class polygon_90_data {
+public:
+ typedef T coordinate_type;
+ typedef typename std::vector<coordinate_type>::const_iterator compact_iterator_type;
+ typedef iterator_compact_to_points<compact_iterator_type, point_data<coordinate_type> > iterator_type;
+
+ inline polygon_90_data(){;} //do nothing default constructor
+
+ /// initialize a polygon from x,y values, it is assumed that the first is an x
+ /// and that the input is a well behaved polygon
+ template<class iT>
+ inline polygon_90_data& set(iT begin_point, iT end_point) {
+ return set_compact(iterator_points_to_compact<iT, typename iT::value_type>(begin_point),
+ iterator_points_to_compact<iT, typename iT::value_type>(end_point));
+ }
+
+ template<class iT>
+ inline polygon_90_data& set_compact(iT input_begin, iT input_end) {
+ coords_.clear(); //just in case there was some old data there
+ while(input_begin != input_end) {
+ coords_.insert(coords_.end(), *input_begin);
+ ++input_begin;
+ }
+ return *this;
+ }
+
+ /// copy constructor (since we have dynamic memory)
+ inline polygon_90_data(const polygon_90_data& that) : coords_(that.coords_) {}
+
+ /// assignment operator (since we have dynamic memory do a deep copy)
+ inline polygon_90_data& operator=(const polygon_90_data& that) {
+ coords_ = that.coords_;
+ return *this;
+ }
+
+ template <typename T2>
+ inline polygon_90_data& operator=(const T2& rvalue);
+
+ /// get begin iterator, returns a pointer to a const Unit
+ inline iterator_type begin() const { return iterator_type(coords_.begin(), coords_.end()); }
+
+ /// get end iterator, returns a pointer to a const Unit
+ inline iterator_type end() const { return iterator_type(coords_.end(), coords_.end()); }
+
+ /// get begin iterator, returns a pointer to a const Unit
+ inline compact_iterator_type begin_compact() const { return coords_.begin(); }
+
+ /// get end iterator, returns a pointer to a const Unit
+ inline compact_iterator_type end_compact() const { return coords_.end(); }
+
+ inline std::size_t size() const { return coords_.size(); }
+
+private:
+ std::vector<coordinate_type> coords_;
+};
+

Added: sandbox/gtl/gtl/polygon_90_with_holes_concept.hpp
==============================================================================
--- (empty file)
+++ sandbox/gtl/gtl/polygon_90_with_holes_concept.hpp 2008-06-03 19:56:56 EDT (Tue, 03 Jun 2008)
@@ -0,0 +1,191 @@
+/*
+ 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).
+*/
+
+struct polygon_90_with_holes_concept : polygon_90_concept {
+public:
+ inline polygon_90_with_holes_concept() {}
+
+ template<typename polygon_with_holes_type, typename hole_iterator_type>
+ static void set_holes(polygon_with_holes_type& polygon, hole_iterator_type holes_begin, hole_iterator_type holes_end) {
+ polygon_with_holes_traits<polygon_with_holes_type>::set_holes(polygon, holes_begin, holes_end);
+ }
+
+ template <typename polygon_with_holes_type>
+ static typename polygon_with_holes_traits<polygon_with_holes_type>::iterator_holes_type
+ begin_holes(const polygon_with_holes_type& polygon) {
+ return polygon_with_holes_traits<polygon_with_holes_type>::begin_holes(polygon);
+ }
+
+ template <typename polygon_with_holes_type>
+ static typename polygon_with_holes_traits<polygon_with_holes_type>::iterator_holes_type
+ end_holes(const polygon_with_holes_type& polygon) {
+ return polygon_with_holes_traits<polygon_with_holes_type>::end_holes(polygon);
+ }
+
+ template <typename polygon_with_holes_type_1, typename polygon_with_holes_type_2>
+ static polygon_with_holes_type_1 copy_construct(const polygon_with_holes_type_2& polygon) {
+ polygon_with_holes_type_1 retval;
+ set(retval, polygon_90_concept::begin(polygon), polygon_90_concept::end(polygon));
+ set_holes(retval, begin_holes(polygon), end_holes(polygon));
+ return retval;
+ }
+
+ template <typename polygon_with_holes_type>
+ static std::size_t size_holes(const polygon_with_holes_type& polygon) {
+ return polygon_with_holes_traits<polygon_with_holes_type>::size_holes(polygon);
+ }
+
+ template <typename polygon_with_holes_type_1, typename polygon_with_holes_type_2>
+ static polygon_with_holes_type_1& assign(polygon_with_holes_type_1& lvalue, const polygon_with_holes_type_2& rvalue) {
+ polygon_90_concept::assign(lvalue, rvalue);
+ set_holes(lvalue, begin_holes(rvalue), end_holes(rvalue));
+ return lvalue;
+ }
+
+ template <typename polygon_with_holes_type>
+ static typename polygon_with_holes_traits<polygon_with_holes_type>::coordinate_type
+ area(const polygon_with_holes_type& polygon) {
+ typename polygon_traits<polygon_with_holes_type>::coordinate_type retval = polygon_90_concept::area(polygon);
+ typename polygon_with_holes_traits<polygon_with_holes_type>::iterator_holes_type b, e;
+ e = end_holes(polygon);
+ for(b = begin_holes(polygon); b != e; ++b) {
+ retval -= polygon_90_concept::area(*b);
+ }
+ }
+
+ /// check if point is inside polygon
+ template <typename polygon_with_holes_type, typename point_type>
+ static bool contains(const polygon_with_holes_type& polygon, const point_type& point,
+ bool consider_touch, point_concept pc) {
+ typename polygon_with_holes_traits<polygon_with_holes_type>::iterator_holes_type b, e;
+ e = end_holes(polygon);
+ for(b = begin_holes(polygon); b != e; ++b) {
+ if(polygon_90_concept::contains(*b, point, !consider_touch, pc)) {
+ return false;
+ }
+ }
+ return polygon_90_concept::contains(polygon, point, consider_touch, pc);
+ }
+
+ /// get the perimeter of the polygon
+ template <typename polygon_with_holes_type>
+ static typename polygon_traits<polygon_with_holes_type>::coordinate_type
+ perimeter(const polygon_with_holes_type& polygon) {
+ typename polygon_traits<polygon_with_holes_type>::coordinate_type retval = polygon_90_concept::perimeter(polygon);
+ typename polygon_with_holes_traits<polygon_with_holes_type>::iterator_holes_type b, e;
+ e = end_holes(polygon);
+ for(b = begin_holes(polygon); b != e; ++b) {
+ retval -= polygon_90_concept::perimeter(*b);
+ }
+ }
+
+ // //awaiting re-implementation of iterator_edges and edge concept
+ // template <typename polygon_with_holes_type, typename point_type>
+ // static point_type project(const polygon_with_holes_type& polygon, const point_type& point) const {
+ // typedef point_data<typename polygon_with_holes_traits<polygon_with_holes_type>::coordinate_type> point_type_2;
+ // point_type_2 retval = polygon_90_concept::project(polygon, point);
+ // double dist = point_concept::euclidian_distance(point retval);
+ // polygon_with_holes_traits<polygon_with_holes_type>::iterator_holes_type b, e;
+ // e = end_holes(polygon);
+ // for(b = begin_holes(polygon); b != e; ++b) {
+ // point_type_2 hole_point = polygon_90_concept::project(*b, point);
+ // double hole_dist = point_concept::euclidian_distance(point hole_point);
+ // if(hole_dist < dist) {
+ // retval = hole_point;
+ // dist = hole_dist;
+ // }
+ // }
+ // return retval;
+ // }
+
+ // //awaiting re-implementation of iterator_edges and edge concept
+ // template <typename polygon_with_holes_type, typename point_type>
+ // static point_type project(point_type& result, const polygon_with_holes_type& polygon,
+ // const point_type& point, direction_2d dir) {
+ // typedef point_data<typename polygon_with_holes_traits<polygon_with_holes_type>::coordinate_type> point_type_2;
+ // point_type_2 retval = polygon_90_concept::project(polygon, point, dir);
+ // double dist = point_concept::euclidian_distance(point retval);
+ // polygon_with_holes_traits<polygon_with_holes_type>::iterator_holes_type b, e;
+ // e = end_holes(polygon);
+ // for(b = begin_holes(polygon); b != e; ++b) {
+ // point_type_2 hole_point = polygon_90_concept::project(*b, point, dir);
+ // double hole_dist = point_concept::euclidian_distance(point hole_point);
+ // if(hole_dist < dist) {
+ // retval = hole_point;
+ // dist = hole_dist;
+ // }
+ // }
+ // return retval;
+ // }
+
+ template <typename polygon_with_holes_type, typename coordinate_type_1, typename coordinate_type_2>
+ static polygon_with_holes_type& move(polygon_with_holes_type& polygon,
+ coordinate_type_1 x_displacement, coordinate_type_2 y_displacement) {
+ typedef typename polygon_with_holes_traits<polygon_with_holes_type>::hole_type hole_type;
+ std::vector<hole_type> holes;
+ holes.resize(size_holes(polygon));
+ typename polygon_with_holes_traits<polygon_with_holes_type>::iterator_holes_type b, e;
+ e = end_holes(polygon);
+ for(b = begin_holes(polygon); b != e; ++b) {
+ holes.push_back(*b);
+ polygon_90_concept::move(holes.back(), x_displacement, y_displacement);
+ }
+ set_holes(polygon, holes.begin(), holes.end());
+ polygon_90_concept::move(polygon, x_displacement, y_displacement);
+ return polygon;
+ }
+
+ /// move polygon by delta in orient
+ template <typename polygon_with_holes_type, typename coordinate_type_1>
+ static polygon_with_holes_type& move(polygon_with_holes_type& polygon,
+ orientation_2d orient, coordinate_type_1 displacement) {
+ if(orient == HORIZONTAL) {
+ move(polygon, displacement, 0);
+ } else {
+ move(polygon, 0, displacement);
+ }
+ return polygon;
+ }
+};
+
+template <typename T>
+inline void testPolygonWithHolesImpl() {
+ rectangle_data<T> rect = rectangle_concept::construct<rectangle_data<T> >(0, 0, 100, 100);
+ polygon_90_data<T> polyHole = polygon_90_concept::construct_from_rectangle<polygon_90_data<T> >(rectangle_concept::construct<rectangle_data<T> >(10, 10, 90, 90));
+ polygon_90_with_holes_data<T> pwh = polygon_90_with_holes_concept::construct_from_rectangle<polygon_90_with_holes_data<T> >(rect);
+ polygon_90_with_holes_concept::set_holes(pwh, &polyHole, (&polyHole)+1);
+ //std::cout << pwh << std::endl;
+ std::cout << "PolygonWithHoles test pattern 1 1 1 1 1 1 0 0 0 0 0 0\n";
+ std::cout << "PolygonWithHoles test pattern ";
+ std::cout << polygon_90_with_holes_concept::contains(pwh, point_data<T>(1, 11), true, point_concept())
+ << " " ;
+ std::cout << polygon_90_with_holes_concept::contains(pwh, point_data<T>(10, 10), true, point_concept())
+ << " " ;
+ std::cout << polygon_90_with_holes_concept::contains(pwh, point_data<T>(10, 90), true, point_concept())
+ << " " ;
+ std::cout << polygon_90_with_holes_concept::contains(pwh, point_data<T>(90, 90), true, point_concept())
+ << " " ;
+ std::cout << polygon_90_with_holes_concept::contains(pwh, point_data<T>(90, 10), true, point_concept())
+ << " " ;
+ std::cout << polygon_90_with_holes_concept::contains(pwh, point_data<T>(90, 80), true, point_concept())
+ << " " ;
+ std::cout << polygon_90_with_holes_concept::contains(pwh, point_data<T>(12, 12), true, point_concept())
+ << " " ;
+ std::cout << polygon_90_with_holes_concept::contains(pwh, point_data<T>(10, 10), false, point_concept())
+ << " " ;
+ std::cout << polygon_90_with_holes_concept::contains(pwh, point_data<T>(10, 90), false, point_concept())
+ << " " ;
+ std::cout << polygon_90_with_holes_concept::contains(pwh, point_data<T>(90, 90), false, point_concept())
+ << " " ;
+ std::cout << polygon_90_with_holes_concept::contains(pwh, point_data<T>(90, 10), false, point_concept())
+ << " " ;
+ std::cout << polygon_90_with_holes_concept::contains(pwh, point_data<T>(90, 80), false, point_concept())
+ << "\n";
+
+ polygon_90_with_holes_concept::move(pwh, 5, 5);
+}

Added: sandbox/gtl/gtl/polygon_90_with_holes_data.hpp
==============================================================================
--- (empty file)
+++ sandbox/gtl/gtl/polygon_90_with_holes_data.hpp 2008-06-03 19:56:56 EDT (Tue, 03 Jun 2008)
@@ -0,0 +1,101 @@
+/*
+ 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).
+*/
+
+template <typename T>
+class polygon_90_with_holes_data {
+public:
+ typedef T coordinate_type;
+ typedef typename polygon_90_data<T>::iterator_type iterator_type;
+ typedef typename polygon_90_data<T>::compact_iterator_type compact_iterator_type;
+ typedef typename std::list<polygon_90_data<coordinate_type> >::const_iterator iterator_holes_type;
+ typedef polygon_90_data<coordinate_type> hole_type;
+
+ /// default constructor of point does not initialize x and y
+ inline polygon_90_with_holes_data(){;} //do nothing default constructor
+
+ /// initialize a polygon from x,y values, it is assumed that the first is an x
+ /// and that the input is a well behaved polygon
+ template<class iT>
+ inline polygon_90_with_holes_data& set(iT input_begin, iT input_end) {
+ self_.set(input_begin, input_end);
+ return *this;
+ }
+
+ /// initialize a polygon from x,y values, it is assumed that the first is an x
+ /// and that the input is a well behaved polygon
+ template<class iT>
+ inline polygon_90_with_holes_data& set_compact(iT input_begin, iT input_end) {
+ self_.set_compact(input_begin, input_end);
+ return *this;
+ }
+
+ /// initialize a polygon from x,y values, it is assumed that the first is an x
+ /// and that the input is a well behaved polygon
+ template<class iT>
+ inline polygon_90_with_holes_data& set_holes(iT input_begin, iT input_end) {
+ holes_.clear(); //just in case there was some old data there
+ for( ; input_begin != input_end; ++ input_begin) {
+ holes_.push_back(hole_type());
+ holes_.back().set_compact((*input_begin).begin_compact(), (*input_begin).end_compact());
+ }
+ return *this;
+ }
+
+ /// copy constructor (since we have dynamic memory)
+ inline polygon_90_with_holes_data(const polygon_90_with_holes_data& that) : self_(that.self_),
+ holes_(that.holes_) {}
+
+ /// assignment operator (since we have dynamic memory do a deep copy)
+ inline polygon_90_with_holes_data& operator=(const polygon_90_with_holes_data& that) {
+ self_ = that.self_;
+ holes_ = that.holes_;
+ return *this;
+ }
+
+ /// get begin iterator, returns a pointer to a const coordinate_type
+ inline const iterator_type begin() const {
+ return self_.begin();
+ }
+
+ /// get end iterator, returns a pointer to a const coordinate_type
+ inline const iterator_type end() const {
+ return self_.end();
+ }
+
+ /// get begin iterator, returns a pointer to a const coordinate_type
+ inline const compact_iterator_type begin_compact() const {
+ return self_.begin_compact();
+ }
+
+ /// get end iterator, returns a pointer to a const coordinate_type
+ inline const compact_iterator_type end_compact() const {
+ return self_.end_compact();
+ }
+
+ inline unsigned int size() const {
+ return self_.size();
+ }
+
+ /// get begin iterator, returns a pointer to a const polygon
+ inline const iterator_holes_type begin_holes() const {
+ return holes_.begin();
+ }
+
+ /// get end iterator, returns a pointer to a const polygon
+ inline const iterator_holes_type end_holes() const {
+ return holes_.end();
+ }
+
+ inline unsigned int size_holes() const {
+ return holes_.size();
+ }
+
+private:
+ polygon_90_data<coordinate_type> self_;
+ std::list<hole_type> holes_;
+};

Modified: sandbox/gtl/gtl/polygon_concept.hpp
==============================================================================
--- sandbox/gtl/gtl/polygon_concept.hpp (original)
+++ sandbox/gtl/gtl/polygon_concept.hpp 2008-06-03 19:56:56 EDT (Tue, 03 Jun 2008)
@@ -5,320 +5,11 @@
   Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   http://www.boost.org/LICENSE_1_0.txt).
 */
-struct polygon_concept {
- inline polygon_concept() {}
-
- template <typename polygon_type>
- struct registration {
- typedef typename polygon_traits<polygon_type>::coordinate_type coordinate_type;
- };
-
-
- template<typename polygon_type, typename iterator_type>
- static void set(polygon_type& polygon, iterator_type input_begin, iterator_type input_end) {
- polygon_traits<polygon_type>::set(polygon, input_begin, input_end);
- }
-
- template<typename polygon_type, typename rectangle_type>
- static void set(polygon_type& polygon, const rectangle_type& rect) {
- typename polygon_traits<polygon_type>::coordinate_type coords[4] =
- {rectangle_concept::xl(rect), rectangle_concept::yl(rect),
- rectangle_concept::xh(rect), rectangle_concept::yh(rect)};
- set(polygon, coords, coords+4);
- }
-
- template<typename polygon_type, typename point_iterator_type>
- static void set_points(polygon_type& polygon, point_iterator_type begin_point, point_iterator_type end_point) {
- return set(iterator_points_to_compact<point_iterator_type, typename point_iterator_type::value_type>(begin_point),
- iterator_points_to_compact<point_iterator_type, typename point_iterator_type::value_type>(end_point));
- }
-
- template <typename polygon_type>
- static typename polygon_traits<polygon_type>::iterator_type begin(const polygon_type& polygon) {
- return polygon_traits<polygon_type>::begin(polygon);
- }
-
- template <typename polygon_type>
- static typename polygon_traits<polygon_type>::iterator_type end(const polygon_type& polygon) {
- return polygon_traits<polygon_type>::end(polygon);
- }
-
- template <typename polygon_type>
- static iterator_compact_to_points<typename polygon_traits<polygon_type>::iterator_type,
- point_data<typename polygon_traits<polygon_type>::coordinate_type> >
- begin_points(const polygon_type& polygon) {
- return iterator_compact_to_points<typename polygon_traits<polygon_type>::iterator_type,
- point_data<typename polygon_traits<polygon_type>::coordinate_type> > (begin(polygon), end(polygon));
- }
-
- template <typename polygon_type>
- static iterator_compact_to_points<typename polygon_traits<polygon_type>::iterator_type,
- point_data<typename polygon_traits<polygon_type>::coordinate_type> >
- end_points(const polygon_type& polygon) {
- return iterator_compact_to_points<typename polygon_traits<polygon_type>::iterator_type,
- point_data<typename polygon_traits<polygon_type>::coordinate_type> > (end(polygon), end(polygon));
- }
-
- template<typename T, class iT>
- static T construct(iT inputBegin, iT inputEnd) { return polygon_traits<T>::construct(inputBegin, inputEnd); }
-
- template<typename polygon_type, typename rectangle_type>
- static polygon_type construct_from_rectangle(const rectangle_type& rect) {
- polygon_type poly;
- set(poly, rect);
- return poly;
- }
-
- template <typename polygon_type, typename polygon_type2>
- static polygon_type copy_construct(const polygon_type2& polygon) {
- return construct(polygon_concept::begin(polygon), polygon_concept::end(polygon));
- }
 
- template <typename polygon_type>
- static std::size_t size(const polygon_type& polygon) {
- return polygon_traits<polygon_type>::size(polygon);
- }
-
- template <typename polygon_type_1, typename polygon_type_2>
- static polygon_type_1& assign(polygon_type_1& lvalue, const polygon_type_2& rvalue) {
- set(lvalue, begin(rvalue), end(rvalue));
- return lvalue;
- }
-
- template <typename polygon_type>
- static direction_1d winding(const polygon_type& polygon){
- winding_direction wd = polygon_traits<polygon_type>::winding(polygon);
- if(wd != unknown_winding) {
- return wd == clockwise_winding ? LOW: HIGH;
- }
- direction_1d dir = HIGH;
- typedef typename polygon_traits<polygon_type>::coordinate_type coordinate_type;
- typedef typename polygon_traits<polygon_type>::iterator_type iterator;
- iterator itr = begin(polygon);
- coordinate_type firstx = *itr;
- coordinate_type minX = firstx;
- ++itr;
- iterator end_itr = end(polygon);
- if(itr == end_itr) return dir;
- coordinate_type prevy = *itr;
- coordinate_type firsty = *itr;
- ++itr;
- for( ; itr != end_itr; ++itr) {
- coordinate_type x = *itr;
- ++itr;
- if(itr == end_itr) break;
- coordinate_type y = *itr;
- if(x <= minX) {
- minX = x;
- //edge directed downward on left side of figure is counterclockwise
- dir = y < prevy ? HIGH : LOW;
- }
- prevy = y;
- }
- if(firstx <= minX) {
- dir = firsty < prevy ? HIGH : LOW;
- }
- return dir;
- }
-
- template <typename polygon_type>
- static rectangle_data<typename polygon_traits<polygon_type>::coordinate_type>
- bounding_box(const polygon_type& polygon) {
- typedef typename polygon_traits<polygon_type>::coordinate_type coordinate_type;
- typedef typename polygon_traits<polygon_type>::iterator_type iterator;
- coordinate_type xmin = 0;
- coordinate_type ymin = 0;
- coordinate_type xmax = 0;
- coordinate_type ymax = 0;
- bool first_iteration = true;
- iterator itr_end = end(polygon);
- for(iterator itr = begin(polygon); itr != itr_end; ++itr) {
- coordinate_type x = *itr;
- ++itr;
- if(itr == itr_end) break;
- coordinate_type y = *itr;
- if(first_iteration) {
- xmin = xmax = x;
- ymin = ymax = x;
- first_iteration = false;
- }
- xmin = std::min(xmin, x);
- xmax = std::max(xmax, x);
- ymin = std::min(ymin, y);
- ymax = std::max(ymax, y);
- }
- typedef rectangle_data<coordinate_type> rectangle_type;
- rectangle_type return_value = rectangle_concept::construct<rectangle_type>(xmin, ymin, xmax, ymax);
- return return_value;
- }
-
- template <typename polygon_type>
- static typename polygon_traits<polygon_type>::coordinate_type
- area(const polygon_type& polygon) {
- //for (long i = 2; i < _size; i += 2) res += ((double)_vertex[i-1])*((double)(_vertex[i-2] - _vertex[i]));
- typedef typename polygon_traits<polygon_type>::coordinate_type coordinate_type;
- typedef typename polygon_traits<polygon_type>::iterator_type iterator;
- coordinate_type retval = 0;
- iterator itr = begin(polygon);
- iterator end_itr = end(polygon);
- coordinate_type firstx = *itr;
- coordinate_type prevx = *itr;
- ++itr;
- if(itr == end_itr) return 0;
- coordinate_type prevy = *itr;
- ++itr;
- for( ; itr != end_itr; ++itr) {
- coordinate_type x = *itr;
- ++itr;
- if(itr == end_itr) break;
- coordinate_type y = *itr;
- retval += (prevy * (prevx - x));
- prevy = y;
- prevx = x;
- }
- retval += (prevy * (prevx - firstx));
- return retval >= 0 ? retval : -retval;
- }
-
- /// get the perimeter of the polygon
- template <typename polygon_type>
- static typename polygon_traits<polygon_type>::coordinate_type
- perimeter(const polygon_type& polygon) {
- typedef typename polygon_traits<polygon_type>::coordinate_type coordinate_type;
- typedef typename polygon_traits<polygon_type>::iterator_type iterator_type;
- typedef iterator_compact_to_points<iterator_type, point_data<coordinate_type> > iterator;
- coordinate_type return_value = 0;
- point_data<coordinate_type> previous_point, first_point;
- iterator itr = begin_points(polygon);
- iterator itr_end = end_points(polygon);
- if(itr == itr_end) return return_value;
- previous_point = first_point = *itr;
- ++itr;
- for( ; itr != itr_end; ++itr) {
- ++itr;
- if(itr == itr_end) break;
- point_data<coordinate_type> current_point = *itr;
- return_value += point_concept::manhattan_distance(current_point, previous_point);
- previous_point = current_point;
- }
- return_value += point_concept::manhattan_distance(previous_point, first_point);
- return return_value;
- }
-
- /// check if point is inside polygon
- template <typename polygon_type, typename point_type>
- static bool contains(const polygon_type& polygon, const point_type& point,
- bool consider_touch, point_concept pc) {
- typedef typename polygon_traits<polygon_type>::coordinate_type coordinate_type;
- typedef typename polygon_traits<polygon_type>::iterator_type iterator_type;
- typedef iterator_compact_to_points<iterator_type, point_data<coordinate_type> > iterator;
- iterator iter, iter_end;
- iter_end = end_points(polygon);
- iter = begin_points(polygon);
- point_data<coordinate_type> prev_pt = *iter;
- unsigned int num = size(polygon);
- unsigned int counts[2] = {0, 0};
- for(unsigned int i = 0; i < num; ++i) {
- if(i == num-1) iter = begin_points(polygon);
- else ++iter;
- point_data<coordinate_type> current_pt = *iter;
- if(point_concept::get<HORIZONTAL>(current_pt) ==
- point_concept::get<HORIZONTAL>(prev_pt)) {
- unsigned int index = point_concept::get<HORIZONTAL>(current_pt) >
- point_concept::get<HORIZONTAL>(point);
- unsigned int increment = 0;
- interval_data<coordinate_type> ivl =
- interval_concept::construct<interval_data<coordinate_type> >(point_concept::get<VERTICAL>(current_pt),
- point_concept::get<VERTICAL>(prev_pt));
- if(interval_concept::contains(ivl, point_concept::get<VERTICAL>(point), true)) {
- if(point_concept::get<HORIZONTAL>(current_pt) ==
- point_concept::get<HORIZONTAL>(point)) return consider_touch;
- ++increment;
- if(point_concept::get<VERTICAL>(current_pt) !=
- point_concept::get<VERTICAL>(point) &&
- point_concept::get<VERTICAL>(prev_pt) !=
- point_concept::get<VERTICAL>(point)) {
- ++increment;
- }
- counts[index] += increment;
- }
- }
- prev_pt = current_pt;
- }
- //odd count implies boundary condition
- if(counts[0] % 2 || counts[1] % 2) return consider_touch;
- //an odd number of edges to the left implies interior pt
- return counts[0] % 4;
- }
-
-// //awaiting re-implementation of iterator_edges and edge concept
-// template <typename polygon_type, typename point_type>
-// static point_type project(const polygon_type& polygon, const point_type& point) const {
-// point_type return_value;
-// typedef iterator_edges<typename polygon_traits<polygon_type>::iterator_type,
-// edge_data<typename polygon_traits<polygon_type>::coordinate_type> > iterator;
-// iterator iter = begin_edges();
-// iterator iter_end = end_edges();
-// double dist = 0;
-// bool first_segment = true;
-// for( ; iter != iter_end; ++iter) {
-// point_type segement_point = segment_concept::project_point(*iter, point);
-// double seg_dist = point_concept::euclidian_distance(point, segment_point);
-// if(first_segment || seg_dist < dist) {
-// dist = seg_dist;
-// return_value = segment_point;
-// }
-// }
-// return return_value;
-// }
-
-// //awaiting re-implementation of iterator_edges and edge concept
-// template <typename polygon_type, typename point_type>
-// static point_type project(point_type& result, const polygon_type& polygon,
-// const point_type& point, direction_2d dir) {
-// typedef iterator_edges<typename polygon_traits<polygon_type>::iterator_type,
-// edge_data<typename polygon_traits<polygon_type>::coordinate_type> > iterator;
-// iterator iter = begin_edges();
-// iterator iter_end = end_edges();
-// double dist = 0;
-// bool found = false;
-// bool first_segment = true;
-// for( ; iter != iter_end; ++iter) {
-// point_type segement_point;
-// if(segment_concept::project_point(segment_point, *iter, point, dir)) {
-// found = true;
-// double seg_dist = point_concept::euclidian_distance(point, segment_point);
-// if(first_segment || seg_dist < dist) {
-// dist = seg_dist;
-// result = segment_point;
-// }
-// }
-// return found;
-// }
-
- template <typename polygon_type, typename coordinate_type_1, typename coordinate_type_2>
- static void move(polygon_type& polygon, coordinate_type_1 x_displacement, coordinate_type_2 y_displacement) {
- std::vector<typename polygon_traits<polygon_type>::coordinate_type> coords;
- coords.reserve(size(polygon));
- bool pingpong = true;
- for(typename polygon_traits<polygon_type>::iterator_type iter = begin(polygon);
- iter != end(polygon); ++iter) {
- coords.push_back((*iter) + (pingpong ? x_displacement : y_displacement));
- pingpong = !pingpong;
- }
- set(polygon, coords.begin(), coords.end());
- }
-
- /// move polygon by delta in orient
- template <typename polygon_type, typename coordinate_type_1>
- static void move(polygon_type& polygon, orientation_2d orient, coordinate_type_1 displacement) {
- if(orient == HORIZONTAL) {
- move(displacement, 0);
- } else {
- move(0, displacement);
- }
- }
+struct polygon_concept : polygon_45_concept {
+ inline polygon_concept() {}
 
+ //inherits its behaviors
 };
 
 

Modified: sandbox/gtl/gtl/polygon_data.hpp
==============================================================================
--- sandbox/gtl/gtl/polygon_data.hpp (original)
+++ sandbox/gtl/gtl/polygon_data.hpp 2008-06-03 19:56:56 EDT (Tue, 03 Jun 2008)
@@ -6,46 +6,6 @@
   http://www.boost.org/LICENSE_1_0.txt).
 */
 template <typename T>
-class polygon_data {
-public:
- typedef T coordinate_type;
- typedef typename std::vector<coordinate_type>::const_iterator iterator_type;
-
- inline polygon_data(){;} //do nothing default constructor
-
- /// initialize a polygon from x,y values, it is assumed that the first is an x
- /// and that the input is a well behaved polygon
- template<class iT>
- inline polygon_data& set(iT input_begin, iT input_end) {
- coords_.clear(); //just in case there was some old data there
- while(input_begin != input_end) {
- coords_.insert(coords_.end(), *input_begin);
- ++input_begin;
- }
- return *this;
- }
-
- /// copy constructor (since we have dynamic memory)
- inline polygon_data(const polygon_data& that) : coords_(that.coords_) {}
-
- /// assignment operator (since we have dynamic memory do a deep copy)
- inline polygon_data& operator=(const polygon_data& that) {
- coords_ = that.coords_;
- return *this;
- }
-
- template <typename T2>
- inline polygon_data& operator=(const T2& rvalue);
-
- /// get begin iterator, returns a pointer to a const Unit
- inline iterator_type begin() const { return coords_.begin(); }
-
- /// get end iterator, returns a pointer to a const Unit
- inline iterator_type end() const { return coords_.end(); }
-
- inline std::size_t size() const { return coords_.size(); }
-
-private:
- std::vector<coordinate_type> coords_;
+class polygon_data : public polygon_45_data<T> {
+ //inherits everything
 };
-

Modified: sandbox/gtl/gtl/polygon_formation.hpp
==============================================================================
--- sandbox/gtl/gtl/polygon_formation.hpp (original)
+++ sandbox/gtl/gtl/polygon_formation.hpp 2008-06-03 19:56:56 EDT (Tue, 03 Jun 2008)
@@ -560,17 +560,24 @@
     ActiveTail<Unit>* p_;
   public:
     typedef Unit coordinate_type;
- typedef typename ActiveTail<Unit>::iterator iterator_type;
+ typedef typename ActiveTail<Unit>::iterator compact_iterator_type;
+ typedef iterator_compact_to_points<compact_iterator_type, point_data<coordinate_type> > iterator_type;
     inline PolyLineHoleData() : p_(0) {}
     inline PolyLineHoleData(ActiveTail<Unit>* p) : p_(p) {}
     //use default copy and assign
- inline iterator_type begin() const { return p_->begin(true, (orientT ? VERTICAL : HORIZONTAL)); }
- inline iterator_type end() const { return p_->end(); }
+ inline compact_iterator_type begin_compact() const { return p_->begin(true, (orientT ? VERTICAL : HORIZONTAL)); }
+ inline compact_iterator_type end_compact() const { return p_->end(); }
+ inline iterator_type begin() const { return iterator_type(begin_compact(), end_compact()); }
+ inline iterator_type end() const { return iterator_type(end_compact(), end_compact()); }
     inline unsigned int size() const { return 0; }
     template<class iT>
     inline PolyLineHoleData& set(iT inputBegin, iT inputEnd) {
       return *this;
     }
+ template<class iT>
+ inline PolyLineHoleData& set_compact(iT inputBegin, iT inputEnd) {
+ return *this;
+ }
    
   };
 
@@ -580,7 +587,8 @@
     ActiveTail<Unit>* p_;
   public:
     typedef Unit coordinate_type;
- typedef typename ActiveTail<Unit>::iterator iterator_type;
+ typedef typename ActiveTail<Unit>::iterator compact_iterator_type;
+ typedef iterator_compact_to_points<compact_iterator_type, point_data<coordinate_type> > iterator_type;
     typedef PolyLineHoleData<orientT, Unit> hole_type;
     class iteratorHoles {
     private:
@@ -611,8 +619,10 @@
     inline PolyLinePolygonData() : p_(0) {}
     inline PolyLinePolygonData(ActiveTail<Unit>* p) : p_(p) {}
     //use default copy and assign
- inline iterator_type begin() const { return p_->begin(false, (orientT ? VERTICAL : HORIZONTAL)); }
- inline iterator_type end() const { return p_->end(); }
+ inline compact_iterator_type begin_compact() const { return p_->begin(false, (orientT ? VERTICAL : HORIZONTAL)); }
+ inline compact_iterator_type end_compact() const { return p_->end(); }
+ inline iterator_type begin() const { return iterator_type(begin_compact(), end_compact()); }
+ inline iterator_type end() const { return iterator_type(end_compact(), end_compact()); }
     inline iteratorHoles begin_holes() const { return iteratorHoles(p_->beginHoles()); }
     inline iteratorHoles end_holes() const { return iteratorHoles(p_->endHoles()); }
     inline ActiveTail<Unit>* yield() { return p_; }
@@ -623,6 +633,10 @@
     inline PolyLinePolygonData& set(iT inputBegin, iT inputEnd) {
       return *this;
     }
+ template<class iT>
+ inline PolyLinePolygonData& set_compact(iT inputBegin, iT inputEnd) {
+ return *this;
+ }
    
     /// initialize a polygon from x,y values, it is assumed that the first is an x
     /// and that the input is a well behaved polygon

Modified: sandbox/gtl/gtl/polygon_set_wrapper.hpp
==============================================================================
--- sandbox/gtl/gtl/polygon_set_wrapper.hpp (original)
+++ sandbox/gtl/gtl/polygon_set_wrapper.hpp 2008-06-03 19:56:56 EDT (Tue, 03 Jun 2008)
@@ -11,9 +11,9 @@
   const T& t_;
 public:
   typedef typename T::value_type geometry_type;
- typedef typename geometry_traits<geometry_type>::geometry_concept geometry_concept;
- typedef typename geometry_concept::template registration<geometry_type>::coordinate_type coordinate_type;
- typedef iterator_geometry_range_to_set<geometry_concept, typename T::const_iterator> iterator_type;
+ typedef typename geometry_concept<geometry_type>::type concept_type;
+ typedef typename concept_type::template registration<geometry_type>::coordinate_type coordinate_type;
+ typedef iterator_geometry_range_to_set<concept_type, typename T::const_iterator> iterator_type;
   typedef polygon_set_const_wrapper operator_arg_type;
   typedef operator_requires_copy operator_storage_tag;
 
@@ -46,9 +46,9 @@
   T& t_;
 public:
   typedef typename T::value_type geometry_type;
- typedef typename geometry_traits<geometry_type>::geometry_concept geometry_concept;
- typedef typename geometry_concept::template registration<geometry_type>::coordinate_type coordinate_type;
- typedef iterator_geometry_range_to_set<geometry_concept, typename T::const_iterator> iterator_type;
+ typedef typename geometry_concept<geometry_type>::type concept_type;
+ typedef typename concept_type::template registration<geometry_type>::coordinate_type coordinate_type;
+ typedef iterator_geometry_range_to_set<concept_type, typename T::const_iterator> iterator_type;
   typedef polygon_set_wrapper operator_arg_type;
   typedef operator_requires_copy operator_storage_tag;
 

Modified: sandbox/gtl/gtl/polygon_traits.hpp
==============================================================================
--- sandbox/gtl/gtl/polygon_traits.hpp (original)
+++ sandbox/gtl/gtl/polygon_traits.hpp 2008-06-03 19:56:56 EDT (Tue, 03 Jun 2008)
@@ -5,10 +5,11 @@
   Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   http://www.boost.org/LICENSE_1_0.txt).
 */
-template <class T>
+template <typename T>
 struct polygon_traits {
   typedef typename T::coordinate_type coordinate_type;
   typedef typename T::iterator_type iterator_type;
+ typedef typename T::compact_iterator_type compact_iterator_type;
 
   /// Get the begin iterator
   static inline iterator_type begin(const T& t) {
@@ -21,12 +22,29 @@
   }
   
   /// Set the data of a polygon with the unique coordinates in an iterator, starting with an x
- template <class iT>
+ template <typename iT>
   static inline T& set(T& t, iT input_begin, iT input_end) {
     t.set(input_begin, input_end);
     return t;
   }
   
+ /// Get the begin iterator
+ static inline compact_iterator_type begin_compact(const T& t) {
+ return t.begin_compact();
+ }
+
+ /// Get the end iterator
+ static inline compact_iterator_type end_compact(const T& t) {
+ return t.end_compact();
+ }
+
+ /// Set the data of a polygon with the unique coordinates in an iterator, starting with an x
+ template <typename iT>
+ static inline T& set_compact(T& t, iT input_begin, iT input_end) {
+ t.set_compact(input_begin, input_end);
+ return t;
+ }
+
   /// Get the number of sides of the polygon
   static inline unsigned int size(const T& t) {
     return t.size();

Modified: sandbox/gtl/gtl/polygon_with_holes_concept.hpp
==============================================================================
--- sandbox/gtl/gtl/polygon_with_holes_concept.hpp (original)
+++ sandbox/gtl/gtl/polygon_with_holes_concept.hpp 2008-06-03 19:56:56 EDT (Tue, 03 Jun 2008)
@@ -6,179 +6,8 @@
   http://www.boost.org/LICENSE_1_0.txt).
 */
 
-struct polygon_with_holes_concept : polygon_concept {
+struct polygon_with_holes_concept : virtual polygon_concept, polygon_45_with_holes_concept {
 public:
-
- template<typename polygon_with_holes_type, typename hole_iterator_type>
- static void set_holes(polygon_with_holes_type& polygon, hole_iterator_type holes_begin, hole_iterator_type holes_end) {
- polygon_with_holes_traits<polygon_with_holes_type>::set_holes(polygon, holes_begin, holes_end);
- }
-
- template <typename polygon_with_holes_type>
- static typename polygon_with_holes_traits<polygon_with_holes_type>::iterator_holes_type begin_holes(const polygon_with_holes_type& polygon) {
- return polygon_with_holes_traits<polygon_with_holes_type>::begin_holes(polygon);
- }
-
- template <typename polygon_with_holes_type>
- static typename polygon_with_holes_traits<polygon_with_holes_type>::iterator_holes_type end_holes(const polygon_with_holes_type& polygon) {
- return polygon_with_holes_traits<polygon_with_holes_type>::end_holes(polygon);
- }
-
- template <typename polygon_with_holes_type_1, typename polygon_with_holes_type_2>
- static polygon_with_holes_type_1 copy_construct(const polygon_with_holes_type_2& polygon) {
- polygon_with_holes_type_1 retval;
- set(retval, polygon_concept::begin(polygon), polygon_concept::end(polygon));
- set_holes(retval, polygon_with_holes_concept::begin_holes(polygon), polygon_with_holes_concept::end_holes(polygon));
- return retval;
- }
-
- template <typename polygon_with_holes_type>
- static std::size_t size_holes(const polygon_with_holes_type& polygon) {
- return polygon_with_holes_traits<polygon_with_holes_type>::size_holes(polygon);
- }
-
- template <typename polygon_with_holes_type_1, typename polygon_with_holes_type_2>
- static polygon_with_holes_type_1& assign(polygon_with_holes_type_1& lvalue, const polygon_with_holes_type_2& rvalue) {
- set(lvalue, polygon_concept::begin(rvalue), polygon_concept::end(rvalue));
- set_holes(lvalue, begin_holes(rvalue), end_holes(rvalue));
- return lvalue;
- }
-
- template <typename polygon_with_holes_type>
- static typename polygon_with_holes_traits<polygon_with_holes_type>::coordinate_type
- area(const polygon_with_holes_type& polygon) {
- typename polygon_traits<polygon_with_holes_type>::coordinate_type retval = polygon_concept::area(polygon);
- typename polygon_with_holes_traits<polygon_with_holes_type>::iterator_holes_type b, e;
- e = end_holes(polygon);
- for(b = begin_holes(polygon); b != e; ++b) {
- retval -= polygon_concept::area(*b);
- }
- }
-
- /// check if point is inside polygon
- template <typename polygon_with_holes_type, typename point_type>
- static bool contains(const polygon_with_holes_type& polygon, const point_type& point,
- bool consider_touch, point_concept pc) {
- typename polygon_with_holes_traits<polygon_with_holes_type>::iterator_holes_type b, e;
- e = end_holes(polygon);
- for(b = begin_holes(polygon); b != e; ++b) {
- if(polygon_concept::contains(*b, point, !consider_touch, pc)) {
- return false;
- }
- }
- return polygon_concept::contains(polygon, point, consider_touch, pc);
- }
-
- /// get the perimeter of the polygon
- template <typename polygon_with_holes_type>
- static typename polygon_traits<polygon_with_holes_type>::coordinate_type
- perimeter(const polygon_with_holes_type& polygon) {
- typename polygon_traits<polygon_with_holes_type>::coordinate_type retval = polygon_concept::perimeter(polygon);
- typename polygon_with_holes_traits<polygon_with_holes_type>::iterator_holes_type b, e;
- e = end_holes(polygon);
- for(b = begin_holes(polygon); b != e; ++b) {
- retval -= polygon_concept::perimeter(*b);
- }
- }
-
- // //awaiting re-implementation of iterator_edges and edge concept
- // template <typename polygon_with_holes_type, typename point_type>
- // static point_type project(const polygon_with_holes_type& polygon, const point_type& point) const {
- // typedef point_data<typename polygon_with_holes_traits<polygon_with_holes_type>::coordinate_type> point_type_2;
- // point_type_2 retval = polygon_concept::project(polygon, point);
- // double dist = point_concept::euclidian_distance(point retval);
- // polygon_with_holes_traits<polygon_with_holes_type>::iterator_holes_type b, e;
- // e = end_holes(polygon);
- // for(b = begin_holes(polygon); b != e; ++b) {
- // point_type_2 hole_point = polygon_concept::project(*b, point);
- // double hole_dist = point_concept::euclidian_distance(point hole_point);
- // if(hole_dist < dist) {
- // retval = hole_point;
- // dist = hole_dist;
- // }
- // }
- // return retval;
- // }
-
- // //awaiting re-implementation of iterator_edges and edge concept
- // template <typename polygon_with_holes_type, typename point_type>
- // static point_type project(point_type& result, const polygon_with_holes_type& polygon,
- // const point_type& point, direction_2d dir) {
- // typedef point_data<typename polygon_with_holes_traits<polygon_with_holes_type>::coordinate_type> point_type_2;
- // point_type_2 retval = polygon_concept::project(polygon, point, dir);
- // double dist = point_concept::euclidian_distance(point retval);
- // polygon_with_holes_traits<polygon_with_holes_type>::iterator_holes_type b, e;
- // e = end_holes(polygon);
- // for(b = begin_holes(polygon); b != e; ++b) {
- // point_type_2 hole_point = polygon_concept::project(*b, point, dir);
- // double hole_dist = point_concept::euclidian_distance(point hole_point);
- // if(hole_dist < dist) {
- // retval = hole_point;
- // dist = hole_dist;
- // }
- // }
- // return retval;
- // }
-
- template <typename polygon_with_holes_type, typename coordinate_type_1, typename coordinate_type_2>
- static void move(polygon_with_holes_type& polygon, coordinate_type_1 x_displacement, coordinate_type_2 y_displacement) {
- typedef typename polygon_with_holes_traits<polygon_with_holes_type>::hole_type hole_type;
- std::vector<hole_type> holes;
- holes.resize(size_holes(polygon));
- typename polygon_with_holes_traits<polygon_with_holes_type>::iterator_holes_type b, e;
- e = end_holes(polygon);
- for(b = begin_holes(polygon); b != e; ++b) {
- holes.push_back(*b);
- polygon_concept::move(holes.back(), x_displacement, y_displacement);
- }
- set_holes(polygon, holes.begin(), holes.end());
- polygon_concept::move(polygon, x_displacement, y_displacement);
- }
-
- /// move polygon by delta in orient
- template <typename polygon_with_holes_type, typename coordinate_type_1>
- static void move(polygon_with_holes_type& polygon, orientation_2d orient, coordinate_type_1 displacement) {
- if(orient == HORIZONTAL) {
- move(polygon, displacement, 0);
- } else {
- move(polygon, 0, displacement);
- }
- }
+ inline polygon_with_holes_concept() {}
+ //inherits its behaviors
 };
-
-template <typename T>
-inline void testPolygonWithHolesImpl() {
- rectangle_data<T> rect = rectangle_concept::construct<rectangle_data<T> >(0, 0, 100, 100);
- polygon_data<T> polyHole = polygon_concept::construct_from_rectangle<polygon_data<T> >(rectangle_concept::construct<rectangle_data<T> >(10, 10, 90, 90));
- polygon_with_holes_data<T> pwh = polygon_with_holes_concept::construct_from_rectangle<polygon_with_holes_data<T> >(rect);
- polygon_with_holes_concept::set_holes(pwh, &polyHole, (&polyHole)+1);
- //std::cout << pwh << std::endl;
- std::cout << "PolygonWithHoles test pattern 1 1 1 1 1 1 0 0 0 0 0 0\n";
- std::cout << "PolygonWithHoles test pattern ";
- std::cout << polygon_with_holes_concept::contains(pwh, point_data<T>(1, 11), true, point_concept())
- << " " ;
- std::cout << polygon_with_holes_concept::contains(pwh, point_data<T>(10, 10), true, point_concept())
- << " " ;
- std::cout << polygon_with_holes_concept::contains(pwh, point_data<T>(10, 90), true, point_concept())
- << " " ;
- std::cout << polygon_with_holes_concept::contains(pwh, point_data<T>(90, 90), true, point_concept())
- << " " ;
- std::cout << polygon_with_holes_concept::contains(pwh, point_data<T>(90, 10), true, point_concept())
- << " " ;
- std::cout << polygon_with_holes_concept::contains(pwh, point_data<T>(90, 80), true, point_concept())
- << " " ;
- std::cout << polygon_with_holes_concept::contains(pwh, point_data<T>(12, 12), true, point_concept())
- << " " ;
- std::cout << polygon_with_holes_concept::contains(pwh, point_data<T>(10, 10), false, point_concept())
- << " " ;
- std::cout << polygon_with_holes_concept::contains(pwh, point_data<T>(10, 90), false, point_concept())
- << " " ;
- std::cout << polygon_with_holes_concept::contains(pwh, point_data<T>(90, 90), false, point_concept())
- << " " ;
- std::cout << polygon_with_holes_concept::contains(pwh, point_data<T>(90, 10), false, point_concept())
- << " " ;
- std::cout << polygon_with_holes_concept::contains(pwh, point_data<T>(90, 80), false, point_concept())
- << "\n";
-
- polygon_with_holes_concept::move(pwh, 5, 5);
-}

Modified: sandbox/gtl/gtl/polygon_with_holes_data.hpp
==============================================================================
--- sandbox/gtl/gtl/polygon_with_holes_data.hpp (original)
+++ sandbox/gtl/gtl/polygon_with_holes_data.hpp 2008-06-03 19:56:56 EDT (Tue, 03 Jun 2008)
@@ -7,76 +7,6 @@
 */
 
 template <typename T>
-class polygon_with_holes_data {
-public:
- typedef T coordinate_type;
- typedef typename std::vector<coordinate_type>::const_iterator iterator_type;
- typedef typename std::list<polygon_data<coordinate_type> >::const_iterator iterator_holes_type;
- typedef polygon_data<coordinate_type> hole_type;
-
- /// default constructor of point does not initialize x and y
- inline polygon_with_holes_data(){;} //do nothing default constructor
-
- /// initialize a polygon from x,y values, it is assumed that the first is an x
- /// and that the input is a well behaved polygon
- template<class iT>
- inline polygon_with_holes_data& set(iT input_begin, iT input_end) {
- self_.set(input_begin, input_end);
- return *this;
- }
-
- /// initialize a polygon from x,y values, it is assumed that the first is an x
- /// and that the input is a well behaved polygon
- template<class iT>
- inline polygon_with_holes_data& set_holes(iT input_begin, iT input_end) {
- holes_.clear(); //just in case there was some old data there
- for( ; input_begin != input_end; ++ input_begin) {
- holes_.push_back(hole_type());
- holes_.back().set((*input_begin).begin(), (*input_begin).end());
- }
- return *this;
- }
-
- /// copy constructor (since we have dynamic memory)
- inline polygon_with_holes_data(const polygon_with_holes_data& that) : self_(that.self_),
- holes_(that.holes_) {}
-
- /// assignment operator (since we have dynamic memory do a deep copy)
- inline polygon_with_holes_data& operator=(const polygon_with_holes_data& that) {
- self_ = that.self_;
- holes_ = that.holes_;
- return *this;
- }
-
- /// get begin iterator, returns a pointer to a const coordinate_type
- inline const iterator_type begin() const {
- return self_.begin();
- }
-
- /// get end iterator, returns a pointer to a const coordinate_type
- inline const iterator_type end() const {
- return self_.end();
- }
-
- inline unsigned int size() const {
- return self_.size();
- }
-
- /// get begin iterator, returns a pointer to a const polygon
- inline const iterator_holes_type begin_holes() const {
- return holes_.begin();
- }
-
- /// get end iterator, returns a pointer to a const polygon
- inline const iterator_holes_type end_holes() const {
- return holes_.end();
- }
-
- inline unsigned int size_holes() const {
- return holes_.size();
- }
-
-private:
- polygon_data<coordinate_type> self_;
- std::list<hole_type> holes_;
+class polygon_with_holes_data : public polygon_45_with_holes_data<T> {
+ //inherits everything
 };

Modified: sandbox/gtl/gtl/polygon_with_holes_traits.hpp
==============================================================================
--- sandbox/gtl/gtl/polygon_with_holes_traits.hpp (original)
+++ sandbox/gtl/gtl/polygon_with_holes_traits.hpp 2008-06-03 19:56:56 EDT (Tue, 03 Jun 2008)
@@ -8,7 +8,6 @@
 
 template <class T>
 struct polygon_with_holes_traits {
- typedef typename T::coordinate_type coordinate_type;
   typedef typename T::iterator_holes_type iterator_holes_type;
   typedef typename T::hole_type hole_type;
 
@@ -23,7 +22,7 @@
   }
 
   /// Set the data of a polygon with the unique coordinates in an iterator, starting with an x
- template <class iT>
+ template <typename iT>
   static inline T& set_holes(T& t, iT inputBegin, iT inputEnd) {
     t.set_holes(inputBegin, inputEnd);
     return t;

Modified: sandbox/gtl/gtl/post_concept_definitions.hpp
==============================================================================
--- sandbox/gtl/gtl/post_concept_definitions.hpp (original)
+++ sandbox/gtl/gtl/post_concept_definitions.hpp 2008-06-03 19:56:56 EDT (Tue, 03 Jun 2008)
@@ -35,6 +35,12 @@
 
 template <class T>
 template <class T2>
+bool rectangle_data<T>::operator==(const T2& rvalue) const {
+ return rectangle_concept::equivalence(*this, rvalue);
+}
+
+template <class T>
+template <class T2>
 point_3d_data<T>& point_3d_data<T>::operator=(const T2& rvalue) {
   point_3d_concept::assign(*this, rvalue);
   return *this;
@@ -42,8 +48,8 @@
 
 template <class T>
 template <class T2>
-polygon_data<T>& polygon_data<T>::operator=(const T2& rvalue) {
- polygon_concept::assign(*this, rvalue);
+polygon_90_data<T>& polygon_90_data<T>::operator=(const T2& rvalue) {
+ polygon_90_concept::assign(*this, rvalue);
   return *this;
 }
 

Modified: sandbox/gtl/gtl/post_geometry_traits_definitions.hpp
==============================================================================
--- sandbox/gtl/gtl/post_geometry_traits_definitions.hpp (original)
+++ sandbox/gtl/gtl/post_geometry_traits_definitions.hpp 2008-06-03 19:56:56 EDT (Tue, 03 Jun 2008)
@@ -8,7 +8,19 @@
 
 template <typename geometry_type>
 struct component_type {
- typedef typename geometry_traits<geometry_type>::geometry_concept::template
+ typedef typename geometry_concept<geometry_type>::type::template
   registration<geometry_type>::component_type type;
 };
 
+template <typename geometry_type>
+struct coordinate_type {
+ typedef typename geometry_concept<geometry_type>::type::template
+ registration<geometry_type>::coordinate_type type;
+};
+
+template <typename geometry_type>
+struct center_type {
+ typedef typename geometry_concept<geometry_type>::type::template
+ registration<geometry_type>::center_type type;
+};
+

Modified: sandbox/gtl/gtl/rectangle_concept.hpp
==============================================================================
--- sandbox/gtl/gtl/rectangle_concept.hpp (original)
+++ sandbox/gtl/gtl/rectangle_concept.hpp 2008-06-03 19:56:56 EDT (Tue, 03 Jun 2008)
@@ -12,6 +12,7 @@
   struct registration {
     typedef typename rectangle_traits<rectangle_type>::coordinate_type coordinate_type;
     typedef interval_data<coordinate_type> component_type;
+ typedef point_data<coordinate_type> center_type;
   };
 
   template <orientation_2d_enum orient, typename T>
@@ -26,6 +27,18 @@
     return rectangle_traits<T>::get(rectangle, orient);
   }
 
+ template <typename T>
+ static inline typename rectangle_traits<T>::interval_type
+ horizontal(const T& rectangle) {
+ return rectangle_traits<T>::get(rectangle, HORIZONTAL);
+ }
+
+ template <typename T>
+ static inline typename rectangle_traits<T>::interval_type
+ vertical(const T& rectangle) {
+ return rectangle_traits<T>::get(rectangle, VERTICAL);
+ }
+
   template <orientation_2d_enum orient, typename T, typename T2>
   static inline void set(T& rectangle, const T2& interval) {
     rectangle_traits<T>::set(rectangle, orient, interval);
@@ -36,6 +49,16 @@
     rectangle_traits<T>::set(rectangle, orient, interval);
   }
 
+ template <typename T, typename T2>
+ static inline void horizontal(T& rectangle, const T2& interval) {
+ rectangle_traits<T>::set(rectangle, HORIZONTAL, interval);
+ }
+
+ template <typename T, typename T2>
+ static inline void vertical(T& rectangle, const T2& interval) {
+ rectangle_traits<T>::set(rectangle, VERTICAL, interval);
+ }
+
   template <typename T, typename T2, typename T3>
   static inline T construct(const T2& interval_horizontal,
                             const T3& interval_vertical) {
@@ -70,27 +93,75 @@
   }
 
   template <typename rectangle_type>
+ static inline typename rectangle_traits<rectangle_type>::coordinate_type
+ get(const rectangle_type& rectangle, orientation_2d orient, direction_1d dir) {
+ return interval_concept::get(rectangle_traits<rectangle_type>::get(rectangle, orient), dir);
+ }
+
+ template <direction_1d_enum dir, typename rectangle_type>
+ static inline typename rectangle_traits<rectangle_type>::coordinate_type
+ get(const rectangle_type& rectangle, orientation_2d orient) {
+ return get(rectangle, orient, dir);
+ }
+
+ template <typename rectangle_type>
+ static inline void set(rectangle_type& rectangle, orientation_2d orient, direction_1d dir,
+ typename rectangle_traits<rectangle_type>::coordinate_type value) {
+ typename rectangle_traits<rectangle_type>::interval_type ivl = orient(rectangle);
+ interval_concept::set(ivl, dir, value);
+ set(rectangle, orient, ivl);
+ }
+
+ template <direction_1d_enum dir, typename rectangle_type>
+ static inline void set(rectangle_type& rectangle, orientation_2d orient,
+ typename rectangle_traits<rectangle_type>::coordinate_type value) {
+ typename rectangle_traits<rectangle_type>::interval_type ivl = get(rectangle, orient);
+ interval_concept::set(ivl, dir, value);
+ set(rectangle, orient, ivl);
+ }
+
+ template <typename rectangle_type>
   static typename rectangle_traits<rectangle_type>::coordinate_type
   xl(const rectangle_type& rectangle) {
- return interval_concept::get<LOW>(get<HORIZONTAL>(rectangle));
+ return get<LOW>(rectangle, HORIZONTAL);
+ }
+
+ template <typename rectangle_type>
+ static void xl(rectangle_type& rectangle, typename rectangle_traits<rectangle_type>::coordinate_type value) {
+ return set<LOW>(rectangle, HORIZONTAL, value);
   }
 
   template <typename rectangle_type>
   static typename rectangle_traits<rectangle_type>::coordinate_type
   xh(const rectangle_type& rectangle) {
- return interval_concept::get<HIGH>(get<HORIZONTAL>(rectangle));
+ return get<HIGH>(rectangle, HORIZONTAL);
+ }
+
+ template <typename rectangle_type>
+ static void xh(rectangle_type& rectangle, typename rectangle_traits<rectangle_type>::coordinate_type value) {
+ return set<HIGH>(rectangle, HORIZONTAL, value);
   }
 
   template <typename rectangle_type>
   static typename rectangle_traits<rectangle_type>::coordinate_type
   yl(const rectangle_type& rectangle) {
- return interval_concept::get<LOW>(get<VERTICAL>(rectangle));
+ return get<LOW>(rectangle, VERTICAL);
+ }
+
+ template <typename rectangle_type>
+ static void yl(rectangle_type& rectangle, typename rectangle_traits<rectangle_type>::coordinate_type value) {
+ return set<LOW>(rectangle, VERTICAL, value);
   }
 
   template <typename rectangle_type>
   static typename rectangle_traits<rectangle_type>::coordinate_type
   yh(const rectangle_type& rectangle) {
- return interval_concept::get<HIGH>(get<VERTICAL>(rectangle));
+ return get<HIGH>(rectangle, VERTICAL);
+ }
+
+ template <typename rectangle_type>
+ static void yh(rectangle_type& rectangle, typename rectangle_traits<rectangle_type>::coordinate_type value) {
+ return set<HIGH>(rectangle, VERTICAL, value);
   }
 
   template <typename rectangle_type, typename rectangle_type2>
@@ -102,10 +173,444 @@
   template <typename rectangle_type, typename point_type>
   static bool contains(const rectangle_type& rectangle, const point_type point_contained,
                                 bool consider_touch, point_concept tag) {
- return interval_concept::contains(get<HORIZONTAL>(rectangle), point_concept::get<HORIZONTAL>(point_contained), consider_touch) &&
- interval_concept::contains(get<VERTICAL>(rectangle), point_concept::get<VERTICAL>(point_contained), consider_touch);
+ return interval_concept::contains(get<HORIZONTAL>(rectangle), point_concept::get<HORIZONTAL>(point_contained), consider_touch, no_type()) &&
+ interval_concept::contains(get<VERTICAL>(rectangle), point_concept::get<VERTICAL>(point_contained), consider_touch, no_type());
+ }
+
+ /// set all four coordinates based upon two points
+ template <typename rectangle_type, typename point_type_1, typename point_type_2>
+ static rectangle_type& set_points(rectangle_type& rectangle, const point_type_1& p1,
+ const point_type_2& p2) {
+ typedef typename rectangle_traits<rectangle_type>::coordinate_type Unit;
+ Unit x1(point_concept::x(p1));
+ Unit x2(point_concept::x(p2));
+ Unit y1(point_concept::y(p1));
+ Unit y2(point_concept::y(p2));
+ horizontal(rectangle, interval_concept::construct<typename rectangle_traits<rectangle_type>::interval_type>(x1, x2));
+ vertical(rectangle, interval_concept::construct<typename rectangle_traits<rectangle_type>::interval_type>(y1, y2));
+ return rectangle;
+ }
+
+ /// move rectangle by delta in orient
+ template <typename rectangle_type>
+ static rectangle_type& move(rectangle_type& rectangle, orientation_2d orient,
+ typename rectangle_traits<rectangle_type>::coordinate_type delta) {
+ typename rectangle_traits<rectangle_type>::interval_type ivl = get(rectangle, orient);
+ interval_concept::move(ivl, delta);
+ set(rectangle, orient, ivl);
+ return rectangle;
+ }
+
+ //awaiting transform re-implementation
+ // /// transform rectangle
+ // RectangleImpl& transform(const AxisTransform& atr);
+
+ // /// transform rectangle
+ // RectangleImpl& transform(const Transform& tr);
+
+ /// convolve this with b
+ template <typename rectangle_type_1, typename rectangle_type_2>
+ static rectangle_type_1& convolve(rectangle_type_1& rectangle,
+ const rectangle_type_2& convolution_rectangle,
+ rectangle_concept tag) {
+ typename rectangle_traits<rectangle_type_1>::interval_type ivl = horizontal(rectangle);
+ horizontal(rectangle,
+ interval_concept::convolve(ivl,
+ horizontal(convolution_rectangle),
+ interval_concept()));
+ ivl = vertical(rectangle);
+ vertical(rectangle,
+ interval_concept::convolve(ivl,
+ vertical(convolution_rectangle),
+ interval_concept()));
+ return rectangle;
+ }
+
+ /// deconvolve this with b
+ template <typename rectangle_type_1, typename rectangle_type_2>
+ static rectangle_type_1& deconvolve(rectangle_type_1& rectangle,
+ const rectangle_type_2& convolution_rectangle,
+ rectangle_concept tag) {
+ typename rectangle_traits<rectangle_type_1>::interval_type ivl = horizontal(rectangle);
+ horizontal(rectangle,
+ interval_concept::deconvolve(ivl,
+ horizontal(convolution_rectangle),
+ interval_concept()));
+ ivl = vertical(rectangle);
+ vertical(rectangle,
+ interval_concept::deconvolve(ivl,
+ vertical(convolution_rectangle),
+ interval_concept()));
+ return rectangle;
+ }
+
+ /// reflectedConvolve this with b
+ template <typename rectangle_type_1, typename rectangle_type_2>
+ static rectangle_type_1& reflected_convolve(rectangle_type_1& rectangle,
+ const rectangle_type_2& convolution_rectangle,
+ rectangle_concept tag) {
+ typename rectangle_traits<rectangle_type_1>::interval_type ivl = horizontal(rectangle);
+ horizontal(rectangle,
+ interval_concept::reflected_convolve(ivl,
+ horizontal(convolution_rectangle),
+ interval_concept()));
+ ivl = vertical(rectangle);
+ vertical(rectangle,
+ interval_concept::reflected_convolve(ivl,
+ vertical(convolution_rectangle),
+ interval_concept()));
+ return rectangle;
+ }
+
+ /// reflectedDeconvolve this with b
+ /// deconvolve this with b
+ template <typename rectangle_type_1, typename rectangle_type_2>
+ static rectangle_type_1& reflected_deconvolve(rectangle_type_1& rectangle,
+ const rectangle_type_2& convolution_rectangle,
+ rectangle_concept tag) {
+ typename rectangle_traits<rectangle_type_1>::interval_type ivl = horizontal(rectangle);
+ horizontal(rectangle,
+ interval_concept::reflected_deconvolve(ivl,
+ horizontal(convolution_rectangle),
+ interval_concept()));
+ ivl = vertical(rectangle);
+ vertical(rectangle,
+ interval_concept::reflected_deconvolve(ivl,
+ vertical(convolution_rectangle),
+ interval_concept()));
+ return rectangle;
+ }
+
+ /// convolve with point
+ template <typename rectangle_type, typename point_type>
+ static rectangle_type& convolve(rectangle_type& rectangle,
+ const point_type& convolution_point,
+ point_concept tag) {
+ typename rectangle_traits<rectangle_type>::interval_type ivl = horizontal(rectangle);
+ horizontal(rectangle,
+ interval_concept::convolve(ivl,
+ point_concept::x(convolution_point),
+ no_type()));
+ ivl = vertical(rectangle);
+ vertical(rectangle,
+ interval_concept::convolve(ivl,
+ point_concept::y(convolution_point),
+ no_type()));
+ return rectangle;
+ }
+
+ /// deconvolve with point
+ template <typename rectangle_type, typename point_type>
+ static rectangle_type& deconvolve(rectangle_type& rectangle,
+ const point_type& convolution_point,
+ point_concept tag) {
+ typename rectangle_traits<rectangle_type>::interval_type ivl = horizontal(rectangle);
+ horizontal(rectangle,
+ interval_concept::deconvolve(ivl,
+ point_concept::x(convolution_point),
+ no_type()));
+ ivl = vertical(rectangle);
+ vertical(rectangle,
+ interval_concept::deconvolve(ivl,
+ point_concept::y(convolution_point),
+ no_type()));
+ return rectangle;
+ }
+
+ /// get the magnitude of the interval range depending on orient
+ template <typename rectangle_type>
+ static typename rectangle_traits<rectangle_type>::coordinate_type
+ delta(const rectangle_type& rectangle, orientation_2d orient) {
+ return interval_concept::delta(get(rectangle, orient));
+ }
+
+ /// get the area of the rectangle
+ template <typename rectangle_type>
+ static typename rectangle_traits<rectangle_type>::coordinate_type
+ area(const rectangle_type& rectangle) {
+ return delta(rectangle, HORIZONTAL) * delta(rectangle, VERTICAL);
+ }
+
+ /// returns the orientation of the longest side
+ template <typename rectangle_type>
+ static orientation_2d guess_orientation(const rectangle_type& rectangle) {
+ return delta(rectangle, HORIZONTAL) >= delta(rectangle, VERTICAL) ?
+ HORIZONTAL : VERTICAL;
+ }
+
+ /// get the half perimeter of the rectangle
+ template <typename rectangle_type>
+ static typename rectangle_traits<rectangle_type>::coordinate_type
+ half_perimeter(const rectangle_type& rectangle) {
+ return delta(rectangle, HORIZONTAL) + delta(rectangle, VERTICAL);
+ }
+
+ /// get the perimeter of the rectangle
+ template <typename rectangle_type>
+ static typename rectangle_traits<rectangle_type>::coordinate_type
+ perimeter(const rectangle_type& rectangle) {
+ return 2 * half_perimeter(rectangle);
+ }
+
+ /// check if Rectangle b intersects `this` Rectangle
+ // [in] b Rectangle that will be checked
+ // [in] considerTouch If true, return true even if b touches the boundary
+ // [ret] . true if `t` intersects b
+ template <typename rectangle_type_1, typename rectangle_type_2>
+ static bool intersects(const rectangle_type_1& rectangle, const rectangle_type_2& b,
+ bool consider_touch, rectangle_concept tag) {
+ return interval_concept::intersects(horizontal(rectangle), horizontal(b), consider_touch,
+ interval_concept()) &&
+ interval_concept::intersects(vertical(rectangle), vertical(b), consider_touch,
+ interval_concept());
+ }
+
+ /// Check if boundaries of Rectangle b and `this` Rectangle intersect
+ // [in] b Rectangle that will be checked
+ // [in] considerTouch If true, return true even if p is on the foundary
+ // [ret] . true if `t` contains p
+ template <typename rectangle_type_1, typename rectangle_type_2>
+ static bool boundaries_intersect(const rectangle_type_1& rectangle, const rectangle_type_2& b,
+ bool consider_touch, rectangle_concept tag) {
+ return (intersects(rectangle, b, consider_touch) &&
+ !(contains(rectangle, b, !consider_touch)) &&
+ !(contains(b, rectangle, !consider_touch)));
+ }
+
+ /// check if b is touching 'this' on the end specified by dir
+ template <typename rectangle_type_1, typename rectangle_type_2>
+ static bool abuts(const rectangle_type_1& rectangle, const rectangle_type_2& b,
+ direction_2d dir, rectangle_concept tag) {
+ return
+ interval_concept::abuts(get(rectangle, orientation_2d(dir)),
+ get(b, orientation_2d(dir)),
+ direction_1d(dir), interval_concept()) &&
+ interval_concept::intersects(get(rectangle, orientation_2d(dir).get_perpendicular()),
+ get(b, orientation_2d(dir).get_perpendicular()),
+ true, interval_concept());
+ }
+
+ /// check if they are touching in the given orientation
+ template <typename rectangle_type_1, typename rectangle_type_2>
+ static bool abuts(const rectangle_type_1& rectangle, const rectangle_type_2& b,
+ orientation_2d orient, rectangle_concept tag) {
+ return
+ interval_concept::abuts(get(rectangle, orient), get(b, orient), interval_concept()) &&
+ interval_concept::intersects(get(rectangle, orient.get_perpendicular()),
+ get(b, orient.get_perpendicular()),
+ true, interval_concept());
+ }
+
+ /// check if they are touching but not overlapping
+ template <typename rectangle_type_1, typename rectangle_type_2>
+ static bool abuts(const rectangle_type_1& rectangle, const rectangle_type_2& b,
+ rectangle_concept tag) {
+ return abuts(rectangle, b, HORIZONTAL) || abuts(rectangle, b, VERTICAL);
   }
 
+ /// intersect rectangle with interval on orient
+ template <typename rectangle_type, typename interval_type>
+ static bool intersect(const rectangle_type& rectangle, const interval_type& b,
+ orientation_2d orient, bool consider_touch, interval_concept tag) {
+ typename rectangle_traits<rectangle_type>::interval_type ivl = get(rectangle, orient);
+ if(interval_concept::intersect(ivl, b, consider_touch, tag)) {
+ set(rectangle, orient, ivl);
+ return true;
+ }
+ return false;
+ }
+
+ /// clip rectangle to b
+ template <typename rectangle_type_1, typename rectangle_type_2>
+ static bool intersect(const rectangle_type_1& rectangle, const rectangle_type_2& b,
+ bool consider_touch, rectangle_concept tag) {
+ if(intersects(rectangle, b)) {
+ intersect(rectangle, horizontal(b), HORIZONTAL, consider_touch, interval_concept());
+ intersect(rectangle, vertical(b), VERTICAL, consider_touch, interval_concept());
+ return true;
+ }
+ return false;
+ }
+
+ /// Sets this to the generalized intersection of this and the given rectangle
+ template <typename rectangle_type_1, typename rectangle_type_2>
+ static rectangle_type_1& generalized_intersect(rectangle_type_1& rectangle,
+ const rectangle_type_2& b, rectangle_concept tag) {
+ typename rectangle_traits<rectangle_type_1>::interval_type ivl = get(rectangle, HORIZONTAL);
+ interval_concept::generalized_intersect(ivl, horizontal(b), interval_concept());
+ horizontal(rectangle, ivl);
+ ivl = vertical(rectangle);
+ interval_concept::generalized_intersect(ivl, vertical(b), interval_concept());
+ vertical(rectangle, ivl);
+ return rectangle;
+ }
+
+ /// bloat the interval specified by orient by bloating
+ template <typename rectangle_type>
+ static rectangle_type& bloat(rectangle_type& rectangle, orientation_2d orient,
+ typename rectangle_traits<rectangle_type>::coordinate_type bloating) {
+ typename rectangle_traits<rectangle_type>::interval_type ivl = get(rectangle, orient);
+ interval_concept::bloat(ivl, bloating);
+ set(rectangle, orient, ivl);
+ return rectangle;
+ }
+
+ /// bloat the Rectangle by bloating
+ template <typename rectangle_type>
+ static rectangle_type& bloat(rectangle_type& rectangle,
+ typename rectangle_traits<rectangle_type>::coordinate_type bloating) {
+ bloat(rectangle, HORIZONTAL, bloating);
+ return bloat(rectangle, VERTICAL, bloating);
+ }
+
+ /// bloat the interval cooresponding to orient by bloating in dir direction
+ template <typename rectangle_type>
+ static rectangle_type& bloat(rectangle_type& rectangle, direction_2d dir,
+ typename rectangle_traits<rectangle_type>::coordinate_type bloating) {
+ typename rectangle_traits<rectangle_type>::interval_type ivl = get(rectangle, orientation_2d(dir));
+ interval_concept::bloat(ivl, direction_1d(dir), bloating);
+ set(rectangle, orientation_2d(dir), ivl);
+ return rectangle;
+ }
+
+ /// shrink the interval specified by orient by bloating
+ template <typename rectangle_type>
+ static rectangle_type& shrink(rectangle_type& rectangle, orientation_2d orient,
+ typename rectangle_traits<rectangle_type>::coordinate_type shrinking) {
+ return bloat(rectangle, orient, -shrinking);
+ }
+
+ /// shrink the Rectangle by bloating
+ template <typename rectangle_type>
+ static rectangle_type& shrink(rectangle_type& rectangle,
+ typename rectangle_traits<rectangle_type>::coordinate_type shrinking) {
+ return bloat(rectangle, -shrinking);
+ }
+
+ /// shrink the interval cooresponding to orient by bloating in dir direction
+ template <typename rectangle_type>
+ static rectangle_type& shrink(rectangle_type& rectangle, direction_2d dir,
+ typename rectangle_traits<rectangle_type>::coordinate_type shrinking) {
+ return bloat(rectangle, dir, -shrinking);
+ }
+
+ /// encompass interval on orient
+ template <typename rectangle_type, typename interval_type>
+ static bool encompass(const rectangle_type& rectangle, const interval_type& b,
+ orientation_2d orient, interval_concept tag) {
+ typename rectangle_traits<rectangle_type>::interval_type ivl = get(rectangle, orient);
+ if(interval_concept::encompass(ivl, b, tag)) {
+ set(rectangle, orient, ivl);
+ return true;
+ }
+ return false;
+ }
+
+ /// enlarge rectangle to encompass the Rectangle b
+ template <typename rectangle_type_1, typename rectangle_type_2>
+ static bool encompass(rectangle_type_1& rectangle, const rectangle_type_2& b,
+ rectangle_concept tag) {
+ //note that operator | is intentional because both should be called regardless
+ return encompass(rectangle, horizontal(b), HORIZONTAL, interval_concept()) |
+ encompass(rectangle, vertical(b), VERTICAL, interval_concept());
+ }
+
+ //for consistency we should have encompass(rectangle, point) and encompass(interval, coordinate)
+
+ /// returns the center of the rectangle
+ template <typename rectangle_type>
+ static inline typename registration<rectangle_type>::center_type
+ center(const rectangle_type& rectangle) {
+ return typename registration<rectangle_type>::center_type(interval_concept::center(horizontal(rectangle)),
+ interval_concept::center(vertical(rectangle)));
+ }
+
+ template <typename rectangle_type>
+ static typename registration<rectangle_type>::center_type
+ get_corner(const rectangle_type& rectangle, direction_2d direction_facing, direction_1d direction_turning) {
+ typedef typename rectangle_traits<rectangle_type>::coordinate_type Unit;
+ Unit u1 = get(rectangle, direction_facing);
+ Unit u2 = get(rectangle, direction_facing.turn(direction_turning));
+ if(orientation_2d(direction_facing).to_int()) std::swap(u1, u2);
+ return point_concept::construct<typename registration<rectangle_type>::center_type>(u1, u2);
+ }
+
+ template <typename rectangle_type>
+ static rectangle_type get_half(const rectangle_type& rectangle, direction_2d dir) {
+ rectangle_type retval(rectangle);
+ set(retval, orientation_2d(dir),
+ interval_concept::get_half(get(rectangle, orientation_2d(dir)), direction_1d(dir)));
+ return retval;
+ }
+
+ template <typename rectangle_type_1, typename rectangle_type_2>
+ static bool join_with(rectangle_type_1& rectangle, const rectangle_type_2& b) {
+ typedef typename rectangle_traits<rectangle_type_1>::interval_type Interval1;
+ typedef typename rectangle_traits<rectangle_type_2>::interval_type Interval2;
+ Interval1 hi1 = get(rectangle, HORIZONTAL);
+ Interval1 vi1 = get(rectangle, VERTICAL);
+ Interval2 hi2 = get(b, HORIZONTAL), vi2 = get(b, VERTICAL);
+ Interval1 temp;
+ if (interval_concept::equivalence(hi1, hi2) && interval_concept::join_with(vi1, vi2)) {
+ vertical(rectangle, vi1);
+ return true;
+ }
+ if (interval_concept::equivalence(vi1, vi2) && interval_concept::join_with(hi1, hi2)) {
+ horizontal(rectangle, hi1);
+ return true;
+ }
+ return false;
+ }
+
+ //TODO: Add distance_type<geometry_type>::type and difference_type<geometry_type>::type
+
+// /// Returns the euclidian distance between the edge of the
+// /// rectangle and the point. Returns 0 if point is inside the
+// /// rectangle
+// template <class T2>
+// double
+// euclidianDistance(const PointImpl<T2> & p) const;
+
+// /// Returns the square of the euclidian distance between the edge of the
+// /// rectangle and the point. Returns 0 if point is inside the
+// /// rectangle
+// template <class T2>
+// UnsignedLongUnit
+// squareEuclidianDistance(const PointImpl<T2> & p) const;
+
+// /// Returns the manhattan distance (deltax + deltay) between the
+// /// edge of the rectangle and the point. Returns 0 if point is
+// /// inside the rectangle
+// template <class T2>
+// double
+// manhattanDistance(const PointImpl<T2> & p) const;
+
+// /// Returns the distance between this rectangle and a unit or a point
+// /// returns 0 if point or coordinate lies within
+// /// the range of the rectangle
+// Unit distance(Unit u, Orientation2D o) const;
+// template <class T2>
+// Unit distance(const PointImpl<T2> & p, Orientation2D o) const;
+
+// /// Returns the distance between two rectangles along the given orientation
+// template <class T2>
+// Unit distance(const RectangleImpl<T2> & r2, Orientation2D o) const;
+
+// /// Returns closest euclidian distance between the edges of the two rectangles.
+// /// Returns 0 if they overlap or touch
+// template <class T2>
+// double euclidianDistance(const RectangleImpl<T2> & r2) const;
+
+// /// Returns the square of the closest euclidian distance between the edges of the two rectangles.
+// /// Returns 0 if they overlap or touch
+// template <class T2>
+// UnsignedLongUnit squareEuclidianDistance(const RectangleImpl<T2> & r2) const;
+
+// /// Returns manhattan distance (deltax + deltay) between the two rectangles
+// /// Returns 0 if they overlap or touch
+// template <class T2>
+// Unit manhattanDistance(const RectangleImpl<T2> & r2) const;
+
   template <typename rectangle_type_1, typename rectangle_type_2>
   class less : public std::binary_function<const rectangle_type_1&, const rectangle_type_2&, bool> {
   private:

Modified: sandbox/gtl/gtl/rectangle_data.hpp
==============================================================================
--- sandbox/gtl/gtl/rectangle_data.hpp (original)
+++ sandbox/gtl/gtl/rectangle_data.hpp 2008-06-03 19:56:56 EDT (Tue, 03 Jun 2008)
@@ -23,6 +23,11 @@
   template <typename T2>
   inline rectangle_data& operator=(const T2& rvalue);
 
+ template <typename T2>
+ inline bool operator==(const T2& rvalue) const;
+ template <typename T2>
+ inline bool operator!=(const T2& rvalue) const { return !((*this) == rvalue); }
+
   inline interval_data<coordinate_type> get(orientation_2d orient) const {
     return ranges_[orient.to_int()]; }
   inline coordinate_type get(direction_2d dir) const {
@@ -37,3 +42,8 @@
   interval_data<coordinate_type> ranges_[2];
 };
 
+template <class T>
+std::ostream& operator << (std::ostream& o, const rectangle_data<T>& r)
+{
+ return o << r.get(HORIZONTAL) << ' ' << r.get(VERTICAL);
+}

Date view Thread view Subject view Author view