ceph/src/boost/libs/polygon/include/boost/polygon/detail/scan_arbitrary.hpp

   1 /*
   2   Copyright 2008 Intel Corporation
   3
   4   Use, modification and distribution are subject to the Boost Software License,
   5   Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   6   http://www.boost.org/LICENSE_1_0.txt).
   7 */
   8 #ifndef BOOST_POLYGON_SCAN_ARBITRARY_HPP
   9 #define BOOST_POLYGON_SCAN_ARBITRARY_HPP
  10 #ifdef BOOST_POLYGON_DEBUG_FILE
  11 #include <fstream>
  12 #endif
  13 #include "polygon_sort_adaptor.hpp"
  14 namespace boost { namespace polygon{
  15
  16   template <typename Unit>
  17   class line_intersection : public scanline_base<Unit> {
  18   private:
  19     typedef typename scanline_base<Unit>::Point Point;
  20
  21     //the first point is the vertex and and second point establishes the slope of an edge eminating from the vertex
  22     //typedef std::pair<Point, Point> half_edge;
  23     typedef typename scanline_base<Unit>::half_edge half_edge;
  24
  25     //scanline comparator functor
  26     typedef typename scanline_base<Unit>::less_half_edge less_half_edge;
  27     typedef typename scanline_base<Unit>::less_point less_point;
  28
  29     //when parallel half edges are encounterd the set of segments is expanded
  30     //when a edge leaves the scanline it is removed from the set
  31     //when the set is empty the element is removed from the map
  32     typedef int segment_id;
  33     typedef std::pair<half_edge, std::set<segment_id> > scanline_element;
  34     typedef std::map<half_edge, std::set<segment_id>, less_half_edge> edge_scanline;
  35     typedef typename edge_scanline::iterator iterator;
  36
  37 //     std::map<Unit, std::set<segment_id> > vertical_data_;
  38 //     edge_scanline edge_scanline_;
  39 //     Unit x_;
  40 //     int just_before_;
  41 //     segment_id segment_id_;
  42 //     std::vector<std::pair<half_edge, int> > event_edges_;
  43 //     std::set<Point> intersection_queue_;
  44   public:
  45 //     inline line_intersection() : vertical_data_(), edge_scanline_(), x_((std::numeric_limits<Unit>::max)()), just_before_(0), segment_id_(0), event_edges_(), intersection_queue_() {
  46 //       less_half_edge lessElm(&x_, &just_before_);
  47 //       edge_scanline_ = edge_scanline(lessElm);
  48 //     }
  49 //     inline line_intersection(const line_intersection& that) : vertical_data_(), edge_scanline_(), x_(), just_before_(), segment_id_(), event_edges_(), intersection_queue_() { (*this) = that; }
  50 //     inline line_intersection& operator=(const line_intersection& that) {
  51 //       x_ = that.x_;
  52 //       just_before_ = that.just_before_;
  53 //       segment_id_ = that.segment_id_;
  54
  55 //       //I cannot simply copy that.edge_scanline_ to this edge_scanline_ becuase the functor store pointers to other members!
  56 //       less_half_edge lessElm(&x_, &just_before_);
  57 //       edge_scanline_ = edge_scanline(lessElm);
  58
  59 //       edge_scanline_.insert(that.edge_scanline_.begin(), that.edge_scanline_.end());
  60 //       return *this;
  61 //     }
  62
  63 //     static inline void between(Point pt, Point pt1, Point pt2) {
  64 //       less_point lp;
  65 //       if(lp(pt1, pt2))
  66 //         return lp(pt, pt2) && lp(pt1, pt);
  67 //       return lp(pt, pt1) && lp(pt2, pt);
  68 //     }
  69
  70     template <typename iT>
  71     static inline void compute_histogram_in_y(iT begin, iT end, std::size_t size, std::vector<std::pair<Unit, std::pair<std::size_t, std::size_t> > >& histogram) {
  72       std::vector<std::pair<Unit, int> > ends;
  73       ends.reserve(size * 2);
  74       for(iT itr = begin ; itr != end; ++itr) {
  75         int count = (*itr).first.first.y() < (*itr).first.second.y() ? 1 : -1;
  76         ends.push_back(std::make_pair((*itr).first.first.y(), count));
  77         ends.push_back(std::make_pair((*itr).first.second.y(), -count));
  78       }
  79       polygon_sort(ends.begin(), ends.end());
  80       histogram.reserve(ends.size());
  81       histogram.push_back(std::make_pair(ends.front().first, std::make_pair(0, 0)));
  82       for(typename std::vector<std::pair<Unit, int> >::iterator itr = ends.begin(); itr != ends.end(); ++itr) {
  83         if((*itr).first != histogram.back().first) {
  84           histogram.push_back(std::make_pair((*itr).first, histogram.back().second));
  85         }
  86         if((*itr).second < 0)
  87           histogram.back().second.second -= (*itr).second;
  88         histogram.back().second.first += (*itr).second;
  89       }
  90     }
  91
  92     template <typename iT>
  93     static inline void compute_y_cuts(std::vector<Unit>& y_cuts, iT begin, iT end, std::size_t size) {
  94       if(begin == end) return;
  95       if(size < 30) return; //30 is empirically chosen, but the algorithm is not sensitive to this constant
  96       std::size_t min_cut = size;
  97       iT cut = begin;
  98       std::size_t position = 0;
  99       std::size_t cut_size = 0;
 100       std::size_t histogram_size = std::distance(begin, end);
 101       for(iT itr = begin; itr != end; ++itr, ++position) {
 102         if(position < histogram_size / 3)
 103           continue;
 104         if(histogram_size - position < histogram_size / 3) break;
 105         if((*itr).second.first < min_cut) {
 106           cut = itr;
 107           min_cut = (*cut).second.first;
 108           cut_size = position;
 109         }
 110       }
 111       if(cut_size == 0 || (*cut).second.first > size / 9) //nine is empirically chosen
 112         return;
 113       compute_y_cuts(y_cuts, begin, cut, (*cut).second.first + (*cut).second.second);
 114       y_cuts.push_back((*cut).first);
 115       compute_y_cuts(y_cuts, cut, end, size - (*cut).second.second);
 116     }
 117
 118     template <typename iT>
 119     static inline void validate_scan_divide_and_conquer(std::vector<std::set<Point> >& intersection_points,
 120                                                         iT begin, iT end) {
 121       std::vector<std::pair<Unit, std::pair<std::size_t, std::size_t> > > histogram;
 122       compute_histogram_in_y(begin, end, std::distance(begin, end), histogram);
 123       std::vector<Unit> y_cuts;
 124       compute_y_cuts(y_cuts, histogram.begin(), histogram.end(), std::distance(begin, end));
 125       std::map<Unit, std::vector<std::pair<half_edge, segment_id> > > bins;
 126       bins[histogram.front().first] = std::vector<std::pair<half_edge, segment_id> >();
 127       for(typename std::vector<Unit>::iterator itr = y_cuts.begin(); itr != y_cuts.end(); ++itr) {
 128         bins[*itr] = std::vector<std::pair<half_edge, segment_id> >();
 129       }
 130       for(iT itr = begin; itr != end; ++itr) {
 131         typename std::map<Unit, std::vector<std::pair<half_edge, segment_id> > >::iterator lb =
 132           bins.lower_bound((std::min)((*itr).first.first.y(), (*itr).first.second.y()));
 133         if(lb != bins.begin())
 134           --lb;
 135         typename std::map<Unit, std::vector<std::pair<half_edge, segment_id> > >::iterator ub =
 136           bins.upper_bound((std::max)((*itr).first.first.y(), (*itr).first.second.y()));
 137         for( ; lb != ub; ++lb) {
 138           (*lb).second.push_back(*itr);
 139         }
 140       }
 141       validate_scan(intersection_points, bins[histogram.front().first].begin(), bins[histogram.front().first].end());
 142       for(typename std::vector<Unit>::iterator itr = y_cuts.begin(); itr != y_cuts.end(); ++itr) {
 143         validate_scan(intersection_points, bins[*itr].begin(), bins[*itr].end(), *itr);
 144       }
 145     }
 146
 147     template <typename iT>
 148     static inline void validate_scan(std::vector<std::set<Point> >& intersection_points,
 149                                      iT begin, iT end) {
 150       validate_scan(intersection_points, begin, end, (std::numeric_limits<Unit>::min)());
 151     }
 152     //quadratic algorithm to do same work as optimal scan for cross checking
 153     template <typename iT>
 154     static inline void validate_scan(std::vector<std::set<Point> >& intersection_points,
 155                                      iT begin, iT end, Unit min_y) {
 156       std::vector<Point> pts;
 157       std::vector<std::pair<half_edge, segment_id> > data(begin, end);
 158       for(std::size_t i = 0; i < data.size(); ++i) {
 159         if(data[i].first.second < data[i].first.first) {
 160           std::swap(data[i].first.first, data[i].first.second);
 161         }
 162       }
 163       typename scanline_base<Unit>::compute_intersection_pack pack_;
 164       polygon_sort(data.begin(), data.end());
 165       //find all intersection points
 166       for(typename std::vector<std::pair<half_edge, segment_id> >::iterator outer = data.begin();
 167           outer != data.end(); ++outer) {
 168         const half_edge& he1 = (*outer).first;
 169         //its own end points
 170         pts.push_back(he1.first);
 171         pts.push_back(he1.second);
 172         std::set<Point>& segmentpts = intersection_points[(*outer).second];
 173         for(typename std::set<Point>::iterator itr = segmentpts.begin(); itr != segmentpts.end(); ++itr) {
 174           if ((*itr).y() >= min_y) {
 175             pts.push_back(*itr);
 176           }
 177         }
 178         bool have_first_y = he1.first.y() >= min_y && he1.second.y() >= min_y;
 179         for(typename std::vector<std::pair<half_edge, segment_id> >::iterator inner = outer;
 180             inner != data.end(); ++inner) {
 181           const half_edge& he2 = (*inner).first;
 182           if(have_first_y || (he2.first.y() >= min_y && he2.second.y() >= min_y)) {
 183             //at least one segment has a low y value within the range
 184             if(he1 == he2) continue;
 185             if((std::min)(he2. first.get(HORIZONTAL),
 186                           he2.second.get(HORIZONTAL)) >=
 187                (std::max)(he1.second.get(HORIZONTAL),
 188                           he1.first.get(HORIZONTAL)))
 189               break;
 190             if(he1.first == he2.first || he1.second == he2.second)
 191               continue;
 192             Point intersection;
 193             if(pack_.compute_intersection(intersection, he1, he2)) {
 194               //their intersection point
 195               pts.push_back(intersection);
 196               intersection_points[(*inner).second].insert(intersection);
 197               intersection_points[(*outer).second].insert(intersection);
 198             }
 199           }
 200         }
 201       }
 202       polygon_sort(pts.begin(), pts.end());
 203       typename std::vector<Point>::iterator newend = std::unique(pts.begin(), pts.end());
 204       typename std::vector<Point>::iterator lfinger = pts.begin();
 205       //find all segments that interact with intersection points
 206       for(typename std::vector<std::pair<half_edge, segment_id> >::iterator outer = data.begin();
 207           outer != data.end(); ++outer) {
 208         const half_edge& he1 = (*outer).first;
 209         segment_id id1 = (*outer).second;
 210         //typedef rectangle_data<Unit> Rectangle;
 211         //Rectangle rect1;
 212         //set_points(rect1, he1.first, he1.second);
 213         //typename std::vector<Point>::iterator itr = lower_bound(pts.begin(), newend, (std::min)(he1.first, he1.second));
 214         //typename std::vector<Point>::iterator itr2 = upper_bound(pts.begin(), newend, (std::max)(he1.first, he1.second));
 215         Point startpt = (std::min)(he1.first, he1.second);
 216         Point stoppt = (std::max)(he1.first, he1.second);
 217         //while(itr != newend && itr != pts.begin() && (*itr).get(HORIZONTAL) >= (std::min)(he1.first.get(HORIZONTAL), he1.second.get(HORIZONTAL))) --itr;
 218         //while(itr2 != newend && (*itr2).get(HORIZONTAL) <= (std::max)(he1.first.get(HORIZONTAL), he1.second.get(HORIZONTAL))) ++itr2;
 219         //itr = pts.begin();
 220         //itr2 = pts.end();
 221         while(lfinger != newend && (*lfinger).x() < startpt.x()) ++lfinger;
 222         for(typename std::vector<Point>::iterator itr = lfinger ; itr != newend && (*itr).x() <= stoppt.x(); ++itr) {
 223           if(scanline_base<Unit>::intersects_grid(*itr, he1))
 224             intersection_points[id1].insert(*itr);
 225         }
 226       }
 227     }
 228
 229     template <typename iT, typename property_type>
 230     static inline void validate_scan(std::vector<std::pair<half_edge, std::pair<property_type, int> > >& output_segments,
 231                                      iT begin, iT end) {
 232       std::vector<std::pair<property_type, int> > input_properties;
 233       std::vector<std::pair<half_edge, int> > input_segments, intermediate_segments;
 234       int index = 0;
 235       for( ; begin != end; ++begin) {
 236         input_properties.push_back((*begin).second);
 237         input_segments.push_back(std::make_pair((*begin).first, index++));
 238       }
 239       validate_scan(intermediate_segments, input_segments.begin(), input_segments.end());
 240       for(std::size_t i = 0; i < intermediate_segments.size(); ++i) {
 241         output_segments.push_back(std::make_pair(intermediate_segments[i].first,
 242                                                  input_properties[intermediate_segments[i].second]));
 243         less_point lp;
 244         if(lp(output_segments.back().first.first, output_segments.back().first.second) !=
 245            lp(input_segments[intermediate_segments[i].second].first.first,
 246               input_segments[intermediate_segments[i].second].first.second)) {
 247           //edge changed orientation, invert count on edge
 248           output_segments.back().second.second *= -1;
 249         }
 250         if(!scanline_base<Unit>::is_vertical(input_segments[intermediate_segments[i].second].first) &&
 251            scanline_base<Unit>::is_vertical(output_segments.back().first)) {
 252           output_segments.back().second.second *= -1;
 253         }
 254         if(lp(output_segments.back().first.second, output_segments.back().first.first)) {
 255           std::swap(output_segments.back().first.first, output_segments.back().first.second);
 256         }
 257       }
 258     }
 259
 260     template <typename iT>
 261     static inline void validate_scan(std::vector<std::pair<half_edge, int> >& output_segments,
 262                                      iT begin, iT end) {
 263       std::vector<std::set<Point> > intersection_points(std::distance(begin, end));
 264       validate_scan_divide_and_conquer(intersection_points, begin, end);
 265       //validate_scan(intersection_points, begin, end);
 266       segment_intersections(output_segments, intersection_points, begin, end);
 267 //       std::pair<segment_id, segment_id> offenders;
 268 //       if(!verify_scan(offenders, output_segments.begin(), output_segments.end())) {
 269 //         std::cout << "break here!\n";
 270 //         for(typename std::set<Point>::iterator itr = intersection_points[offenders.first].begin();
 271 //             itr != intersection_points[offenders.first].end(); ++itr) {
 272 //           std::cout << (*itr).x() << " " << (*itr).y() << " ";
 273 //         } std::cout << "\n";
 274 //         for(typename std::set<Point>::iterator itr = intersection_points[offenders.second].begin();
 275 //             itr != intersection_points[offenders.second].end(); ++itr) {
 276 //           std::cout << (*itr).x() << " " << (*itr).y() << " ";
 277 //         } std::cout << "\n";
 278 //         exit(1);
 279 //       }
 280     }
 281
 282     //quadratic algorithm to find intersections
 283     template <typename iT, typename segment_id>
 284     static inline bool verify_scan(std::pair<segment_id, segment_id>& offenders,
 285                                    iT begin, iT end) {
 286
 287       std::vector<std::pair<half_edge, segment_id> > data(begin, end);
 288       for(std::size_t i = 0; i < data.size(); ++i) {
 289         if(data[i].first.second < data[i].first.first) {
 290           std::swap(data[i].first.first, data[i].first.second);
 291         }
 292       }
 293       polygon_sort(data.begin(), data.end());
 294       for(typename std::vector<std::pair<half_edge, segment_id> >::iterator outer = data.begin();
 295           outer != data.end(); ++outer) {
 296         const half_edge& he1 = (*outer).first;
 297         segment_id id1 = (*outer).second;
 298         for(typename std::vector<std::pair<half_edge, segment_id> >::iterator inner = outer;
 299             inner != data.end(); ++inner) {
 300           const half_edge& he2 = (*inner).first;
 301           if(he1 == he2) continue;
 302           if((std::min)(he2. first.get(HORIZONTAL),
 303                         he2.second.get(HORIZONTAL)) >
 304              (std::max)(he1.second.get(HORIZONTAL),
 305                         he1.first.get(HORIZONTAL)))
 306             break;
 307           segment_id id2 = (*inner).second;
 308           if(scanline_base<Unit>::intersects(he1, he2)) {
 309             offenders.first = id1;
 310             offenders.second = id2;
 311             //std::cout << he1.first.x() << " " << he1.first.y() << " " << he1.second.x() << " " << he1.second.y() << " " << he2.first.x() << " " << he2.first.y() << " " << he2.second.x() << " " << he2.second.y() << "\n";
 312             return false;
 313           }
 314         }
 315       }
 316       return true;
 317     }
 318
 319     class less_point_down_slope : public std::binary_function<Point, Point, bool> {
 320     public:
 321       inline less_point_down_slope() {}
 322       inline bool operator () (const Point& pt1, const Point& pt2) const {
 323         if(pt1.get(HORIZONTAL) < pt2.get(HORIZONTAL)) return true;
 324         if(pt1.get(HORIZONTAL) == pt2.get(HORIZONTAL)) {
 325           if(pt1.get(VERTICAL) > pt2.get(VERTICAL)) return true;
 326         }
 327         return false;
 328       }
 329     };
 330
 331     template <typename iT>
 332     static inline void segment_edge(std::vector<std::pair<half_edge, int> >& output_segments,
 333                                     const half_edge& , segment_id id, iT begin, iT end) {
 334       iT current = begin;
 335       iT next = begin;
 336       ++next;
 337       while(next != end) {
 338         output_segments.push_back(std::make_pair(half_edge(*current, *next), id));
 339         current = next;
 340         ++next;
 341       }
 342     }
 343
 344     template <typename iT>
 345     static inline void segment_intersections(std::vector<std::pair<half_edge, int> >& output_segments,
 346                                              std::vector<std::set<Point> >& intersection_points,
 347                                              iT begin, iT end) {
 348       for(iT iter = begin; iter != end; ++iter) {
 349         //less_point lp;
 350         const half_edge& he = (*iter).first;
 351         //if(lp(he.first, he.second)) {
 352         //  //it is the begin event
 353           segment_id id = (*iter).second;
 354           const std::set<Point>& pts = intersection_points[id];
 355           Point hpt(he.first.get(HORIZONTAL)+1, he.first.get(VERTICAL));
 356           if(!scanline_base<Unit>::is_vertical(he) && scanline_base<Unit>::less_slope(he.first.get(HORIZONTAL), he.first.get(VERTICAL),
 357                                             he.second, hpt)) {
 358             //slope is below horizontal
 359             std::vector<Point> tmpPts;
 360             tmpPts.reserve(pts.size());
 361             tmpPts.insert(tmpPts.end(), pts.begin(), pts.end());
 362             less_point_down_slope lpds;
 363             polygon_sort(tmpPts.begin(), tmpPts.end(), lpds);
 364             segment_edge(output_segments, he, id, tmpPts.begin(), tmpPts.end());
 365           } else {
 366             segment_edge(output_segments, he, id, pts.begin(), pts.end());
 367           }
 368           //}
 369       }
 370     }
 371
 372 //     //iT iterator over unsorted pair<Point> representing line segments of input
 373 //     //output_segments is populated with fully intersected output line segment half
 374 //     //edges and the index of the input segment that they are assoicated with
 375 //     //duplicate output half edges with different ids will be generated in the case
 376 //     //that parallel input segments intersection
 377 //     //outputs are in sorted order and include both begin and end events for
 378 //     //each segment
 379 //     template <typename iT>
 380 //     inline void scan(std::vector<std::pair<half_edge, int> >& output_segments,
 381 //                      iT begin, iT end) {
 382 //       std::map<segment_id, std::set<Point> > intersection_points;
 383 //       scan(intersection_points, begin, end);
 384 //       segment_intersections(output_segments, intersection_points, begin, end);
 385 //     }
 386
 387 //     //iT iterator over sorted sequence of half edge, segment id pairs representing segment begin and end points
 388 //     //intersection points provides a mapping from input segment id (vector index) to the set
 389 //     //of intersection points assocated with that input segment
 390 //     template <typename iT>
 391 //     inline void scan(std::map<segment_id, std::set<Point> >& intersection_points,
 392 //                      iT begin, iT end) {
 393 //       for(iT iter = begin; iter != end; ++iter) {
 394 //         const std::pair<half_edge, int>& elem = *iter;
 395 //         const half_edge& he = elem.first;
 396 //         Unit current_x = he.first.get(HORIZONTAL);
 397 //         if(current_x != x_) {
 398 //           process_scan_event(intersection_points);
 399 //           while(!intersection_queue_.empty() &&
 400 //                 (*(intersection_queue_.begin()).get(HORIZONTAL) < current_x)) {
 401 //             x_ = *(intersection_queue_.begin()).get(HORIZONTAL);
 402 //             process_intersections_at_scan_event(intersection_points);
 403 //           }
 404 //           x_ = current_x;
 405 //         }
 406 //         event_edges_.push_back(elem);
 407 //       }
 408 //       process_scan_event(intersection_points);
 409 //     }
 410
 411 //     inline iterator lookup(const half_edge& he) {
 412 //       return edge_scanline_.find(he);
 413 //     }
 414
 415 //     inline void insert_into_scanline(const half_edge& he, int id) {
 416 //       edge_scanline_[he].insert(id);
 417 //     }
 418
 419 //     inline void lookup_and_remove(const half_edge& he, int id) {
 420 //       iterator remove_iter = lookup(he);
 421 //       if(remove_iter == edge_scanline_.end()) {
 422 //         //std::cout << "failed to find removal segment in scanline\n";
 423 //         return;
 424 //       }
 425 //       std::set<segment_id>& ids = (*remove_iter).second;
 426 //       std::set<segment_id>::iterator id_iter = ids.find(id);
 427 //       if(id_iter == ids.end()) {
 428 //         //std::cout << "failed to find removal segment id in scanline set\n";
 429 //         return;
 430 //       }
 431 //       ids.erase(id_iter);
 432 //       if(ids.empty())
 433 //         edge_scanline_.erase(remove_iter);
 434 //     }
 435
 436 //     static inline void update_segments(std::map<segment_id, std::set<Point> >& intersection_points,
 437 //                                        const std::set<segment_id>& segments, Point pt) {
 438 //       for(std::set<segment_id>::const_iterator itr = segments.begin(); itr != segments.end(); ++itr) {
 439 //         intersection_points[*itr].insert(pt);
 440 //       }
 441 //     }
 442
 443 //     inline void process_intersections_at_scan_event(std::map<segment_id, std::set<Point> >& intersection_points) {
 444 //       //there may be additional intersection points at this x location that haven't been
 445 //       //found yet if vertical or near vertical line segments intersect more than
 446 //       //once before the next x location
 447 //       just_before_ = true;
 448 //       std::set<iterator> intersecting_elements;
 449 //       std::set<Unit> intersection_locations;
 450 //       typedef typename std::set<Point>::iterator intersection_iterator;
 451 //       intersection_iterator iter;
 452 //       //first find all secondary intersection locations and all scanline iterators
 453 //       //that are intersecting
 454 //       for(iter = intersection_queue_.begin();
 455 //           iter != intersection_queue_.end() && (*iter).get(HORIZONTAL) == x_; ++iter) {
 456 //         Point pt = *iter;
 457 //         Unit y = pt.get(VERTICAL);
 458 //         intersection_locations.insert(y);
 459 //         //if x_ is max there can be only end events and no sloping edges
 460 //         if(x_ != (std::numeric_limits<Unit>::max)()) {
 461 //           //deal with edges that project to the right of scanline
 462 //           //first find the edges in the scanline adjacent to primary intersectin points
 463 //           //lookup segment in scanline at pt
 464 //           iterator itr = edge_scanline_.lower_bound(half_edge(pt, Point(x_+1, y)));
 465 //           //look above pt in scanline until reaching end or segment that doesn't intersect
 466 //           //1x1 grid upper right of pt
 467 //           //look below pt in scanline until reaching begin or segment that doesn't interset
 468 //           //1x1 grid upper right of pt
 469
 470 //           //second find edges in scanline on the y interval of each edge found in the previous
 471 //           //step for x_ to x_ + 1
 472
 473 //           //third find overlaps in the y intervals of all found edges to find all
 474 //           //secondary intersection points
 475
 476 //         }
 477 //       }
 478 //       //erase the intersection points from the queue
 479 //       intersection_queue_.erase(intersection_queue_.begin(), iter);
 480 //       std::vector<scanline_element> insertion_edges;
 481 //       insertion_edges.reserve(intersecting_elements.size());
 482 //       std::vector<std::pair<Unit, iterator> > sloping_ends;
 483 //       //do all the work of updating the output of all intersecting
 484 //       for(typename std::set<iterator>::iterator inter_iter = intersecting_elements.begin();
 485 //           inter_iter != intersecting_elements.end(); ++inter_iter) {
 486 //         //if it is horizontal update it now and continue
 487 //         if(is_horizontal((*inter_iter).first)) {
 488 //           update_segments(intersection_points, (*inter_iter).second, Point(x_, (*inter_iter).first.get(VERTICAL)));
 489 //         } else {
 490 //           //if x_ is max there can be only end events and no sloping edges
 491 //           if(x_ != (std::numeric_limits<Unit>::max)()) {
 492 //             //insert its end points into the vector of sloping ends
 493 //             const half_edge& he = (*inter_iter).first;
 494 //             Unit y = evalAtXforY(x_, he.first, he.second);
 495 //             Unit y2 = evalAtXforY(x_+1, he.first, he.second);
 496 //             if(y2 >= y) y2 +=1; //we round up, in exact case we don't worry about overbite of one
 497 //             else y += 1; //downward sloping round up
 498 //             sloping_ends.push_back(std::make_pair(y, inter_iter));
 499 //             sloping_ends.push_back(std::make_pair(y2, inter_iter));
 500 //           }
 501 //         }
 502 //       }
 503
 504 //       //merge sloping element data
 505 //       polygon_sort(sloping_ends.begin(), sloping_ends.end());
 506 //       std::map<Unit, std::set<iterator> > sloping_elements;
 507 //       std::set<iterator> merge_elements;
 508 //       for(typename std::vector<std::pair<Unit, iterator> >::iterator slop_iter = sloping_ends.begin();
 509 //           slop_iter == sloping_ends.end(); ++slop_iter) {
 510 //         //merge into sloping elements
 511 //         typename std::set<iterator>::iterator merge_iterator = merge_elements.find((*slop_iter).second);
 512 //         if(merge_iterator == merge_elements.end()) {
 513 //           merge_elements.insert((*slop_iter).second);
 514 //         } else {
 515 //           merge_elements.erase(merge_iterator);
 516 //         }
 517 //         sloping_elements[(*slop_iter).first] = merge_elements;
 518 //       }
 519
 520 //       //scan intersection points
 521 //       typename std::map<Unit, std::set<segment_id> >::iterator vertical_iter = vertical_data_.begin();
 522 //       typename std::map<Unit, std::set<iterator> >::iterator sloping_iter = sloping_elements.begin();
 523 //       for(typename std::set<Unit>::iterator position_iter = intersection_locations.begin();
 524 //           position_iter == intersection_locations.end(); ++position_iter) {
 525 //         //look for vertical segments that intersect this point and update them
 526 //         Unit y = *position_iter;
 527 //         Point pt(x_, y);
 528 //         //handle vertical segments
 529 //         if(vertical_iter != vertical_data_.end()) {
 530 //           typename std::map<Unit, std::set<segment_id> >::iterator next_vertical = vertical_iter;
 531 //           for(++next_vertical; next_vertical != vertical_data_.end() &&
 532 //                 (*next_vertical).first < y; ++next_vertical) {
 533 //             vertical_iter = next_vertical;
 534 //           }
 535 //           if((*vertical_iter).first < y && !(*vertical_iter).second.empty()) {
 536 //             update_segments(intersection_points, (*vertical_iter).second, pt);
 537 //             ++vertical_iter;
 538 //             if(vertical_iter != vertical_data_.end() && (*vertical_iter).first == y)
 539 //               update_segments(intersection_points, (*vertical_iter).second, pt);
 540 //           }
 541 //         }
 542 //         //handle sloping segments
 543 //         if(sloping_iter != sloping_elements.end()) {
 544 //           typename std::map<Unit, std::set<iterator> >::iterator next_sloping = sloping_iter;
 545 //           for(++next_sloping; next_sloping != sloping_elements.end() &&
 546 //                 (*next_sloping).first < y; ++next_sloping) {
 547 //             sloping_iter = next_sloping;
 548 //           }
 549 //           if((*sloping_iter).first < y && !(*sloping_iter).second.empty()) {
 550 //             for(typename std::set<iterator>::iterator element_iter = (*sloping_iter).second.begin();
 551 //                 element_iter != (*sloping_iter).second.end(); ++element_iter) {
 552 //               const half_edge& he = (*element_iter).first;
 553 //               if(intersects_grid(pt, he)) {
 554 //                 update_segments(intersection_points, (*element_iter).second, pt);
 555 //               }
 556 //             }
 557 //             ++sloping_iter;
 558 //             if(sloping_iter != sloping_elements.end() && (*sloping_iter).first == y &&
 559 //                !(*sloping_iter).second.empty()) {
 560 //               for(typename std::set<iterator>::iterator element_iter = (*sloping_iter).second.begin();
 561 //                   element_iter != (*sloping_iter).second.end(); ++element_iter) {
 562 //                 const half_edge& he = (*element_iter).first;
 563 //                 if(intersects_grid(pt, he)) {
 564 //                   update_segments(intersection_points, (*element_iter).second, pt);
 565 //                 }
 566 //               }
 567 //             }
 568 //           }
 569 //         }
 570 //       }
 571
 572 //       //erase and reinsert edges into scanline with check for future intersection
 573 //     }
 574
 575 //     inline void process_scan_event(std::map<segment_id, std::set<Point> >& intersection_points) {
 576 //       just_before_ = true;
 577
 578 //       //process end events by removing those segments from the scanline
 579 //       //and insert vertices of all events into intersection queue
 580 //       Point prev_point((std::numeric_limits<Unit>::min)(), (std::numeric_limits<Unit>::min)());
 581 //       less_point lp;
 582 //       std::set<segment_id> vertical_ids;
 583 //       vertical_data_.clear();
 584 //       for(std::size_t i = 0; i < event_edges_.size(); ++i) {
 585 //         segment_id id = event_edges_[i].second;
 586 //         const half_edge& he = event_edges_[i].first;
 587 //         //vertical half edges are handled during intersection processing because
 588 //         //they cannot be inserted into the scanline
 589 //         if(!is_vertical(he)) {
 590 //           if(lp(he.second, he.first)) {
 591 //             //half edge is end event
 592 //             lookup_and_remove(he, id);
 593 //           } else {
 594 //             //half edge is begin event
 595 //             insert_into_scanline(he, id);
 596 //             //note that they will be immediately removed and reinserted after
 597 //             //handling their intersection (vertex)
 598 //             //an optimization would allow them to be processed specially to avoid the redundant
 599 //             //removal and reinsertion
 600 //           }
 601 //         } else {
 602 //           //common case if you are lucky
 603 //           //update the map of y to set of segment id
 604 //           if(lp(he.second, he.first)) {
 605 //             //half edge is end event
 606 //             std::set<segment_id>::iterator itr = vertical_ids.find(id);
 607 //             if(itr == vertical_ids.end()) {
 608 //               //std::cout << "Failed to find end event id in vertical ids\n";
 609 //             } else {
 610 //               vertical_ids.erase(itr);
 611 //               vertical_data_[he.first.get(HORIZONTAL)] = vertical_ids;
 612 //             }
 613 //           } else {
 614 //             //half edge is a begin event
 615 //             vertical_ids.insert(id);
 616 //             vertical_data_[he.first.get(HORIZONTAL)] = vertical_ids;
 617 //           }
 618 //         }
 619 //         //prevent repeated insertion of same vertex into intersection queue
 620 //         if(prev_point != he.first)
 621 //           intersection_queue_.insert(he.first);
 622 //         else
 623 //           prev_point = he.first;
 624 //         // process intersections at scan event
 625 //         process_intersections_at_scan_event(intersection_points);
 626 //       }
 627 //       event_edges_.clear();
 628 //     }
 629
 630   public:
 631     template <typename stream_type>
 632     static inline bool test_validate_scan(stream_type& stdcout) {
 633       std::vector<std::pair<half_edge, segment_id> > input, edges;
 634       input.push_back(std::make_pair(half_edge(Point(0, 0), Point(0, 10)), 0));
 635       input.push_back(std::make_pair(half_edge(Point(0, 0), Point(10, 10)), 1));
 636       std::pair<segment_id, segment_id> result;
 637       validate_scan(edges, input.begin(), input.end());
 638       if(!verify_scan(result, edges.begin(), edges.end())) {
 639         stdcout << "s fail1 " << result.first << " " << result.second << "\n";
 640         return false;
 641       }
 642       input.push_back(std::make_pair(half_edge(Point(0, 5), Point(5, 5)), 2));
 643       edges.clear();
 644       validate_scan(edges, input.begin(), input.end());
 645       if(!verify_scan(result, edges.begin(), edges.end())) {
 646         stdcout << "s fail2 " << result.first << " " << result.second << "\n";
 647         return false;
 648       }
 649       input.pop_back();
 650       input.push_back(std::make_pair(half_edge(Point(1, 0), Point(11, 11)), input.size()));
 651       edges.clear();
 652       validate_scan(edges, input.begin(), input.end());
 653       if(!verify_scan(result, edges.begin(), edges.end())) {
 654         stdcout << "s fail3 " << result.first << " " << result.second << "\n";
 655         return false;
 656       }
 657       input.push_back(std::make_pair(half_edge(Point(1, 0), Point(10, 11)), input.size()));
 658       edges.clear();
 659       validate_scan(edges, input.begin(), input.end());
 660       if(!verify_scan(result, edges.begin(), edges.end())) {
 661         stdcout << "s fail4 " << result.first << " " << result.second << "\n";
 662         return false;
 663       }
 664       input.pop_back();
 665       input.push_back(std::make_pair(half_edge(Point(1, 2), Point(11, 11)), input.size()));
 666       edges.clear();
 667       validate_scan(edges, input.begin(), input.end());
 668       if(!verify_scan(result, edges.begin(), edges.end())) {
 669         stdcout << "s fail5 " << result.first << " " << result.second << "\n";
 670         return false;
 671       }
 672       input.push_back(std::make_pair(half_edge(Point(0, 5), Point(0, 11)), input.size()));
 673       edges.clear();
 674       validate_scan(edges, input.begin(), input.end());
 675       if(!verify_scan(result, edges.begin(), edges.end())) {
 676         stdcout << "s fail6 " << result.first << " " << result.second << "\n";
 677         return false;
 678       }
 679       input.pop_back();
 680       for(std::size_t i = 0; i < input.size(); ++i) {
 681         std::swap(input[i].first.first, input[i].first.second);
 682       }
 683       edges.clear();
 684       validate_scan(edges, input.begin(), input.end());
 685       if(!verify_scan(result, edges.begin(), edges.end())) {
 686         stdcout << "s fail5 2 " << result.first << " " << result.second << "\n";
 687         return false;
 688       }
 689       for(std::size_t i = 0; i < input.size(); ++i) {
 690         input[i].first.first = Point(input[i].first.first.get(HORIZONTAL) * -1,
 691                                      input[i].first.first.get(VERTICAL) * -1);
 692         input[i].first.second = Point(input[i].first.second.get(HORIZONTAL) * -1,
 693                                      input[i].first.second.get(VERTICAL) * -1);
 694       }
 695       edges.clear();
 696       validate_scan(edges, input.begin(), input.end());
 697       stdcout << edges.size() << "\n";
 698       if(!verify_scan(result, edges.begin(), edges.end())) {
 699         stdcout << "s fail5 3 " << result.first << " " << result.second << "\n";
 700         return false;
 701       }
 702       input.clear();
 703       edges.clear();
 704       input.push_back(std::make_pair(half_edge(Point(5, 7), Point(7, 6)), 0));
 705       input.push_back(std::make_pair(half_edge(Point(2, 4), Point(6, 7)), 1));
 706             validate_scan(edges, input.begin(), input.end());
 707       if(!verify_scan(result, edges.begin(), edges.end())) {
 708         stdcout << "s fail2 1 " << result.first << " " << result.second << "\n";
 709         print(input);
 710         print(edges);
 711         return false;
 712       }
 713       input.clear();
 714       edges.clear();
 715       input.push_back(std::make_pair(half_edge(Point(3, 2), Point(1, 7)), 0));
 716       input.push_back(std::make_pair(half_edge(Point(0, 6), Point(7, 4)), 1));
 717             validate_scan(edges, input.begin(), input.end());
 718       if(!verify_scan(result, edges.begin(), edges.end())) {
 719         stdcout << "s fail2 2 " << result.first << " " << result.second << "\n";
 720         print(input);
 721         print(edges);
 722         return false;
 723       }
 724       input.clear();
 725       edges.clear();
 726       input.push_back(std::make_pair(half_edge(Point(6, 6), Point(1, 0)), 0));
 727       input.push_back(std::make_pair(half_edge(Point(3, 6), Point(2, 3)), 1));
 728             validate_scan(edges, input.begin(), input.end());
 729       if(!verify_scan(result, edges.begin(), edges.end())) {
 730         stdcout << "s fail2 3 " << result.first << " " << result.second << "\n";
 731         print(input);
 732         print(edges);
 733         return false;
 734       }
 735       input.clear();
 736       edges.clear();
 737       input.push_back(std::make_pair(half_edge(Point(0, 0), Point(7, 0)), 0));
 738       input.push_back(std::make_pair(half_edge(Point(6, 0), Point(2, 0)), 1));
 739             validate_scan(edges, input.begin(), input.end());
 740       if(!verify_scan(result, edges.begin(), edges.end())) {
 741         stdcout << "s fail2 4 " << result.first << " " << result.second << "\n";
 742         print(input);
 743         print(edges);
 744         return false;
 745       }
 746       input.clear();
 747       edges.clear();
 748       input.push_back(std::make_pair(half_edge(Point(-17333131 - -17208131, -10316869 - -10191869), Point(0, 0)), 0));
 749       input.push_back(std::make_pair(half_edge(Point(-17291260 - -17208131, -10200000 - -10191869), Point(-17075000 - -17208131, -10200000 - -10191869)), 1));
 750       validate_scan(edges, input.begin(), input.end());
 751       if(!verify_scan(result, edges.begin(), edges.end())) {
 752         stdcout << "s fail2 5 " << result.first << " " << result.second << "\n";
 753         print(input);
 754         print(edges);
 755         return false;
 756       }
 757       input.clear();
 758       edges.clear();
 759       input.push_back(std::make_pair(half_edge(Point(-17333131, -10316869), Point(-17208131, -10191869)), 0));
 760       input.push_back(std::make_pair(half_edge(Point(-17291260, -10200000), Point(-17075000, -10200000)), 1));
 761       validate_scan(edges, input.begin(), input.end());
 762       if(!verify_scan(result, edges.begin(), edges.end())) {
 763         stdcout << "s fail2 6 " << result.first << " " << result.second << "\n";
 764         print(input);
 765         print(edges);
 766         return false;
 767       }
 768       input.clear();
 769       edges.clear();
 770       input.push_back(std::make_pair(half_edge(Point(-9850009+9853379, -286971+290340), Point(-12777869+9853379, -3214831+290340)), 0));
 771       input.push_back(std::make_pair(half_edge(Point(-5223510+9853379, -290340+290340), Point(-9858140+9853379, -290340+290340)), 1));
 772       validate_scan(edges, input.begin(), input.end());
 773       print(edges);
 774       if(!verify_scan(result, edges.begin(), edges.end())) {
 775         stdcout << "s fail2 7 " << result.first << " " << result.second << "\n";
 776         print(input);
 777         print(edges);
 778         return false;
 779       }
 780       input.clear();
 781       edges.clear();
 782       input.push_back(std::make_pair(half_edge(Point(-9850009, -286971), Point(-12777869, -3214831)), 0));
 783       input.push_back(std::make_pair(half_edge(Point(-5223510, -290340), Point(-9858140, -290340)), 1));
 784       validate_scan(edges, input.begin(), input.end());
 785       if(!verify_scan(result, edges.begin(), edges.end())) {
 786         stdcout << "s fail2 8 " << result.first << " " << result.second << "\n";
 787         print(input);
 788         print(edges);
 789         return false;
 790       }
 791       //3 3 2 2: 0; 4 2 0 6: 1; 0 3 6 3: 2; 4 1 5 5: 3;
 792       input.clear();
 793       edges.clear();
 794       input.push_back(std::make_pair(half_edge(Point(3, 3), Point(2, 2)), 0));
 795       input.push_back(std::make_pair(half_edge(Point(4, 2), Point(0, 6)), 1));
 796       input.push_back(std::make_pair(half_edge(Point(0, 3), Point(6, 3)), 2));
 797       input.push_back(std::make_pair(half_edge(Point(4, 1), Point(5, 5)), 3));
 798             validate_scan(edges, input.begin(), input.end());
 799       if(!verify_scan(result, edges.begin(), edges.end())) {
 800         stdcout << "s fail4 1 " << result.first << " " << result.second << "\n";
 801         print(input);
 802         print(edges);
 803         return false;
 804       }
 805       //5 7 1 3: 0; 4 5 2 1: 1; 2 5 2 1: 2; 4 1 5 3: 3;
 806       input.clear();
 807       edges.clear();
 808       input.push_back(std::make_pair(half_edge(Point(5, 7), Point(1, 3)), 0));
 809       input.push_back(std::make_pair(half_edge(Point(4, 5), Point(2, 1)), 1));
 810       input.push_back(std::make_pair(half_edge(Point(2, 5), Point(2, 1)), 2));
 811       input.push_back(std::make_pair(half_edge(Point(4, 1), Point(5, 3)), 3));
 812             validate_scan(edges, input.begin(), input.end());
 813       if(!verify_scan(result, edges.begin(), edges.end())) {
 814         stdcout << "s fail4 2 " << result.first << " " << result.second << "\n";
 815         print(input);
 816         print(edges);
 817         return false;
 818       }
 819       //1 0 -4 -1: 0; 0 0 2 -1: 1;
 820       input.clear();
 821       edges.clear();
 822       input.push_back(std::make_pair(half_edge(Point(1, 0), Point(-4, -1)), 0));
 823       input.push_back(std::make_pair(half_edge(Point(0, 0), Point(2, -1)), 1));
 824             validate_scan(edges, input.begin(), input.end());
 825       if(!verify_scan(result, edges.begin(), edges.end())) {
 826         stdcout << "s fail2 5 " << result.first << " " << result.second << "\n";
 827         print(input);
 828         print(edges);
 829         return false;
 830       }
 831       Unit min_c =0;
 832       Unit max_c =0;
 833       for(unsigned int outer = 0; outer < 1000; ++outer) {
 834         input.clear();
 835         for(unsigned int i = 0; i < 4; ++i) {
 836           Unit x1 = rand();
 837           Unit x2 = rand();
 838           Unit y1 = rand();
 839           Unit y2 = rand();
 840           int neg1 = rand() % 2;
 841           if(neg1) x1 *= -1;
 842           int neg2 = rand() % 2;
 843           if(neg2) x2 *= -1;
 844           int neg3 = rand() % 2;
 845           if(neg3) y1 *= -1;
 846           int neg4 = rand() % 2;
 847           if(neg4) y2 *= -1;
 848           if(x1 < min_c) min_c = x1;
 849           if(x2 < min_c) min_c = x2;
 850           if(y1 < min_c) min_c = y1;
 851           if(y2 < min_c) min_c = y2;
 852           if(x1 > max_c) max_c = x1;
 853           if(x2 > max_c) max_c = x2;
 854           if(y1 > max_c) max_c = y1;
 855           if(y2 > max_c) max_c = y2;
 856           Point pt1(x1, y1);
 857           Point pt2(x2, y2);
 858           if(pt1 != pt2)
 859             input.push_back(std::make_pair(half_edge(pt1, pt2), i));
 860         }
 861         edges.clear();
 862         validate_scan(edges, input.begin(), input.end());
 863         if(!verify_scan(result, edges.begin(), edges.end())) {
 864           stdcout << "s fail9 " << outer << ": " << result.first << " " << result.second << "\n";
 865           print(input);
 866           print(edges);
 867           return false;
 868         }
 869       }
 870       return true;
 871     }
 872
 873     //static void print(const std::pair<half_edge, segment_id>& segment) {
 874       //std::cout << segment.first.first << " " << segment.first.second << ": " << segment.second << "; ";
 875     //}
 876     static void print(const std::vector<std::pair<half_edge, segment_id> >& vec) {
 877       for(std::size_t i = 0; i < vec.size(); ++ i) {
 878       //  print(vec[i]);
 879       }
 880       //std::cout << "\n";
 881     }
 882
 883     template <typename stream_type>
 884     static inline bool test_verify_scan(stream_type& stdcout) {
 885       std::vector<std::pair<half_edge, segment_id> > edges;
 886       edges.push_back(std::make_pair(half_edge(Point(0, 0), Point(0, 10)), 0));
 887       edges.push_back(std::make_pair(half_edge(Point(0, 0), Point(10, 10)), 1));
 888       std::pair<segment_id, segment_id> result;
 889       if(!verify_scan(result, edges.begin(), edges.end())) {
 890         stdcout << "fail1\n";
 891         return false;
 892       }
 893       edges.push_back(std::make_pair(half_edge(Point(0, 5), Point(5, 5)), 2));
 894       if(verify_scan(result, edges.begin(), edges.end())) {
 895         stdcout << "fail2\n";
 896         return false;
 897       }
 898       edges.pop_back();
 899       edges.push_back(std::make_pair(half_edge(Point(1, 0), Point(11, 11)), (segment_id)edges.size()));
 900       if(!verify_scan(result, edges.begin(), edges.end())) {
 901         stdcout << "fail3\n";
 902         return false;
 903       }
 904       edges.push_back(std::make_pair(half_edge(Point(1, 0), Point(10, 11)), (segment_id)edges.size()));
 905       if(verify_scan(result, edges.begin(), edges.end())) {
 906         stdcout << "fail4\n";
 907         return false;
 908       }
 909       edges.pop_back();
 910       edges.push_back(std::make_pair(half_edge(Point(1, 2), Point(11, 11)), (segment_id)edges.size()));
 911       if(!verify_scan(result, edges.begin(), edges.end())) {
 912         stdcout << "fail5 " << result.first << " " << result.second << "\n";
 913         return false;
 914       }
 915       edges.push_back(std::make_pair(half_edge(Point(0, 5), Point(0, 11)), (segment_id)edges.size()));
 916       if(verify_scan(result, edges.begin(), edges.end())) {
 917         stdcout << "fail6 " << result.first << " " << result.second << "\n";
 918         return false;
 919       }
 920       edges.pop_back();
 921       for(std::size_t i = 0; i < edges.size(); ++i) {
 922         std::swap(edges[i].first.first, edges[i].first.second);
 923       }
 924       if(!verify_scan(result, edges.begin(), edges.end())) {
 925         stdcout << "fail5 2 " << result.first << " " << result.second << "\n";
 926         return false;
 927       }
 928       for(std::size_t i = 0; i < edges.size(); ++i) {
 929         edges[i].first.first = Point(edges[i].first.first.get(HORIZONTAL) * -1,
 930                                      edges[i].first.first.get(VERTICAL) * -1);
 931         edges[i].first.second = Point(edges[i].first.second.get(HORIZONTAL) * -1,
 932                                      edges[i].first.second.get(VERTICAL) * -1);
 933       }
 934       if(!verify_scan(result, edges.begin(), edges.end())) {
 935         stdcout << "fail5 3 " << result.first << " " << result.second << "\n";
 936         return false;
 937       }
 938       return true;
 939     }
 940
 941   };
 942
 943   //scanline consumes the "flattened" fully intersected line segments produced by
 944   //a pass of line_intersection along with property and count information and performs a
 945   //useful operation like booleans or property merge or connectivity extraction
 946   template <typename Unit, typename property_type, typename keytype = std::set<property_type> >
 947   class scanline : public scanline_base<Unit> {
 948   public:
 949     //definitions
 950     typedef typename scanline_base<Unit>::Point Point;
 951
 952     //the first point is the vertex and and second point establishes the slope of an edge eminating from the vertex
 953     //typedef std::pair<Point, Point> half_edge;
 954     typedef typename scanline_base<Unit>::half_edge half_edge;
 955
 956     //scanline comparator functor
 957     typedef typename scanline_base<Unit>::less_half_edge less_half_edge;
 958     typedef typename scanline_base<Unit>::less_point less_point;
 959
 960     typedef keytype property_set;
 961     //this is the data type used internally to store the combination of property counts at a given location
 962     typedef std::vector<std::pair<property_type, int> > property_map;
 963     //this data structure assocates a property and count to a half edge
 964     typedef std::pair<half_edge, std::pair<property_type, int> > vertex_property;
 965     //this data type is used internally to store the combined property data for a given half edge
 966     typedef std::pair<half_edge, property_map> vertex_data;
 967     //this data type stores the combination of many half edges
 968     typedef std::vector<vertex_property> property_merge_data;
 969     //this data structure stores end points of edges in the scanline
 970     typedef std::set<Point, less_point> end_point_queue;
 971
 972     //this is the output data type that is created by the scanline before it is post processed based on content of property sets
 973     typedef std::pair<half_edge, std::pair<property_set, property_set> > half_edge_property;
 974
 975     //this is the scanline data structure
 976     typedef std::map<half_edge, property_map, less_half_edge> scanline_type;
 977     typedef std::pair<half_edge, property_map> scanline_element;
 978     typedef typename scanline_type::iterator iterator;
 979     typedef typename scanline_type::const_iterator const_iterator;
 980
 981     //data
 982     scanline_type scan_data_;
 983     std::vector<iterator> removal_set_; //edges to be removed at the current scanline stop
 984     std::vector<scanline_element> insertion_set_; //edge to be inserted after current scanline stop
 985     end_point_queue end_point_queue_;
 986     Unit x_;
 987     Unit y_;
 988     int just_before_;
 989     typename scanline_base<Unit>::evalAtXforYPack evalAtXforYPack_;
 990   public:
 991     inline scanline() : scan_data_(), removal_set_(), insertion_set_(), end_point_queue_(),
 992                         x_((std::numeric_limits<Unit>::max)()), y_((std::numeric_limits<Unit>::max)()), just_before_(false), evalAtXforYPack_() {
 993       less_half_edge lessElm(&x_, &just_before_, &evalAtXforYPack_);
 994       scan_data_ = scanline_type(lessElm);
 995     }
 996     inline scanline(const scanline& that) : scan_data_(), removal_set_(), insertion_set_(), end_point_queue_(),
 997                                             x_((std::numeric_limits<Unit>::max)()), y_((std::numeric_limits<Unit>::max)()), just_before_(false), evalAtXforYPack_() {
 998       (*this) = that; }
 999     inline scanline& operator=(const scanline& that) {
1000       x_ = that.x_;
1001       y_ = that.y_;
1002       just_before_ = that.just_before_;
1003       end_point_queue_ = that.end_point_queue_;
1004       //I cannot simply copy that.scanline_type to this scanline_type becuase the functor store pointers to other members!
1005       less_half_edge lessElm(&x_, &just_before_);
1006       scan_data_ = scanline_type(lessElm);
1007
1008       scan_data_.insert(that.scan_data_.begin(), that.scan_data_.end());
1009       return *this;
1010     }
1011
1012     template <typename result_type, typename result_functor>
1013     void write_out(result_type& result, result_functor rf, const half_edge& he,
1014                    const property_map& pm_left, const property_map& pm_right) {
1015       //std::cout << "write out ";
1016       //std::cout << he.first << ", " << he.second << "\n";
1017       property_set ps_left, ps_right;
1018       set_unique_property(ps_left, pm_left);
1019       set_unique_property(ps_right, pm_right);
1020       if(ps_left != ps_right) {
1021         //std::cout << "!equivalent\n";
1022         rf(result, he, ps_left, ps_right);
1023       }
1024     }
1025
1026     template <typename result_type, typename result_functor, typename iT>
1027     iT handle_input_events(result_type& result, result_functor rf, iT begin, iT end) {
1028       //typedef typename high_precision_type<Unit>::type high_precision;
1029       //for each event
1030       property_map vertical_properties_above;
1031       property_map vertical_properties_below;
1032       half_edge vertical_edge_above;
1033       half_edge vertical_edge_below;
1034       std::vector<scanline_element> insertion_elements;
1035       //current_iter should increase monotonically toward end as we process scanline stop
1036       iterator current_iter = scan_data_.begin();
1037       just_before_ = true;
1038       Unit y = (std::numeric_limits<Unit>::min)();
1039       bool first_iteration = true;
1040       //we want to return from inside the loop when we hit end or new x
1041 #ifdef BOOST_POLYGON_MSVC
1042 #pragma warning (push)
1043 #pragma warning (disable: 4127)
1044 #endif
1045       while(true) {
1046         if(begin == end || (!first_iteration && ((*begin).first.first.get(VERTICAL) != y ||
1047                                                  (*begin).first.first.get(HORIZONTAL) != x_))) {
1048           //lookup iterator range in scanline for elements coming in from the left
1049           //that end at this y
1050           Point pt(x_, y);
1051           //grab the properties coming in from below
1052           property_map properties_below;
1053           if(current_iter != scan_data_.end()) {
1054             //make sure we are looking at element in scanline just below y
1055             //if(evalAtXforY(x_, (*current_iter).first.first, (*current_iter).first.second) != y) {
1056             if(scanline_base<Unit>::on_above_or_below(Point(x_, y), (*current_iter).first) != 0) {
1057               Point e2(pt);
1058               if(e2.get(VERTICAL) != (std::numeric_limits<Unit>::max)())
1059                 e2.set(VERTICAL, e2.get(VERTICAL) + 1);
1060               else
1061                 e2.set(VERTICAL, e2.get(VERTICAL) - 1);
1062               half_edge vhe(pt, e2);
1063               current_iter = scan_data_.lower_bound(vhe);
1064             }
1065             if(current_iter != scan_data_.end()) {
1066               //get the bottom iterator for elements at this point
1067               //while(evalAtXforY(x_, (*current_iter).first.first, (*current_iter).first.second) >= (high_precision)y &&
1068               while(scanline_base<Unit>::on_above_or_below(Point(x_, y), (*current_iter).first) != 1 &&
1069                     current_iter != scan_data_.begin()) {
1070                 --current_iter;
1071               }
1072               //if(evalAtXforY(x_, (*current_iter).first.first, (*current_iter).first.second) >= (high_precision)y) {
1073               if(scanline_base<Unit>::on_above_or_below(Point(x_, y), (*current_iter).first) != 1) {
1074                 properties_below.clear();
1075               } else {
1076                 properties_below = (*current_iter).second;
1077                 //move back up to y or one past y
1078                 ++current_iter;
1079               }
1080             }
1081           }
1082           std::vector<iterator> edges_from_left;
1083           while(current_iter != scan_data_.end() &&
1084                 //can only be true if y is integer
1085                 //evalAtXforY(x_, (*current_iter).first.first, (*current_iter).first.second) == y) {
1086                 scanline_base<Unit>::on_above_or_below(Point(x_, y), (*current_iter).first) == 0) {
1087             //removal_set_.push_back(current_iter);
1088             ++current_iter;
1089           }
1090           //merge vertical count with count from below
1091           if(!vertical_properties_below.empty()) {
1092             merge_property_maps(vertical_properties_below, properties_below);
1093             //write out vertical edge
1094             write_out(result, rf, vertical_edge_below, properties_below, vertical_properties_below);
1095           } else {
1096             merge_property_maps(vertical_properties_below, properties_below);
1097           }
1098           //iteratively add intertion element counts to count from below
1099           //and write them to insertion set
1100           for(std::size_t i = 0; i < insertion_elements.size(); ++i) {
1101             if(i == 0) {
1102               merge_property_maps(insertion_elements[i].second, vertical_properties_below);
1103               write_out(result, rf, insertion_elements[i].first, insertion_elements[i].second, vertical_properties_below);
1104             } else {
1105               merge_property_maps(insertion_elements[i].second, insertion_elements[i-1].second);
1106               write_out(result, rf, insertion_elements[i].first, insertion_elements[i].second, insertion_elements[i-1].second);
1107             }
1108             insertion_set_.push_back(insertion_elements[i]);
1109           }
1110           if((begin == end || (*begin).first.first.get(HORIZONTAL) != x_)) {
1111             if(vertical_properties_above.empty()) {
1112               return begin;
1113             } else {
1114               y = vertical_edge_above.second.get(VERTICAL);
1115               vertical_properties_below.clear();
1116               vertical_properties_above.swap(vertical_properties_below);
1117               vertical_edge_below = vertical_edge_above;
1118               insertion_elements.clear();
1119               continue;
1120             }
1121           }
1122           vertical_properties_below.clear();
1123           vertical_properties_above.swap(vertical_properties_below);
1124           vertical_edge_below = vertical_edge_above;
1125           insertion_elements.clear();
1126         }
1127         if(begin != end) {
1128           const vertex_property& vp = *begin;
1129           const half_edge& he = vp.first;
1130           y = he.first.get(VERTICAL);
1131           first_iteration = false;
1132           if(! vertical_properties_below.empty() &&
1133              vertical_edge_below.second.get(VERTICAL) < y) {
1134             y = vertical_edge_below.second.get(VERTICAL);
1135             continue;
1136           }
1137           if(scanline_base<Unit>::is_vertical(he)) {
1138             update_property_map(vertical_properties_above, vp.second);
1139             vertical_edge_above = he;
1140           } else {
1141             if(insertion_elements.empty() ||
1142                insertion_elements.back().first != he) {
1143               insertion_elements.push_back(scanline_element(he, property_map()));
1144             }
1145             update_property_map(insertion_elements.back().second, vp.second);
1146           }
1147           ++begin;
1148         }
1149       }
1150 #ifdef BOOST_POLYGON_MSVC
1151 #pragma warning (pop)
1152 #endif
1153
1154     }
1155
1156     inline void erase_end_events(typename end_point_queue::iterator epqi) {
1157       end_point_queue_.erase(end_point_queue_.begin(), epqi);
1158       for(typename std::vector<iterator>::iterator retire_itr = removal_set_.begin();
1159           retire_itr != removal_set_.end(); ++retire_itr) {
1160         scan_data_.erase(*retire_itr);
1161       }
1162       removal_set_.clear();
1163     }
1164
1165
1166     inline void remove_retired_edges_from_scanline() {
1167       just_before_ = true;
1168       typename end_point_queue::iterator epqi = end_point_queue_.begin();
1169       Unit current_x = x_;
1170       Unit previous_x = x_;
1171       while(epqi != end_point_queue_.end() &&
1172             (*epqi).get(HORIZONTAL) <= current_x) {
1173         x_ = (*epqi).get(HORIZONTAL);
1174         if(x_ != previous_x) erase_end_events(epqi);
1175         previous_x = x_;
1176         //lookup elements
1177         Point e2(*epqi);
1178         if(e2.get(VERTICAL) != (std::numeric_limits<Unit>::max)())
1179           e2.set(VERTICAL, e2.get(VERTICAL) + 1);
1180         else
1181           e2.set(VERTICAL, e2.get(VERTICAL) - 1);
1182         half_edge vhe_e(*epqi, e2);
1183         iterator current_iter = scan_data_.lower_bound(vhe_e);
1184         while(current_iter != scan_data_.end() && (*current_iter).first.second == (*epqi)) {
1185           //evalAtXforY(x_, (*current_iter).first.first, (*current_iter).first.second) == (*epqi).get(VERTICAL)) {
1186           removal_set_.push_back(current_iter);
1187           ++current_iter;
1188         }
1189         ++epqi;
1190       }
1191       x_ = current_x;
1192       erase_end_events(epqi);
1193     }
1194
1195     inline void insert_new_edges_into_scanline() {
1196       just_before_ = false;
1197       for(typename std::vector<scanline_element>::iterator insert_itr = insertion_set_.begin();
1198           insert_itr != insertion_set_.end(); ++insert_itr) {
1199         scan_data_.insert(*insert_itr);
1200         end_point_queue_.insert((*insert_itr).first.second);
1201       }
1202       insertion_set_.clear();
1203     }
1204
1205     //iterator over range of vertex property elements and call result functor
1206     //passing edge to be output, the merged data on both sides and the result
1207     template <typename result_type, typename result_functor, typename iT>
1208     void scan(result_type& result, result_functor rf, iT begin, iT end) {
1209       while(begin != end) {
1210         x_ = (*begin).first.first.get(HORIZONTAL); //update scanline stop location
1211         //print_scanline();
1212         --x_;
1213         remove_retired_edges_from_scanline();
1214         ++x_;
1215         begin = handle_input_events(result, rf, begin, end);
1216         remove_retired_edges_from_scanline();
1217         //print_scanline();
1218         insert_new_edges_into_scanline();
1219       }
1220       //print_scanline();
1221       x_ = (std::numeric_limits<Unit>::max)();
1222       remove_retired_edges_from_scanline();
1223     }
1224
1225     //inline void print_scanline() {
1226     //  std::cout << "scanline at " << x_ << ": ";
1227     //  for(iterator itr = scan_data_.begin(); itr != scan_data_.end(); ++itr) {
1228     //    const scanline_element& se = *itr;
1229     //    const half_edge& he = se.first;
1230     //    const property_map& mp = se.second;
1231     //    std::cout << he.first << ", " << he.second << " ( ";
1232     //    for(std::size_t i = 0; i < mp.size(); ++i) {
1233     //      std::cout << mp[i].first << ":" << mp[i].second << " ";
1234     //    } std::cout << ") ";
1235     //  } std::cout << "\n";
1236     //}
1237
1238     static inline void merge_property_maps(property_map& mp, const property_map& mp2) {
1239       property_map newmp;
1240       newmp.reserve(mp.size() + mp2.size());
1241       unsigned int i = 0;
1242       unsigned int j = 0;
1243       while(i != mp.size() && j != mp2.size()) {
1244         if(mp[i].first < mp2[j].first) {
1245           newmp.push_back(mp[i]);
1246           ++i;
1247         } else if(mp[i].first > mp2[j].first) {
1248           newmp.push_back(mp2[j]);
1249           ++j;
1250         } else {
1251           int count = mp[i].second;
1252           count += mp2[j].second;
1253           if(count) {
1254             newmp.push_back(mp[i]);
1255             newmp.back().second = count;
1256           }
1257           ++i;
1258           ++j;
1259         }
1260       }
1261       while(i != mp.size()) {
1262         newmp.push_back(mp[i]);
1263         ++i;
1264       }
1265       while(j != mp2.size()) {
1266         newmp.push_back(mp2[j]);
1267         ++j;
1268       }
1269       mp.swap(newmp);
1270     }
1271
1272     static inline void update_property_map(property_map& mp, const std::pair<property_type, int>& prop_data) {
1273       property_map newmp;
1274       newmp.reserve(mp.size() +1);
1275       bool consumed = false;
1276       for(std::size_t i = 0; i < mp.size(); ++i) {
1277         if(!consumed && prop_data.first == mp[i].first) {
1278           consumed = true;
1279           int count = prop_data.second + mp[i].second;
1280           if(count)
1281             newmp.push_back(std::make_pair(prop_data.first, count));
1282         } else if(!consumed && prop_data.first < mp[i].first) {
1283           consumed = true;
1284           newmp.push_back(prop_data);
1285           newmp.push_back(mp[i]);
1286         } else {
1287           newmp.push_back(mp[i]);
1288         }
1289       }
1290       if(!consumed) newmp.push_back(prop_data);
1291       mp.swap(newmp);
1292     }
1293
1294     static inline void set_unique_property(property_set& unqiue_property, const property_map& property) {
1295       unqiue_property.clear();
1296       for(typename property_map::const_iterator itr = property.begin(); itr != property.end(); ++itr) {
1297         if((*itr).second > 0)
1298           unqiue_property.insert(unqiue_property.end(), (*itr).first);
1299       }
1300     }
1301
1302     static inline bool common_vertex(const half_edge& he1, const half_edge& he2) {
1303       return he1.first == he2.first ||
1304         he1.first == he2.second ||
1305         he1.second == he2.first ||
1306         he1.second == he2.second;
1307     }
1308
1309     typedef typename scanline_base<Unit>::vertex_half_edge vertex_half_edge;
1310     template <typename iT>
1311     static inline void convert_segments_to_vertex_half_edges(std::vector<vertex_half_edge>& output, iT begin, iT end) {
1312       for( ; begin != end; ++begin) {
1313         const half_edge& he = (*begin).first;
1314         int count = (*begin).second;
1315         output.push_back(vertex_half_edge(he.first, he.second, count));
1316         output.push_back(vertex_half_edge(he.second, he.first, -count));
1317       }
1318       polygon_sort(output.begin(), output.end());
1319     }
1320
1321     class test_functor {
1322     public:
1323       inline test_functor() {}
1324       inline void operator()(std::vector<std::pair<half_edge, std::pair<property_set, property_set> > >& result,
1325                              const half_edge& he, const property_set& ps_left, const property_set& ps_right) {
1326         result.push_back(std::make_pair(he, std::make_pair(ps_left, ps_right)));
1327       }
1328     };
1329     template <typename stream_type>
1330     static inline bool test_scanline(stream_type& stdcout) {
1331       std::vector<std::pair<half_edge, std::pair<property_set, property_set> > > result;
1332       std::vector<std::pair<half_edge, std::pair<property_type, int> > > input;
1333       input.push_back(std::make_pair(half_edge(Point(0, 0), Point(0, 10)), std::make_pair(0, 1)));
1334       input.push_back(std::make_pair(half_edge(Point(0, 0), Point(10, 0)), std::make_pair(0, 1)));
1335       input.push_back(std::make_pair(half_edge(Point(0, 10), Point(10, 10)), std::make_pair(0, -1)));
1336       input.push_back(std::make_pair(half_edge(Point(10, 0), Point(10, 10)), std::make_pair(0, -1)));
1337       scanline sl;
1338       test_functor tf;
1339       sl.scan(result, tf, input.begin(), input.end());
1340       stdcout << "scanned\n";
1341       for(std::size_t i = 0; i < result.size(); ++i) {
1342         stdcout << result[i].first.first << ", " << result[i].first.second << "; ";
1343       } stdcout << "\n";
1344       input.clear();
1345       result.clear();
1346       input.push_back(std::make_pair(half_edge(Point(-1, -1), Point(10, 0)), std::make_pair(0, 1)));
1347       input.push_back(std::make_pair(half_edge(Point(-1, -1), Point(0, 10)), std::make_pair(0, -1)));
1348       input.push_back(std::make_pair(half_edge(Point(0, 10), Point(11, 11)), std::make_pair(0, -1)));
1349       input.push_back(std::make_pair(half_edge(Point(10, 0), Point(11, 11)), std::make_pair(0, 1)));
1350       scanline sl2;
1351       sl2.scan(result, tf, input.begin(), input.end());
1352       stdcout << "scanned\n";
1353       for(std::size_t i = 0; i < result.size(); ++i) {
1354         stdcout << result[i].first.first << ", " << result[i].first.second << "; ";
1355       } stdcout << "\n";
1356       input.clear();
1357       result.clear();
1358       input.push_back(std::make_pair(half_edge(Point(0, 0), Point(0, 10)), std::make_pair(0, 1)));
1359       input.push_back(std::make_pair(half_edge(Point(0, 0), Point(10, 0)), std::make_pair(0, 1)));
1360       input.push_back(std::make_pair(half_edge(Point(0, 10), Point(10, 10)), std::make_pair(0, -1)));
1361       input.push_back(std::make_pair(half_edge(Point(1, 1), Point(8, 2)), std::make_pair(1, 1)));
1362       input.push_back(std::make_pair(half_edge(Point(1, 1), Point(2, 8)), std::make_pair(1, -1)));
1363       input.push_back(std::make_pair(half_edge(Point(2, 8), Point(9, 9)), std::make_pair(1, -1)));
1364       input.push_back(std::make_pair(half_edge(Point(8, 2), Point(9, 9)), std::make_pair(1, 1)));
1365       input.push_back(std::make_pair(half_edge(Point(10, 0), Point(10, 10)), std::make_pair(0, -1)));
1366       scanline sl3;
1367       sl3.scan(result, tf, input.begin(), input.end());
1368       stdcout << "scanned\n";
1369       for(std::size_t i = 0; i < result.size(); ++i) {
1370         stdcout << result[i].first.first << ", " << result[i].first.second << "; ";
1371       } stdcout << "\n";
1372       input.clear();
1373       result.clear();
1374       input.push_back(std::make_pair(half_edge(Point(0, 0), Point(0, 10)), std::make_pair(0, 1)));
1375       input.push_back(std::make_pair(half_edge(Point(0, 0), Point(10, 0)), std::make_pair(0, 1)));
1376       input.push_back(std::make_pair(half_edge(Point(0, 10), Point(10, 10)), std::make_pair(0, -1)));
1377       input.push_back(std::make_pair(half_edge(Point(1, 1), Point(8, 2)), std::make_pair(0, 1)));
1378       input.push_back(std::make_pair(half_edge(Point(1, 1), Point(2, 8)), std::make_pair(0, -1)));
1379       input.push_back(std::make_pair(half_edge(Point(2, 8), Point(9, 9)), std::make_pair(0, -1)));
1380       input.push_back(std::make_pair(half_edge(Point(8, 2), Point(9, 9)), std::make_pair(0, 1)));
1381       input.push_back(std::make_pair(half_edge(Point(10, 0), Point(10, 10)), std::make_pair(0, -1)));
1382       scanline sl4;
1383       sl4.scan(result, tf, input.begin(), input.end());
1384       stdcout << "scanned\n";
1385       for(std::size_t i = 0; i < result.size(); ++i) {
1386         stdcout << result[i].first.first << ", " << result[i].first.second << "; ";
1387       } stdcout << "\n";
1388       input.clear();
1389       result.clear();
1390       input.push_back(std::make_pair(half_edge(Point(0, 0), Point(10, 0)), std::make_pair(0, 1)));
1391       input.push_back(std::make_pair(half_edge(Point(0, 0), Point(9, 1)), std::make_pair(0, 1)));
1392       input.push_back(std::make_pair(half_edge(Point(0, 0), Point(1, 9)), std::make_pair(0, -1)));
1393       input.push_back(std::make_pair(half_edge(Point(0, 0), Point(0, 10)), std::make_pair(0, 1)));
1394       input.push_back(std::make_pair(half_edge(Point(0, 10), Point(10, 10)), std::make_pair(0, -1)));
1395       input.push_back(std::make_pair(half_edge(Point(1, 9), Point(10, 10)), std::make_pair(0, -1)));
1396       input.push_back(std::make_pair(half_edge(Point(9, 1), Point(10, 10)), std::make_pair(0, 1)));
1397       input.push_back(std::make_pair(half_edge(Point(10, 0), Point(10, 10)), std::make_pair(0, -1)));
1398       scanline sl5;
1399       sl5.scan(result, tf, input.begin(), input.end());
1400       stdcout << "scanned\n";
1401       for(std::size_t i = 0; i < result.size(); ++i) {
1402         stdcout << result[i].first.first << ", " << result[i].first.second << "; ";
1403       } stdcout << "\n";
1404       input.clear();
1405       result.clear();
1406       input.push_back(std::make_pair(half_edge(Point(0, 0), Point(10, 0)), std::make_pair(0, 1)));
1407       input.push_back(std::make_pair(half_edge(Point(0, 0), Point(9, 1)), std::make_pair(1, 1)));
1408       input.push_back(std::make_pair(half_edge(Point(0, 0), Point(1, 9)), std::make_pair(1, -1)));
1409       input.push_back(std::make_pair(half_edge(Point(0, 0), Point(0, 10)), std::make_pair(0, 1)));
1410       input.push_back(std::make_pair(half_edge(Point(0, 10), Point(10, 10)), std::make_pair(0, -1)));
1411       input.push_back(std::make_pair(half_edge(Point(1, 9), Point(10, 10)), std::make_pair(1, -1)));
1412       input.push_back(std::make_pair(half_edge(Point(9, 1), Point(10, 10)), std::make_pair(1, 1)));
1413       input.push_back(std::make_pair(half_edge(Point(10, 0), Point(10, 10)), std::make_pair(0, -1)));
1414       scanline sl6;
1415       sl6.scan(result, tf, input.begin(), input.end());
1416       stdcout << "scanned\n";
1417       for(std::size_t i = 0; i < result.size(); ++i) {
1418         stdcout << result[i].first.first << ", " << result[i].first.second << "; ";
1419       } stdcout << "\n";
1420       input.clear();
1421       result.clear();
1422       input.push_back(std::make_pair(half_edge(Point(0, 0), Point(10, 0)), std::make_pair(0, 1)));
1423       input.push_back(std::make_pair(half_edge(Point(0, 0), Point(9, 1)), std::make_pair(1, 1)));
1424       input.push_back(std::make_pair(half_edge(Point(0, 0), Point(1, 9)), std::make_pair(1, -1)));
1425       input.push_back(std::make_pair(half_edge(Point(0, 0), Point(0, 10)), std::make_pair(0, 1)));
1426       input.push_back(std::make_pair(half_edge(Point(0, 10), Point(10, 10)), std::make_pair(0, -1)));
1427       input.push_back(std::make_pair(half_edge(Point(0, 20), Point(10, 20)), std::make_pair(0, 1)));
1428       input.push_back(std::make_pair(half_edge(Point(0, 20), Point(9, 21)), std::make_pair(1, 1)));
1429       input.push_back(std::make_pair(half_edge(Point(0, 20), Point(1, 29)), std::make_pair(1, -1)));
1430       input.push_back(std::make_pair(half_edge(Point(0, 20), Point(0, 30)), std::make_pair(0, 1)));
1431       input.push_back(std::make_pair(half_edge(Point(0, 30), Point(10, 30)), std::make_pair(0, -1)));
1432       input.push_back(std::make_pair(half_edge(Point(1, 9), Point(10, 10)), std::make_pair(1, -1)));
1433       input.push_back(std::make_pair(half_edge(Point(1, 29), Point(10, 30)), std::make_pair(1, -1)));
1434       input.push_back(std::make_pair(half_edge(Point(9, 1), Point(10, 10)), std::make_pair(1, 1)));
1435       input.push_back(std::make_pair(half_edge(Point(9, 21), Point(10, 30)), std::make_pair(1, 1)));
1436       input.push_back(std::make_pair(half_edge(Point(10, 20), Point(10, 30)), std::make_pair(0, -1)));
1437       input.push_back(std::make_pair(half_edge(Point(10, 20), Point(10, 30)), std::make_pair(0, -1)));
1438       scanline sl7;
1439       sl7.scan(result, tf, input.begin(), input.end());
1440       stdcout << "scanned\n";
1441       for(std::size_t i = 0; i < result.size(); ++i) {
1442         stdcout << result[i].first.first << ", " << result[i].first.second << "; ";
1443       } stdcout << "\n";
1444       input.clear();
1445       result.clear();
1446       input.push_back(std::make_pair(half_edge(Point(-1, -1), Point(10, 0)), std::make_pair(0, 1))); //a
1447       input.push_back(std::make_pair(half_edge(Point(-1, -1), Point(0, 10)), std::make_pair(0, -1))); //a
1448       input.push_back(std::make_pair(half_edge(Point(0, 10), Point(11, 11)), std::make_pair(0, -1))); //a
1449       input.push_back(std::make_pair(half_edge(Point(10, 0), Point(20, 0)), std::make_pair(0, 1))); //b
1450       input.push_back(std::make_pair(half_edge(Point(10, 0), Point(11, 11)), std::make_pair(0, -1))); //b
1451       input.push_back(std::make_pair(half_edge(Point(10, 0), Point(11, 11)), std::make_pair(0, 1))); //a
1452       input.push_back(std::make_pair(half_edge(Point(11, 11), Point(20, 10)), std::make_pair(0, -1))); //b
1453       input.push_back(std::make_pair(half_edge(Point(20, 0), Point(30, 0)), std::make_pair(0, 1))); //c
1454       input.push_back(std::make_pair(half_edge(Point(20, 0), Point(20, 10)), std::make_pair(0, -1))); //b
1455       input.push_back(std::make_pair(half_edge(Point(20, 0), Point(20, 10)), std::make_pair(0, 1))); //c
1456       input.push_back(std::make_pair(half_edge(Point(20, 10), Point(30, 10)), std::make_pair(0, -1))); //c
1457       input.push_back(std::make_pair(half_edge(Point(30, 0), Point(30, 10)), std::make_pair(0, -1))); //c
1458       scanline sl8;
1459       sl8.scan(result, tf, input.begin(), input.end());
1460       stdcout << "scanned\n";
1461       for(std::size_t i = 0; i < result.size(); ++i) {
1462         stdcout << result[i].first.first << ", " << result[i].first.second << "; ";
1463       } stdcout << "\n";
1464       return true;
1465     }
1466
1467   };
1468
1469   template <typename Unit>
1470   class merge_output_functor {
1471   public:
1472     typedef typename scanline_base<Unit>::half_edge half_edge;
1473     merge_output_functor() {}
1474     template <typename result_type, typename key_type>
1475     void operator()(result_type& result, const half_edge& edge, const key_type& left, const key_type& right) {
1476       typename std::pair<half_edge, int> elem;
1477       elem.first = edge;
1478       elem.second = 1;
1479       if(edge.second < edge.first) elem.second *= -1;
1480       if(scanline_base<Unit>::is_vertical(edge)) elem.second *= -1;
1481       if(!left.empty())
1482         result[left].insert_clean(elem);
1483       elem.second *= -1;
1484       if(!right.empty())
1485         result[right].insert_clean(elem);
1486     }
1487   };
1488
1489   template <typename Unit, typename property_type, typename key_type = std::set<property_type>,
1490             typename output_functor_type = merge_output_functor<Unit> >
1491   class property_merge : public scanline_base<Unit> {
1492   protected:
1493     typedef typename scanline_base<Unit>::Point Point;
1494
1495     //the first point is the vertex and and second point establishes the slope of an edge eminating from the vertex
1496     //typedef std::pair<Point, Point> half_edge;
1497     typedef typename scanline_base<Unit>::half_edge half_edge;
1498
1499     //scanline comparator functor
1500     typedef typename scanline_base<Unit>::less_half_edge less_half_edge;
1501     typedef typename scanline_base<Unit>::less_point less_point;
1502
1503     //this data structure assocates a property and count to a half edge
1504     typedef std::pair<half_edge, std::pair<property_type, int> > vertex_property;
1505     //this data type stores the combination of many half edges
1506     typedef std::vector<vertex_property> property_merge_data;
1507
1508     //this is the data type used internally to store the combination of property counts at a given location
1509     typedef std::vector<std::pair<property_type, int> > property_map;
1510     //this data type is used internally to store the combined property data for a given half edge
1511     typedef std::pair<half_edge, property_map> vertex_data;
1512
1513     property_merge_data pmd;
1514     typename scanline_base<Unit>::evalAtXforYPack evalAtXforYPack_;
1515
1516     template<typename vertex_data_type>
1517     class less_vertex_data {
1518       typename scanline_base<Unit>::evalAtXforYPack* pack_;
1519     public:
1520       less_vertex_data() : pack_() {}
1521       less_vertex_data(typename scanline_base<Unit>::evalAtXforYPack* pack) : pack_(pack) {}
1522       bool operator() (const vertex_data_type& lvalue, const vertex_data_type& rvalue) const {
1523         less_point lp;
1524         if(lp(lvalue.first.first, rvalue.first.first)) return true;
1525         if(lp(rvalue.first.first, lvalue.first.first)) return false;
1526         Unit x = lvalue.first.first.get(HORIZONTAL);
1527         int just_before_ = 0;
1528         less_half_edge lhe(&x, &just_before_, pack_);
1529         return lhe(lvalue.first, rvalue.first);
1530       }
1531     };
1532
1533
1534     inline void sort_property_merge_data() {
1535       less_vertex_data<vertex_property> lvd(&evalAtXforYPack_);
1536       polygon_sort(pmd.begin(), pmd.end(), lvd);
1537     }
1538   public:
1539     inline property_merge_data& get_property_merge_data() { return pmd; }
1540     inline property_merge() : pmd(), evalAtXforYPack_() {}
1541     inline property_merge(const property_merge& pm) : pmd(pm.pmd), evalAtXforYPack_(pm.evalAtXforYPack_) {}
1542     inline property_merge& operator=(const property_merge& pm) { pmd = pm.pmd; return *this; }
1543
1544     template <typename polygon_type>
1545     void insert(const polygon_type& polygon_object, const property_type& property_value, bool is_hole = false) {
1546       insert(polygon_object, property_value, is_hole, typename geometry_concept<polygon_type>::type());
1547     }
1548
1549     //result type should be std::map<std::set<property_type>, polygon_set_type>
1550     //or std::map<std::vector<property_type>, polygon_set_type>
1551     template <typename result_type>
1552     void merge(result_type& result) {
1553       if(pmd.empty()) return;
1554       //intersect data
1555       property_merge_data tmp_pmd;
1556       line_intersection<Unit>::validate_scan(tmp_pmd, pmd.begin(), pmd.end());
1557       pmd.swap(tmp_pmd);
1558       sort_property_merge_data();
1559       scanline<Unit, property_type, key_type> sl;
1560       output_functor_type mof;
1561       sl.scan(result, mof, pmd.begin(), pmd.end());
1562     }
1563
1564     inline bool verify1() {
1565       std::pair<int, int> offenders;
1566       std::vector<std::pair<half_edge, int> > lines;
1567       int count = 0;
1568       for(std::size_t i = 0; i < pmd.size(); ++i) {
1569         lines.push_back(std::make_pair(pmd[i].first, count++));
1570       }
1571       if(!line_intersection<Unit>::verify_scan(offenders, lines.begin(), lines.end())) {
1572         //stdcout << "Intersection failed!\n";
1573         //stdcout << offenders.first << " " << offenders.second << "\n";
1574         return false;
1575       }
1576       std::vector<Point> pts;
1577       for(std::size_t i = 0; i < lines.size(); ++i) {
1578         pts.push_back(lines[i].first.first);
1579         pts.push_back(lines[i].first.second);
1580       }
1581       polygon_sort(pts.begin(), pts.end());
1582       for(std::size_t i = 0; i < pts.size(); i+=2) {
1583         if(pts[i] != pts[i+1]) {
1584           //stdcout << "Non-closed figures after line intersection!\n";
1585           return false;
1586         }
1587       }
1588       return true;
1589     }
1590
1591     void clear() {*this = property_merge();}
1592
1593   protected:
1594     template <typename polygon_type>
1595     void insert(const polygon_type& polygon_object, const property_type& property_value, bool is_hole,
1596                 polygon_concept ) {
1597       bool first_iteration = true;
1598       bool second_iteration = true;
1599       Point first_point;
1600       Point second_point;
1601       Point previous_previous_point;
1602       Point previous_point;
1603       Point current_point;
1604       direction_1d winding_dir = winding(polygon_object);
1605       for(typename polygon_traits<polygon_type>::iterator_type itr = begin_points(polygon_object);
1606           itr != end_points(polygon_object); ++itr) {
1607         assign(current_point, *itr);
1608         if(first_iteration) {
1609           first_iteration = false;
1610           first_point = previous_point = current_point;
1611         } else if(second_iteration) {
1612           if(previous_point != current_point) {
1613             second_iteration = false;
1614             previous_previous_point = previous_point;
1615             second_point = previous_point = current_point;
1616           }
1617         } else {
1618           if(previous_point != current_point) {
1619             create_vertex(pmd, previous_point, current_point, winding_dir,
1620                           is_hole, property_value);
1621             previous_previous_point = previous_point;
1622             previous_point = current_point;
1623           }
1624         }
1625       }
1626       current_point = first_point;
1627       if(!first_iteration && !second_iteration) {
1628         if(previous_point != current_point) {
1629           create_vertex(pmd, previous_point, current_point, winding_dir,
1630                         is_hole, property_value);
1631           previous_previous_point = previous_point;
1632           previous_point = current_point;
1633         }
1634         current_point = second_point;
1635         create_vertex(pmd, previous_point, current_point, winding_dir,
1636                       is_hole, property_value);
1637         previous_previous_point = previous_point;
1638         previous_point = current_point;
1639       }
1640     }
1641
1642     template <typename polygon_with_holes_type>
1643     void insert(const polygon_with_holes_type& polygon_with_holes_object, const property_type& property_value, bool is_hole,
1644                 polygon_with_holes_concept) {
1645       insert(polygon_with_holes_object, property_value, is_hole, polygon_concept());
1646       for(typename polygon_with_holes_traits<polygon_with_holes_type>::iterator_holes_type itr =
1647             begin_holes(polygon_with_holes_object);
1648           itr != end_holes(polygon_with_holes_object); ++itr) {
1649         insert(*itr, property_value, !is_hole, polygon_concept());
1650       }
1651     }
1652
1653     template <typename rectangle_type>
1654     void insert(const rectangle_type& rectangle_object, const property_type& property_value, bool is_hole,
1655                 rectangle_concept ) {
1656       polygon_90_data<Unit> poly;
1657       assign(poly, rectangle_object);
1658       insert(poly, property_value, is_hole, polygon_concept());
1659     }
1660
1661   public: //change to private when done testing
1662
1663     static inline void create_vertex(property_merge_data& pmd,
1664                                      const Point& current_point,
1665                                      const Point& next_point,
1666                                      direction_1d winding,
1667                                      bool is_hole, const property_type& property) {
1668       if(current_point == next_point) return;
1669       vertex_property current_vertex;
1670       current_vertex.first.first = current_point;
1671       current_vertex.first.second = next_point;
1672       current_vertex.second.first = property;
1673       int multiplier = 1;
1674       if(winding == CLOCKWISE)
1675         multiplier = -1;
1676       if(is_hole)
1677         multiplier *= -1;
1678       if(current_point < next_point) {
1679         multiplier *= -1;
1680         std::swap(current_vertex.first.first, current_vertex.first.second);
1681       }
1682       current_vertex.second.second = multiplier * (euclidean_distance(next_point, current_point, HORIZONTAL) == 0 ? -1: 1);
1683       pmd.push_back(current_vertex);
1684       //current_vertex.first.second = previous_point;
1685       //current_vertex.second.second *= -1;
1686       //pmd.push_back(current_vertex);
1687     }
1688
1689     static inline void sort_vertex_half_edges(vertex_data& vertex) {
1690       less_half_edge_pair lessF(vertex.first);
1691       polygon_sort(vertex.second.begin(), vertex.second.end(), lessF);
1692     }
1693
1694     class less_half_edge_pair {
1695     private:
1696       Point pt_;
1697     public:
1698       less_half_edge_pair(const Point& pt) : pt_(pt) {}
1699       bool operator()(const half_edge& e1, const half_edge& e2) {
1700         const Point& pt1 = e1.first;
1701         const Point& pt2 = e2.first;
1702         if(get(pt1, HORIZONTAL) ==
1703            get(pt_, HORIZONTAL)) {
1704           //vertical edge is always largest
1705           return false;
1706         }
1707         if(get(pt2, HORIZONTAL) ==
1708            get(pt_, HORIZONTAL)) {
1709           //if half edge 1 is not vertical its slope is less than that of half edge 2
1710           return get(pt1, HORIZONTAL) != get(pt2, HORIZONTAL);
1711         }
1712         return scanline_base<Unit>::less_slope(get(pt_, HORIZONTAL),
1713                                                get(pt_, VERTICAL), pt1, pt2);
1714       }
1715     };
1716
1717   public:
1718     //test functions
1719     template <typename stream_type>
1720     static stream_type& print (stream_type& o, const property_map& c)
1721     {
1722       o << "count: {";
1723       for(typename property_map::const_iterator itr = c.begin(); itr != c.end(); ++itr) {
1724         o << ((*itr).first) << ":" << ((*itr).second) << " ";
1725       }
1726       return o << "} ";
1727     }
1728
1729
1730     template <typename stream_type>
1731     static stream_type& print (stream_type& o, const half_edge& he)
1732     {
1733       o << "half edge: (";
1734       o << (he.first);
1735       return o << ", " << (he.second) << ") ";
1736     }
1737
1738     template <typename stream_type>
1739     static stream_type& print (stream_type& o, const vertex_property& c)
1740     {
1741       o << "vertex property: {";
1742       print(o, c.first);
1743       o << ", " << c.second.first << ":" << c.second.second << " ";
1744       return o;
1745     }
1746
1747     template <typename stream_type>
1748     static stream_type& print (stream_type& o, const std::vector<vertex_property>& hev)
1749     {
1750       o << "vertex properties: {";
1751       for(std::size_t i = 0; i < hev.size(); ++i) {
1752         print(o, (hev[i])) << " ";
1753       }
1754       return o << "} ";
1755     }
1756
1757     template <typename stream_type>
1758     static stream_type& print (stream_type& o, const std::vector<half_edge>& hev)
1759     {
1760       o << "half edges: {";
1761       for(std::size_t i = 0; i < hev.size(); ++i) {
1762         print(o, (hev[i])) << " ";
1763       }
1764       return o << "} ";
1765     }
1766
1767     template <typename stream_type>
1768     static stream_type& print (stream_type& o, const vertex_data& v)
1769     {
1770       return print(o << "vertex: <" << (v.first) << ", ", (v.second)) << "> ";
1771     }
1772
1773     template <typename stream_type>
1774     static stream_type& print (stream_type& o, const std::vector<vertex_data>& vv)
1775     {
1776       o << "vertices: {";
1777       for(std::size_t i = 0; i < vv.size(); ++i) {
1778         print(o, (vv[i])) << " ";
1779       }
1780       return o << "} ";
1781     }
1782
1783
1784
1785     template <typename stream_type>
1786     static inline bool test_insertion(stream_type& stdcout) {
1787       property_merge si;
1788       rectangle_data<Unit> rect;
1789       xl(rect, 0);
1790       yl(rect, 1);
1791       xh(rect, 10);
1792       yh(rect, 11);
1793
1794       si.insert(rect, 333);
1795       print(stdcout, si.pmd) << "\n";
1796
1797       Point pts[4] = {Point(0, 0), Point(10,-3), Point(13, 8), Point(0, 0) };
1798       polygon_data<Unit> poly;
1799       property_merge si2;
1800       poly.set(pts, pts+3);
1801       si2.insert(poly, 444);
1802       si2.sort_property_merge_data();
1803       print(stdcout, si2.pmd) << "\n";
1804       property_merge si3;
1805       poly.set(pts, pts+4);
1806       si3.insert(poly, 444);
1807       si3.sort_property_merge_data();
1808       stdcout << (si2.pmd == si3.pmd) << "\n";
1809       std::reverse(pts, pts+4);
1810       property_merge si4;
1811       poly.set(pts, pts+4);
1812       si4.insert(poly, 444);
1813       si4.sort_property_merge_data();
1814       print(stdcout, si4.pmd) << "\n";
1815       stdcout << (si2.pmd == si4.pmd) << "\n";
1816       std::reverse(pts, pts+3);
1817       property_merge si5;
1818       poly.set(pts, pts+4);
1819       si5.insert(poly, 444);
1820       si5.sort_property_merge_data();
1821       stdcout << (si2.pmd == si5.pmd) << "\n";
1822
1823       return true;
1824     }
1825
1826     template <typename stream_type>
1827     static inline bool test_merge(stream_type& stdcout) {
1828       property_merge si;
1829       rectangle_data<Unit> rect;
1830       xl(rect, 0);
1831       yl(rect, 1);
1832       xh(rect, 10);
1833       yh(rect, 11);
1834
1835       si.insert(rect, 333);
1836       std::map<std::set<property_type>, polygon_set_data<Unit> > result;
1837       si.merge(result);
1838       print(stdcout, si.pmd) << "\n";
1839       polygon_set_data<Unit> psd = (*(result.begin())).second;
1840       std::vector<polygon_data<Unit> > polys;
1841       psd.get(polys);
1842       if(polys.size() != 1) {
1843         stdcout << "fail merge 1\n";
1844         return false;
1845       }
1846       stdcout << (polys[0]) << "\n";
1847       si.clear();
1848       std::vector<Point> pts;
1849       pts.push_back(Point(0, 0));
1850       pts.push_back(Point(10, -10));
1851       pts.push_back(Point(10, 10));
1852       polygon_data<Unit> poly;
1853       poly.set(pts.begin(), pts.end());
1854       si.insert(poly, 444);
1855       pts.clear();
1856       pts.push_back(Point(5, 0));
1857       pts.push_back(Point(-5, -10));
1858       pts.push_back(Point(-5, 10));
1859       poly.set(pts.begin(), pts.end());
1860       si.insert(poly, 444);
1861       result.clear();
1862       si.merge(result);
1863       print(stdcout, si.pmd) << "\n";
1864       psd = (*(result.begin())).second;
1865       stdcout << psd << "\n";
1866       polys.clear();
1867       psd.get(polys);
1868       if(polys.size() != 1) {
1869         stdcout << "fail merge 2\n";
1870         return false;
1871       }
1872       //Polygon { -4 -1, 3 3, -2 3 }
1873       //Polygon { 0 -4, -4 -2, -2 1 }
1874       si.clear();
1875       pts.clear();
1876       pts.push_back(Point(-4, -1));
1877       pts.push_back(Point(3, 3));
1878       pts.push_back(Point(-2, 3));
1879       poly.set(pts.begin(), pts.end());
1880       si.insert(poly, 444);
1881       pts.clear();
1882       pts.push_back(Point(0, -4));
1883       pts.push_back(Point(-4, -2));
1884       pts.push_back(Point(-2, 1));
1885       poly.set(pts.begin(), pts.end());
1886       si.insert(poly, 444);
1887       result.clear();
1888       si.merge(result);
1889       print(stdcout, si.pmd) << "\n";
1890       psd = (*(result.begin())).second;
1891       stdcout << psd << "\n";
1892       polys.clear();
1893       psd.get(polys);
1894       if(polys.size() != 1) {
1895         stdcout << "fail merge 3\n";
1896         return false;
1897       }
1898       stdcout << "Polygon { -2 2, -2 2, 1 4 } \n";
1899       stdcout << "Polygon { 2 4, 2 -4, -3 1 } \n";
1900       si.clear();
1901       pts.clear();
1902       pts.push_back(Point(-2, 2));
1903       pts.push_back(Point(-2, 2));
1904       pts.push_back(Point(1, 4));
1905       poly.set(pts.begin(), pts.end());
1906       si.insert(poly, 444);
1907       pts.clear();
1908       pts.push_back(Point(2, 4));
1909       pts.push_back(Point(2, -4));
1910       pts.push_back(Point(-3, 1));
1911       poly.set(pts.begin(), pts.end());
1912       si.insert(poly, 444);
1913       result.clear();
1914       si.merge(result);
1915       print(stdcout, si.pmd) << "\n";
1916       psd = (*(result.begin())).second;
1917       stdcout << psd << "\n";
1918       polys.clear();
1919       psd.get(polys);
1920       if(polys.size() != 1) {
1921         stdcout << "fail merge 4\n";
1922         return false;
1923       }
1924       stdcout << (polys[0]) << "\n";
1925       stdcout << "Polygon { -4 0, -2 -3, 3 -4 } \n";
1926       stdcout << "Polygon { -1 1, 1 -2, -4 -3 } \n";
1927       si.clear();
1928       pts.clear();
1929       pts.push_back(Point(-4, 0));
1930       pts.push_back(Point(-2, -3));
1931       pts.push_back(Point(3, -4));
1932       poly.set(pts.begin(), pts.end());
1933       si.insert(poly, 444);
1934       pts.clear();
1935       pts.push_back(Point(-1, 1));
1936       pts.push_back(Point(1, -2));
1937       pts.push_back(Point(-4, -3));
1938       poly.set(pts.begin(), pts.end());
1939       si.insert(poly, 444);
1940       result.clear();
1941       si.merge(result);
1942       print(stdcout, si.pmd) << "\n";
1943       psd = (*(result.begin())).second;
1944       stdcout << psd << "\n";
1945       polys.clear();
1946       psd.get(polys);
1947       if(polys.size() != 1) {
1948         stdcout << "fail merge 5\n";
1949         return false;
1950       }
1951       stdcout << "Polygon { 2 2, -2 0, 0 1 }  \n";
1952       stdcout << "Polygon { 4 -2, 3 -1, 2 3 }  \n";
1953       si.clear();
1954       pts.clear();
1955       pts.push_back(Point(2, 2));
1956       pts.push_back(Point(-2, 0));
1957       pts.push_back(Point(0, 1));
1958       poly.set(pts.begin(), pts.end());
1959       si.insert(poly, 444);
1960       pts.clear();
1961       pts.push_back(Point(4, -2));
1962       pts.push_back(Point(3, -1));
1963       pts.push_back(Point(2, 3));
1964       poly.set(pts.begin(), pts.end());
1965       si.insert(poly, 444);
1966       result.clear();
1967       si.merge(result);
1968       print(stdcout, si.pmd) << "\n";
1969       if(!result.empty()) {
1970         psd = (*(result.begin())).second;
1971         stdcout << psd << "\n";
1972         polys.clear();
1973         psd.get(polys);
1974         if(polys.size() != 1) {
1975           stdcout << "fail merge 6\n";
1976           return false;
1977         }
1978         stdcout << (polys[0]) << "\n";
1979       }
1980       stdcout << "Polygon { 0 2, 3 -1, 4 1 }  \n";
1981       stdcout << "Polygon { -4 3, 3 3, 4 2 }  \n";
1982       si.clear();
1983       pts.clear();
1984       pts.push_back(Point(0, 2));
1985       pts.push_back(Point(3, -1));
1986       pts.push_back(Point(4, 1));
1987       poly.set(pts.begin(), pts.end());
1988       si.insert(poly, 444);
1989       pts.clear();
1990       pts.push_back(Point(-4, 3));
1991       pts.push_back(Point(3, 3));
1992       pts.push_back(Point(4, 2));
1993       poly.set(pts.begin(), pts.end());
1994       si.insert(poly, 444);
1995       result.clear();
1996       si.merge(result);
1997       print(stdcout, si.pmd) << "\n";
1998       if(!result.empty()) {
1999         psd = (*(result.begin())).second;
2000         stdcout << psd << "\n";
2001         polys.clear();
2002         psd.get(polys);
2003         if(polys.size() == 0) {
2004           stdcout << "fail merge 7\n";
2005           return false;
2006         }
2007         stdcout << (polys[0]) << "\n";
2008       }
2009 stdcout << "Polygon { 1 -2, -1 4, 3 -2 }   \n";
2010 stdcout << "Polygon { 0 -3, 3 1, -3 -4 }   \n";
2011       si.clear();
2012       pts.clear();
2013       pts.push_back(Point(1, -2));
2014       pts.push_back(Point(-1, 4));
2015       pts.push_back(Point(3, -2));
2016       poly.set(pts.begin(), pts.end());
2017       si.insert(poly, 444);
2018       pts.clear();
2019       pts.push_back(Point(0, -3));
2020       pts.push_back(Point(3, 1));
2021       pts.push_back(Point(-3, -4));
2022       poly.set(pts.begin(), pts.end());
2023       si.insert(poly, 444);
2024       result.clear();
2025       si.merge(result);
2026       print(stdcout, si.pmd) << "\n";
2027       if(!result.empty()) {
2028         psd = (*(result.begin())).second;
2029         stdcout << psd << "\n";
2030         polys.clear();
2031         psd.get(polys);
2032         if(polys.size() == 0) {
2033           stdcout << "fail merge 8\n";
2034           return false;
2035         }
2036         stdcout << (polys[0]) << "\n";
2037       }
2038 stdcout << "Polygon { 2 2, 3 0, -3 4 }  \n";
2039 stdcout << "Polygon { -2 -2, 0 0, -1 -1 }  \n";
2040       si.clear();
2041       pts.clear();
2042       pts.push_back(Point(2, 2));
2043       pts.push_back(Point(3, 0));
2044       pts.push_back(Point(-3, 4));
2045       poly.set(pts.begin(), pts.end());
2046       si.insert(poly, 444);
2047       pts.clear();
2048       pts.push_back(Point(-2, -2));
2049       pts.push_back(Point(0, 0));
2050       pts.push_back(Point(-1, -1));
2051       poly.set(pts.begin(), pts.end());
2052       si.insert(poly, 444);
2053       result.clear();
2054       si.merge(result);
2055       print(stdcout, si.pmd) << "\n";
2056       if(!result.empty()) {
2057         psd = (*(result.begin())).second;
2058         stdcout << psd << "\n";
2059         polys.clear();
2060         psd.get(polys);
2061         if(polys.size() == 0) {
2062           stdcout << "fail merge 9\n";
2063           return false;
2064         }
2065         stdcout << (polys[0]) << "\n";
2066       }
2067       si.clear();
2068       pts.clear();
2069       //5624841,17616200,75000,9125000
2070       //pts.push_back(Point(5624841,75000));
2071       //pts.push_back(Point(5624841,9125000));
2072       //pts.push_back(Point(17616200,9125000));
2073       //pts.push_back(Point(17616200,75000));
2074 pts.push_back(Point(12262940, 6652520 )); pts.push_back(Point(12125750, 6652520 )); pts.push_back(Point(12121272, 6652961 )); pts.push_back(Point(12112981, 6656396 )); pts.push_back(Point(12106636, 6662741 )); pts.push_back(Point(12103201, 6671032 )); pts.push_back(Point(12103201, 6680007 )); pts.push_back(Point(12106636, 6688298 ));
2075 pts.push_back(Point(12109500, 6691780 )); pts.push_back(Point(12748600, 7330890 )); pts.push_back(Point(15762600, 7330890 )); pts.push_back(Point(15904620, 7472900 )); pts.push_back(Point(15909200, 7473030 )); pts.push_back(Point(15935830, 7476006 )); pts.push_back(Point(15992796, 7499602 )); pts.push_back(Point(16036397, 7543203 ));
2076 pts.push_back(Point(16059993, 7600169 )); pts.push_back(Point(16059993, 7661830 )); pts.push_back(Point(16036397, 7718796 )); pts.push_back(Point(15992796, 7762397 )); pts.push_back(Point(15935830, 7785993 )); pts.push_back(Point(15874169, 7785993 )); pts.push_back(Point(15817203, 7762397 )); pts.push_back(Point(15773602, 7718796 ));
2077 pts.push_back(Point(15750006, 7661830 )); pts.push_back(Point(15747030, 7635200 )); pts.push_back(Point(15746900, 7630620 )); pts.push_back(Point(15670220, 7553930 )); pts.push_back(Point(14872950, 7553930 )); pts.push_back(Point(14872950, 7626170 ));
2078 pts.push_back(Point(14869973, 7661280 )); pts.push_back(Point(14846377, 7718246 )); pts.push_back(Point(14802776, 7761847 )); pts.push_back(Point(14745810, 7785443 )); pts.push_back(Point(14684149, 7785443 )); pts.push_back(Point(14627183, 7761847 )); pts.push_back(Point(14583582, 7718246 ));
2079 pts.push_back(Point(14559986, 7661280 )); pts.push_back(Point(14557070, 7636660 )); pts.push_back(Point(14556670, 7625570 )); pts.push_back(Point(13703330, 7625570 )); pts.push_back(Point(13702930, 7636660 )); pts.push_back(Point(13699993, 7661830 )); pts.push_back(Point(13676397, 7718796 ));
2080 pts.push_back(Point(13632796, 7762397 )); pts.push_back(Point(13575830, 7785993 )); pts.push_back(Point(13514169, 7785993 )); pts.push_back(Point(13457203, 7762397 )); pts.push_back(Point(13436270, 7745670 )); pts.push_back(Point(13432940, 7742520 )); pts.push_back(Point(12963760, 7742520 ));
2081 pts.push_back(Point(12959272, 7742961 )); pts.push_back(Point(12950981, 7746396 )); pts.push_back(Point(12944636, 7752741 )); pts.push_back(Point(12941201, 7761032 )); pts.push_back(Point(12941201, 7770007 )); pts.push_back(Point(12944636, 7778298 )); pts.push_back(Point(12947490, 7781780 ));
2082 pts.push_back(Point(13425330, 8259620 )); pts.push_back(Point(15601330, 8259620 )); pts.push_back(Point(15904620, 8562900 )); pts.push_back(Point(15909200, 8563030 )); pts.push_back(Point(15935830, 8566006 )); pts.push_back(Point(15992796, 8589602 )); pts.push_back(Point(16036397, 8633203 ));
2083 pts.push_back(Point(16059993, 8690169 )); pts.push_back(Point(16059993, 8751830 )); pts.push_back(Point(16036397, 8808796 )); pts.push_back(Point(15992796, 8852397 )); pts.push_back(Point(15935830, 8875993 )); pts.push_back(Point(15874169, 8875993 )); pts.push_back(Point(15817203, 8852397 )); pts.push_back(Point(15773602, 8808796 ));
2084 pts.push_back(Point(15750006, 8751830 )); pts.push_back(Point(15747030, 8725200 )); pts.push_back(Point(15746900, 8720620 )); pts.push_back(Point(15508950, 8482660 )); pts.push_back(Point(14689890, 8482660 )); pts.push_back(Point(14685412, 8483101 )); pts.push_back(Point(14677121, 8486536 ));
2085 pts.push_back(Point(14670776, 8492881 )); pts.push_back(Point(14667341, 8501172 )); pts.push_back(Point(14667341, 8510147 )); pts.push_back(Point(14670776, 8518438 )); pts.push_back(Point(14673630, 8521920 )); pts.push_back(Point(14714620, 8562900 )); pts.push_back(Point(14719200, 8563030 )); pts.push_back(Point(14745830, 8566006 ));
2086 pts.push_back(Point(14802796, 8589602 )); pts.push_back(Point(14846397, 8633203 )); pts.push_back(Point(14869993, 8690169 )); pts.push_back(Point(14869993, 8751830 )); pts.push_back(Point(14846397, 8808796 )); pts.push_back(Point(14802796, 8852397 )); pts.push_back(Point(14745830, 8875993 )); pts.push_back(Point(14684169, 8875993 ));
2087 pts.push_back(Point(14627203, 8852397 )); pts.push_back(Point(14583602, 8808796 )); pts.push_back(Point(14560006, 8751830 )); pts.push_back(Point(14557030, 8725200 )); pts.push_back(Point(14556900, 8720620 )); pts.push_back(Point(14408270, 8571980 )); pts.push_back(Point(13696320, 8571980 )); pts.push_back(Point(13696320, 8675520 ));
2088 pts.push_back(Point(13699963, 8690161 )); pts.push_back(Point(13699963, 8751818 )); pts.push_back(Point(13676368, 8808781 )); pts.push_back(Point(13632771, 8852378 )); pts.push_back(Point(13575808, 8875973 )); pts.push_back(Point(13514151, 8875973 )); pts.push_back(Point(13457188, 8852378 )); pts.push_back(Point(13436270, 8835670 )); pts.push_back(Point(13432940, 8832520 ));
2089 pts.push_back(Point(13281760, 8832520 )); pts.push_back(Point(13277272, 8832961 )); pts.push_back(Point(13268981, 8836396 )); pts.push_back(Point(13262636, 8842741 )); pts.push_back(Point(13259201, 8851032 )); pts.push_back(Point(13259201, 8860007 )); pts.push_back(Point(13262636, 8868298 )); pts.push_back(Point(13265500, 8871780 ));
2090 pts.push_back(Point(13518710, 9125000 )); pts.push_back(Point(16270720, 9125000 )); pts.push_back(Point(16270720, 8939590 )); pts.push_back(Point(17120780, 8939590 )); pts.push_back(Point(17120780, 9125000 )); pts.push_back(Point(17616200, 9125000 )); pts.push_back(Point(17616200,   75000 )); pts.push_back(Point(16024790,   75000 ));
2091 pts.push_back(Point(16021460,   80700 )); pts.push_back(Point(16016397,   88796 )); pts.push_back(Point(15972796,  132397 )); pts.push_back(Point(15915830,  155993 )); pts.push_back(Point(15908730,  157240 )); pts.push_back(Point(15905000,  157800 )); pts.push_back(Point(15516800,  546000 )); pts.push_back(Point(15905000,  934200 ));
2092 pts.push_back(Point(15908730,  934760 )); pts.push_back(Point(15915830,  936006 )); pts.push_back(Point(15972796,  959602 )); pts.push_back(Point(16016397, 1003203 )); pts.push_back(Point(16039993, 1060169 )); pts.push_back(Point(16039993, 1121830 )); pts.push_back(Point(16016397, 1178796 )); pts.push_back(Point(15972796, 1222397 ));
2093 pts.push_back(Point(15915830, 1245993 )); pts.push_back(Point(15854169, 1245993 )); pts.push_back(Point(15797203, 1222397 )); pts.push_back(Point(15753602, 1178796 )); pts.push_back(Point(15730006, 1121830 )); pts.push_back(Point(15728760, 1114730 )); pts.push_back(Point(15728200, 1111000 )); pts.push_back(Point(15363500,  746300 ));
2094 pts.push_back(Point(14602620,  746300 )); pts.push_back(Point(14598142,  746741 )); pts.push_back(Point(14589851,  750176 )); pts.push_back(Point(14583506,  756521 )); pts.push_back(Point(14580071,  764812 )); pts.push_back(Point(14580071,  773787 )); pts.push_back(Point(14583506,  782078 )); pts.push_back(Point(14586360,  785560 ));
2095 pts.push_back(Point(14586370,  785560 )); pts.push_back(Point(14735000,  934200 )); pts.push_back(Point(14738730,  934760 )); pts.push_back(Point(14745830,  936006 )); pts.push_back(Point(14802796,  959602 )); pts.push_back(Point(14846397, 1003203 )); pts.push_back(Point(14869993, 1060169 ));
2096 pts.push_back(Point(14870450, 1062550 )); pts.push_back(Point(14872170, 1071980 )); pts.push_back(Point(14972780, 1071980 )); pts.push_back(Point(15925000, 2024200 )); pts.push_back(Point(15928730, 2024760 )); pts.push_back(Point(15935830, 2026006 )); pts.push_back(Point(15992796, 2049602 ));
2097 pts.push_back(Point(16036397, 2093203 )); pts.push_back(Point(16059993, 2150169 )); pts.push_back(Point(16059993, 2211830 )); pts.push_back(Point(16036397, 2268796 )); pts.push_back(Point(15992796, 2312397 )); pts.push_back(Point(15935830, 2335993 )); pts.push_back(Point(15874169, 2335993 ));
2098 pts.push_back(Point(15817203, 2312397 )); pts.push_back(Point(15773602, 2268796 )); pts.push_back(Point(15750006, 2211830 )); pts.push_back(Point(15748760, 2204730 )); pts.push_back(Point(15748200, 2201000 )); pts.push_back(Point(14869220, 1322020 )); pts.push_back(Point(14088350, 1322020 ));
2099 pts.push_back(Point(14083862, 1322461 )); pts.push_back(Point(14075571, 1325896 )); pts.push_back(Point(14069226, 1332241 )); pts.push_back(Point(14065791, 1340532 )); pts.push_back(Point(14065791, 1349507 )); pts.push_back(Point(14069226, 1357798 )); pts.push_back(Point(14072080, 1361280 ));
2100 pts.push_back(Point(14072090, 1361280 )); pts.push_back(Point(14735000, 2024200 )); pts.push_back(Point(14738730, 2024760 )); pts.push_back(Point(14745830, 2026006 )); pts.push_back(Point(14802796, 2049602 )); pts.push_back(Point(14846397, 2093203 )); pts.push_back(Point(14869993, 2150169 ));
2101 pts.push_back(Point(14869993, 2211830 )); pts.push_back(Point(14846397, 2268796 )); pts.push_back(Point(14802796, 2312397 )); pts.push_back(Point(14745830, 2335993 )); pts.push_back(Point(14684169, 2335993 )); pts.push_back(Point(14627203, 2312397 )); pts.push_back(Point(14583602, 2268796 )); pts.push_back(Point(14560006, 2211830 ));
2102 pts.push_back(Point(14558760, 2204730 )); pts.push_back(Point(14558200, 2201000 )); pts.push_back(Point(13752220, 1395020 )); pts.push_back(Point(12991340, 1395020 )); pts.push_back(Point(12986862, 1395461 )); pts.push_back(Point(12978571, 1398896 )); pts.push_back(Point(12972226, 1405241 ));
2103 pts.push_back(Point(12968791, 1413532 )); pts.push_back(Point(12968791, 1422507 )); pts.push_back(Point(12972226, 1430798 )); pts.push_back(Point(12975080, 1434280 )); pts.push_back(Point(12975090, 1434280 )); pts.push_back(Point(13565000, 2024200 )); pts.push_back(Point(13568730, 2024760 )); pts.push_back(Point(13575830, 2026006 ));
2104 pts.push_back(Point(13632796, 2049602 )); pts.push_back(Point(13676397, 2093203 )); pts.push_back(Point(13699993, 2150169 )); pts.push_back(Point(13699993, 2211830 )); pts.push_back(Point(13676397, 2268796 )); pts.push_back(Point(13632796, 2312397 )); pts.push_back(Point(13575830, 2335993 ));
2105 pts.push_back(Point(13514169, 2335993 )); pts.push_back(Point(13457203, 2312397 )); pts.push_back(Point(13413602, 2268796 )); pts.push_back(Point(13390006, 2211830 )); pts.push_back(Point(13388760, 2204730 )); pts.push_back(Point(13388200, 2201000 )); pts.push_back(Point(12655220, 1468020 ));
2106 pts.push_back(Point(11894340, 1468020 )); pts.push_back(Point(11889862, 1468461 )); pts.push_back(Point(11881571, 1471896 )); pts.push_back(Point(11875226, 1478241 )); pts.push_back(Point(11871791, 1486532 )); pts.push_back(Point(11871791, 1495507 ));
2107 pts.push_back(Point(11875226, 1503798 )); pts.push_back(Point(11878090, 1507280 )); pts.push_back(Point(12395000, 2024200 )); pts.push_back(Point(12398730, 2024760 )); pts.push_back(Point(12405830, 2026006 )); pts.push_back(Point(12462796, 2049602 )); pts.push_back(Point(12506397, 2093203 ));
2108 pts.push_back(Point(12529993, 2150169 )); pts.push_back(Point(12529993, 2211830 )); pts.push_back(Point(12506397, 2268796 )); pts.push_back(Point(12462796, 2312397 )); pts.push_back(Point(12405830, 2335993 )); pts.push_back(Point(12344169, 2335993 ));
2109 pts.push_back(Point(12287203, 2312397 )); pts.push_back(Point(12243602, 2268796 )); pts.push_back(Point(12220006, 2211830 )); pts.push_back(Point(12218760, 2204730 )); pts.push_back(Point(12218200, 2201000 )); pts.push_back(Point(11558220, 1541020 ));
2110 pts.push_back(Point(10797340, 1541020 )); pts.push_back(Point(10792862, 1541461 )); pts.push_back(Point(10784571, 1544896 )); pts.push_back(Point(10778226, 1551241 )); pts.push_back(Point(10774791, 1559532 )); pts.push_back(Point(10774791, 1568507 )); pts.push_back(Point(10778226, 1576798 )); pts.push_back(Point(10781080, 1580280 ));
2111 pts.push_back(Point(10781090, 1580280 )); pts.push_back(Point(11225000, 2024200 )); pts.push_back(Point(11228730, 2024760 )); pts.push_back(Point(11235830, 2026006 )); pts.push_back(Point(11292796, 2049602 )); pts.push_back(Point(11336397, 2093203 )); pts.push_back(Point(11359993, 2150169 ));
2112 pts.push_back(Point(11359993, 2211830 )); pts.push_back(Point(11336397, 2268796 )); pts.push_back(Point(11292796, 2312397 )); pts.push_back(Point(11235830, 2335993 )); pts.push_back(Point(11174169, 2335993 )); pts.push_back(Point(11117203, 2312397 )); pts.push_back(Point(11073602, 2268796 )); pts.push_back(Point(11050006, 2211830 ));
2113 pts.push_back(Point(11048760, 2204730 )); pts.push_back(Point(11048200, 2201000 )); pts.push_back(Point(10461220, 1614020 )); pts.push_back(Point( 5647400, 1614020 )); pts.push_back(Point( 5642912, 1614461 ));
2114 pts.push_back(Point( 5634621, 1617896 )); pts.push_back(Point( 5628276, 1624241 )); pts.push_back(Point( 5624841, 1632532 )); pts.push_back(Point( 5624841, 1641507 )); pts.push_back(Point( 5628276, 1649798 )); pts.push_back(Point( 5631130, 1653280 ));
2115 pts.push_back(Point( 5688490, 1710640 )); pts.push_back(Point( 9722350, 1710640 )); pts.push_back(Point(10034620, 2022900 )); pts.push_back(Point(10039200, 2023030 )); pts.push_back(Point(10065830, 2026006 )); pts.push_back(Point(10122796, 2049602 ));
2116 pts.push_back(Point(10166397, 2093203 )); pts.push_back(Point(10189993, 2150169 )); pts.push_back(Point(10189993, 2211830 )); pts.push_back(Point(10166397, 2268796 )); pts.push_back(Point(10158620, 2279450 )); pts.push_back(Point(10158620, 2404900 )); pts.push_back(Point(10548950, 2795240 ));
2117 pts.push_back(Point(15586950, 2795240 )); pts.push_back(Point(15904620, 3112900 )); pts.push_back(Point(15909200, 3113030 )); pts.push_back(Point(15935830, 3116006 )); pts.push_back(Point(15992796, 3139602 )); pts.push_back(Point(16036397, 3183203 )); pts.push_back(Point(16059993, 3240169 )); pts.push_back(Point(16059993, 3301830 ));
2118 pts.push_back(Point(16036397, 3358796 )); pts.push_back(Point(15992796, 3402397 )); pts.push_back(Point(15935830, 3425993 )); pts.push_back(Point(15874169, 3425993 )); pts.push_back(Point(15817203, 3402397 )); pts.push_back(Point(15773602, 3358796 )); pts.push_back(Point(15750006, 3301830 )); pts.push_back(Point(15747030, 3275200 ));
2119 pts.push_back(Point(15746900, 3270620 )); pts.push_back(Point(15494570, 3018280 )); pts.push_back(Point(14675510, 3018280 )); pts.push_back(Point(14671032, 3018721 )); pts.push_back(Point(14662741, 3022156 )); pts.push_back(Point(14656396, 3028501 )); pts.push_back(Point(14652961, 3036792 ));
2120 pts.push_back(Point(14652961, 3045767 )); pts.push_back(Point(14656396, 3054058 )); pts.push_back(Point(14659260, 3057540 )); pts.push_back(Point(14714620, 3112900 )); pts.push_back(Point(14719200, 3113030 )); pts.push_back(Point(14745830, 3116006 )); pts.push_back(Point(14802796, 3139602 ));
2121 pts.push_back(Point(14846397, 3183203 )); pts.push_back(Point(14869993, 3240169 )); pts.push_back(Point(14869993, 3301830 )); pts.push_back(Point(14846397, 3358796 )); pts.push_back(Point(14802796, 3402397 )); pts.push_back(Point(14745830, 3425993 )); pts.push_back(Point(14684169, 3425993 )); pts.push_back(Point(14627203, 3402397 ));
2122 pts.push_back(Point(14583602, 3358796 )); pts.push_back(Point(14560006, 3301830 )); pts.push_back(Point(14557030, 3275200 )); pts.push_back(Point(14556900, 3270620 )); pts.push_back(Point(14370700, 3084410 )); pts.push_back(Point(13702830, 3084410 )); pts.push_back(Point(13702830, 3263160 ));
2123 pts.push_back(Point(13700003, 3302210 )); pts.push_back(Point(13676407, 3359176 )); pts.push_back(Point(13632806, 3402777 )); pts.push_back(Point(13575840, 3426373 )); pts.push_back(Point(13514179, 3426373 )); pts.push_back(Point(13457213, 3402777 )); pts.push_back(Point(13413612, 3359176 ));
2124 pts.push_back(Point(13390016, 3302210 )); pts.push_back(Point(13387030, 3275200 )); pts.push_back(Point(13386900, 3270620 )); pts.push_back(Point(13266840, 3150550 )); pts.push_back(Point(12532920, 3150550 )); pts.push_back(Point(12532920, 3264990 )); pts.push_back(Point(12529993, 3301820 ));
2125 pts.push_back(Point(12506397, 3358786 )); pts.push_back(Point(12462796, 3402387 )); pts.push_back(Point(12405830, 3425983 )); pts.push_back(Point(12344169, 3425983 )); pts.push_back(Point(12287203, 3402387 )); pts.push_back(Point(12243602, 3358786 )); pts.push_back(Point(12220006, 3301820 )); pts.push_back(Point(12217030, 3275200 ));
2126 pts.push_back(Point(12216900, 3270620 )); pts.push_back(Point(12157460, 3211170 )); pts.push_back(Point(11362030, 3211170 )); pts.push_back(Point(11360250, 3220520 )); pts.push_back(Point(11359993, 3221830 )); pts.push_back(Point(11336397, 3278796 ));
2127 pts.push_back(Point(11292796, 3322397 )); pts.push_back(Point(11235830, 3345993 )); pts.push_back(Point(11174169, 3345993 )); pts.push_back(Point(11117203, 3322397 )); pts.push_back(Point(11096270, 3305670 )); pts.push_back(Point(11092940, 3302520 )); pts.push_back(Point(10680760, 3302520 ));
2128 pts.push_back(Point(10676272, 3302961 )); pts.push_back(Point(10667981, 3306396 )); pts.push_back(Point(10661636, 3312741 )); pts.push_back(Point(10658201, 3321032 )); pts.push_back(Point(10658201, 3330007 )); pts.push_back(Point(10661636, 3338298 )); pts.push_back(Point(10664500, 3341780 ));
2129 pts.push_back(Point(11264260, 3941550 )); pts.push_back(Point(15643260, 3941550 )); pts.push_back(Point(15904620, 4202900 )); pts.push_back(Point(15909200, 4203030 )); pts.push_back(Point(15935830, 4206006 )); pts.push_back(Point(15992796, 4229602 ));
2130 pts.push_back(Point(16036397, 4273203 )); pts.push_back(Point(16059993, 4330169 )); pts.push_back(Point(16059993, 4391830 )); pts.push_back(Point(16036397, 4448796 )); pts.push_back(Point(15992796, 4492397 ));
2131 pts.push_back(Point(15935830, 4515993 )); pts.push_back(Point(15874169, 4515993 )); pts.push_back(Point(15817203, 4492397 )); pts.push_back(Point(15773602, 4448796 )); pts.push_back(Point(15750006, 4391830 )); pts.push_back(Point(15747030, 4365200 )); pts.push_back(Point(15746900, 4360620 ));
2132 pts.push_back(Point(15550880, 4164590 )); pts.push_back(Point(14825070, 4164590 )); pts.push_back(Point(14825070, 4247610 )); pts.push_back(Point(14846397, 4273213 )); pts.push_back(Point(14869993, 4330179 )); pts.push_back(Point(14869993, 4391840 )); pts.push_back(Point(14846397, 4448806 ));
2133 pts.push_back(Point(14802796, 4492407 )); pts.push_back(Point(14745830, 4516003 )); pts.push_back(Point(14684169, 4516003 )); pts.push_back(Point(14627203, 4492407 )); pts.push_back(Point(14583602, 4448806 )); pts.push_back(Point(14560006, 4391840 )); pts.push_back(Point(14557030, 4365200 ));
2134 pts.push_back(Point(14556900, 4360620 )); pts.push_back(Point(14432520, 4236230 )); pts.push_back(Point(13702830, 4236230 )); pts.push_back(Point(13702830, 4352930 )); pts.push_back(Point(13699993, 4391750 )); pts.push_back(Point(13676397, 4448716 ));
2135 pts.push_back(Point(13632796, 4492317 )); pts.push_back(Point(13575830, 4515913 )); pts.push_back(Point(13514169, 4515913 )); pts.push_back(Point(13457203, 4492317 )); pts.push_back(Point(13413602, 4448716 )); pts.push_back(Point(13390006, 4391750 )); pts.push_back(Point(13387030, 4365200 ));
2136 pts.push_back(Point(13386900, 4360620 )); pts.push_back(Point(13334170, 4307880 )); pts.push_back(Point(12532990, 4307880 )); pts.push_back(Point(12532990, 4357550 )); pts.push_back(Point(12529993, 4391760 )); pts.push_back(Point(12506397, 4448726 )); pts.push_back(Point(12462796, 4492327 ));
2137 pts.push_back(Point(12405830, 4515923 )); pts.push_back(Point(12344169, 4515923 )); pts.push_back(Point(12287203, 4492327 )); pts.push_back(Point(12243602, 4448726 )); pts.push_back(Point(12220006, 4391760 )); pts.push_back(Point(12217970, 4378710 )); pts.push_back(Point(12216810, 4368500 ));
2138 pts.push_back(Point(11363190, 4368500 )); pts.push_back(Point(11362030, 4378710 )); pts.push_back(Point(11359983, 4391828 )); pts.push_back(Point(11336388, 4448791 )); pts.push_back(Point(11292791, 4492388 )); pts.push_back(Point(11235828, 4515983 )); pts.push_back(Point(11174171, 4515983 )); pts.push_back(Point(11117208, 4492388 ));
2139 pts.push_back(Point(11096270, 4475670 )); pts.push_back(Point(11092940, 4472520 )); pts.push_back(Point(11057750, 4472520 )); pts.push_back(Point(11053272, 4472961 )); pts.push_back(Point(11044981, 4476396 )); pts.push_back(Point(11038636, 4482741 )); pts.push_back(Point(11035201, 4491032 ));
2140 pts.push_back(Point(11035201, 4500007 )); pts.push_back(Point(11038636, 4508298 )); pts.push_back(Point(11041490, 4511780 )); pts.push_back(Point(11573490, 5043780 )); pts.push_back(Point(15655490, 5043780 )); pts.push_back(Point(15904620, 5292900 ));
2141 pts.push_back(Point(15909200, 5293030 )); pts.push_back(Point(15935830, 5296006 )); pts.push_back(Point(15992796, 5319602 )); pts.push_back(Point(16036397, 5363203 )); pts.push_back(Point(16059993, 5420169 )); pts.push_back(Point(16059993, 5481830 )); pts.push_back(Point(16036397, 5538796 ));
2142 pts.push_back(Point(15992796, 5582397 )); pts.push_back(Point(15935830, 5605993 )); pts.push_back(Point(15874169, 5605993 )); pts.push_back(Point(15817203, 5582397 )); pts.push_back(Point(15773602, 5538796 )); pts.push_back(Point(15750006, 5481830 )); pts.push_back(Point(15747030, 5455200 ));
2143 pts.push_back(Point(15746900, 5450620 )); pts.push_back(Point(15563110, 5266820 )); pts.push_back(Point(14857380, 5266820 )); pts.push_back(Point(14857380, 5382430 )); pts.push_back(Point(14869993, 5420179 )); pts.push_back(Point(14869993, 5481840 )); pts.push_back(Point(14846397, 5538806 )); pts.push_back(Point(14802796, 5582407 ));
2144 pts.push_back(Point(14745830, 5606003 )); pts.push_back(Point(14684169, 5606003 )); pts.push_back(Point(14627203, 5582407 )); pts.push_back(Point(14583602, 5538806 )); pts.push_back(Point(14560006, 5481840 )); pts.push_back(Point(14557030, 5455200 )); pts.push_back(Point(14556900, 5450620 )); pts.push_back(Point(14444750, 5338460 ));
2145 pts.push_back(Point(13702890, 5338460 )); pts.push_back(Point(13702890, 5364400 )); pts.push_back(Point(13699993, 5401800 )); pts.push_back(Point(13676397, 5458766 )); pts.push_back(Point(13632796, 5502367 )); pts.push_back(Point(13575830, 5525963 )); pts.push_back(Point(13514169, 5525963 )); pts.push_back(Point(13457203, 5502367 ));
2146 pts.push_back(Point(13413602, 5458766 )); pts.push_back(Point(13390006, 5401800 )); pts.push_back(Point(13389230, 5397620 )); pts.push_back(Point(13387590, 5388060 )); pts.push_back(Point(12532960, 5388060 )); pts.push_back(Point(12532960, 5446220 )); pts.push_back(Point(12529993, 5481820 ));
2147 pts.push_back(Point(12506397, 5538786 )); pts.push_back(Point(12462796, 5582387 )); pts.push_back(Point(12405830, 5605983 )); pts.push_back(Point(12344169, 5605983 )); pts.push_back(Point(12287203, 5582387 )); pts.push_back(Point(12266270, 5565670 )); pts.push_back(Point(12262940, 5562520 )); pts.push_back(Point(11737750, 5562520 ));
2148 pts.push_back(Point(11733272, 5562961 )); pts.push_back(Point(11724981, 5566396 )); pts.push_back(Point(11718636, 5572741 )); pts.push_back(Point(11715201, 5581032 )); pts.push_back(Point(11715201, 5590007 )); pts.push_back(Point(11718636, 5598298 )); pts.push_back(Point(11721500, 5601780 ));
2149 pts.push_back(Point(12287760, 6168050 )); pts.push_back(Point(15689760, 6168050 )); pts.push_back(Point(15904620, 6382900 )); pts.push_back(Point(15909200, 6383030 )); pts.push_back(Point(15935830, 6386006 )); pts.push_back(Point(15992796, 6409602 ));
2150 pts.push_back(Point(16036397, 6453203 )); pts.push_back(Point(16059993, 6510169 )); pts.push_back(Point(16059993, 6571830 )); pts.push_back(Point(16036397, 6628796 )); pts.push_back(Point(15992796, 6672397 )); pts.push_back(Point(15935830, 6695993 )); pts.push_back(Point(15874169, 6695993 ));
2151 pts.push_back(Point(15817203, 6672397 )); pts.push_back(Point(15773602, 6628796 )); pts.push_back(Point(15750006, 6571830 )); pts.push_back(Point(15747030, 6545200 )); pts.push_back(Point(15746900, 6540620 )); pts.push_back(Point(15597380, 6391090 )); pts.push_back(Point(14858060, 6391090 ));
2152 pts.push_back(Point(14858060, 6473860 )); pts.push_back(Point(14869993, 6510179 )); pts.push_back(Point(14869993, 6571840 )); pts.push_back(Point(14846397, 6628806 )); pts.push_back(Point(14802796, 6672407 )); pts.push_back(Point(14745830, 6696003 )); pts.push_back(Point(14684169, 6696003 ));
2153 pts.push_back(Point(14627203, 6672407 )); pts.push_back(Point(14583602, 6628806 )); pts.push_back(Point(14560006, 6571840 )); pts.push_back(Point(14557030, 6545200 )); pts.push_back(Point(14556900, 6540620 )); pts.push_back(Point(14479020, 6462730 ));
2154 pts.push_back(Point(13702990, 6462730 )); pts.push_back(Point(13702990, 6537170 )); pts.push_back(Point(13700003, 6571840 )); pts.push_back(Point(13676407, 6628806 )); pts.push_back(Point(13632806, 6672407 )); pts.push_back(Point(13575840, 6696003 ));
2155 pts.push_back(Point(13514179, 6696003 )); pts.push_back(Point(13457213, 6672407 )); pts.push_back(Point(13413612, 6628806 )); pts.push_back(Point(13390016, 6571840 )); pts.push_back(Point(13387040, 6545550 )); pts.push_back(Point(13386710, 6534380 ));
2156 pts.push_back(Point(12533290, 6534380 )); pts.push_back(Point(12532960, 6545550 )); pts.push_back(Point(12529983, 6571828 )); pts.push_back(Point(12506388, 6628791 )); pts.push_back(Point(12462791, 6672388 )); pts.push_back(Point(12405828, 6695983 ));
2157 pts.push_back(Point(12344171, 6695983 )); pts.push_back(Point(12287208, 6672388 )); pts.push_back(Point(12266270, 6655670 ));
2158       poly.set(pts.begin(), pts.end());
2159       si.insert(poly, 444);
2160       result.clear();
2161       si.merge(result);
2162       si.verify1();
2163       print(stdcout, si.pmd) << "\n";
2164       if(!result.empty()) {
2165         psd = (*(result.begin())).second;
2166         stdcout << psd << "\n";
2167         std::vector<Point> outpts;
2168         for(typename polygon_set_data<Unit>::iterator_type itr = psd.begin();
2169             itr != psd.end(); ++itr) {
2170           outpts.push_back((*itr).first.first);
2171           outpts.push_back((*itr).first.second);
2172         }
2173         polygon_sort(outpts.begin(), outpts.end());
2174         for(std::size_t i = 0; i < outpts.size(); i+=2) {
2175           if(outpts[i] != outpts[i+1]) {
2176             stdcout << "Polygon set not a closed figure\n";
2177             stdcout << i << "\n";
2178             stdcout << outpts[i] << " " << outpts[i+1] << "\n";
2179             return 0;
2180           }
2181         }
2182         polys.clear();
2183         psd.get(polys);
2184         if(polys.size() == 0) {
2185           stdcout << "fail merge 10\n";
2186           return false;
2187         }
2188         stdcout << (polys[0]) << "\n";
2189       }
2190       for(unsigned int i = 0; i < 10; ++i) {
2191         stdcout << "random case # " << i << "\n";
2192         si.clear();
2193         pts.clear();
2194         pts.push_back(Point(rand()%9-4, rand()%9-4));
2195         pts.push_back(Point(rand()%9-4, rand()%9-4));
2196         pts.push_back(Point(rand()%9-4, rand()%9-4));
2197         polygon_data<Unit> poly1;
2198         poly1.set(pts.begin(), pts.end());
2199         stdcout << poly1 << "\n";
2200         si.insert(poly1, 444);
2201         pts.clear();
2202         pts.push_back(Point(rand()%9-4, rand()%9-4));
2203         pts.push_back(Point(rand()%9-4, rand()%9-4));
2204         pts.push_back(Point(rand()%9-4, rand()%9-4));
2205         polygon_data<Unit> poly2;
2206         poly2.set(pts.begin(), pts.end());
2207         stdcout << poly2 << "\n";
2208         si.insert(poly2, 444);
2209         result.clear();
2210         si.merge(result);
2211         print(stdcout, si.pmd) << "\n";
2212         if(!result.empty()) {
2213           psd = (*(result.begin())).second;
2214           stdcout << psd << "\n";
2215           polys.clear();
2216           psd.get(polys);
2217           if(polys.size() == 0) {
2218             si.clear();
2219             si.insert(poly1, 333);
2220             result.clear();
2221             si.merge(result);
2222             psd = (*(result.begin())).second;
2223             std::vector<polygon_data<Unit> > polys1;
2224             psd.get(polys1);
2225             si.clear();
2226             si.insert(poly2, 333);
2227             result.clear();
2228             si.merge(result);
2229             psd = (*(result.begin())).second;
2230             std::vector<polygon_data<Unit> > polys2;
2231             psd.get(polys2);
2232             if(!polys1.empty() || !polys2.empty()) {
2233               stdcout << "fail random merge " << i << "\n";
2234               return false;
2235             }
2236           }
2237         }
2238         if(!polys.empty())
2239           stdcout << polys.size() << ": " << (polys[0]) << "\n";
2240       }
2241       return true;
2242     }
2243
2244     template <typename stream_type>
2245     static inline bool check_rectangle_trio(rectangle_data<Unit> rect1, rectangle_data<Unit> rect2, rectangle_data<Unit> rect3, stream_type& stdcout) {
2246         property_merge si;
2247         std::map<std::set<property_type>, polygon_set_data<Unit> > result;
2248         std::vector<polygon_data<Unit> > polys;
2249         property_merge_90<property_type, Unit> si90;
2250         std::map<std::set<property_type>, polygon_90_set_data<Unit> > result90;
2251         std::vector<polygon_data<Unit> > polys90;
2252         si.insert(rect1, 111);
2253         si90.insert(rect1, 111);
2254         stdcout << rect1 << "\n";
2255         si.insert(rect2, 222);
2256         si90.insert(rect2, 222);
2257         stdcout << rect2 << "\n";
2258         si.insert(rect3, 333);
2259         si90.insert(rect3, 333);
2260         stdcout << rect3 << "\n";
2261         si.merge(result);
2262         si90.merge(result90);
2263         if(result.size() != result90.size()) {
2264           stdcout << "merge failed with size mismatch\n";
2265           return 0;
2266         }
2267         typename std::map<std::set<property_type>, polygon_90_set_data<Unit> >::iterator itr90 = result90.begin();
2268         for(typename std::map<std::set<property_type>, polygon_set_data<Unit> >::iterator itr = result.begin();
2269             itr != result.end(); ++itr) {
2270           for(typename std::set<property_type>::const_iterator set_itr = (*itr).first.begin();
2271               set_itr != (*itr).first.end(); ++set_itr) {
2272             stdcout << (*set_itr) << " ";
2273           } stdcout << ") \n";
2274           polygon_set_data<Unit> psd = (*itr).second;
2275           polygon_90_set_data<Unit> psd90 = (*itr90).second;
2276           polys.clear();
2277           polys90.clear();
2278           psd.get(polys);
2279           psd90.get(polys90);
2280           if(polys.size() != polys90.size()) {
2281             stdcout << "merge failed with polygon count mismatch\n";
2282             stdcout << psd << "\n";
2283             for(std::size_t j = 0; j < polys.size(); ++j) {
2284               stdcout << polys[j] << "\n";
2285             }
2286             stdcout << "reference\n";
2287             for(std::size_t j = 0; j < polys90.size(); ++j) {
2288               stdcout << polys90[j] << "\n";
2289             }
2290             return 0;
2291           }
2292           bool failed = false;
2293           for(std::size_t j = 0; j < polys.size(); ++j) {
2294             stdcout << polys[j] << "\n";
2295             stdcout << polys90[j] << "\n";
2296 #ifdef BOOST_POLYGON_ICC
2297 #pragma warning (push)
2298 #pragma warning (disable:1572)
2299 #endif
2300             if(area(polys[j]) != area(polys90[j])) {
2301 #ifdef BOOST_POLYGON_ICC
2302 #pragma warning (pop)
2303 #endif
2304               stdcout << "merge failed with area mismatch\n";
2305               failed = true;
2306             }
2307           }
2308           if(failed) return 0;
2309           ++itr90;
2310         }
2311         return true;
2312     }
2313
2314     template <typename stream_type>
2315     static inline bool test_manhattan_intersection(stream_type& stdcout) {
2316       rectangle_data<Unit> rect1, rect2, rect3;
2317       set_points(rect1, (Point(-1, 2)), (Point(1, 4)));
2318       set_points(rect2, (Point(-1, 2)), (Point(2, 3)));
2319       set_points(rect3, (Point(-3, 0)), (Point(4, 2)));
2320       if(!check_rectangle_trio(rect1, rect2, rect3, stdcout)) {
2321         return false;
2322       }
2323       for(unsigned int i = 0; i < 100; ++i) {
2324         property_merge si;
2325         std::map<std::set<property_type>, polygon_set_data<Unit> > result;
2326         std::vector<polygon_data<Unit> > polys;
2327         property_merge_90<property_type, Unit> si90;
2328         std::map<std::set<property_type>, polygon_90_set_data<Unit> > result90;
2329         std::vector<polygon_data<Unit> > polys90;
2330         stdcout << "random case # " << i << "\n";
2331         set_points(rect1, (Point(rand()%9-4, rand()%9-4)), (Point(rand()%9-4, rand()%9-4)));
2332         set_points(rect2, (Point(rand()%9-4, rand()%9-4)), (Point(rand()%9-4, rand()%9-4)));
2333         set_points(rect3, (Point(rand()%9-4, rand()%9-4)), (Point(rand()%9-4, rand()%9-4)));
2334         if(!check_rectangle_trio(rect1, rect2, rect3, stdcout)) {
2335           return false;
2336         }
2337       }
2338       return true;
2339     }
2340
2341     template <typename stream_type>
2342     static inline bool test_intersection(stream_type& stdcout) {
2343       property_merge si;
2344       rectangle_data<Unit> rect;
2345       xl(rect, 0);
2346       yl(rect, 10);
2347       xh(rect, 30);
2348       yh(rect, 20);
2349       si.insert(rect, 333);
2350       xl(rect, 10);
2351       yl(rect, 0);
2352       xh(rect, 20);
2353       yh(rect, 30);
2354       si.insert(rect, 444);
2355       xl(rect, 15);
2356       yl(rect, 0);
2357       xh(rect, 25);
2358       yh(rect, 30);
2359       si.insert(rect, 555);
2360       std::map<std::set<property_type>, polygon_set_data<Unit> > result;
2361       si.merge(result);
2362       print(stdcout, si.pmd) << "\n";
2363       for(typename std::map<std::set<property_type>, polygon_set_data<Unit> >::iterator itr = result.begin();
2364           itr != result.end(); ++itr) {
2365         stdcout << "( ";
2366         for(typename std::set<property_type>::const_iterator set_itr = (*itr).first.begin();
2367             set_itr != (*itr).first.end(); ++set_itr) {
2368           stdcout << (*set_itr) << " ";
2369         } stdcout << ") \n";
2370         polygon_set_data<Unit> psd = (*itr).second;
2371         stdcout << psd << "\n";
2372         std::vector<polygon_data<Unit> > polys;
2373         psd.get(polys);
2374         for(std::size_t i = 0; i < polys.size(); ++i) {
2375           stdcout << polys[i] << "\n";
2376         }
2377       }
2378       std::vector<Point> pts;
2379       std::vector<polygon_data<Unit> > polys;
2380       for(unsigned int i = 0; i < 10; ++i) {
2381         property_merge si2;
2382         stdcout << "random case # " << i << "\n";
2383         si.clear();
2384         pts.clear();
2385         pts.push_back(Point(rand()%9-4, rand()%9-4));
2386         pts.push_back(Point(rand()%9-4, rand()%9-4));
2387         pts.push_back(Point(rand()%9-4, rand()%9-4));
2388         polygon_data<Unit> poly1;
2389         poly1.set(pts.begin(), pts.end());
2390         stdcout << poly1 << "\n";
2391         si.insert(poly1, 444);
2392         si2.insert(poly1, 333);
2393         pts.clear();
2394         pts.push_back(Point(rand()%9-4, rand()%9-4));
2395         pts.push_back(Point(rand()%9-4, rand()%9-4));
2396         pts.push_back(Point(rand()%9-4, rand()%9-4));
2397         polygon_data<Unit> poly2;
2398         poly2.set(pts.begin(), pts.end());
2399         stdcout << poly2 << "\n";
2400         si.insert(poly2, 444);
2401         si2.insert(poly2, 444);
2402         pts.clear();
2403         pts.push_back(Point(rand()%9-4, rand()%9-4));
2404         pts.push_back(Point(rand()%9-4, rand()%9-4));
2405         pts.push_back(Point(rand()%9-4, rand()%9-4));
2406         polygon_data<Unit> poly3;
2407         poly3.set(pts.begin(), pts.end());
2408         stdcout << poly3 << "\n";
2409         si.insert(poly3, 444);
2410         si2.insert(poly3, 555);
2411         result.clear();
2412         std::map<std::set<property_type>, polygon_set_data<Unit> > result2;
2413         si.merge(result);
2414         si2.merge(result2);
2415         stdcout << "merged result\n";
2416       for(typename std::map<std::set<property_type>, polygon_set_data<Unit> >::iterator itr = result.begin();
2417           itr != result.end(); ++itr) {
2418         stdcout << "( ";
2419         for(typename std::set<property_type>::const_iterator set_itr = (*itr).first.begin();
2420             set_itr != (*itr).first.end(); ++set_itr) {
2421           stdcout << (*set_itr) << " ";
2422         } stdcout << ") \n";
2423         polygon_set_data<Unit> psd = (*itr).second;
2424         stdcout << psd << "\n";
2425         std::vector<polygon_data<Unit> > polys2;
2426         psd.get(polys2);
2427         for(std::size_t ii = 0; ii < polys2.size(); ++ii) {
2428           stdcout << polys2[ii] << "\n";
2429         }
2430       }
2431       stdcout << "intersected pmd\n";
2432       print(stdcout, si2.pmd) << "\n";
2433       stdcout << "intersected result\n";
2434       for(typename std::map<std::set<property_type>, polygon_set_data<Unit> >::iterator itr = result2.begin();
2435           itr != result2.end(); ++itr) {
2436         stdcout << "( ";
2437         for(typename std::set<property_type>::const_iterator set_itr = (*itr).first.begin();
2438             set_itr != (*itr).first.end(); ++set_itr) {
2439           stdcout << (*set_itr) << " ";
2440         } stdcout << ") \n";
2441         polygon_set_data<Unit> psd = (*itr).second;
2442         stdcout << psd << "\n";
2443         std::vector<polygon_data<Unit> > polys2;
2444         psd.get(polys2);
2445         for(std::size_t ii = 0; ii < polys2.size(); ++ii) {
2446           stdcout << polys2[ii] << "\n";
2447         }
2448       }
2449         si.clear();
2450         for(typename std::map<std::set<property_type>, polygon_set_data<Unit> >::iterator itr = result2.begin();
2451             itr != result2.end(); ++itr) {
2452           polys.clear();
2453           (*itr).second.get(polys);
2454           for(std::size_t j = 0; j < polys.size(); ++j) {
2455             si.insert(polys[j], 444);
2456           }
2457         }
2458         result2.clear();
2459         si.merge(result2);
2460       stdcout << "remerged result\n";
2461       for(typename std::map<std::set<property_type>, polygon_set_data<Unit> >::iterator itr = result2.begin();
2462           itr != result2.end(); ++itr) {
2463         stdcout << "( ";
2464         for(typename std::set<property_type>::const_iterator set_itr = (*itr).first.begin();
2465             set_itr != (*itr).first.end(); ++set_itr) {
2466           stdcout << (*set_itr) << " ";
2467         } stdcout << ") \n";
2468         polygon_set_data<Unit> psd = (*itr).second;
2469         stdcout << psd << "\n";
2470         std::vector<polygon_data<Unit> > polys2;
2471         psd.get(polys2);
2472         for(std::size_t ii = 0; ii < polys2.size(); ++ii) {
2473           stdcout << polys2[ii] << "\n";
2474         }
2475       }
2476       std::vector<polygon_data<Unit> > polys2;
2477       polys.clear();
2478       (*(result.begin())).second.get(polys);
2479       (*(result2.begin())).second.get(polys2);
2480       if(!(polys == polys2)) {
2481           stdcout << "failed intersection check # " << i << "\n";
2482           return false;
2483         }
2484       }
2485       return true;
2486     }
2487   };
2488
2489   template <typename Unit>
2490   class arbitrary_boolean_op : public scanline_base<Unit> {
2491   private:
2492
2493     typedef int property_type;
2494     typedef typename scanline_base<Unit>::Point Point;
2495
2496     //the first point is the vertex and and second point establishes the slope of an edge eminating from the vertex
2497     //typedef std::pair<Point, Point> half_edge;
2498     typedef typename scanline_base<Unit>::half_edge half_edge;
2499
2500     //scanline comparator functor
2501     typedef typename scanline_base<Unit>::less_half_edge less_half_edge;
2502     typedef typename scanline_base<Unit>::less_point less_point;
2503
2504     //this data structure assocates a property and count to a half edge
2505     typedef std::pair<half_edge, std::pair<property_type, int> > vertex_property;
2506     //this data type stores the combination of many half edges
2507     typedef std::vector<vertex_property> property_merge_data;
2508
2509     //this is the data type used internally to store the combination of property counts at a given location
2510     typedef std::vector<std::pair<property_type, int> > property_map;
2511     //this data type is used internally to store the combined property data for a given half edge
2512     typedef std::pair<half_edge, property_map> vertex_data;
2513
2514     property_merge_data pmd;
2515     typename scanline_base<Unit>::evalAtXforYPack evalAtXforYPack_;
2516
2517     template<typename vertex_data_type>
2518     class less_vertex_data {
2519       typename scanline_base<Unit>::evalAtXforYPack* pack_;
2520     public:
2521       less_vertex_data() : pack_() {}
2522       less_vertex_data(typename scanline_base<Unit>::evalAtXforYPack* pack) : pack_(pack) {}
2523       bool operator()(const vertex_data_type& lvalue, const vertex_data_type& rvalue) const {
2524         less_point lp;
2525         if(lp(lvalue.first.first, rvalue.first.first)) return true;
2526         if(lp(rvalue.first.first, lvalue.first.first)) return false;
2527         Unit x = lvalue.first.first.get(HORIZONTAL);
2528         int just_before_ = 0;
2529         less_half_edge lhe(&x, &just_before_, pack_);
2530         return lhe(lvalue.first, rvalue.first);
2531       }
2532     };
2533
2534     template <typename result_type, typename key_type, int op_type>
2535     class boolean_output_functor {
2536     public:
2537       boolean_output_functor() {}
2538       void operator()(result_type& result, const half_edge& edge, const key_type& left, const key_type& right) {
2539         typename std::pair<half_edge, int> elem;
2540         elem.first = edge;
2541         elem.second = 1;
2542         if(edge.second < edge.first) elem.second *= -1;
2543         if(scanline_base<Unit>::is_vertical(edge)) elem.second *= -1;
2544 #ifdef BOOST_POLYGON_MSVC
2545 #pragma warning (push)
2546 #pragma warning (disable: 4127)
2547 #endif
2548         if(op_type == 0) { //OR
2549           if(!left.empty() && right.empty()) {
2550             result.insert_clean(elem);
2551           } else if(!right.empty() && left.empty()) {
2552             elem.second *= -1;
2553             result.insert_clean(elem);
2554           }
2555         } else if(op_type == 1) { //AND
2556           if(left.size() == 2 && right.size() != 2) {
2557             result.insert_clean(elem);
2558           } else if(right.size() == 2 && left.size() != 2) {
2559             elem.second *= -1;
2560             result.insert_clean(elem);
2561           }
2562         } else if(op_type == 2) { //XOR
2563           if(left.size() == 1 && right.size() != 1) {
2564             result.insert_clean(elem);
2565           } else if(right.size() == 1 && left.size() != 1) {
2566             elem.second *= -1;
2567             result.insert_clean(elem);
2568           }
2569         } else { //SUBTRACT
2570           if(left.size() == 1) {
2571             if((*(left.begin())) == 0) {
2572               result.insert_clean(elem);
2573             }
2574           }
2575 #ifdef BOOST_POLYGON_MSVC
2576 #pragma warning (pop)
2577 #endif
2578           if(right.size() == 1) {
2579             if((*(right.begin())) == 0) {
2580               elem.second *= -1;
2581               result.insert_clean(elem);
2582             }
2583           }
2584         }
2585       }
2586     };
2587
2588     inline void sort_property_merge_data() {
2589       less_vertex_data<vertex_property> lvd(&evalAtXforYPack_);
2590       polygon_sort(pmd.begin(), pmd.end(), lvd);
2591     }
2592   public:
2593     inline arbitrary_boolean_op() : pmd(), evalAtXforYPack_() {}
2594     inline arbitrary_boolean_op(const arbitrary_boolean_op& pm) : pmd(pm.pmd), evalAtXforYPack_(pm.evalAtXforYPack_) {}
2595     inline arbitrary_boolean_op& operator=(const arbitrary_boolean_op& pm) { pmd = pm.pmd; return *this; }
2596
2597     enum BOOLEAN_OP_TYPE {
2598       BOOLEAN_OR = 0,
2599       BOOLEAN_AND = 1,
2600       BOOLEAN_XOR = 2,
2601       BOOLEAN_NOT = 3
2602     };
2603     template <typename result_type, typename iT1, typename iT2>
2604     inline void execute(result_type& result, iT1 b1, iT1 e1, iT2 b2, iT2 e2, int op) {
2605       //intersect data
2606       insert(b1, e1, 0);
2607       insert(b2, e2, 1);
2608       property_merge_data tmp_pmd;
2609       //#define BOOST_POLYGON_DEBUG_FILE
2610 #ifdef BOOST_POLYGON_DEBUG_FILE
2611       std::fstream debug_file;
2612       debug_file.open("gtl_debug.txt", std::ios::out);
2613       property_merge<Unit, property_type, std::vector<property_type> >::print(debug_file, pmd);
2614       debug_file.close();
2615 #endif
2616       if(pmd.empty())
2617         return;
2618       line_intersection<Unit>::validate_scan(tmp_pmd, pmd.begin(), pmd.end());
2619       pmd.swap(tmp_pmd);
2620       sort_property_merge_data();
2621       scanline<Unit, property_type, std::vector<property_type> > sl;
2622       if(op == BOOLEAN_OR) {
2623         boolean_output_functor<result_type, std::vector<property_type>, 0> bof;
2624         sl.scan(result, bof, pmd.begin(), pmd.end());
2625       } else if(op == BOOLEAN_AND) {
2626         boolean_output_functor<result_type, std::vector<property_type>, 1> bof;
2627         sl.scan(result, bof, pmd.begin(), pmd.end());
2628       } else if(op == BOOLEAN_XOR) {
2629         boolean_output_functor<result_type, std::vector<property_type>, 2> bof;
2630         sl.scan(result, bof, pmd.begin(), pmd.end());
2631       } else if(op == BOOLEAN_NOT) {
2632         boolean_output_functor<result_type, std::vector<property_type>, 3> bof;
2633         sl.scan(result, bof, pmd.begin(), pmd.end());
2634       }
2635     }
2636
2637     inline void clear() {*this = arbitrary_boolean_op();}
2638
2639   private:
2640     template <typename iT>
2641     void insert(iT b, iT e, int id) {
2642       for(;
2643           b != e; ++b) {
2644         pmd.push_back(vertex_property(half_edge((*b).first.first, (*b).first.second),
2645                                       std::pair<property_type, int>(id, (*b).second)));
2646       }
2647     }
2648
2649   };
2650
2651   template <typename Unit, typename stream_type>
2652   bool test_arbitrary_boolean_op(stream_type& stdcout) {
2653     polygon_set_data<Unit> psd;
2654     rectangle_data<Unit> rect;
2655     set_points(rect, point_data<Unit>(0, 0), point_data<Unit>(10, 10));
2656     psd.insert(rect);
2657     polygon_set_data<Unit> psd2;
2658     set_points(rect, point_data<Unit>(5, 5), point_data<Unit>(15, 15));
2659     psd2.insert(rect);
2660     std::vector<polygon_data<Unit> > pv;
2661     pv.clear();
2662     arbitrary_boolean_op<Unit> abo;
2663     polygon_set_data<Unit> psd3;
2664     abo.execute(psd3, psd.begin(), psd.end(), psd2.begin(), psd2.end(), arbitrary_boolean_op<Unit>::BOOLEAN_OR);
2665     psd3.get(pv);
2666     for(std::size_t i = 0; i < pv.size(); ++i) {
2667       stdcout << pv[i] << "\n";
2668     }
2669     pv.clear();
2670     abo.clear();
2671     psd3.clear();
2672     abo.execute(psd3, psd.begin(), psd.end(), psd2.begin(), psd2.end(), arbitrary_boolean_op<Unit>::BOOLEAN_AND);
2673     psd3.get(pv);
2674     for(std::size_t i = 0; i < pv.size(); ++i) {
2675       stdcout << pv[i] << "\n";
2676     }
2677     pv.clear();
2678     abo.clear();
2679     psd3.clear();
2680     abo.execute(psd3, psd.begin(), psd.end(), psd2.begin(), psd2.end(), arbitrary_boolean_op<Unit>::BOOLEAN_XOR);
2681     psd3.get(pv);
2682     for(std::size_t i = 0; i < pv.size(); ++i) {
2683       stdcout << pv[i] << "\n";
2684     }
2685     pv.clear();
2686     abo.clear();
2687     psd3.clear();
2688     abo.execute(psd3, psd.begin(), psd.end(), psd2.begin(), psd2.end(), arbitrary_boolean_op<Unit>::BOOLEAN_NOT);
2689     psd3.get(pv);
2690     for(std::size_t i = 0; i < pv.size(); ++i) {
2691       stdcout << pv[i] << "\n";
2692     }
2693     return true;
2694   }
2695
2696
2697
2698
2699
2700
2701
2702
2703
2704
2705
2706
2707
2708
2709   template <typename Unit, typename property_type>
2710   class arbitrary_connectivity_extraction : public scanline_base<Unit> {
2711   private:
2712
2713     typedef typename scanline_base<Unit>::Point Point;
2714
2715     //the first point is the vertex and and second point establishes the slope of an edge eminating from the vertex
2716     //typedef std::pair<Point, Point> half_edge;
2717     typedef typename scanline_base<Unit>::half_edge half_edge;
2718
2719     //scanline comparator functor
2720     typedef typename scanline_base<Unit>::less_half_edge less_half_edge;
2721     typedef typename scanline_base<Unit>::less_point less_point;
2722
2723     //this data structure assocates a property and count to a half edge
2724     typedef std::pair<half_edge, std::pair<property_type, int> > vertex_property;
2725     //this data type stores the combination of many half edges
2726     typedef std::vector<vertex_property> property_merge_data;
2727
2728     //this is the data type used internally to store the combination of property counts at a given location
2729     typedef std::vector<std::pair<property_type, int> > property_map;
2730     //this data type is used internally to store the combined property data for a given half edge
2731     typedef std::pair<half_edge, property_map> vertex_data;
2732
2733     property_merge_data pmd;
2734     typename scanline_base<Unit>::evalAtXforYPack evalAtXforYPack_;
2735
2736     template<typename vertex_data_type>
2737     class less_vertex_data {
2738       typename scanline_base<Unit>::evalAtXforYPack* pack_;
2739     public:
2740       less_vertex_data() : pack_() {}
2741       less_vertex_data(typename scanline_base<Unit>::evalAtXforYPack* pack) : pack_(pack) {}
2742       bool operator()(const vertex_data_type& lvalue, const vertex_data_type& rvalue) const {
2743         less_point lp;
2744         if(lp(lvalue.first.first, rvalue.first.first)) return true;
2745         if(lp(rvalue.first.first, lvalue.first.first)) return false;
2746         Unit x = lvalue.first.first.get(HORIZONTAL);
2747         int just_before_ = 0;
2748         less_half_edge lhe(&x, &just_before_, pack_);
2749         return lhe(lvalue.first, rvalue.first);
2750       }
2751     };
2752
2753
2754     template <typename cT>
2755     static void process_previous_x(cT& output) {
2756       std::map<point_data<Unit>, std::set<property_type> >& y_prop_map = output.first.second;
2757       if(y_prop_map.empty()) return;
2758       Unit x = output.first.first;
2759       for(typename std::map<point_data<Unit>, std::set<property_type> >::iterator itr =
2760             y_prop_map.begin(); itr != y_prop_map.end(); ++itr) {
2761         if((*itr).first.x() < x) {
2762           y_prop_map.erase(y_prop_map.begin(), itr);
2763           continue;
2764         }
2765         for(typename std::set<property_type>::iterator inner_itr = itr->second.begin();
2766             inner_itr != itr->second.end(); ++inner_itr) {
2767           std::set<property_type>& output_edges = (*(output.second))[*inner_itr];
2768           typename std::set<property_type>::iterator inner_inner_itr = inner_itr;
2769           ++inner_inner_itr;
2770           for( ; inner_inner_itr != itr->second.end(); ++inner_inner_itr) {
2771             output_edges.insert(output_edges.end(), *inner_inner_itr);
2772             std::set<property_type>& output_edges_2 = (*(output.second))[*inner_inner_itr];
2773             output_edges_2.insert(output_edges_2.end(), *inner_itr);
2774           }
2775         }
2776       }
2777     }
2778
2779     template <typename result_type, typename key_type>
2780     class connectivity_extraction_output_functor {
2781     public:
2782       connectivity_extraction_output_functor() {}
2783       void operator()(result_type& result, const half_edge& edge, const key_type& left, const key_type& right) {
2784         Unit& x = result.first.first;
2785         std::map<point_data<Unit>, std::set<property_type> >& y_prop_map = result.first.second;
2786         point_data<Unit> pt = edge.first;
2787         if(pt.x() != x) process_previous_x(result);
2788         x = pt.x();
2789         std::set<property_type>& output_set = y_prop_map[pt];
2790         {
2791           for(typename key_type::const_iterator itr1 =
2792                 left.begin(); itr1 != left.end(); ++itr1) {
2793             output_set.insert(output_set.end(), *itr1);
2794           }
2795           for(typename key_type::const_iterator itr2 =
2796                 right.begin(); itr2 != right.end(); ++itr2) {
2797             output_set.insert(output_set.end(), *itr2);
2798           }
2799         }
2800         std::set<property_type>& output_set2 = y_prop_map[edge.second];
2801         for(typename key_type::const_iterator itr1 =
2802               left.begin(); itr1 != left.end(); ++itr1) {
2803           output_set2.insert(output_set2.end(), *itr1);
2804         }
2805         for(typename key_type::const_iterator itr2 =
2806               right.begin(); itr2 != right.end(); ++itr2) {
2807           output_set2.insert(output_set2.end(), *itr2);
2808         }
2809       }
2810     };
2811
2812     inline void sort_property_merge_data() {
2813       less_vertex_data<vertex_property> lvd(&evalAtXforYPack_);
2814       polygon_sort(pmd.begin(), pmd.end(), lvd);
2815     }
2816   public:
2817     inline arbitrary_connectivity_extraction() : pmd(), evalAtXforYPack_() {}
2818     inline arbitrary_connectivity_extraction
2819     (const arbitrary_connectivity_extraction& pm) : pmd(pm.pmd), evalAtXforYPack_(pm.evalAtXforYPack_) {}
2820     inline arbitrary_connectivity_extraction& operator=
2821       (const arbitrary_connectivity_extraction& pm) { pmd = pm.pmd; return *this; }
2822
2823     template <typename result_type>
2824     inline void execute(result_type& result) {
2825       //intersect data
2826       property_merge_data tmp_pmd;
2827       line_intersection<Unit>::validate_scan(tmp_pmd, pmd.begin(), pmd.end());
2828       pmd.swap(tmp_pmd);
2829       sort_property_merge_data();
2830       scanline<Unit, property_type, std::vector<property_type> > sl;
2831       std::pair<std::pair<Unit, std::map<point_data<Unit>, std::set<property_type> > >,
2832         result_type*> output
2833         (std::make_pair(std::make_pair((std::numeric_limits<Unit>::max)(),
2834                                        std::map<point_data<Unit>,
2835                                        std::set<property_type> >()), &result));
2836       connectivity_extraction_output_functor<std::pair<std::pair<Unit,
2837         std::map<point_data<Unit>, std::set<property_type> > >, result_type*>,
2838         std::vector<property_type> > ceof;
2839       sl.scan(output, ceof, pmd.begin(), pmd.end());
2840       process_previous_x(output);
2841     }
2842
2843     inline void clear() {*this = arbitrary_connectivity_extraction();}
2844
2845     template <typename iT>
2846     void populateTouchSetData(iT begin, iT end,
2847                                      property_type property) {
2848       for( ; begin != end; ++begin) {
2849         pmd.push_back(vertex_property(half_edge((*begin).first.first, (*begin).first.second),
2850                                       std::pair<property_type, int>(property, (*begin).second)));
2851       }
2852     }
2853
2854   };
2855
2856 }
2857 }
2858 #endif