Boost logo

Boost-Commit :

Subject: [Boost-commit] svn:boost r66403 - in trunk/boost/polygon: . detail
From: lucanus.j.simonson_at_[hidden]
Date: 2010-11-04 14:37:49


Author: ljsimons
Date: 2010-11-04 14:37:35 EDT (Thu, 04 Nov 2010)
New Revision: 66403
URL: http://svn.boost.org/trac/boost/changeset/66403

Log:
various bug fixes made since 1.44 release
Text files modified:
   trunk/boost/polygon/detail/iterator_geometry_to_set.hpp | 14 ++++-
   trunk/boost/polygon/detail/polygon_45_formation.hpp | 2
   trunk/boost/polygon/detail/polygon_arbitrary_formation.hpp | 38 +++++++++++----
   trunk/boost/polygon/gmp_override.hpp | 2
   trunk/boost/polygon/isotropy.hpp | 12 +++++
   trunk/boost/polygon/polygon_90_set_data.hpp | 92 +++++++++++++++++++++------------------
   trunk/boost/polygon/polygon_set_data.hpp | 86 ++++++++++++++++++------------------
   7 files changed, 144 insertions(+), 102 deletions(-)

Modified: trunk/boost/polygon/detail/iterator_geometry_to_set.hpp
==============================================================================
--- trunk/boost/polygon/detail/iterator_geometry_to_set.hpp (original)
+++ trunk/boost/polygon/detail/iterator_geometry_to_set.hpp 2010-11-04 14:37:35 EDT (Thu, 04 Nov 2010)
@@ -253,8 +253,13 @@
             typename polygon_with_holes_traits<polygon_with_holes_type>::hole_type>(*itrhb, HIGH, orient_, !is_hole_);
           ++itrhb;
         } else {
- itrhib = itrhie = iterator_geometry_to_set<polygon_90_concept,
- typename polygon_with_holes_traits<polygon_with_holes_type>::hole_type>();
+ //in this case we have no holes so we just need the iterhib == itrhie, which
+ //is always true if they were default initialized in the initial case or
+ //both point to end of the previous hole processed
+ //no need to explicitly reset them, and it causes an stl debug assertion to use
+ //the default constructed iterator this way
+ //itrhib = itrhie = iterator_geometry_to_set<polygon_90_concept,
+ // typename polygon_with_holes_traits<polygon_with_holes_type>::hole_type>();
         }
       } else {
         ++itrhib;
@@ -266,8 +271,9 @@
               typename polygon_with_holes_traits<polygon_with_holes_type>::hole_type>(*itrhb, HIGH, orient_, !is_hole_);
             ++itrhb;
           } else {
- itrhib = itrhie = iterator_geometry_to_set<polygon_90_concept,
- typename polygon_with_holes_traits<polygon_with_holes_type>::hole_type>();
+ //this is the same case as above
+ //itrhib = itrhie = iterator_geometry_to_set<polygon_90_concept,
+ // typename polygon_with_holes_traits<polygon_with_holes_type>::hole_type>();
           }
         }
       }

Modified: trunk/boost/polygon/detail/polygon_45_formation.hpp
==============================================================================
--- trunk/boost/polygon/detail/polygon_45_formation.hpp (original)
+++ trunk/boost/polygon/detail/polygon_45_formation.hpp 2010-11-04 14:37:35 EDT (Thu, 04 Nov 2010)
@@ -478,7 +478,7 @@
       ct counts[4];
     };
 
- typedef Vertex45CountT<signed char> Vertex45Count;
+ typedef Vertex45CountT<int> Vertex45Count;
 
 // inline std::ostream& operator<< (std::ostream& o, const Vertex45Count& c) {
 // o << c[0] << ", " << c[1] << ", ";

Modified: trunk/boost/polygon/detail/polygon_arbitrary_formation.hpp
==============================================================================
--- trunk/boost/polygon/detail/polygon_arbitrary_formation.hpp (original)
+++ trunk/boost/polygon/detail/polygon_arbitrary_formation.hpp 2010-11-04 14:37:35 EDT (Thu, 04 Nov 2010)
@@ -455,6 +455,10 @@
         //truncate downward if it went up due to negative number
         if(x < x_unit) --x_unit;
         if(y < y_unit) --y_unit;
