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