Subject: [Boost-commit] svn:boost r56634 - sandbox/gtl/boost/polygon
From: lucanus.j.simonson_at_[hidden]
Date: 2009-10-07 12:33:11
Author: ljsimons
Date: 2009-10-07 12:33:10 EDT (Wed, 07 Oct 2009)
New Revision: 56634
URL: http://svn.boost.org/trac/boost/changeset/56634
Log:
fixed bug in polygon contains() which was ignoring point in holes case and added unit test
Text files modified:
sandbox/gtl/boost/polygon/gtl_boost_unit_test.cpp | 16 +++++
sandbox/gtl/boost/polygon/polygon_traits.hpp | 123 +++++++++++++++++++++++++++++++++++++++
2 files changed, 136 insertions(+), 3 deletions(-)
Modified: sandbox/gtl/boost/polygon/gtl_boost_unit_test.cpp
==============================================================================
--- sandbox/gtl/boost/polygon/gtl_boost_unit_test.cpp (original)
+++ sandbox/gtl/boost/polygon/gtl_boost_unit_test.cpp 2009-10-07 12:33:10 EDT (Wed, 07 Oct 2009)
@@ -1708,11 +1708,27 @@
pts.push_back(Point(-20, -20));
pts.push_back(Point(0, 0));
polygon_data<int> poly;
+ polygon_with_holes_data<int> poly2;
+ polygon_45_data<int> poly45;
+ polygon_45_with_holes_data<int> poly245;
+ polygon_90_data<int> poly90;
+ polygon_90_with_holes_data<int> poly290;
poly.set(pts.begin(), pts.end());
+ poly2.set(pts.begin(), pts.end());
+ assign(poly45, Rectangle(0, 0, 100, 100));
+ assign(poly245, Rectangle(0, 0, 100, 100));
+ assign(poly90, Rectangle(0, 0, 100, 100));
+ assign(poly290, Rectangle(0, 0, 100, 100));
for(unsigned int i = 0; i < pts.size(); ++i) {
if(!contains(poly, pts[i], true)) return false;
if(contains(poly, pts[i], false)) return false;
+ if(!contains(poly2, pts[i], true)) return false;
+ if(contains(poly2, pts[i], false)) return false;
}
+ if(!contains(poly45, pts[0], true)) return false;
+ if(contains(poly245, pts[0], false)) return false;
+ if(!contains(poly90, pts[0], true)) return false;
+ if(contains(poly290, pts[0], false)) return false;
Point pt(0, -10);
if(contains(poly, pt)) return false;
Point p2(0, 1);
Modified: sandbox/gtl/boost/polygon/polygon_traits.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/polygon_traits.hpp (original)
+++ sandbox/gtl/boost/polygon/polygon_traits.hpp 2009-10-07 12:33:10 EDT (Wed, 07 Oct 2009)
@@ -79,6 +79,7 @@
>::type > {
typedef typename polygon_90_traits<T>::coordinate_type coordinate_type;
typedef iterator_compact_to_points<typename polygon_90_traits<T>::compact_iterator_type, point_data<coordinate_type> > iterator_type;
+ typedef point_data<coordinate_type> point_type;
// Get the begin iterator
static inline iterator_type begin_points(const T& t) {
@@ -308,6 +309,15 @@
typename is_any_mutable_polygon_without_holes_type<T>::type>::type type;
};
+ template <typename T>
+ struct polygon_from_polygon_with_holes_type {};
+ template <>
+ struct polygon_from_polygon_with_holes_type<polygon_with_holes_concept> { typedef polygon_concept type; };
+ template <>
+ struct polygon_from_polygon_with_holes_type<polygon_45_with_holes_concept> { typedef polygon_45_concept type; };
+ template <>
+ struct polygon_from_polygon_with_holes_type<polygon_90_with_holes_concept> { typedef polygon_90_concept type; };
+
template <>
struct geometry_domain<polygon_45_concept> { typedef forty_five_domain type; };
template <>
@@ -1075,9 +1085,8 @@
template <typename T, typename input_point_type>
typename enable_if<
- typename gtl_and_3< typename is_polygon_with_holes_type<T>::type,
- typename gtl_same_type<typename geometry_domain<typename geometry_concept<T>::type>::type, manhattan_domain>::type,
- typename gtl_same_type<typename geometry_concept<input_point_type>::type, point_concept>::type>::type,
+ typename gtl_and< typename is_polygon_90_type<T>::type,
+ typename gtl_same_type<typename geometry_concept<input_point_type>::type, point_concept>::type>::type,
bool>::type
contains(const T& polygon, const input_point_type& point, bool consider_touch = true) {
typedef T polygon_type;
@@ -1232,6 +1241,80 @@
template <typename T, typename input_point_type>
typename enable_if<
+ typename gtl_and< typename is_any_mutable_polygon_with_holes_type<T>::type,
+ typename gtl_same_type<typename geometry_concept<input_point_type>::type, point_concept>::type>::type,
+ bool>::type
+ contains(const T& polygon, const input_point_type& point, bool consider_touch = true) {
+ typedef typename polygon_with_holes_traits<T>::iterator_holes_type holes_iterator;
+ bool isInside = contains( view_as< typename polygon_from_polygon_with_holes_type<
+ typename geometry_concept<T>::type>::type>( polygon ), point, consider_touch );
+ if(!isInside) return false; //no need to check holes
+ holes_iterator itH = begin_holes( polygon );
+ while( itH != end_holes( polygon ) ) {
+ if( contains( *itH, point, !consider_touch ) ) {
+ isInside = false;
+ break;
+ }
+ ++itH;
+ }
+ return isInside;
+ }
+
+ template <typename T, typename input_point_type>
+ typename enable_if<
+ typename gtl_and_3<
+ typename is_polygon_type<T>::type,
+ typename gtl_different_type<typename geometry_domain<typename geometry_concept<T>::type>::type, manhattan_domain>::type,
+ typename gtl_same_type<typename geometry_concept<input_point_type>::type, point_concept>::type>::type,
+ bool>::type
+ contains(const T& polygon, const input_point_type& point, bool consider_touch = true) {
+ typedef typename point_traits<input_point_type>::coordinate_type Unit;
+ typedef point_data<Unit> Point;
+ typedef std::pair<Point, Point> half_edge;
+ typedef typename polygon_traits<T>::iterator_type iterator;
+ iterator itr = begin_points(polygon);
+ iterator itrEnd = end_points(polygon);
+ half_edge he;
+ if(itr == itrEnd) return false;
+ assign(he.first, *itr);
+ Point firstPt;
+ assign(firstPt, *itr);
+ ++itr;
+ if(itr == itrEnd) return false;
+ bool done = false;
+ int above = 0;
+ while(!done) {
+ Point currentPt;
+ if(itr == itrEnd) {
+ done = true;
+ currentPt = firstPt;
+ } else {
+ assign(currentPt, *itr);
+ ++itr;
+ }
+ if(currentPt == he.first) {
+ continue;
+ } else {
+ he.second = currentPt;
+ if(equivalence(point, currentPt)) return consider_touch;
+ Unit xmin = (std::min)(x(he.first), x(he.second));
+ Unit xmax = (std::max)(x(he.first), x(he.second));
+ if(x(point) >= xmin && x(point) < xmax) { //double counts if <= xmax
+ Point tmppt;
+ assign(tmppt, point);
+ int oabedge = edge_utils<Unit>::on_above_or_below(tmppt, he);
+ if(oabedge == 0) return consider_touch;
+ if(oabedge == 1) ++above;
+ }
+ }
+ he.first = he.second;
+ }
+ return above % 2 != 0; //if the point is above an odd number of edges is must be inside polygon
+ }
+
+ /*
+ template <typename T, typename input_point_type>
+ typename enable_if<
typename gtl_and_3<
typename is_polygon_with_holes_type<T>::type,
typename gtl_different_type<typename geometry_domain<typename geometry_concept<T>::type>::type, manhattan_domain>::type,
@@ -1281,6 +1364,7 @@
}
return above % 2 != 0; //if the point is above an odd number of edges is must be inside polygon
}
+ */
template <typename T1, typename T2>
typename enable_if<
@@ -1676,6 +1760,39 @@
typedef polygon_90_with_holes_concept type;
};
+ template <typename T>
+ struct view_of<polygon_concept, T> {
+ const T* t;
+ view_of(const T& obj) : t(&obj) {}
+ typedef typename polygon_traits<T>::coordinate_type coordinate_type;
+ typedef typename polygon_traits<T>::iterator_type iterator_type;
+ typedef typename polygon_traits<T>::point_type point_type;
+
+ /// Get the begin iterator
+ inline iterator_type begin() const {
+ return polygon_traits<T>::begin_points(*t);
+ }
+
+ /// Get the end iterator
+ inline iterator_type end() const {
+ return polygon_traits<T>::end_points(*t);
+ }
+
+ /// Get the number of sides of the polygon
+ inline std::size_t size() const {
+ return polygon_traits<T>::size(*t);
+ }
+
+ /// Get the winding direction of the polygon
+ inline winding_direction winding() const {
+ return polygon_traits<T>::winding(*t);
+ }
+ };
+
+ template <typename T>
+ struct geometry_concept<view_of<polygon_concept, T> > {
+ typedef polygon_concept type;
+ };
}
}