+ if(is_horizontal(he1))
+ y_unit = he1.first.y();
+ if(is_horizontal(he2))
+ y_unit = he2.first.y();
         //if(x != exp_x || y != exp_y)
         // std::cout << exp_x << " " << exp_y << " " << x << " " << y << std::endl;
         //Unit y1 = evalAtXforY(exp_x, he1.first, he1.second);
@@ -464,11 +468,11 @@
         if(!projected && !contains(rect1, result, true)) return false;
         if(!projected && !contains(rect2, result, true)) return false;
         if(projected) {
- rectangle_data<long double> inf_rect((long double)(std::numeric_limits<Unit>::min)(),
- (long double) (std::numeric_limits<Unit>::min)(),
+ rectangle_data<long double> inf_rect(-(long double)(std::numeric_limits<Unit>::max)(),
+ -(long double) (std::numeric_limits<Unit>::max)(),
                                                (long double)(std::numeric_limits<Unit>::max)(),
                                                (long double) (std::numeric_limits<Unit>::max)() );
- if(contains(inf_rect, intersection, true)) {
+ if(contains(inf_rect, point_data<long double>(x, y), true)) {
             intersection = result;
             return true;
           } else
@@ -477,6 +481,7 @@
         intersection = result;
         return true;
       }
+
       inline bool compute_intersection(Point& intersection, const half_edge& he1, const half_edge& he2,
                                        bool projected = false, bool round_closest = false) {
         if(!projected && !intersects(he1, he2))
@@ -491,6 +496,13 @@
         } else {
           return lazy_success;
         }
+ return compute_exact_intersection(intersection, he1, he2, projected, round_closest);
+ }
+
+ inline bool compute_exact_intersection(Point& intersection, const half_edge& he1, const half_edge& he2,
+ bool projected = false, bool round_closest = false) {
+ if(!projected && !intersects(he1, he2))
+ return false;
         typedef rectangle_data<Unit> Rectangle;
         Rectangle rect1, rect2;
         set_points(rect1, he1.first, he1.second);
@@ -542,6 +554,7 @@
         y_den = (dx1 * dy2 - dx2 * dy1);
         x = x_num / x_den;
         y = y_num / y_den;
+ //std::cout << x << " " << y << std::endl;
         //std::cout << "cross1 " << dy1 << " " << dx2 << " " << dy1 * dx2 << std::endl;
         //std::cout << "cross2 " << dy2 << " " << dx1 << " " << dy2 * dx1 << std::endl;
         //Unit exp_x = compute_x_intercept<at>(x11, x21, y11, y21, dy1, dy2, dx1, dx2);
@@ -555,6 +568,10 @@
         //truncate downward if it went up due to negative number
         if(x < (high_precision)x_unit) --x_unit;
         if(y < (high_precision)y_unit) --y_unit;
+ if(is_horizontal(he1))
+ y_unit = he1.first.y();
+ if(is_horizontal(he2))
+ y_unit = he2.first.y();
         //if(x != exp_x || y != exp_y)
         // std::cout << exp_x << " " << exp_y << " " << x << " " << y << std::endl;
         //Unit y1 = evalAtXforY(exp_x, he1.first, he1.second);
@@ -564,14 +581,9 @@
         if(!contains(rect1, result, true)) return false;
         if(!contains(rect2, result, true)) return false;
         if(projected) {
- rectangle_data<long double> inf_rect((long double)(std::numeric_limits<Unit>::min)(),
- (long double) (std::numeric_limits<Unit>::min)(),
- (long double)(std::numeric_limits<Unit>::max)(),
- (long double) (std::numeric_limits<Unit>::max)() );
- if(contains(inf_rect, intersection, true)) {
- intersection = result;
- return true;
- } else
+ high_precision b1 = (high_precision) (std::numeric_limits<Unit>::min)();
+ high_precision b2 = (high_precision) (std::numeric_limits<Unit>::max)();
+ if(x > b2 || y > b2 || x < b1 || y < b1)
             return false;
         }
         intersection = result;
@@ -641,6 +653,10 @@
       //truncate downward if it went up due to negative number
       if(x < (high_precision)x_unit) --x_unit;
       if(y < (high_precision)y_unit) --y_unit;
+ if(is_horizontal(he1))
+ y_unit = he1.first.y();
+ if(is_horizontal(he2))
+ y_unit = he2.first.y();
       //if(x != exp_x || y != exp_y)
       // std::cout << exp_x << " " << exp_y << " " << x << " " << y << std::endl;
       //Unit y1 = evalAtXforY(exp_x, he1.first, he1.second);

Modified: trunk/boost/polygon/gmp_override.hpp
==============================================================================
--- trunk/boost/polygon/gmp_override.hpp (original)
+++ trunk/boost/polygon/gmp_override.hpp 2010-11-04 14:37:35 EDT (Thu, 04 Nov 2010)
@@ -125,5 +125,5 @@
 
 }
 }
-
+//==
 #endif

Modified: trunk/boost/polygon/isotropy.hpp
==============================================================================
--- trunk/boost/polygon/isotropy.hpp (original)
+++ trunk/boost/polygon/isotropy.hpp 2010-11-04 14:37:35 EDT (Thu, 04 Nov 2010)
@@ -198,6 +198,16 @@
     typedef double coordinate_distance;
   };
 
+ template <>
+ struct coordinate_traits<long double> {
+ typedef long double coordinate_type;
+ typedef long double area_type;
+ typedef long double manhattan_area_type;
+ typedef long double unsigned_area_type;
+ typedef long double coordinate_difference;
+ typedef long double coordinate_distance;
+ };
+
   template <typename T>
   struct scaling_policy {
     template <typename T2>
@@ -222,6 +232,8 @@
   struct geometry_concept<float> { typedef coordinate_concept type; };
   template <>
   struct geometry_concept<double> { typedef coordinate_concept type; };
+ template <>
+ struct geometry_concept<long double> { typedef coordinate_concept type; };
 
 #ifndef BOOST_POLYGON_NO_DEPS
   struct gtl_no : mpl::bool_<false> {};

Modified: trunk/boost/polygon/polygon_90_set_data.hpp
==============================================================================
--- trunk/boost/polygon/polygon_90_set_data.hpp (original)
+++ trunk/boost/polygon/polygon_90_set_data.hpp 2010-11-04 14:37:35 EDT (Thu, 04 Nov 2010)
@@ -244,37 +244,47 @@
     // get the scanline orientation of the polygon set
     inline orientation_2d orient() const { return orient_; }
 
- polygon_90_set_data<coordinate_type>& operator-=(const polygon_90_set_data& that) {
- sort();
- that.sort();
- value_type data;
- std::swap(data, data_);
- applyBooleanBinaryOp(data.begin(), data.end(),
- that.begin(), that.end(), boolean_op::BinaryCount<boolean_op::BinaryNot>());
- return *this;
- }
- polygon_90_set_data<coordinate_type>& operator^=(const polygon_90_set_data& that) {
- sort();
- that.sort();
- value_type data;
- std::swap(data, data_);
- applyBooleanBinaryOp(data.begin(), data.end(),
- that.begin(), that.end(), boolean_op::BinaryCount<boolean_op::BinaryXor>());
- return *this;
- }
- polygon_90_set_data<coordinate_type>& operator&=(const polygon_90_set_data& that) {
- sort();
- that.sort();
- value_type data;
- std::swap(data, data_);
- applyBooleanBinaryOp(data.begin(), data.end(),
- that.begin(), that.end(), boolean_op::BinaryCount<boolean_op::BinaryAnd>());
- return *this;
- }
- polygon_90_set_data<coordinate_type>& operator|=(const polygon_90_set_data& that) {
- insert(that);
- return *this;
- }
+ // Start BM
+ // The problem: If we have two polygon sets with two different scanline orientations:
+ // I tried changing the orientation of one to coincide with other (If not, resulting boolean operation
+ // produces spurious results).
+ // First I tried copying polygon data from one of the sets into another set with corrected orientation
+ // using one of the copy constructor that takes in orientation (see somewhere above in this file) --> copy constructor throws error
+ // Then I tried another approach:(see below). This approach also fails to produce the desired results when test case is run.
+ // Here is the part that beats me: If I comment out the whole section, I can do all the operations (^=, -=, &= )these commented out
+ // operations perform. So then why do we need them?. Hence, I commented out this whole section.
+ // End BM
+ // polygon_90_set_data<coordinate_type>& operator-=(const polygon_90_set_data& that) {
+ // sort();
+ // that.sort();
+ // value_type data;
+ // std::swap(data, data_);
+ // applyBooleanBinaryOp(data.begin(), data.end(),
+ // that.begin(), that.end(), boolean_op::BinaryCount<boolean_op::BinaryNot>());
+ // return *this;
+ // }
+ // polygon_90_set_data<coordinate_type>& operator^=(const polygon_90_set_data& that) {
+ // sort();
+ // that.sort();
+ // value_type data;
+ // std::swap(data, data_);
+ // applyBooleanBinaryOp(data.begin(), data.end(),
+ // that.begin(), that.end(), boolean_op::BinaryCount<boolean_op::BinaryXor>());
+ // return *this;
+ // }
+ // polygon_90_set_data<coordinate_type>& operator&=(const polygon_90_set_data& that) {
+ // sort();
+ // that.sort();
+ // value_type data;
+ // std::swap(data, data_);
+ // applyBooleanBinaryOp(data.begin(), data.end(),
+ // that.begin(), that.end(), boolean_op::BinaryCount<boolean_op::BinaryAnd>());
+ // return *this;
+ // }
+ // polygon_90_set_data<coordinate_type>& operator|=(const polygon_90_set_data& that) {
+ // insert(that);
+ // return *this;
+ // }
 
     void clean() const {
       sort();
@@ -439,7 +449,7 @@
 
     static bool remove_colinear_pts(std::vector<point_data<coordinate_type> >& poly) {
       bool found_colinear = true;
- while(found_colinear) {
+ while(found_colinear && poly.size() >= 4) {
         found_colinear = false;
         typename std::vector<point_data<coordinate_type> >::iterator itr = poly.begin();
         itr += poly.size() - 1; //get last element position
@@ -504,9 +514,9 @@
           //polygon_45_data<coordinate_type> testpoly(*itrh);
           if(resize_poly_down((*itrh).coords_, west_bloating, east_bloating, south_bloating, north_bloating)) {
             iterator_geometry_to_set<polygon_90_concept, view_of<polygon_90_concept, polygon_45_data<coordinate_type> > >
- begin_input(view_as<polygon_90_concept>(*itrh), LOW, orient_, true, true),
- end_input(view_as<polygon_90_concept>(*itrh), HIGH, orient_, true, true);
- insert(begin_input, end_input, orient_);
+ begin_input2(view_as<polygon_90_concept>(*itrh), LOW, orient_, true, true),
+ end_input2(view_as<polygon_90_concept>(*itrh), HIGH, orient_, true, true);
+ insert(begin_input2, end_input2, orient_);
             //polygon_90_set_data<coordinate_type> pstesthole;
             //pstesthole.insert(rect);
             //iterator_geometry_to_set<polygon_90_concept, view_of<polygon_90_concept, polygon_45_data<coordinate_type> > >
@@ -569,9 +579,9 @@
             //polygon_45_data<coordinate_type> testpoly(*itrh);
             resize_poly_up((*itrh).coords_, -west_shrinking, -east_shrinking, -south_shrinking, -north_shrinking);
             iterator_geometry_to_set<polygon_90_concept, view_of<polygon_90_concept, polygon_45_data<coordinate_type> > >
- begin_input(view_as<polygon_90_concept>(*itrh), LOW, orient_, true, true),
- end_input(view_as<polygon_90_concept>(*itrh), HIGH, orient_, true, true);
- insert(begin_input, end_input, orient_);
+ begin_input2(view_as<polygon_90_concept>(*itrh), LOW, orient_, true, true),
+ end_input2(view_as<polygon_90_concept>(*itrh), HIGH, orient_, true, true);
+ insert(begin_input2, end_input2, orient_);
             //polygon_90_set_data<coordinate_type> pstesthole;
             //pstesthole.insert(rect);
             //iterator_geometry_to_set<polygon_90_concept, view_of<polygon_90_concept, polygon_45_data<coordinate_type> > >
@@ -638,8 +648,7 @@
         return shrink(0, shrinking, 0, 0);
       if(dir == SOUTH)
         return shrink(0, 0, shrinking, 0);
- if(dir == NORTH)
- return shrink(0, 0, 0, shrinking);
+ return shrink(0, 0, 0, shrinking);
     }
 
     polygon_90_set_data&
@@ -650,8 +659,7 @@
         return bloat(0, shrinking, 0, 0);
       if(dir == SOUTH)
         return bloat(0, 0, shrinking, 0);
- if(dir == NORTH)
- return bloat(0, 0, 0, shrinking);
+ return bloat(0, 0, 0, shrinking);
     }
 
     polygon_90_set_data&

Modified: trunk/boost/polygon/polygon_set_data.hpp
==============================================================================
--- trunk/boost/polygon/polygon_set_data.hpp (original)
+++ trunk/boost/polygon/polygon_set_data.hpp 2010-11-04 14:37:35 EDT (Thu, 04 Nov 2010)
@@ -359,24 +359,7 @@
     }
 
     inline polygon_set_data&
- resize(coordinate_type resizing, bool corner_fill_arc = false, unsigned int num_circle_segments=0) {
- if(!corner_fill_arc) {
- if(resizing < 0)
- return shrink(-resizing);
- if(resizing > 0)
- return bloat(resizing);
- return *this;
- }
- if(resizing == 0) return *this;
- std::list<polygon_with_holes_data<coordinate_type> > pl;
- get(pl);
- clear();
- for(typename std::list<polygon_with_holes_data<coordinate_type> >::iterator itr = pl.begin(); itr != pl.end(); ++itr) {
- insert_with_resize(*itr, resizing, corner_fill_arc, num_circle_segments);
- }
- clean();
- return *this;
- }
+ resize(coordinate_type resizing, bool corner_fill_arc = false, unsigned int num_circle_segments=0);
 
     template <typename transform_type>
     inline polygon_set_data&
@@ -425,37 +408,53 @@
       return *this;
     }
 
- static inline void compute_offset_edge(point_data<coordinate_type>& pt1, point_data<coordinate_type>& pt2,
- const point_data<coordinate_type>& prev_pt,
- const point_data<coordinate_type>& current_pt,
- coordinate_type distance, int multiplier) {
- coordinate_type dx = current_pt.x() - prev_pt.x();
- coordinate_type dy = current_pt.y() - prev_pt.y();
- double ddx = (double)dx;
- double ddy = (double)dy;
- double edge_length = std::sqrt(ddx*ddx + ddy*ddy);
- double dnx = dy;
- double dny = -dx;
- dnx = dnx * (double)distance / edge_length;
- dny = dny * (double)distance / edge_length;
- dnx = std::floor(dnx+0.5);
- dny = std::floor(dny+0.5);
- pt1.x(prev_pt.x() + (coordinate_type)dnx * (coordinate_type)multiplier);
- pt2.x(current_pt.x() + (coordinate_type)dnx * (coordinate_type)multiplier);
- pt1.y(prev_pt.y() + (coordinate_type)dny * (coordinate_type)multiplier);
- pt2.y(current_pt.y() + (coordinate_type)dny * (coordinate_type)multiplier);
+ static inline void compute_offset_edge(point_data<long double>& pt1, point_data<long double>& pt2,
+ const point_data<long double>& prev_pt,
+ const point_data<long double>& current_pt,
+ long double distance, int multiplier) {
+ long double dx = current_pt.x() - prev_pt.x();
+ long double dy = current_pt.y() - prev_pt.y();
+ long double edge_length = std::sqrt(dx*dx + dy*dy);
+ long double dnx = dy;
+ long double dny = -dx;
+ dnx = dnx * (long double)distance / edge_length;
+ dny = dny * (long double)distance / edge_length;
+ pt1.x(prev_pt.x() + (long double)dnx * (long double)multiplier);
+ pt2.x(current_pt.x() + (long double)dnx * (long double)multiplier);
+ pt1.y(prev_pt.y() + (long double)dny * (long double)multiplier);
+ pt2.y(current_pt.y() + (long double)dny * (long double)multiplier);
     }
 
     static inline void modify_pt(point_data<coordinate_type>& pt, const point_data<coordinate_type>& prev_pt,
                                  const point_data<coordinate_type>& current_pt, const point_data<coordinate_type>& next_pt,
                                  coordinate_type distance, coordinate_type multiplier) {
- std::pair<point_data<coordinate_type>, point_data<coordinate_type> > he1(prev_pt, current_pt), he2(current_pt, next_pt);
+ std::pair<point_data<long double>, point_data<long double> > he1, he2;
+ he1.first.x((long double)(prev_pt.x()));
+ he1.first.y((long double)(prev_pt.y()));
+ he1.second.x((long double)(current_pt.x()));
+ he1.second.y((long double)(current_pt.y()));
+ he2.first.x((long double)(current_pt.x()));
+ he2.first.y((long double)(current_pt.y()));
+ he2.second.x((long double)(next_pt.x()));
+ he2.second.y((long double)(next_pt.y()));
       compute_offset_edge(he1.first, he1.second, prev_pt, current_pt, distance, multiplier);
       compute_offset_edge(he2.first, he2.second, current_pt, next_pt, distance, multiplier);
- typename scanline_base<coordinate_type>::compute_intersection_pack pack;
- if(!pack.compute_lazy_intersection(pt, he1, he2, true, true)) {
- pt = he1.second; //colinear offset edges use shared point
+ typename scanline_base<long double>::compute_intersection_pack pack;
+ point_data<long double> rpt;
+ point_data<long double> bisectorpt((he1.second.x()+he2.first.x())/2,
+ (he1.second.y()+he2.first.y())/2);
+ point_data<long double> orig_pt((long double)pt.x(), (long double)pt.y());
+ if(euclidean_distance(bisectorpt, orig_pt) < distance/2) {
+ if(!pack.compute_lazy_intersection(rpt, he1, he2, true, false)) {
+ rpt = he1.second; //colinear offset edges use shared point
+ }
+ } else {
+ if(!pack.compute_lazy_intersection(rpt, he1, std::pair<point_data<long double>, point_data<long double> >(orig_pt, bisectorpt), true, false)) {
+ rpt = he1.second; //colinear offset edges use shared point
+ }
       }
+ pt.x((coordinate_type)(std::floor(rpt.x()+0.5)));
+ pt.y((coordinate_type)(std::floor(rpt.y()+0.5)));
     }
 
     static void resize_poly_up(std::vector<point_data<coordinate_type> >& poly, coordinate_type distance, coordinate_type multiplier) {
@@ -615,7 +614,7 @@
 
       // for all corners
       polygon_set_data<T> sizingSet;
- bool sizing_sign = resizing>0;
+ bool sizing_sign = resizing<0;
       bool prev_concave = true;
       point_data<T> prev_point;
       //int iCtr=0;
@@ -911,7 +910,7 @@
       }
       return_points.push_back(round_down<T>(center));
       return_points.push_back(round_down<T>(start));
- int i=0;
+ unsigned int i=0;
       double curr_angle = ps+delta_angle;
       while( curr_angle < pe - 0.01 && i < 2 * num_circle_segments) {
          i++;
@@ -996,5 +995,6 @@
 #include "detail/polygon_set_view.hpp"
 
 #include "polygon_set_concept.hpp"
+#include "detail/minkowski.hpp"
 #endif
 


Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk