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_POLYGON_ARBITRARY_FORMATION_HPP 9 #define BOOST_POLYGON_POLYGON_ARBITRARY_FORMATION_HPP 10 namespace boost { namespace polygon{ 11 template <typename T, typename T2> 12 struct PolyLineArbitraryByConcept {}; 13 14 template <typename T> 15 class poly_line_arbitrary_polygon_data; 16 template <typename T> 17 class poly_line_arbitrary_hole_data; 18 19 template <typename Unit> 20 struct scanline_base { 21 22 typedef point_data<Unit> Point; 23 typedef std::pair<Point, Point> half_edge; 24 25 class less_point : public std::binary_function<Point, Point, bool> { 26 public: less_point()27 inline less_point() {} operator ()(const Point & pt1,const Point & pt2) const28 inline bool operator () (const Point& pt1, const Point& pt2) const { 29 if(pt1.get(HORIZONTAL) < pt2.get(HORIZONTAL)) return true; 30 if(pt1.get(HORIZONTAL) == pt2.get(HORIZONTAL)) { 31 if(pt1.get(VERTICAL) < pt2.get(VERTICAL)) return true; 32 } 33 return false; 34 } 35 }; 36 betweenboost::polygon::scanline_base37 static inline bool between(Point pt, Point pt1, Point pt2) { 38 less_point lp; 39 if(lp(pt1, pt2)) 40 return lp(pt, pt2) && lp(pt1, pt); 41 return lp(pt, pt1) && lp(pt2, pt); 42 } 43 44 template <typename area_type> compute_interceptboost::polygon::scanline_base45 static inline Unit compute_intercept(const area_type& dy2, 46 const area_type& dx1, 47 const area_type& dx2) { 48 //intercept = dy2 * dx1 / dx2 49 //return (Unit)(((area_type)dy2 * (area_type)dx1) / (area_type)dx2); 50 area_type dx1_q = dx1 / dx2; 51 area_type dx1_r = dx1 % dx2; 52 return dx1_q * dy2 + (dy2 * dx1_r)/dx2; 53 } 54 55 template <typename area_type> equal_slopeboost::polygon::scanline_base56 static inline bool equal_slope(area_type dx1, area_type dy1, area_type dx2, area_type dy2) { 57 typedef typename coordinate_traits<Unit>::unsigned_area_type unsigned_product_type; 58 unsigned_product_type cross_1 = (unsigned_product_type)(dx2 < 0 ? -dx2 :dx2) * (unsigned_product_type)(dy1 < 0 ? -dy1 : dy1); 59 unsigned_product_type cross_2 = (unsigned_product_type)(dx1 < 0 ? -dx1 :dx1) * (unsigned_product_type)(dy2 < 0 ? -dy2 : dy2); 60 int dx1_sign = dx1 < 0 ? -1 : 1; 61 int dx2_sign = dx2 < 0 ? -1 : 1; 62 int dy1_sign = dy1 < 0 ? -1 : 1; 63 int dy2_sign = dy2 < 0 ? -1 : 1; 64 int cross_1_sign = dx2_sign * dy1_sign; 65 int cross_2_sign = dx1_sign * dy2_sign; 66 return cross_1 == cross_2 && (cross_1_sign == cross_2_sign || cross_1 == 0); 67 } 68 69 template <typename T> equal_slope_hpboost::polygon::scanline_base70 static inline bool equal_slope_hp(const T& dx1, const T& dy1, const T& dx2, const T& dy2) { 71 return dx1 * dy2 == dx2 * dy1; 72 } 73 equal_slopeboost::polygon::scanline_base74 static inline bool equal_slope(const Unit& x, const Unit& y, 75 const Point& pt1, const Point& pt2) { 76 const Point* pts[2] = {&pt1, &pt2}; 77 typedef typename coordinate_traits<Unit>::manhattan_area_type at; 78 at dy2 = (at)pts[1]->get(VERTICAL) - (at)y; 79 at dy1 = (at)pts[0]->get(VERTICAL) - (at)y; 80 at dx2 = (at)pts[1]->get(HORIZONTAL) - (at)x; 81 at dx1 = (at)pts[0]->get(HORIZONTAL) - (at)x; 82 return equal_slope(dx1, dy1, dx2, dy2); 83 } 84 85 template <typename area_type> less_slopeboost::polygon::scanline_base86 static inline bool less_slope(area_type dx1, area_type dy1, area_type dx2, area_type dy2) { 87 //reflext x and y slopes to right hand side half plane 88 if(dx1 < 0) { 89 dy1 *= -1; 90 dx1 *= -1; 91 } else if(dx1 == 0) { 92 //if the first slope is vertical the first cannot be less 93 return false; 94 } 95 if(dx2 < 0) { 96 dy2 *= -1; 97 dx2 *= -1; 98 } else if(dx2 == 0) { 99 //if the second slope is vertical the first is always less unless it is also vertical, in which case they are equal 100 return dx1 != 0; 101 } 102 typedef typename coordinate_traits<Unit>::unsigned_area_type unsigned_product_type; 103 unsigned_product_type cross_1 = (unsigned_product_type)(dx2 < 0 ? -dx2 :dx2) * (unsigned_product_type)(dy1 < 0 ? -dy1 : dy1); 104 unsigned_product_type cross_2 = (unsigned_product_type)(dx1 < 0 ? -dx1 :dx1) * (unsigned_product_type)(dy2 < 0 ? -dy2 : dy2); 105 int dx1_sign = dx1 < 0 ? -1 : 1; 106 int dx2_sign = dx2 < 0 ? -1 : 1; 107 int dy1_sign = dy1 < 0 ? -1 : 1; 108 int dy2_sign = dy2 < 0 ? -1 : 1; 109 int cross_1_sign = dx2_sign * dy1_sign; 110 int cross_2_sign = dx1_sign * dy2_sign; 111 if(cross_1_sign < cross_2_sign) return true; 112 if(cross_2_sign < cross_1_sign) return false; 113 if(cross_1_sign == -1) return cross_2 < cross_1; 114 return cross_1 < cross_2; 115 } 116 less_slopeboost::polygon::scanline_base117 static inline bool less_slope(const Unit& x, const Unit& y, 118 const Point& pt1, const Point& pt2) { 119 const Point* pts[2] = {&pt1, &pt2}; 120 //compute y value on edge from pt_ to pts[1] at the x value of pts[0] 121 typedef typename coordinate_traits<Unit>::manhattan_area_type at; 122 at dy2 = (at)pts[1]->get(VERTICAL) - (at)y; 123 at dy1 = (at)pts[0]->get(VERTICAL) - (at)y; 124 at dx2 = (at)pts[1]->get(HORIZONTAL) - (at)x; 125 at dx1 = (at)pts[0]->get(HORIZONTAL) - (at)x; 126 return less_slope(dx1, dy1, dx2, dy2); 127 } 128 129 //return -1 below, 0 on and 1 above line on_above_or_belowboost::polygon::scanline_base130 static inline int on_above_or_below(Point pt, const half_edge& he) { 131 if(pt == he.first || pt == he.second) return 0; 132 if(equal_slope(pt.get(HORIZONTAL), pt.get(VERTICAL), he.first, he.second)) return 0; 133 bool less_result = less_slope(pt.get(HORIZONTAL), pt.get(VERTICAL), he.first, he.second); 134 int retval = less_result ? -1 : 1; 135 less_point lp; 136 if(lp(he.second, he.first)) retval *= -1; 137 if(!between(pt, he.first, he.second)) retval *= -1; 138 return retval; 139 } 140 141 //returns true is the segment intersects the integer grid square with lower 142 //left corner at point intersects_gridboost::polygon::scanline_base143 static inline bool intersects_grid(Point pt, const half_edge& he) { 144 if(pt == he.second) return true; 145 if(pt == he.first) return true; 146 rectangle_data<Unit> rect1; 147 set_points(rect1, he.first, he.second); 148 if(contains(rect1, pt, true)) { 149 if(is_vertical(he) || is_horizontal(he)) return true; 150 } else { 151 return false; //can't intersect a grid not within bounding box 152 } 153 Unit x = pt.get(HORIZONTAL); 154 Unit y = pt.get(VERTICAL); 155 if(equal_slope(x, y, he.first, he.second) && 156 between(pt, he.first, he.second)) return true; 157 Point pt01(pt.get(HORIZONTAL), pt.get(VERTICAL) + 1); 158 Point pt10(pt.get(HORIZONTAL) + 1, pt.get(VERTICAL)); 159 Point pt11(pt.get(HORIZONTAL) + 1, pt.get(VERTICAL) + 1); 160 // if(pt01 == he.first) return true; 161 // if(pt10 == he.first) return true; 162 // if(pt11 == he.first) return true; 163 // if(pt01 == he.second) return true; 164 // if(pt10 == he.second) return true; 165 // if(pt11 == he.second) return true; 166 //check non-integer intersections 167 half_edge widget1(pt, pt11); 168 //intersects but not just at pt11 169 if(intersects(widget1, he) && on_above_or_below(pt11, he)) return true; 170 half_edge widget2(pt01, pt10); 171 //intersects but not just at pt01 or 10 172 if(intersects(widget2, he) && on_above_or_below(pt01, he) && on_above_or_below(pt10, he)) return true; 173 return false; 174 } 175 evalAtXforYlazyboost::polygon::scanline_base176 static inline Unit evalAtXforYlazy(Unit xIn, Point pt, Point other_pt) { 177 long double 178 evalAtXforYret, evalAtXforYxIn, evalAtXforYx1, evalAtXforYy1, evalAtXforYdx1, evalAtXforYdx, 179 evalAtXforYdy, evalAtXforYx2, evalAtXforYy2, evalAtXforY0; 180 //y = (x - x1)dy/dx + y1 181 //y = (xIn - pt.x)*(other_pt.y-pt.y)/(other_pt.x-pt.x) + pt.y 182 //assert pt.x != other_pt.x 183 if(pt.y() == other_pt.y()) 184 return pt.y(); 185 evalAtXforYxIn = xIn; 186 evalAtXforYx1 = pt.get(HORIZONTAL); 187 evalAtXforYy1 = pt.get(VERTICAL); 188 evalAtXforYdx1 = evalAtXforYxIn - evalAtXforYx1; 189 evalAtXforY0 = 0; 190 if(evalAtXforYdx1 == evalAtXforY0) return (Unit)evalAtXforYy1; 191 evalAtXforYx2 = other_pt.get(HORIZONTAL); 192 evalAtXforYy2 = other_pt.get(VERTICAL); 193 194 evalAtXforYdx = evalAtXforYx2 - evalAtXforYx1; 195 evalAtXforYdy = evalAtXforYy2 - evalAtXforYy1; 196 evalAtXforYret = ((evalAtXforYdx1) * evalAtXforYdy / evalAtXforYdx + evalAtXforYy1); 197 return (Unit)evalAtXforYret; 198 } 199 evalAtXforYboost::polygon::scanline_base200 static inline typename high_precision_type<Unit>::type evalAtXforY(Unit xIn, Point pt, Point other_pt) { 201 typename high_precision_type<Unit>::type 202 evalAtXforYret, evalAtXforYxIn, evalAtXforYx1, evalAtXforYy1, evalAtXforYdx1, evalAtXforYdx, 203 evalAtXforYdy, evalAtXforYx2, evalAtXforYy2, evalAtXforY0; 204 //y = (x - x1)dy/dx + y1 205 //y = (xIn - pt.x)*(other_pt.y-pt.y)/(other_pt.x-pt.x) + pt.y 206 //assert pt.x != other_pt.x 207 typedef typename high_precision_type<Unit>::type high_precision; 208 if(pt.y() == other_pt.y()) 209 return (high_precision)pt.y(); 210 evalAtXforYxIn = (high_precision)xIn; 211 evalAtXforYx1 = pt.get(HORIZONTAL); 212 evalAtXforYy1 = pt.get(VERTICAL); 213 evalAtXforYdx1 = evalAtXforYxIn - evalAtXforYx1; 214 evalAtXforY0 = high_precision(0); 215 if(evalAtXforYdx1 == evalAtXforY0) return evalAtXforYret = evalAtXforYy1; 216 evalAtXforYx2 = (high_precision)other_pt.get(HORIZONTAL); 217 evalAtXforYy2 = (high_precision)other_pt.get(VERTICAL); 218 219 evalAtXforYdx = evalAtXforYx2 - evalAtXforYx1; 220 evalAtXforYdy = evalAtXforYy2 - evalAtXforYy1; 221 evalAtXforYret = ((evalAtXforYdx1) * evalAtXforYdy / evalAtXforYdx + evalAtXforYy1); 222 return evalAtXforYret; 223 } 224 225 struct evalAtXforYPack { 226 typename high_precision_type<Unit>::type 227 evalAtXforYret, evalAtXforYxIn, evalAtXforYx1, evalAtXforYy1, evalAtXforYdx1, evalAtXforYdx, 228 evalAtXforYdy, evalAtXforYx2, evalAtXforYy2, evalAtXforY0; evalAtXforYboost::polygon::scanline_base::evalAtXforYPack229 inline const typename high_precision_type<Unit>::type& evalAtXforY(Unit xIn, Point pt, Point other_pt) { 230 //y = (x - x1)dy/dx + y1 231 //y = (xIn - pt.x)*(other_pt.y-pt.y)/(other_pt.x-pt.x) + pt.y 232 //assert pt.x != other_pt.x 233 typedef typename high_precision_type<Unit>::type high_precision; 234 if(pt.y() == other_pt.y()) { 235 evalAtXforYret = (high_precision)pt.y(); 236 return evalAtXforYret; 237 } 238 evalAtXforYxIn = (high_precision)xIn; 239 evalAtXforYx1 = pt.get(HORIZONTAL); 240 evalAtXforYy1 = pt.get(VERTICAL); 241 evalAtXforYdx1 = evalAtXforYxIn - evalAtXforYx1; 242 evalAtXforY0 = high_precision(0); 243 if(evalAtXforYdx1 == evalAtXforY0) return evalAtXforYret = evalAtXforYy1; 244 evalAtXforYx2 = (high_precision)other_pt.get(HORIZONTAL); 245 evalAtXforYy2 = (high_precision)other_pt.get(VERTICAL); 246 247 evalAtXforYdx = evalAtXforYx2 - evalAtXforYx1; 248 evalAtXforYdy = evalAtXforYy2 - evalAtXforYy1; 249 evalAtXforYret = ((evalAtXforYdx1) * evalAtXforYdy / evalAtXforYdx + evalAtXforYy1); 250 return evalAtXforYret; 251 } 252 }; 253 is_verticalboost::polygon::scanline_base254 static inline bool is_vertical(const half_edge& he) { 255 return he.first.get(HORIZONTAL) == he.second.get(HORIZONTAL); 256 } 257 is_horizontalboost::polygon::scanline_base258 static inline bool is_horizontal(const half_edge& he) { 259 return he.first.get(VERTICAL) == he.second.get(VERTICAL); 260 } 261 is_45_degreeboost::polygon::scanline_base262 static inline bool is_45_degree(const half_edge& he) { 263 return euclidean_distance(he.first, he.second, HORIZONTAL) == euclidean_distance(he.first, he.second, VERTICAL); 264 } 265 266 //scanline comparator functor 267 class less_half_edge : public std::binary_function<half_edge, half_edge, bool> { 268 private: 269 Unit *x_; //x value at which to apply comparison 270 int *justBefore_; 271 evalAtXforYPack * pack_; 272 public: less_half_edge()273 inline less_half_edge() : x_(0), justBefore_(0), pack_(0) {} less_half_edge(Unit * x,int * justBefore,evalAtXforYPack * packIn)274 inline less_half_edge(Unit *x, int *justBefore, evalAtXforYPack * packIn) : x_(x), justBefore_(justBefore), pack_(packIn) {} less_half_edge(const less_half_edge & that)275 inline less_half_edge(const less_half_edge& that) : x_(that.x_), justBefore_(that.justBefore_), 276 pack_(that.pack_){} operator =(const less_half_edge & that)277 inline less_half_edge& operator=(const less_half_edge& that) { 278 x_ = that.x_; 279 justBefore_ = that.justBefore_; 280 pack_ = that.pack_; 281 return *this; } operator ()(const half_edge & elm1,const half_edge & elm2) const282 inline bool operator () (const half_edge& elm1, const half_edge& elm2) const { 283 if((std::max)(elm1.first.y(), elm1.second.y()) < (std::min)(elm2.first.y(), elm2.second.y())) 284 return true; 285 if((std::min)(elm1.first.y(), elm1.second.y()) > (std::max)(elm2.first.y(), elm2.second.y())) 286 return false; 287 288 //check if either x of elem1 is equal to x_ 289 Unit localx = *x_; 290 Unit elm1y = 0; 291 bool elm1_at_x = false; 292 if(localx == elm1.first.get(HORIZONTAL)) { 293 elm1_at_x = true; 294 elm1y = elm1.first.get(VERTICAL); 295 } else if(localx == elm1.second.get(HORIZONTAL)) { 296 elm1_at_x = true; 297 elm1y = elm1.second.get(VERTICAL); 298 } 299 Unit elm2y = 0; 300 bool elm2_at_x = false; 301 if(localx == elm2.first.get(HORIZONTAL)) { 302 elm2_at_x = true; 303 elm2y = elm2.first.get(VERTICAL); 304 } else if(localx == elm2.second.get(HORIZONTAL)) { 305 elm2_at_x = true; 306 elm2y = elm2.second.get(VERTICAL); 307 } 308 bool retval = false; 309 if(!(elm1_at_x && elm2_at_x)) { 310 //at least one of the segments doesn't have an end point a the current x 311 //-1 below, 1 above 312 int pt1_oab = on_above_or_below(elm1.first, half_edge(elm2.first, elm2.second)); 313 int pt2_oab = on_above_or_below(elm1.second, half_edge(elm2.first, elm2.second)); 314 if(pt1_oab == pt2_oab) { 315 if(pt1_oab == -1) 316 retval = true; //pt1 is below elm2 so elm1 is below elm2 317 } else { 318 //the segments can't cross so elm2 is on whatever side of elm1 that one of its ends is 319 int pt3_oab = on_above_or_below(elm2.first, half_edge(elm1.first, elm1.second)); 320 if(pt3_oab == 1) 321 retval = true; //elm1's point is above elm1 322 } 323 } else { 324 if(elm1y < elm2y) { 325 retval = true; 326 } else if(elm1y == elm2y) { 327 if(elm1 == elm2) 328 return false; 329 retval = less_slope(elm1.second.get(HORIZONTAL) - elm1.first.get(HORIZONTAL), 330 elm1.second.get(VERTICAL) - elm1.first.get(VERTICAL), 331 elm2.second.get(HORIZONTAL) - elm2.first.get(HORIZONTAL), 332 elm2.second.get(VERTICAL) - elm2.first.get(VERTICAL)); 333 retval = ((*justBefore_) != 0) ^ retval; 334 } 335 } 336 return retval; 337 } 338 }; 339 340 template <typename unsigned_product_type> unsigned_modboost::polygon::scanline_base341 static inline void unsigned_mod(unsigned_product_type& result, int& result_sign, unsigned_product_type a, int a_sign, unsigned_product_type b, int b_sign) { 342 result = a % b; 343 result_sign = a_sign; 344 } 345 346 template <typename unsigned_product_type> unsigned_addboost::polygon::scanline_base347 static inline void unsigned_add(unsigned_product_type& result, int& result_sign, unsigned_product_type a, int a_sign, unsigned_product_type b, int b_sign) { 348 int switcher = 0; 349 if(a_sign < 0) switcher += 1; 350 if(b_sign < 0) switcher += 2; 351 if(a < b) switcher += 4; 352 switch (switcher) { 353 case 0: //both positive 354 result = a + b; 355 result_sign = 1; 356 break; 357 case 1: //a is negative 358 result = a - b; 359 result_sign = -1; 360 break; 361 case 2: //b is negative 362 result = a - b; 363 result_sign = 1; 364 break; 365 case 3: //both negative 366 result = a + b; 367 result_sign = -1; 368 break; 369 case 4: //both positive 370 result = a + b; 371 result_sign = 1; 372 break; 373 case 5: //a is negative 374 result = b - a; 375 result_sign = 1; 376 break; 377 case 6: //b is negative 378 result = b - a; 379 result_sign = -1; 380 break; 381 case 7: //both negative 382 result = b + a; 383 result_sign = -1; 384 break; 385 }; 386 } 387 388 struct compute_intersection_pack { 389 typedef typename high_precision_type<Unit>::type high_precision; 390 high_precision y_high, dx1, dy1, dx2, dy2, x11, x21, y11, y21, x_num, y_num, x_den, y_den, x, y; compute_lazy_intersectionboost::polygon::scanline_base::compute_intersection_pack391 static inline bool compute_lazy_intersection(Point& intersection, const half_edge& he1, const half_edge& he2, 392 bool projected = false, bool round_closest = false) { 393 long double y_high, dx1, dy1, dx2, dy2, x11, x21, y11, y21, x_num, y_num, x_den, y_den, x, y; 394 typedef rectangle_data<Unit> Rectangle; 395 Rectangle rect1, rect2; 396 set_points(rect1, he1.first, he1.second); 397 set_points(rect2, he2.first, he2.second); 398 if(!projected && !::boost::polygon::intersects(rect1, rect2, true)) return false; 399 if(is_vertical(he1)) { 400 if(is_vertical(he2)) return false; 401 y_high = evalAtXforYlazy(he1.first.get(HORIZONTAL), he2.first, he2.second); 402 Unit y_local = (Unit)y_high; 403 if(y_high < y_local) --y_local; 404 if(projected || contains(rect1.get(VERTICAL), y_local, true)) { 405 intersection = Point(he1.first.get(HORIZONTAL), y_local); 406 return true; 407 } else { 408 return false; 409 } 410 } else if(is_vertical(he2)) { 411 y_high = evalAtXforYlazy(he2.first.get(HORIZONTAL), he1.first, he1.second); 412 Unit y_local = (Unit)y_high; 413 if(y_high < y_local) --y_local; 414 if(projected || contains(rect2.get(VERTICAL), y_local, true)) { 415 intersection = Point(he2.first.get(HORIZONTAL), y_local); 416 return true; 417 } else { 418 return false; 419 } 420 } 421 //the bounding boxes of the two line segments intersect, so we check closer to find the intersection point 422 dy2 = (he2.second.get(VERTICAL)) - 423 (he2.first.get(VERTICAL)); 424 dy1 = (he1.second.get(VERTICAL)) - 425 (he1.first.get(VERTICAL)); 426 dx2 = (he2.second.get(HORIZONTAL)) - 427 (he2.first.get(HORIZONTAL)); 428 dx1 = (he1.second.get(HORIZONTAL)) - 429 (he1.first.get(HORIZONTAL)); 430 if(equal_slope_hp(dx1, dy1, dx2, dy2)) return false; 431 //the line segments have different slopes 432 //we can assume that the line segments are not vertical because such an intersection is handled elsewhere 433 x11 = (he1.first.get(HORIZONTAL)); 434 x21 = (he2.first.get(HORIZONTAL)); 435 y11 = (he1.first.get(VERTICAL)); 436 y21 = (he2.first.get(VERTICAL)); 437 //Unit exp_x = ((at)x11 * (at)dy1 * (at)dx2 - (at)x21 * (at)dy2 * (at)dx1 + (at)y21 * (at)dx1 * (at)dx2 - (at)y11 * (at)dx1 * (at)dx2) / ((at)dy1 * (at)dx2 - (at)dy2 * (at)dx1); 438 //Unit exp_y = ((at)y11 * (at)dx1 * (at)dy2 - (at)y21 * (at)dx2 * (at)dy1 + (at)x21 * (at)dy1 * (at)dy2 - (at)x11 * (at)dy1 * (at)dy2) / ((at)dx1 * (at)dy2 - (at)dx2 * (at)dy1); 439 x_num = (x11 * dy1 * dx2 - x21 * dy2 * dx1 + y21 * dx1 * dx2 - y11 * dx1 * dx2); 440 x_den = (dy1 * dx2 - dy2 * dx1); 441 y_num = (y11 * dx1 * dy2 - y21 * dx2 * dy1 + x21 * dy1 * dy2 - x11 * dy1 * dy2); 442 y_den = (dx1 * dy2 - dx2 * dy1); 443 x = x_num / x_den; 444 y = y_num / y_den; 445 //std::cout << "cross1 " << dy1 << " " << dx2 << " " << dy1 * dx2 << "\n"; 446 //std::cout << "cross2 " << dy2 << " " << dx1 << " " << dy2 * dx1 << "\n"; 447 //Unit exp_x = compute_x_intercept<at>(x11, x21, y11, y21, dy1, dy2, dx1, dx2); 448 //Unit exp_y = compute_x_intercept<at>(y11, y21, x11, x21, dx1, dx2, dy1, dy2); 449 if(round_closest) { 450 x = x + 0.5; 451 y = y + 0.5; 452 } 453 Unit x_unit = (Unit)(x); 454 Unit y_unit = (Unit)(y); 455 //truncate downward if it went up due to negative number 456 if(x < x_unit) --x_unit; 457 if(y < y_unit) --y_unit; 458 if(is_horizontal(he1)) 459 y_unit = he1.first.y(); 460 if(is_horizontal(he2)) 461 y_unit = he2.first.y(); 462 //if(x != exp_x || y != exp_y) 463 // std::cout << exp_x << " " << exp_y << " " << x << " " << y << "\n"; 464 //Unit y1 = evalAtXforY(exp_x, he1.first, he1.second); 465 //Unit y2 = evalAtXforY(exp_x, he2.first, he2.second); 466 //std::cout << exp_x << " " << exp_y << " " << y1 << " " << y2 << "\n"; 467 Point result(x_unit, y_unit); 468 if(!projected && !contains(rect1, result, true)) return false; 469 if(!projected && !contains(rect2, result, true)) return false; 470 if(projected) { 471 rectangle_data<long double> inf_rect(-(long double)(std::numeric_limits<Unit>::max)(), 472 -(long double) (std::numeric_limits<Unit>::max)(), 473 (long double)(std::numeric_limits<Unit>::max)(), 474 (long double) (std::numeric_limits<Unit>::max)() ); 475 if(contains(inf_rect, point_data<long double>(x, y), true)) { 476 intersection = result; 477 return true; 478 } else 479 return false; 480 } 481 intersection = result; 482 return true; 483 } 484 compute_intersectionboost::polygon::scanline_base::compute_intersection_pack485 inline bool compute_intersection(Point& intersection, const half_edge& he1, const half_edge& he2, 486 bool projected = false, bool round_closest = false) { 487 if(!projected && !intersects(he1, he2)) 488 return false; 489 bool lazy_success = compute_lazy_intersection(intersection, he1, he2, projected); 490 if(!projected) { 491 if(lazy_success) { 492 if(intersects_grid(intersection, he1) && 493 intersects_grid(intersection, he2)) 494 return true; 495 } 496 } else { 497 return lazy_success; 498 } 499 return compute_exact_intersection(intersection, he1, he2, projected, round_closest); 500 } 501 compute_exact_intersectionboost::polygon::scanline_base::compute_intersection_pack502 inline bool compute_exact_intersection(Point& intersection, const half_edge& he1, const half_edge& he2, 503 bool projected = false, bool round_closest = false) { 504 if(!projected && !intersects(he1, he2)) 505 return false; 506 typedef rectangle_data<Unit> Rectangle; 507 Rectangle rect1, rect2; 508 set_points(rect1, he1.first, he1.second); 509 set_points(rect2, he2.first, he2.second); 510 if(!::boost::polygon::intersects(rect1, rect2, true)) return false; 511 if(is_vertical(he1)) { 512 if(is_vertical(he2)) return false; 513 y_high = evalAtXforY(he1.first.get(HORIZONTAL), he2.first, he2.second); 514 Unit y = convert_high_precision_type<Unit>(y_high); 515 if(y_high < (high_precision)y) --y; 516 if(contains(rect1.get(VERTICAL), y, true)) { 517 intersection = Point(he1.first.get(HORIZONTAL), y); 518 return true; 519 } else { 520 return false; 521 } 522 } else if(is_vertical(he2)) { 523 y_high = evalAtXforY(he2.first.get(HORIZONTAL), he1.first, he1.second); 524 Unit y = convert_high_precision_type<Unit>(y_high); 525 if(y_high < (high_precision)y) --y; 526 if(contains(rect2.get(VERTICAL), y, true)) { 527 intersection = Point(he2.first.get(HORIZONTAL), y); 528 return true; 529 } else { 530 return false; 531 } 532 } 533 //the bounding boxes of the two line segments intersect, so we check closer to find the intersection point 534 dy2 = (high_precision)(he2.second.get(VERTICAL)) - 535 (high_precision)(he2.first.get(VERTICAL)); 536 dy1 = (high_precision)(he1.second.get(VERTICAL)) - 537 (high_precision)(he1.first.get(VERTICAL)); 538 dx2 = (high_precision)(he2.second.get(HORIZONTAL)) - 539 (high_precision)(he2.first.get(HORIZONTAL)); 540 dx1 = (high_precision)(he1.second.get(HORIZONTAL)) - 541 (high_precision)(he1.first.get(HORIZONTAL)); 542 if(equal_slope_hp(dx1, dy1, dx2, dy2)) return false; 543 //the line segments have different slopes 544 //we can assume that the line segments are not vertical because such an intersection is handled elsewhere 545 x11 = (high_precision)(he1.first.get(HORIZONTAL)); 546 x21 = (high_precision)(he2.first.get(HORIZONTAL)); 547 y11 = (high_precision)(he1.first.get(VERTICAL)); 548 y21 = (high_precision)(he2.first.get(VERTICAL)); 549 //Unit exp_x = ((at)x11 * (at)dy1 * (at)dx2 - (at)x21 * (at)dy2 * (at)dx1 + (at)y21 * (at)dx1 * (at)dx2 - (at)y11 * (at)dx1 * (at)dx2) / ((at)dy1 * (at)dx2 - (at)dy2 * (at)dx1); 550 //Unit exp_y = ((at)y11 * (at)dx1 * (at)dy2 - (at)y21 * (at)dx2 * (at)dy1 + (at)x21 * (at)dy1 * (at)dy2 - (at)x11 * (at)dy1 * (at)dy2) / ((at)dx1 * (at)dy2 - (at)dx2 * (at)dy1); 551 x_num = (x11 * dy1 * dx2 - x21 * dy2 * dx1 + y21 * dx1 * dx2 - y11 * dx1 * dx2); 552 x_den = (dy1 * dx2 - dy2 * dx1); 553 y_num = (y11 * dx1 * dy2 - y21 * dx2 * dy1 + x21 * dy1 * dy2 - x11 * dy1 * dy2); 554 y_den = (dx1 * dy2 - dx2 * dy1); 555 x = x_num / x_den; 556 y = y_num / y_den; 557 //std::cout << x << " " << y << "\n"; 558 //std::cout << "cross1 " << dy1 << " " << dx2 << " " << dy1 * dx2 << "\n"; 559 //std::cout << "cross2 " << dy2 << " " << dx1 << " " << dy2 * dx1 << "\n"; 560 //Unit exp_x = compute_x_intercept<at>(x11, x21, y11, y21, dy1, dy2, dx1, dx2); 561 //Unit exp_y = compute_x_intercept<at>(y11, y21, x11, x21, dx1, dx2, dy1, dy2); 562 if(round_closest) { 563 x = x + (high_precision)0.5; 564 y = y + (high_precision)0.5; 565 } 566 Unit x_unit = convert_high_precision_type<Unit>(x); 567 Unit y_unit = convert_high_precision_type<Unit>(y); 568 //truncate downward if it went up due to negative number 569 if(x < (high_precision)x_unit) --x_unit; 570 if(y < (high_precision)y_unit) --y_unit; 571 if(is_horizontal(he1)) 572 y_unit = he1.first.y(); 573 if(is_horizontal(he2)) 574 y_unit = he2.first.y(); 575 //if(x != exp_x || y != exp_y) 576 // std::cout << exp_x << " " << exp_y << " " << x << " " << y << "\n"; 577 //Unit y1 = evalAtXforY(exp_x, he1.first, he1.second); 578 //Unit y2 = evalAtXforY(exp_x, he2.first, he2.second); 579 //std::cout << exp_x << " " << exp_y << " " << y1 << " " << y2 << "\n"; 580 Point result(x_unit, y_unit); 581 if(!contains(rect1, result, true)) return false; 582 if(!contains(rect2, result, true)) return false; 583 if(projected) { 584 high_precision b1 = (high_precision) (std::numeric_limits<Unit>::min)(); 585 high_precision b2 = (high_precision) (std::numeric_limits<Unit>::max)(); 586 if(x > b2 || y > b2 || x < b1 || y < b1) 587 return false; 588 } 589 intersection = result; 590 return true; 591 } 592 }; 593 compute_intersectionboost::polygon::scanline_base594 static inline bool compute_intersection(Point& intersection, const half_edge& he1, const half_edge& he2) { 595 typedef typename high_precision_type<Unit>::type high_precision; 596 typedef rectangle_data<Unit> Rectangle; 597 Rectangle rect1, rect2; 598 set_points(rect1, he1.first, he1.second); 599 set_points(rect2, he2.first, he2.second); 600 if(!::boost::polygon::intersects(rect1, rect2, true)) return false; 601 if(is_vertical(he1)) { 602 if(is_vertical(he2)) return false; 603 high_precision y_high = evalAtXforY(he1.first.get(HORIZONTAL), he2.first, he2.second); 604 Unit y = convert_high_precision_type<Unit>(y_high); 605 if(y_high < (high_precision)y) --y; 606 if(contains(rect1.get(VERTICAL), y, true)) { 607 intersection = Point(he1.first.get(HORIZONTAL), y); 608 return true; 609 } else { 610 return false; 611 } 612 } else if(is_vertical(he2)) { 613 high_precision y_high = evalAtXforY(he2.first.get(HORIZONTAL), he1.first, he1.second); 614 Unit y = convert_high_precision_type<Unit>(y_high); 615 if(y_high < (high_precision)y) --y; 616 if(contains(rect2.get(VERTICAL), y, true)) { 617 intersection = Point(he2.first.get(HORIZONTAL), y); 618 return true; 619 } else { 620 return false; 621 } 622 } 623 //the bounding boxes of the two line segments intersect, so we check closer to find the intersection point 624 high_precision dy2 = (high_precision)(he2.second.get(VERTICAL)) - 625 (high_precision)(he2.first.get(VERTICAL)); 626 high_precision dy1 = (high_precision)(he1.second.get(VERTICAL)) - 627 (high_precision)(he1.first.get(VERTICAL)); 628 high_precision dx2 = (high_precision)(he2.second.get(HORIZONTAL)) - 629 (high_precision)(he2.first.get(HORIZONTAL)); 630 high_precision dx1 = (high_precision)(he1.second.get(HORIZONTAL)) - 631 (high_precision)(he1.first.get(HORIZONTAL)); 632 if(equal_slope_hp(dx1, dy1, dx2, dy2)) return false; 633 //the line segments have different slopes 634 //we can assume that the line segments are not vertical because such an intersection is handled elsewhere 635 high_precision x11 = (high_precision)(he1.first.get(HORIZONTAL)); 636 high_precision x21 = (high_precision)(he2.first.get(HORIZONTAL)); 637 high_precision y11 = (high_precision)(he1.first.get(VERTICAL)); 638 high_precision y21 = (high_precision)(he2.first.get(VERTICAL)); 639 //Unit exp_x = ((at)x11 * (at)dy1 * (at)dx2 - (at)x21 * (at)dy2 * (at)dx1 + (at)y21 * (at)dx1 * (at)dx2 - (at)y11 * (at)dx1 * (at)dx2) / ((at)dy1 * (at)dx2 - (at)dy2 * (at)dx1); 640 //Unit exp_y = ((at)y11 * (at)dx1 * (at)dy2 - (at)y21 * (at)dx2 * (at)dy1 + (at)x21 * (at)dy1 * (at)dy2 - (at)x11 * (at)dy1 * (at)dy2) / ((at)dx1 * (at)dy2 - (at)dx2 * (at)dy1); 641 high_precision x_num = (x11 * dy1 * dx2 - x21 * dy2 * dx1 + y21 * dx1 * dx2 - y11 * dx1 * dx2); 642 high_precision x_den = (dy1 * dx2 - dy2 * dx1); 643 high_precision y_num = (y11 * dx1 * dy2 - y21 * dx2 * dy1 + x21 * dy1 * dy2 - x11 * dy1 * dy2); 644 high_precision y_den = (dx1 * dy2 - dx2 * dy1); 645 high_precision x = x_num / x_den; 646 high_precision y = y_num / y_den; 647 //std::cout << "cross1 " << dy1 << " " << dx2 << " " << dy1 * dx2 << "\n"; 648 //std::cout << "cross2 " << dy2 << " " << dx1 << " " << dy2 * dx1 << "\n"; 649 //Unit exp_x = compute_x_intercept<at>(x11, x21, y11, y21, dy1, dy2, dx1, dx2); 650 //Unit exp_y = compute_x_intercept<at>(y11, y21, x11, x21, dx1, dx2, dy1, dy2); 651 Unit x_unit = convert_high_precision_type<Unit>(x); 652 Unit y_unit = convert_high_precision_type<Unit>(y); 653 //truncate downward if it went up due to negative number 654 if(x < (high_precision)x_unit) --x_unit; 655 if(y < (high_precision)y_unit) --y_unit; 656 if(is_horizontal(he1)) 657 y_unit = he1.first.y(); 658 if(is_horizontal(he2)) 659 y_unit = he2.first.y(); 660 //if(x != exp_x || y != exp_y) 661 // std::cout << exp_x << " " << exp_y << " " << x << " " << y << "\n"; 662 //Unit y1 = evalAtXforY(exp_x, he1.first, he1.second); 663 //Unit y2 = evalAtXforY(exp_x, he2.first, he2.second); 664 //std::cout << exp_x << " " << exp_y << " " << y1 << " " << y2 << "\n"; 665 Point result(x_unit, y_unit); 666 if(!contains(rect1, result, true)) return false; 667 if(!contains(rect2, result, true)) return false; 668 intersection = result; 669 return true; 670 } 671 intersectsboost::polygon::scanline_base672 static inline bool intersects(const half_edge& he1, const half_edge& he2) { 673 typedef rectangle_data<Unit> Rectangle; 674 Rectangle rect1, rect2; 675 set_points(rect1, he1.first, he1.second); 676 set_points(rect2, he2.first, he2.second); 677 if(::boost::polygon::intersects(rect1, rect2, false)) { 678 if(he1.first == he2.first) { 679 if(he1.second != he2.second && equal_slope(he1.first.get(HORIZONTAL), he1.first.get(VERTICAL), 680 he1.second, he2.second)) { 681 return true; 682 } else { 683 return false; 684 } 685 } 686 if(he1.first == he2.second) { 687 if(he1.second != he2.first && equal_slope(he1.first.get(HORIZONTAL), he1.first.get(VERTICAL), 688 he1.second, he2.first)) { 689 return true; 690 } else { 691 return false; 692 } 693 } 694 if(he1.second == he2.first) { 695 if(he1.first != he2.second && equal_slope(he1.second.get(HORIZONTAL), he1.second.get(VERTICAL), 696 he1.first, he2.second)) { 697 return true; 698 } else { 699 return false; 700 } 701 } 702 if(he1.second == he2.second) { 703 if(he1.first != he2.first && equal_slope(he1.second.get(HORIZONTAL), he1.second.get(VERTICAL), 704 he1.first, he2.first)) { 705 return true; 706 } else { 707 return false; 708 } 709 } 710 int oab1 = on_above_or_below(he1.first, he2); 711 if(oab1 == 0 && between(he1.first, he2.first, he2.second)) return true; 712 int oab2 = on_above_or_below(he1.second, he2); 713 if(oab2 == 0 && between(he1.second, he2.first, he2.second)) return true; 714 if(oab1 == oab2 && oab1 != 0) return false; //both points of he1 are on same side of he2 715 int oab3 = on_above_or_below(he2.first, he1); 716 if(oab3 == 0 && between(he2.first, he1.first, he1.second)) return true; 717 int oab4 = on_above_or_below(he2.second, he1); 718 if(oab4 == 0 && between(he2.second, he1.first, he1.second)) return true; 719 if(oab3 == oab4) return false; //both points of he2 are on same side of he1 720 return true; //they must cross 721 } 722 if(is_vertical(he1) && is_vertical(he2) && he1.first.get(HORIZONTAL) == he2.first.get(HORIZONTAL)) 723 return ::boost::polygon::intersects(rect1.get(VERTICAL), rect2.get(VERTICAL), false) && 724 rect1.get(VERTICAL) != rect2.get(VERTICAL); 725 if(is_horizontal(he1) && is_horizontal(he2) && he1.first.get(VERTICAL) == he2.first.get(VERTICAL)) 726 return ::boost::polygon::intersects(rect1.get(HORIZONTAL), rect2.get(HORIZONTAL), false) && 727 rect1.get(HORIZONTAL) != rect2.get(HORIZONTAL); 728 return false; 729 } 730 731 class vertex_half_edge { 732 public: 733 typedef typename high_precision_type<Unit>::type high_precision; 734 Point pt; 735 Point other_pt; // 1, 0 or -1 736 int count; //dxdydTheta vertex_half_edge()737 inline vertex_half_edge() : pt(), other_pt(), count() {} vertex_half_edge(const Point & point,const Point & other_point,int countIn)738 inline vertex_half_edge(const Point& point, const Point& other_point, int countIn) : pt(point), other_pt(other_point), count(countIn) {} vertex_half_edge(const vertex_half_edge & vertex)739 inline vertex_half_edge(const vertex_half_edge& vertex) : pt(vertex.pt), other_pt(vertex.other_pt), count(vertex.count) {} operator =(const vertex_half_edge & vertex)740 inline vertex_half_edge& operator=(const vertex_half_edge& vertex){ 741 pt = vertex.pt; other_pt = vertex.other_pt; count = vertex.count; return *this; } vertex_half_edge(const std::pair<Point,Point> & vertex)742 inline vertex_half_edge(const std::pair<Point, Point>& vertex) : pt(), other_pt(), count() {} operator =(const std::pair<Point,Point> & vertex)743 inline vertex_half_edge& operator=(const std::pair<Point, Point>& vertex){ return *this; } operator ==(const vertex_half_edge & vertex) const744 inline bool operator==(const vertex_half_edge& vertex) const { 745 return pt == vertex.pt && other_pt == vertex.other_pt && count == vertex.count; } operator !=(const vertex_half_edge & vertex) const746 inline bool operator!=(const vertex_half_edge& vertex) const { return !((*this) == vertex); } operator ==(const std::pair<Point,Point> & vertex) const747 inline bool operator==(const std::pair<Point, Point>& vertex) const { return false; } operator !=(const std::pair<Point,Point> & vertex) const748 inline bool operator!=(const std::pair<Point, Point>& vertex) const { return !((*this) == vertex); } operator <(const vertex_half_edge & vertex) const749 inline bool operator<(const vertex_half_edge& vertex) const { 750 if(pt.get(HORIZONTAL) < vertex.pt.get(HORIZONTAL)) return true; 751 if(pt.get(HORIZONTAL) == vertex.pt.get(HORIZONTAL)) { 752 if(pt.get(VERTICAL) < vertex.pt.get(VERTICAL)) return true; 753 if(pt.get(VERTICAL) == vertex.pt.get(VERTICAL)) { return less_slope(pt.get(HORIZONTAL), pt.get(VERTICAL), 754 other_pt, vertex.other_pt); 755 } 756 } 757 return false; 758 } operator >(const vertex_half_edge & vertex) const759 inline bool operator>(const vertex_half_edge& vertex) const { return vertex < (*this); } operator <=(const vertex_half_edge & vertex) const760 inline bool operator<=(const vertex_half_edge& vertex) const { return !((*this) > vertex); } operator >=(const vertex_half_edge & vertex) const761 inline bool operator>=(const vertex_half_edge& vertex) const { return !((*this) < vertex); } evalAtX(Unit xIn) const762 inline high_precision evalAtX(Unit xIn) const { return evalAtXforYlazy(xIn, pt, other_pt); } is_vertical() const763 inline bool is_vertical() const { 764 return pt.get(HORIZONTAL) == other_pt.get(HORIZONTAL); 765 } is_begin() const766 inline bool is_begin() const { 767 return pt.get(HORIZONTAL) < other_pt.get(HORIZONTAL) || 768 (pt.get(HORIZONTAL) == other_pt.get(HORIZONTAL) && 769 (pt.get(VERTICAL) < other_pt.get(VERTICAL))); 770 } 771 }; 772 773 //when scanning Vertex45 for polygon formation we need a scanline comparator functor 774 class less_vertex_half_edge : public std::binary_function<vertex_half_edge, vertex_half_edge, bool> { 775 private: 776 Unit *x_; //x value at which to apply comparison 777 int *justBefore_; 778 public: less_vertex_half_edge()779 inline less_vertex_half_edge() : x_(0), justBefore_(0) {} less_vertex_half_edge(Unit * x,int * justBefore)780 inline less_vertex_half_edge(Unit *x, int *justBefore) : x_(x), justBefore_(justBefore) {} less_vertex_half_edge(const less_vertex_half_edge & that)781 inline less_vertex_half_edge(const less_vertex_half_edge& that) : x_(that.x_), justBefore_(that.justBefore_) {} operator =(const less_vertex_half_edge & that)782 inline less_vertex_half_edge& operator=(const less_vertex_half_edge& that) { x_ = that.x_; justBefore_ = that.justBefore_; return *this; } operator ()(const vertex_half_edge & elm1,const vertex_half_edge & elm2) const783 inline bool operator () (const vertex_half_edge& elm1, const vertex_half_edge& elm2) const { 784 if((std::max)(elm1.pt.y(), elm1.other_pt.y()) < (std::min)(elm2.pt.y(), elm2.other_pt.y())) 785 return true; 786 if((std::min)(elm1.pt.y(), elm1.other_pt.y()) > (std::max)(elm2.pt.y(), elm2.other_pt.y())) 787 return false; 788 //check if either x of elem1 is equal to x_ 789 Unit localx = *x_; 790 Unit elm1y = 0; 791 bool elm1_at_x = false; 792 if(localx == elm1.pt.get(HORIZONTAL)) { 793 elm1_at_x = true; 794 elm1y = elm1.pt.get(VERTICAL); 795 } else if(localx == elm1.other_pt.get(HORIZONTAL)) { 796 elm1_at_x = true; 797 elm1y = elm1.other_pt.get(VERTICAL); 798 } 799 Unit elm2y = 0; 800 bool elm2_at_x = false; 801 if(localx == elm2.pt.get(HORIZONTAL)) { 802 elm2_at_x = true; 803 elm2y = elm2.pt.get(VERTICAL); 804 } else if(localx == elm2.other_pt.get(HORIZONTAL)) { 805 elm2_at_x = true; 806 elm2y = elm2.other_pt.get(VERTICAL); 807 } 808 bool retval = false; 809 if(!(elm1_at_x && elm2_at_x)) { 810 //at least one of the segments doesn't have an end point a the current x 811 //-1 below, 1 above 812 int pt1_oab = on_above_or_below(elm1.pt, half_edge(elm2.pt, elm2.other_pt)); 813 int pt2_oab = on_above_or_below(elm1.other_pt, half_edge(elm2.pt, elm2.other_pt)); 814 if(pt1_oab == pt2_oab) { 815 if(pt1_oab == -1) 816 retval = true; //pt1 is below elm2 so elm1 is below elm2 817 } else { 818 //the segments can't cross so elm2 is on whatever side of elm1 that one of its ends is 819 int pt3_oab = on_above_or_below(elm2.pt, half_edge(elm1.pt, elm1.other_pt)); 820 if(pt3_oab == 1) 821 retval = true; //elm1's point is above elm1 822 } 823 } else { 824 if(elm1y < elm2y) { 825 retval = true; 826 } else if(elm1y == elm2y) { 827 if(elm1.pt == elm2.pt && elm1.other_pt == elm2.other_pt) 828 return false; 829 retval = less_slope(elm1.other_pt.get(HORIZONTAL) - elm1.pt.get(HORIZONTAL), 830 elm1.other_pt.get(VERTICAL) - elm1.pt.get(VERTICAL), 831 elm2.other_pt.get(HORIZONTAL) - elm2.pt.get(HORIZONTAL), 832 elm2.other_pt.get(VERTICAL) - elm2.pt.get(VERTICAL)); 833 retval = ((*justBefore_) != 0) ^ retval; 834 } 835 } 836 return retval; 837 } 838 }; 839 840 }; 841 842 template <typename Unit> 843 class polygon_arbitrary_formation : public scanline_base<Unit> { 844 public: 845 typedef typename scanline_base<Unit>::Point Point; 846 typedef typename scanline_base<Unit>::half_edge half_edge; 847 typedef typename scanline_base<Unit>::vertex_half_edge vertex_half_edge; 848 typedef typename scanline_base<Unit>::less_vertex_half_edge less_vertex_half_edge; 849 850 class poly_line_arbitrary { 851 public: 852 typedef typename std::list<Point>::const_iterator iterator; 853 854 // default constructor of point does not initialize x and y poly_line_arbitrary()855 inline poly_line_arbitrary() : points() {} //do nothing default constructor 856 857 // initialize a polygon from x,y values, it is assumed that the first is an x 858 // and that the input is a well behaved polygon 859 template<class iT> set(iT inputBegin,iT inputEnd)860 inline poly_line_arbitrary& set(iT inputBegin, iT inputEnd) { 861 points.clear(); //just in case there was some old data there 862 while(inputBegin != inputEnd) { 863 points.insert(points.end(), *inputBegin); 864 ++inputBegin; 865 } 866 return *this; 867 } 868 869 // copy constructor (since we have dynamic memory) poly_line_arbitrary(const poly_line_arbitrary & that)870 inline poly_line_arbitrary(const poly_line_arbitrary& that) : points(that.points) {} 871 872 // assignment operator (since we have dynamic memory do a deep copy) operator =(const poly_line_arbitrary & that)873 inline poly_line_arbitrary& operator=(const poly_line_arbitrary& that) { 874 points = that.points; 875 return *this; 876 } 877 878 // get begin iterator, returns a pointer to a const Unit begin() const879 inline iterator begin() const { return points.begin(); } 880 881 // get end iterator, returns a pointer to a const Unit end() const882 inline iterator end() const { return points.end(); } 883 size() const884 inline std::size_t size() const { return points.size(); } 885 886 //public data member 887 std::list<Point> points; 888 }; 889 890 class active_tail_arbitrary { 891 protected: 892 //data 893 poly_line_arbitrary* tailp_; 894 active_tail_arbitrary *otherTailp_; 895 std::list<active_tail_arbitrary*> holesList_; 896 bool head_; 897 public: 898 899 /** 900 * @brief iterator over coordinates of the figure 901 */ 902 typedef typename poly_line_arbitrary::iterator iterator; 903 904 /** 905 * @brief iterator over holes contained within the figure 906 */ 907 typedef typename std::list<active_tail_arbitrary*>::const_iterator iteratorHoles; 908 909 //default constructor active_tail_arbitrary()910 inline active_tail_arbitrary() : tailp_(), otherTailp_(), holesList_(), head_() {} 911 912 //constructor active_tail_arbitrary(const vertex_half_edge & vertex,active_tail_arbitrary * otherTailp=0)913 inline active_tail_arbitrary(const vertex_half_edge& vertex, active_tail_arbitrary* otherTailp = 0) : tailp_(), otherTailp_(), holesList_(), head_() { 914 tailp_ = new poly_line_arbitrary; 915 tailp_->points.push_back(vertex.pt); 916 //bool headArray[4] = {false, true, true, true}; 917 bool inverted = vertex.count == -1; 918 head_ = (!vertex.is_vertical) ^ inverted; 919 otherTailp_ = otherTailp; 920 } 921 active_tail_arbitrary(Point point,active_tail_arbitrary * otherTailp,bool head=true)922 inline active_tail_arbitrary(Point point, active_tail_arbitrary* otherTailp, bool head = true) : 923 tailp_(), otherTailp_(), holesList_(), head_() { 924 tailp_ = new poly_line_arbitrary; 925 tailp_->points.push_back(point); 926 head_ = head; 927 otherTailp_ = otherTailp; 928 929 } active_tail_arbitrary(active_tail_arbitrary * otherTailp)930 inline active_tail_arbitrary(active_tail_arbitrary* otherTailp) : 931 tailp_(), otherTailp_(), holesList_(), head_() { 932 tailp_ = otherTailp->tailp_; 933 otherTailp_ = otherTailp; 934 } 935 936 //copy constructor active_tail_arbitrary(const active_tail_arbitrary & that)937 inline active_tail_arbitrary(const active_tail_arbitrary& that) : 938 tailp_(), otherTailp_(), holesList_(), head_() { (*this) = that; } 939 940 //destructor ~active_tail_arbitrary()941 inline ~active_tail_arbitrary() { 942 destroyContents(); 943 } 944 945 //assignment operator operator =(const active_tail_arbitrary & that)946 inline active_tail_arbitrary& operator=(const active_tail_arbitrary& that) { 947 tailp_ = new poly_line_arbitrary(*(that.tailp_)); 948 head_ = that.head_; 949 otherTailp_ = that.otherTailp_; 950 holesList_ = that.holesList_; 951 return *this; 952 } 953 954 //equivalence operator operator ==(const active_tail_arbitrary & b) const955 inline bool operator==(const active_tail_arbitrary& b) const { 956 return tailp_ == b.tailp_ && head_ == b.head_; 957 } 958 959 /** 960 * @brief get the pointer to the polyline that this is an active tail of 961 */ getTail() const962 inline poly_line_arbitrary* getTail() const { return tailp_; } 963 964 /** 965 * @brief get the pointer to the polyline at the other end of the chain 966 */ getOtherTail() const967 inline poly_line_arbitrary* getOtherTail() const { return otherTailp_->tailp_; } 968 969 /** 970 * @brief get the pointer to the activetail at the other end of the chain 971 */ getOtherActiveTail() const972 inline active_tail_arbitrary* getOtherActiveTail() const { return otherTailp_; } 973 974 /** 975 * @brief test if another active tail is the other end of the chain 976 */ isOtherTail(const active_tail_arbitrary & b) const977 inline bool isOtherTail(const active_tail_arbitrary& b) const { return &b == otherTailp_; } 978 979 /** 980 * @brief update this end of chain pointer to new polyline 981 */ updateTail(poly_line_arbitrary * newTail)982 inline active_tail_arbitrary& updateTail(poly_line_arbitrary* newTail) { tailp_ = newTail; return *this; } 983 join(active_tail_arbitrary * tail)984 inline bool join(active_tail_arbitrary* tail) { 985 if(tail == otherTailp_) { 986 //std::cout << "joining to other tail!\n"; 987 return false; 988 } 989 if(tail->head_ == head_) { 990 //std::cout << "joining head to head!\n"; 991 return false; 992 } 993 if(!tailp_) { 994 //std::cout << "joining empty tail!\n"; 995 return false; 996 } 997 if(!(otherTailp_->head_)) { 998 otherTailp_->copyHoles(*tail); 999 otherTailp_->copyHoles(*this); 1000 } else { 1001 tail->otherTailp_->copyHoles(*this); 1002 tail->otherTailp_->copyHoles(*tail); 1003 } 1004 poly_line_arbitrary* tail1 = tailp_; 1005 poly_line_arbitrary* tail2 = tail->tailp_; 1006 if(head_) std::swap(tail1, tail2); 1007 typename std::list<point_data<Unit> >::reverse_iterator riter = tail1->points.rbegin(); 1008 typename std::list<point_data<Unit> >::iterator iter = tail2->points.begin(); 1009 if(*riter == *iter) { 1010 tail1->points.pop_back(); //remove duplicate point 1011 } 1012 tail1->points.splice(tail1->points.end(), tail2->points); 1013 delete tail2; 1014 otherTailp_->tailp_ = tail1; 1015 tail->otherTailp_->tailp_ = tail1; 1016 otherTailp_->otherTailp_ = tail->otherTailp_; 1017 tail->otherTailp_->otherTailp_ = otherTailp_; 1018 tailp_ = 0; 1019 tail->tailp_ = 0; 1020 tail->otherTailp_ = 0; 1021 otherTailp_ = 0; 1022 return true; 1023 } 1024 1025 /** 1026 * @brief associate a hole to this active tail by the specified policy 1027 */ addHole(active_tail_arbitrary * hole)1028 inline active_tail_arbitrary* addHole(active_tail_arbitrary* hole) { 1029 holesList_.push_back(hole); 1030 copyHoles(*hole); 1031 copyHoles(*(hole->otherTailp_)); 1032 return this; 1033 } 1034 1035 /** 1036 * @brief get the list of holes 1037 */ getHoles() const1038 inline const std::list<active_tail_arbitrary*>& getHoles() const { return holesList_; } 1039 1040 /** 1041 * @brief copy holes from that to this 1042 */ copyHoles(active_tail_arbitrary & that)1043 inline void copyHoles(active_tail_arbitrary& that) { holesList_.splice(holesList_.end(), that.holesList_); } 1044 1045 /** 1046 * @brief find out if solid to right 1047 */ solidToRight() const1048 inline bool solidToRight() const { return !head_; } solidToLeft() const1049 inline bool solidToLeft() const { return head_; } 1050 1051 /** 1052 * @brief get vertex 1053 */ getPoint() const1054 inline Point getPoint() const { 1055 if(head_) return tailp_->points.front(); 1056 return tailp_->points.back(); 1057 } 1058 1059 /** 1060 * @brief add a coordinate to the polygon at this active tail end, properly handle degenerate edges by removing redundant coordinate 1061 */ pushPoint(Point point)1062 inline void pushPoint(Point point) { 1063 if(head_) { 1064 //if(tailp_->points.size() < 2) { 1065 // tailp_->points.push_front(point); 1066 // return; 1067 //} 1068 typename std::list<Point>::iterator iter = tailp_->points.begin(); 1069 if(iter == tailp_->points.end()) { 1070 tailp_->points.push_front(point); 1071 return; 1072 } 1073 ++iter; 1074 if(iter == tailp_->points.end()) { 1075 tailp_->points.push_front(point); 1076 return; 1077 } 1078 --iter; 1079 if(*iter != point) { 1080 tailp_->points.push_front(point); 1081 } 1082 return; 1083 } 1084 //if(tailp_->points.size() < 2) { 1085 // tailp_->points.push_back(point); 1086 // return; 1087 //} 1088 typename std::list<Point>::reverse_iterator iter = tailp_->points.rbegin(); 1089 if(iter == tailp_->points.rend()) { 1090 tailp_->points.push_back(point); 1091 return; 1092 } 1093 ++iter; 1094 if(iter == tailp_->points.rend()) { 1095 tailp_->points.push_back(point); 1096 return; 1097 } 1098 --iter; 1099 if(*iter != point) { 1100 tailp_->points.push_back(point); 1101 } 1102 } 1103 1104 /** 1105 * @brief joins the two chains that the two active tail tails are ends of 1106 * checks for closure of figure and writes out polygons appropriately 1107 * returns a handle to a hole if one is closed 1108 */ 1109 template <class cT> joinChains(Point point,active_tail_arbitrary * at1,active_tail_arbitrary * at2,bool solid,cT & output)1110 static inline active_tail_arbitrary* joinChains(Point point, active_tail_arbitrary* at1, active_tail_arbitrary* at2, bool solid, 1111 cT& output) { 1112 if(at1->otherTailp_ == at2) { 1113 //if(at2->otherTailp_ != at1) std::cout << "half closed error\n"; 1114 //we are closing a figure 1115 at1->pushPoint(point); 1116 at2->pushPoint(point); 1117 if(solid) { 1118 //we are closing a solid figure, write to output 1119 //std::cout << "test1\n"; 1120 at1->copyHoles(*(at1->otherTailp_)); 1121 typename PolyLineArbitraryByConcept<Unit, typename geometry_concept<typename cT::value_type>::type>::type polyData(at1); 1122 //poly_line_arbitrary_polygon_data polyData(at1); 1123 //std::cout << "test2\n"; 1124 //std::cout << poly << "\n"; 1125 //std::cout << "test3\n"; 1126 typedef typename cT::value_type result_type; 1127 output.push_back(result_type()); 1128 assign(output.back(), polyData); 1129 //std::cout << "test4\n"; 1130 //std::cout << "delete " << at1->otherTailp_ << "\n"; 1131 //at1->print(); 1132 //at1->otherTailp_->print(); 1133 delete at1->otherTailp_; 1134 //at1->print(); 1135 //at1->otherTailp_->print(); 1136 //std::cout << "test5\n"; 1137 //std::cout << "delete " << at1 << "\n"; 1138 delete at1; 1139 //std::cout << "test6\n"; 1140 return 0; 1141 } else { 1142 //we are closing a hole, return the tail end active tail of the figure 1143 return at1; 1144 } 1145 } 1146 //we are not closing a figure 1147 at1->pushPoint(point); 1148 at1->join(at2); 1149 delete at1; 1150 delete at2; 1151 return 0; 1152 } 1153 destroyContents()1154 inline void destroyContents() { 1155 if(otherTailp_) { 1156 //std::cout << "delete p " << tailp_ << "\n"; 1157 if(tailp_) delete tailp_; 1158 tailp_ = 0; 1159 otherTailp_->otherTailp_ = 0; 1160 otherTailp_->tailp_ = 0; 1161 otherTailp_ = 0; 1162 } 1163 for(typename std::list<active_tail_arbitrary*>::iterator itr = holesList_.begin(); itr != holesList_.end(); ++itr) { 1164 //std::cout << "delete p " << (*itr) << "\n"; 1165 if(*itr) { 1166 if((*itr)->otherTailp_) { 1167 delete (*itr)->otherTailp_; 1168 (*itr)->otherTailp_ = 0; 1169 } 1170 delete (*itr); 1171 } 1172 (*itr) = 0; 1173 } 1174 holesList_.clear(); 1175 } 1176 print()1177 inline void print() { 1178 //std::cout << this << " " << tailp_ << " " << otherTailp_ << " " << holesList_.size() << " " << head_ << "\n"; 1179 } 1180 createActiveTailsAsPair(Point point,bool solid,active_tail_arbitrary * phole,bool fractureHoles)1181 static inline std::pair<active_tail_arbitrary*, active_tail_arbitrary*> createActiveTailsAsPair(Point point, bool solid, 1182 active_tail_arbitrary* phole, bool fractureHoles) { 1183 active_tail_arbitrary* at1 = 0; 1184 active_tail_arbitrary* at2 = 0; 1185 if(phole && fractureHoles) { 1186 //std::cout << "adding hole\n"; 1187 at1 = phole; 1188 //assert solid == false, we should be creating a corner with solid below and to the left if there was a hole 1189 at2 = at1->getOtherActiveTail(); 1190 at2->pushPoint(point); 1191 at1->pushPoint(point); 1192 } else { 1193 at1 = new active_tail_arbitrary(point, at2, solid); 1194 at2 = new active_tail_arbitrary(at1); 1195 at1->otherTailp_ = at2; 1196 at2->head_ = !solid; 1197 if(phole) 1198 at2->addHole(phole); //assert fractureHoles == false 1199 } 1200 return std::pair<active_tail_arbitrary*, active_tail_arbitrary*>(at1, at2); 1201 } 1202 1203 }; 1204 1205 1206 typedef std::vector<std::pair<Point, int> > vertex_arbitrary_count; 1207 1208 class less_half_edge_count : public std::binary_function<vertex_half_edge, vertex_half_edge, bool> { 1209 private: 1210 Point pt_; 1211 public: less_half_edge_count()1212 inline less_half_edge_count() : pt_() {} less_half_edge_count(Point point)1213 inline less_half_edge_count(Point point) : pt_(point) {} operator ()(const std::pair<Point,int> & elm1,const std::pair<Point,int> & elm2) const1214 inline bool operator () (const std::pair<Point, int>& elm1, const std::pair<Point, int>& elm2) const { 1215 return scanline_base<Unit>::less_slope(pt_.get(HORIZONTAL), pt_.get(VERTICAL), elm1.first, elm2.first); 1216 } 1217 }; 1218 sort_vertex_arbitrary_count(vertex_arbitrary_count & count,const Point & pt)1219 static inline void sort_vertex_arbitrary_count(vertex_arbitrary_count& count, const Point& pt) { 1220 less_half_edge_count lfec(pt); 1221 polygon_sort(count.begin(), count.end(), lfec); 1222 } 1223 1224 typedef std::vector<std::pair<std::pair<std::pair<Point, Point>, int>, active_tail_arbitrary*> > incoming_count; 1225 1226 class less_incoming_count : public std::binary_function<std::pair<std::pair<std::pair<Point, Point>, int>, active_tail_arbitrary*>, 1227 std::pair<std::pair<std::pair<Point, Point>, int>, active_tail_arbitrary*>, bool> { 1228 private: 1229 Point pt_; 1230 public: less_incoming_count()1231 inline less_incoming_count() : pt_() {} less_incoming_count(Point point)1232 inline less_incoming_count(Point point) : pt_(point) {} operator ()(const std::pair<std::pair<std::pair<Point,Point>,int>,active_tail_arbitrary * > & elm1,const std::pair<std::pair<std::pair<Point,Point>,int>,active_tail_arbitrary * > & elm2) const1233 inline bool operator () (const std::pair<std::pair<std::pair<Point, Point>, int>, active_tail_arbitrary*>& elm1, 1234 const std::pair<std::pair<std::pair<Point, Point>, int>, active_tail_arbitrary*>& elm2) const { 1235 Unit dx1 = elm1.first.first.first.get(HORIZONTAL) - elm1.first.first.second.get(HORIZONTAL); 1236 Unit dx2 = elm2.first.first.first.get(HORIZONTAL) - elm2.first.first.second.get(HORIZONTAL); 1237 Unit dy1 = elm1.first.first.first.get(VERTICAL) - elm1.first.first.second.get(VERTICAL); 1238 Unit dy2 = elm2.first.first.first.get(VERTICAL) - elm2.first.first.second.get(VERTICAL); 1239 return scanline_base<Unit>::less_slope(dx1, dy1, dx2, dy2); 1240 } 1241 }; 1242 sort_incoming_count(incoming_count & count,const Point & pt)1243 static inline void sort_incoming_count(incoming_count& count, const Point& pt) { 1244 less_incoming_count lfec(pt); 1245 polygon_sort(count.begin(), count.end(), lfec); 1246 } 1247 compact_vertex_arbitrary_count(const Point & pt,vertex_arbitrary_count & count)1248 static inline void compact_vertex_arbitrary_count(const Point& pt, vertex_arbitrary_count &count) { 1249 if(count.empty()) return; 1250 vertex_arbitrary_count tmp; 1251 tmp.reserve(count.size()); 1252 tmp.push_back(count[0]); 1253 //merge duplicates 1254 for(std::size_t i = 1; i < count.size(); ++i) { 1255 if(!equal_slope(pt.get(HORIZONTAL), pt.get(VERTICAL), tmp[i-1].first, count[i].first)) { 1256 tmp.push_back(count[i]); 1257 } else { 1258 tmp.back().second += count[i].second; 1259 } 1260 } 1261 count.clear(); 1262 count.swap(tmp); 1263 } 1264 1265 // inline std::ostream& operator<< (std::ostream& o, const vertex_arbitrary_count& c) { 1266 // for(unsinged int i = 0; i < c.size(); ++i) { 1267 // o << c[i].first << " " << c[i].second << " "; 1268 // } 1269 // return o; 1270 // } 1271 1272 class vertex_arbitrary_compact { 1273 public: 1274 Point pt; 1275 vertex_arbitrary_count count; vertex_arbitrary_compact()1276 inline vertex_arbitrary_compact() : pt(), count() {} vertex_arbitrary_compact(const Point & point,const Point & other_point,int countIn)1277 inline vertex_arbitrary_compact(const Point& point, const Point& other_point, int countIn) : pt(point), count() { 1278 count.push_back(std::pair<Point, int>(other_point, countIn)); 1279 } vertex_arbitrary_compact(const vertex_half_edge & vertex)1280 inline vertex_arbitrary_compact(const vertex_half_edge& vertex) : pt(vertex.pt), count() { 1281 count.push_back(std::pair<Point, int>(vertex.other_pt, vertex.count)); 1282 } vertex_arbitrary_compact(const vertex_arbitrary_compact & vertex)1283 inline vertex_arbitrary_compact(const vertex_arbitrary_compact& vertex) : pt(vertex.pt), count(vertex.count) {} operator =(const vertex_arbitrary_compact & vertex)1284 inline vertex_arbitrary_compact& operator=(const vertex_arbitrary_compact& vertex){ 1285 pt = vertex.pt; count = vertex.count; return *this; } 1286 //inline vertex_arbitrary_compact(const std::pair<Point, Point>& vertex) {} operator =(const std::pair<Point,Point> & vertex)1287 inline vertex_arbitrary_compact& operator=(const std::pair<Point, Point>& vertex){ return *this; } operator ==(const vertex_arbitrary_compact & vertex) const1288 inline bool operator==(const vertex_arbitrary_compact& vertex) const { 1289 return pt == vertex.pt && count == vertex.count; } operator !=(const vertex_arbitrary_compact & vertex) const1290 inline bool operator!=(const vertex_arbitrary_compact& vertex) const { return !((*this) == vertex); } operator ==(const std::pair<Point,Point> & vertex) const1291 inline bool operator==(const std::pair<Point, Point>& vertex) const { return false; } operator !=(const std::pair<Point,Point> & vertex) const1292 inline bool operator!=(const std::pair<Point, Point>& vertex) const { return !((*this) == vertex); } operator <(const vertex_arbitrary_compact & vertex) const1293 inline bool operator<(const vertex_arbitrary_compact& vertex) const { 1294 if(pt.get(HORIZONTAL) < vertex.pt.get(HORIZONTAL)) return true; 1295 if(pt.get(HORIZONTAL) == vertex.pt.get(HORIZONTAL)) { 1296 return pt.get(VERTICAL) < vertex.pt.get(VERTICAL); 1297 } 1298 return false; 1299 } operator >(const vertex_arbitrary_compact & vertex) const1300 inline bool operator>(const vertex_arbitrary_compact& vertex) const { return vertex < (*this); } operator <=(const vertex_arbitrary_compact & vertex) const1301 inline bool operator<=(const vertex_arbitrary_compact& vertex) const { return !((*this) > vertex); } operator >=(const vertex_arbitrary_compact & vertex) const1302 inline bool operator>=(const vertex_arbitrary_compact& vertex) const { return !((*this) < vertex); } have_vertex_half_edge(int index) const1303 inline bool have_vertex_half_edge(int index) const { return count[index]; } operator [](int index) const1304 inline vertex_half_edge operator[](int index) const { return vertex_half_edge(pt, count[index]); } 1305 }; 1306 1307 // inline std::ostream& operator<< (std::ostream& o, const vertex_arbitrary_compact& c) { 1308 // o << c.pt << ", " << c.count; 1309 // return o; 1310 // } 1311 1312 protected: 1313 //definitions 1314 typedef std::map<vertex_half_edge, active_tail_arbitrary*, less_vertex_half_edge> scanline_data; 1315 typedef typename scanline_data::iterator iterator; 1316 typedef typename scanline_data::const_iterator const_iterator; 1317 1318 //data 1319 scanline_data scanData_; 1320 Unit x_; 1321 int justBefore_; 1322 int fractureHoles_; 1323 public: polygon_arbitrary_formation()1324 inline polygon_arbitrary_formation() : 1325 scanData_(), x_((std::numeric_limits<Unit>::min)()), justBefore_(false), fractureHoles_(0) { 1326 less_vertex_half_edge lessElm(&x_, &justBefore_); 1327 scanData_ = scanline_data(lessElm); 1328 } polygon_arbitrary_formation(bool fractureHoles)1329 inline polygon_arbitrary_formation(bool fractureHoles) : 1330 scanData_(), x_((std::numeric_limits<Unit>::min)()), justBefore_(false), fractureHoles_(fractureHoles) { 1331 less_vertex_half_edge lessElm(&x_, &justBefore_); 1332 scanData_ = scanline_data(lessElm); 1333 } polygon_arbitrary_formation(const polygon_arbitrary_formation & that)1334 inline polygon_arbitrary_formation(const polygon_arbitrary_formation& that) : 1335 scanData_(), x_((std::numeric_limits<Unit>::min)()), justBefore_(false), fractureHoles_(0) { (*this) = that; } operator =(const polygon_arbitrary_formation & that)1336 inline polygon_arbitrary_formation& operator=(const polygon_arbitrary_formation& that) { 1337 x_ = that.x_; 1338 justBefore_ = that.justBefore_; 1339 fractureHoles_ = that.fractureHoles_; 1340 less_vertex_half_edge lessElm(&x_, &justBefore_); 1341 scanData_ = scanline_data(lessElm); 1342 for(const_iterator itr = that.scanData_.begin(); itr != that.scanData_.end(); ++itr){ 1343 scanData_.insert(scanData_.end(), *itr); 1344 } 1345 return *this; 1346 } 1347 1348 //cT is an output container of Polygon45 or Polygon45WithHoles 1349 //iT is an iterator over vertex_half_edge elements 1350 //inputBegin - inputEnd is a range of sorted iT that represents 1351 //one or more scanline stops worth of data 1352 template <class cT, class iT> scan(cT & output,iT inputBegin,iT inputEnd)1353 void scan(cT& output, iT inputBegin, iT inputEnd) { 1354 //std::cout << "1\n"; 1355 while(inputBegin != inputEnd) { 1356 //std::cout << "2\n"; 1357 x_ = (*inputBegin).pt.get(HORIZONTAL); 1358 //std::cout << "SCAN FORMATION " << x_ << "\n"; 1359 //std::cout << "x_ = " << x_ << "\n"; 1360 //std::cout << "scan line size: " << scanData_.size() << "\n"; 1361 inputBegin = processEvent_(output, inputBegin, inputEnd); 1362 } 1363 //std::cout << "scan line size: " << scanData_.size() << "\n"; 1364 } 1365 1366 protected: 1367 //functions 1368 template <class cT, class cT2> processPoint_(cT & output,cT2 & elements,Point point,incoming_count & counts_from_scanline,vertex_arbitrary_count & incoming_count)1369 inline std::pair<std::pair<Point, int>, active_tail_arbitrary*> processPoint_(cT& output, cT2& elements, Point point, 1370 incoming_count& counts_from_scanline, vertex_arbitrary_count& incoming_count) { 1371 //std::cout << "\nAT POINT: " << point << "\n"; 1372 //join any closing solid corners 1373 std::vector<int> counts; 1374 std::vector<int> incoming; 1375 std::vector<active_tail_arbitrary*> tails; 1376 counts.reserve(counts_from_scanline.size()); 1377 tails.reserve(counts_from_scanline.size()); 1378 incoming.reserve(incoming_count.size()); 1379 for(std::size_t i = 0; i < counts_from_scanline.size(); ++i) { 1380 counts.push_back(counts_from_scanline[i].first.second); 1381 tails.push_back(counts_from_scanline[i].second); 1382 } 1383 for(std::size_t i = 0; i < incoming_count.size(); ++i) { 1384 incoming.push_back(incoming_count[i].second); 1385 if(incoming_count[i].first < point) { 1386 incoming.back() = 0; 1387 } 1388 } 1389 1390 active_tail_arbitrary* returnValue = 0; 1391 std::pair<Point, int> returnCount(Point(0, 0), 0); 1392 int i_size_less_1 = (int)(incoming.size()) -1; 1393 int c_size_less_1 = (int)(counts.size()) -1; 1394 int i_size = incoming.size(); 1395 int c_size = counts.size(); 1396 1397 bool have_vertical_tail_from_below = false; 1398 if(c_size && 1399 scanline_base<Unit>::is_vertical(counts_from_scanline.back().first.first)) { 1400 have_vertical_tail_from_below = true; 1401 } 1402 //assert size = size_less_1 + 1 1403 //std::cout << tails.size() << " " << incoming.size() << " " << counts_from_scanline.size() << " " << incoming_count.size() << "\n"; 1404 // for(std::size_t i = 0; i < counts.size(); ++i) { 1405 // std::cout << counts_from_scanline[i].first.first.first.get(HORIZONTAL) << ","; 1406 // std::cout << counts_from_scanline[i].first.first.first.get(VERTICAL) << " "; 1407 // std::cout << counts_from_scanline[i].first.first.second.get(HORIZONTAL) << ","; 1408 // std::cout << counts_from_scanline[i].first.first.second.get(VERTICAL) << ":"; 1409 // std::cout << counts_from_scanline[i].first.second << " "; 1410 // } std::cout << "\n"; 1411 // print(incoming_count); 1412 { 1413 for(int i = 0; i < c_size_less_1; ++i) { 1414 //std::cout << i << "\n"; 1415 if(counts[i] == -1) { 1416 //std::cout << "fixed i\n"; 1417 for(int j = i + 1; j < c_size; ++j) { 1418 //std::cout << j << "\n"; 1419 if(counts[j]) { 1420 if(counts[j] == 1) { 1421 //std::cout << "case1: " << i << " " << j << "\n"; 1422 //if a figure is closed it will be written out by this function to output 1423 active_tail_arbitrary::joinChains(point, tails[i], tails[j], true, output); 1424 counts[i] = 0; 1425 counts[j] = 0; 1426 tails[i] = 0; 1427 tails[j] = 0; 1428 } 1429 break; 1430 } 1431 } 1432 } 1433 } 1434 } 1435 //find any pairs of incoming edges that need to create pair for leading solid 1436 //std::cout << "checking case2\n"; 1437 { 1438 for(int i = 0; i < i_size_less_1; ++i) { 1439 //std::cout << i << "\n"; 1440 if(incoming[i] == 1) { 1441 //std::cout << "fixed i\n"; 1442 for(int j = i + 1; j < i_size; ++j) { 1443 //std::cout << j << "\n"; 1444 if(incoming[j]) { 1445 //std::cout << incoming[j] << "\n"; 1446 if(incoming[j] == -1) { 1447 //std::cout << "case2: " << i << " " << j << "\n"; 1448 //std::cout << "creating active tail pair\n"; 1449 std::pair<active_tail_arbitrary*, active_tail_arbitrary*> tailPair = 1450 active_tail_arbitrary::createActiveTailsAsPair(point, true, 0, fractureHoles_ != 0); 1451 //tailPair.first->print(); 1452 //tailPair.second->print(); 1453 if(j == i_size_less_1 && incoming_count[j].first.get(HORIZONTAL) == point.get(HORIZONTAL)) { 1454 //vertical active tail becomes return value 1455 returnValue = tailPair.first; 1456 returnCount.first = point; 1457 returnCount.second = 1; 1458 } else { 1459 //std::cout << "new element " << j-1 << " " << -1 << "\n"; 1460 //std::cout << point << " " << incoming_count[j].first << "\n"; 1461 elements.push_back(std::pair<vertex_half_edge, 1462 active_tail_arbitrary*>(vertex_half_edge(point, 1463 incoming_count[j].first, -1), tailPair.first)); 1464 } 1465 //std::cout << "new element " << i-1 << " " << 1 << "\n"; 1466 //std::cout << point << " " << incoming_count[i].first << "\n"; 1467 elements.push_back(std::pair<vertex_half_edge, 1468 active_tail_arbitrary*>(vertex_half_edge(point, 1469 incoming_count[i].first, 1), tailPair.second)); 1470 incoming[i] = 0; 1471 incoming[j] = 0; 1472 } 1473 break; 1474 } 1475 } 1476 } 1477 } 1478 } 1479 //find any active tail that needs to pass through to an incoming edge 1480 //we expect to find no more than two pass through 1481 1482 //find pass through with solid on top 1483 { 1484 //std::cout << "checking case 3\n"; 1485 for(int i = 0; i < c_size; ++i) { 1486 //std::cout << i << "\n"; 1487 if(counts[i] != 0) { 1488 if(counts[i] == 1) { 1489 //std::cout << "fixed i\n"; 1490 for(int j = i_size_less_1; j >= 0; --j) { 1491 if(incoming[j] != 0) { 1492 if(incoming[j] == 1) { 1493 //std::cout << "case3: " << i << " " << j << "\n"; 1494 //tails[i]->print(); 1495 //pass through solid on top 1496 tails[i]->pushPoint(point); 1497 //std::cout << "after push\n"; 1498 if(j == i_size_less_1 && incoming_count[j].first.get(HORIZONTAL) == point.get(HORIZONTAL)) { 1499 returnValue = tails[i]; 1500 returnCount.first = point; 1501 returnCount.second = -1; 1502 } else { 1503 elements.push_back(std::pair<vertex_half_edge, 1504 active_tail_arbitrary*>(vertex_half_edge(point, 1505 incoming_count[j].first, incoming[j]), tails[i])); 1506 } 1507 tails[i] = 0; 1508 counts[i] = 0; 1509 incoming[j] = 0; 1510 } 1511 break; 1512 } 1513 } 1514 } 1515 break; 1516 } 1517 } 1518 } 1519 //std::cout << "checking case 4\n"; 1520 //find pass through with solid on bottom 1521 { 1522 for(int i = c_size_less_1; i >= 0; --i) { 1523 //std::cout << "i = " << i << " with count " << counts[i] << "\n"; 1524 if(counts[i] != 0) { 1525 if(counts[i] == -1) { 1526 for(int j = 0; j < i_size; ++j) { 1527 if(incoming[j] != 0) { 1528 if(incoming[j] == -1) { 1529 //std::cout << "case4: " << i << " " << j << "\n"; 1530 //pass through solid on bottom 1531 tails[i]->pushPoint(point); 1532 if(j == i_size_less_1 && incoming_count[j].first.get(HORIZONTAL) == point.get(HORIZONTAL)) { 1533 returnValue = tails[i]; 1534 returnCount.first = point; 1535 returnCount.second = 1; 1536 } else { 1537 //std::cout << "new element " << j-1 << " " << incoming[j] << "\n"; 1538 //std::cout << point << " " << incoming_count[j].first << "\n"; 1539 elements.push_back(std::pair<vertex_half_edge, 1540 active_tail_arbitrary*>(vertex_half_edge(point, 1541 incoming_count[j].first, incoming[j]), tails[i])); 1542 } 1543 tails[i] = 0; 1544 counts[i] = 0; 1545 incoming[j] = 0; 1546 } 1547 break; 1548 } 1549 } 1550 } 1551 break; 1552 } 1553 } 1554 } 1555 //find the end of a hole or the beginning of a hole 1556 1557 //find end of a hole 1558 { 1559 for(int i = 0; i < c_size_less_1; ++i) { 1560 if(counts[i] != 0) { 1561 for(int j = i+1; j < c_size; ++j) { 1562 if(counts[j] != 0) { 1563 //std::cout << "case5: " << i << " " << j << "\n"; 1564 //we are ending a hole and may potentially close a figure and have to handle the hole 1565 returnValue = active_tail_arbitrary::joinChains(point, tails[i], tails[j], false, output); 1566 if(returnValue) returnCount.first = point; 1567 //std::cout << returnValue << "\n"; 1568 tails[i] = 0; 1569 tails[j] = 0; 1570 counts[i] = 0; 1571 counts[j] = 0; 1572 break; 1573 } 1574 } 1575 break; 1576 } 1577 } 1578 } 1579 //find beginning of a hole 1580 { 1581 for(int i = 0; i < i_size_less_1; ++i) { 1582 if(incoming[i] != 0) { 1583 for(int j = i+1; j < i_size; ++j) { 1584 if(incoming[j] != 0) { 1585 //std::cout << "case6: " << i << " " << j << "\n"; 1586 //we are beginning a empty space 1587 active_tail_arbitrary* holep = 0; 1588 //if(c_size && counts[c_size_less_1] == 0 && 1589 // counts_from_scanline[c_size_less_1].first.first.first.get(HORIZONTAL) == point.get(HORIZONTAL)) 1590 if(have_vertical_tail_from_below) { 1591 holep = tails[c_size_less_1]; 1592 tails[c_size_less_1] = 0; 1593 have_vertical_tail_from_below = false; 1594 } 1595 std::pair<active_tail_arbitrary*, active_tail_arbitrary*> tailPair = 1596 active_tail_arbitrary::createActiveTailsAsPair(point, false, holep, fractureHoles_ != 0); 1597 if(j == i_size_less_1 && incoming_count[j].first.get(HORIZONTAL) == point.get(HORIZONTAL)) { 1598 //std::cout << "vertical element " << point << "\n"; 1599 returnValue = tailPair.first; 1600 returnCount.first = point; 1601 //returnCount = incoming_count[j]; 1602 returnCount.second = -1; 1603 } else { 1604 //std::cout << "new element " << j-1 << " " << incoming[j] << "\n"; 1605 //std::cout << point << " " << incoming_count[j].first << "\n"; 1606 elements.push_back(std::pair<vertex_half_edge, 1607 active_tail_arbitrary*>(vertex_half_edge(point, 1608 incoming_count[j].first, incoming[j]), tailPair.first)); 1609 } 1610 //std::cout << "new element " << i-1 << " " << incoming[i] << "\n"; 1611 //std::cout << point << " " << incoming_count[i].first << "\n"; 1612 elements.push_back(std::pair<vertex_half_edge, 1613 active_tail_arbitrary*>(vertex_half_edge(point, 1614 incoming_count[i].first, incoming[i]), tailPair.second)); 1615 incoming[i] = 0; 1616 incoming[j] = 0; 1617 break; 1618 } 1619 } 1620 break; 1621 } 1622 } 1623 } 1624 if(have_vertical_tail_from_below) { 1625 if(tails.back()) { 1626 tails.back()->pushPoint(point); 1627 returnValue = tails.back(); 1628 returnCount.first = point; 1629 returnCount.second = counts.back(); 1630 } 1631 } 1632 //assert that tails, counts and incoming are all null 1633 return std::pair<std::pair<Point, int>, active_tail_arbitrary*>(returnCount, returnValue); 1634 } 1635 print(const vertex_arbitrary_count & count)1636 static inline void print(const vertex_arbitrary_count& count) { 1637 for(unsigned i = 0; i < count.size(); ++i) { 1638 //std::cout << count[i].first.get(HORIZONTAL) << ","; 1639 //std::cout << count[i].first.get(VERTICAL) << ":"; 1640 //std::cout << count[i].second << " "; 1641 } //std::cout << "\n"; 1642 } 1643 print(const scanline_data & data)1644 static inline void print(const scanline_data& data) { 1645 for(typename scanline_data::const_iterator itr = data.begin(); itr != data.end(); ++itr){ 1646 //std::cout << itr->first.pt << ", " << itr->first.other_pt << "; "; 1647 } //std::cout << "\n"; 1648 } 1649 1650 template <class cT, class iT> processEvent_(cT & output,iT inputBegin,iT inputEnd)1651 inline iT processEvent_(cT& output, iT inputBegin, iT inputEnd) { 1652 typedef typename high_precision_type<Unit>::type high_precision; 1653 //std::cout << "processEvent_\n"; 1654 justBefore_ = true; 1655 //collect up all elements from the tree that are at the y 1656 //values of events in the input queue 1657 //create vector of new elements to add into tree 1658 active_tail_arbitrary* verticalTail = 0; 1659 std::pair<Point, int> verticalCount(Point(0, 0), 0); 1660 iT currentIter = inputBegin; 1661 std::vector<iterator> elementIters; 1662 std::vector<std::pair<vertex_half_edge, active_tail_arbitrary*> > elements; 1663 while(currentIter != inputEnd && currentIter->pt.get(HORIZONTAL) == x_) { 1664 //std::cout << "loop\n"; 1665 Unit currentY = (*currentIter).pt.get(VERTICAL); 1666 //std::cout << "current Y " << currentY << "\n"; 1667 //std::cout << "scanline size " << scanData_.size() << "\n"; 1668 //print(scanData_); 1669 iterator iter = lookUp_(currentY); 1670 //std::cout << "found element in scanline " << (iter != scanData_.end()) << "\n"; 1671 //int counts[4] = {0, 0, 0, 0}; 1672 incoming_count counts_from_scanline; 1673 //std::cout << "finding elements in tree\n"; 1674 //if(iter != scanData_.end()) 1675 // std::cout << "first iter y is " << iter->first.evalAtX(x_) << "\n"; 1676 while(iter != scanData_.end() && 1677 ((iter->first.pt.x() == x_ && iter->first.pt.y() == currentY) || 1678 (iter->first.other_pt.x() == x_ && iter->first.other_pt.y() == currentY))) { 1679 //iter->first.evalAtX(x_) == (high_precision)currentY) { 1680 //std::cout << "loop2\n"; 1681 elementIters.push_back(iter); 1682 counts_from_scanline.push_back(std::pair<std::pair<std::pair<Point, Point>, int>, active_tail_arbitrary*> 1683 (std::pair<std::pair<Point, Point>, int>(std::pair<Point, Point>(iter->first.pt, 1684 iter->first.other_pt), 1685 iter->first.count), 1686 iter->second)); 1687 ++iter; 1688 } 1689 Point currentPoint(x_, currentY); 1690 //std::cout << "counts_from_scanline size " << counts_from_scanline.size() << "\n"; 1691 sort_incoming_count(counts_from_scanline, currentPoint); 1692 1693 vertex_arbitrary_count incoming; 1694 //std::cout << "aggregating\n"; 1695 do { 1696 //std::cout << "loop3\n"; 1697 const vertex_half_edge& elem = *currentIter; 1698 incoming.push_back(std::pair<Point, int>(elem.other_pt, elem.count)); 1699 ++currentIter; 1700 } while(currentIter != inputEnd && currentIter->pt.get(VERTICAL) == currentY && 1701 currentIter->pt.get(HORIZONTAL) == x_); 1702 //print(incoming); 1703 sort_vertex_arbitrary_count(incoming, currentPoint); 1704 //std::cout << currentPoint.get(HORIZONTAL) << "," << currentPoint.get(VERTICAL) << "\n"; 1705 //print(incoming); 1706 //std::cout << "incoming counts from input size " << incoming.size() << "\n"; 1707 //compact_vertex_arbitrary_count(currentPoint, incoming); 1708 vertex_arbitrary_count tmp; 1709 tmp.reserve(incoming.size()); 1710 for(std::size_t i = 0; i < incoming.size(); ++i) { 1711 if(currentPoint < incoming[i].first) { 1712 tmp.push_back(incoming[i]); 1713 } 1714 } 1715 incoming.swap(tmp); 1716 //std::cout << "incoming counts from input size " << incoming.size() << "\n"; 1717 //now counts_from_scanline has the data from the left and 1718 //incoming has the data from the right at this point 1719 //cancel out any end points 1720 if(verticalTail) { 1721 //std::cout << "adding vertical tail to counts from scanline\n"; 1722 //std::cout << -verticalCount.second << "\n"; 1723 counts_from_scanline.push_back(std::pair<std::pair<std::pair<Point, Point>, int>, active_tail_arbitrary*> 1724 (std::pair<std::pair<Point, Point>, int>(std::pair<Point, Point>(verticalCount.first, 1725 currentPoint), 1726 -verticalCount.second), 1727 verticalTail)); 1728 } 1729 if(!incoming.empty() && incoming.back().first.get(HORIZONTAL) == x_) { 1730 //std::cout << "inverted vertical event\n"; 1731 incoming.back().second *= -1; 1732 } 1733 //std::cout << "calling processPoint_\n"; 1734 std::pair<std::pair<Point, int>, active_tail_arbitrary*> result = processPoint_(output, elements, Point(x_, currentY), counts_from_scanline, incoming); 1735 verticalCount = result.first; 1736 verticalTail = result.second; 1737 //if(verticalTail) { 1738 // std::cout << "have vertical tail\n"; 1739 // std::cout << verticalCount.second << "\n"; 1740 //} 1741 if(verticalTail && !(verticalCount.second)) { 1742 //we got a hole out of the point we just processed 1743 //iter is still at the next y element above the current y value in the tree 1744 //std::cout << "checking whether ot handle hole\n"; 1745 if(currentIter == inputEnd || 1746 currentIter->pt.get(HORIZONTAL) != x_ || 1747 scanline_base<Unit>::on_above_or_below(currentIter->pt, half_edge(iter->first.pt, iter->first.other_pt)) != -1) { 1748 //(high_precision)(currentIter->pt.get(VERTICAL)) >= iter->first.evalAtX(x_)) { 1749 1750 //std::cout << "handle hole here\n"; 1751 if(fractureHoles_) { 1752 //std::cout << "fracture hole here\n"; 1753 //we need to handle the hole now and not at the next input vertex 1754 active_tail_arbitrary* at = iter->second; 1755 high_precision precise_y = iter->first.evalAtX(x_); 1756 Unit fracture_y = convert_high_precision_type<Unit>(precise_y); 1757 if(precise_y < fracture_y) --fracture_y; 1758 Point point(x_, fracture_y); 1759 verticalTail->getOtherActiveTail()->pushPoint(point); 1760 iter->second = verticalTail->getOtherActiveTail(); 1761 at->pushPoint(point); 1762 verticalTail->join(at); 1763 delete at; 1764 delete verticalTail; 1765 verticalTail = 0; 1766 } else { 1767 //std::cout << "push hole onto list\n"; 1768 iter->second->addHole(verticalTail); 1769 verticalTail = 0; 1770 } 1771 } 1772 } 1773 } 1774 //std::cout << "erasing\n"; 1775 //erase all elements from the tree 1776 for(typename std::vector<iterator>::iterator iter = elementIters.begin(); 1777 iter != elementIters.end(); ++iter) { 1778 //std::cout << "erasing loop\n"; 1779 scanData_.erase(*iter); 1780 } 1781 //switch comparison tie breaking policy 1782 justBefore_ = false; 1783 //add new elements into tree 1784 //std::cout << "inserting\n"; 1785 for(typename std::vector<std::pair<vertex_half_edge, active_tail_arbitrary*> >::iterator iter = elements.begin(); 1786 iter != elements.end(); ++iter) { 1787 //std::cout << "inserting loop\n"; 1788 scanData_.insert(scanData_.end(), *iter); 1789 } 1790 //std::cout << "end processEvent\n"; 1791 return currentIter; 1792 } 1793 lookUp_(Unit y)1794 inline iterator lookUp_(Unit y){ 1795 //if just before then we need to look from 1 not -1 1796 //std::cout << "just before " << justBefore_ << "\n"; 1797 return scanData_.lower_bound(vertex_half_edge(Point(x_, y), Point(x_, y+1), 0)); 1798 } 1799 1800 public: //test functions 1801 1802 template <typename stream_type> testPolygonArbitraryFormationRect(stream_type & stdcout)1803 static inline bool testPolygonArbitraryFormationRect(stream_type& stdcout) { 1804 stdcout << "testing polygon formation\n"; 1805 polygon_arbitrary_formation pf(true); 1806 std::vector<polygon_data<Unit> > polys; 1807 std::vector<vertex_half_edge> data; 1808 data.push_back(vertex_half_edge(Point(0, 0), Point(10, 0), 1)); 1809 data.push_back(vertex_half_edge(Point(0, 0), Point(0, 10), 1)); 1810 data.push_back(vertex_half_edge(Point(0, 10), Point(0, 0), -1)); 1811 data.push_back(vertex_half_edge(Point(0, 10), Point(10, 10), -1)); 1812 data.push_back(vertex_half_edge(Point(10, 0), Point(0, 0), -1)); 1813 data.push_back(vertex_half_edge(Point(10, 0), Point(10, 10), -1)); 1814 data.push_back(vertex_half_edge(Point(10, 10), Point(10, 0), 1)); 1815 data.push_back(vertex_half_edge(Point(10, 10), Point(0, 10), 1)); 1816 polygon_sort(data.begin(), data.end()); 1817 pf.scan(polys, data.begin(), data.end()); 1818 stdcout << "result size: " << polys.size() << "\n"; 1819 for(std::size_t i = 0; i < polys.size(); ++i) { 1820 stdcout << polys[i] << "\n"; 1821 } 1822 stdcout << "done testing polygon formation\n"; 1823 return true; 1824 } 1825 1826 template <typename stream_type> testPolygonArbitraryFormationP1(stream_type & stdcout)1827 static inline bool testPolygonArbitraryFormationP1(stream_type& stdcout) { 1828 stdcout << "testing polygon formation P1\n"; 1829 polygon_arbitrary_formation pf(true); 1830 std::vector<polygon_data<Unit> > polys; 1831 std::vector<vertex_half_edge> data; 1832 data.push_back(vertex_half_edge(Point(0, 0), Point(10, 10), 1)); 1833 data.push_back(vertex_half_edge(Point(0, 0), Point(0, 10), 1)); 1834 data.push_back(vertex_half_edge(Point(0, 10), Point(0, 0), -1)); 1835 data.push_back(vertex_half_edge(Point(0, 10), Point(10, 20), -1)); 1836 data.push_back(vertex_half_edge(Point(10, 10), Point(0, 0), -1)); 1837 data.push_back(vertex_half_edge(Point(10, 10), Point(10, 20), -1)); 1838 data.push_back(vertex_half_edge(Point(10, 20), Point(10, 10), 1)); 1839 data.push_back(vertex_half_edge(Point(10, 20), Point(0, 10), 1)); 1840 polygon_sort(data.begin(), data.end()); 1841 pf.scan(polys, data.begin(), data.end()); 1842 stdcout << "result size: " << polys.size() << "\n"; 1843 for(std::size_t i = 0; i < polys.size(); ++i) { 1844 stdcout << polys[i] << "\n"; 1845 } 1846 stdcout << "done testing polygon formation\n"; 1847 return true; 1848 } 1849 1850 template <typename stream_type> testPolygonArbitraryFormationP2(stream_type & stdcout)1851 static inline bool testPolygonArbitraryFormationP2(stream_type& stdcout) { 1852 stdcout << "testing polygon formation P2\n"; 1853 polygon_arbitrary_formation pf(true); 1854 std::vector<polygon_data<Unit> > polys; 1855 std::vector<vertex_half_edge> data; 1856 data.push_back(vertex_half_edge(Point(-3, 1), Point(2, -4), 1)); 1857 data.push_back(vertex_half_edge(Point(-3, 1), Point(-2, 2), -1)); 1858 data.push_back(vertex_half_edge(Point(-2, 2), Point(2, 4), -1)); 1859 data.push_back(vertex_half_edge(Point(-2, 2), Point(-3, 1), 1)); 1860 data.push_back(vertex_half_edge(Point(2, -4), Point(-3, 1), -1)); 1861 data.push_back(vertex_half_edge(Point(2, -4), Point(2, 4), -1)); 1862 data.push_back(vertex_half_edge(Point(2, 4), Point(-2, 2), 1)); 1863 data.push_back(vertex_half_edge(Point(2, 4), Point(2, -4), 1)); 1864 polygon_sort(data.begin(), data.end()); 1865 pf.scan(polys, data.begin(), data.end()); 1866 stdcout << "result size: " << polys.size() << "\n"; 1867 for(std::size_t i = 0; i < polys.size(); ++i) { 1868 stdcout << polys[i] << "\n"; 1869 } 1870 stdcout << "done testing polygon formation\n"; 1871 return true; 1872 } 1873 1874 1875 template <typename stream_type> testPolygonArbitraryFormationPolys(stream_type & stdcout)1876 static inline bool testPolygonArbitraryFormationPolys(stream_type& stdcout) { 1877 stdcout << "testing polygon formation polys\n"; 1878 polygon_arbitrary_formation pf(false); 1879 std::vector<polygon_with_holes_data<Unit> > polys; 1880 polygon_arbitrary_formation pf2(true); 1881 std::vector<polygon_with_holes_data<Unit> > polys2; 1882 std::vector<vertex_half_edge> data; 1883 data.push_back(vertex_half_edge(Point(0, 0), Point(100, 1), 1)); 1884 data.push_back(vertex_half_edge(Point(0, 0), Point(1, 100), -1)); 1885 data.push_back(vertex_half_edge(Point(1, 100), Point(0, 0), 1)); 1886 data.push_back(vertex_half_edge(Point(1, 100), Point(101, 101), -1)); 1887 data.push_back(vertex_half_edge(Point(100, 1), Point(0, 0), -1)); 1888 data.push_back(vertex_half_edge(Point(100, 1), Point(101, 101), 1)); 1889 data.push_back(vertex_half_edge(Point(101, 101), Point(100, 1), -1)); 1890 data.push_back(vertex_half_edge(Point(101, 101), Point(1, 100), 1)); 1891 1892 data.push_back(vertex_half_edge(Point(2, 2), Point(10, 2), -1)); 1893 data.push_back(vertex_half_edge(Point(2, 2), Point(2, 10), -1)); 1894 data.push_back(vertex_half_edge(Point(2, 10), Point(2, 2), 1)); 1895 data.push_back(vertex_half_edge(Point(2, 10), Point(10, 10), 1)); 1896 data.push_back(vertex_half_edge(Point(10, 2), Point(2, 2), 1)); 1897 data.push_back(vertex_half_edge(Point(10, 2), Point(10, 10), 1)); 1898 data.push_back(vertex_half_edge(Point(10, 10), Point(10, 2), -1)); 1899 data.push_back(vertex_half_edge(Point(10, 10), Point(2, 10), -1)); 1900 1901 data.push_back(vertex_half_edge(Point(2, 12), Point(10, 12), -1)); 1902 data.push_back(vertex_half_edge(Point(2, 12), Point(2, 22), -1)); 1903 data.push_back(vertex_half_edge(Point(2, 22), Point(2, 12), 1)); 1904 data.push_back(vertex_half_edge(Point(2, 22), Point(10, 22), 1)); 1905 data.push_back(vertex_half_edge(Point(10, 12), Point(2, 12), 1)); 1906 data.push_back(vertex_half_edge(Point(10, 12), Point(10, 22), 1)); 1907 data.push_back(vertex_half_edge(Point(10, 22), Point(10, 12), -1)); 1908 data.push_back(vertex_half_edge(Point(10, 22), Point(2, 22), -1)); 1909 1910 polygon_sort(data.begin(), data.end()); 1911 pf.scan(polys, data.begin(), data.end()); 1912 stdcout << "result size: " << polys.size() << "\n"; 1913 for(std::size_t i = 0; i < polys.size(); ++i) { 1914 stdcout << polys[i] << "\n"; 1915 } 1916 pf2.scan(polys2, data.begin(), data.end()); 1917 stdcout << "result size: " << polys2.size() << "\n"; 1918 for(std::size_t i = 0; i < polys2.size(); ++i) { 1919 stdcout << polys2[i] << "\n"; 1920 } 1921 stdcout << "done testing polygon formation\n"; 1922 return true; 1923 } 1924 1925 template <typename stream_type> testPolygonArbitraryFormationSelfTouch1(stream_type & stdcout)1926 static inline bool testPolygonArbitraryFormationSelfTouch1(stream_type& stdcout) { 1927 stdcout << "testing polygon formation self touch 1\n"; 1928 polygon_arbitrary_formation pf(true); 1929 std::vector<polygon_data<Unit> > polys; 1930 std::vector<vertex_half_edge> data; 1931 data.push_back(vertex_half_edge(Point(0, 0), Point(10, 0), 1)); 1932 data.push_back(vertex_half_edge(Point(0, 0), Point(0, 10), 1)); 1933 1934 data.push_back(vertex_half_edge(Point(0, 10), Point(0, 0), -1)); 1935 data.push_back(vertex_half_edge(Point(0, 10), Point(5, 10), -1)); 1936 1937 data.push_back(vertex_half_edge(Point(10, 0), Point(0, 0), -1)); 1938 data.push_back(vertex_half_edge(Point(10, 0), Point(10, 5), -1)); 1939 1940 data.push_back(vertex_half_edge(Point(10, 5), Point(10, 0), 1)); 1941 data.push_back(vertex_half_edge(Point(10, 5), Point(5, 5), 1)); 1942 1943 data.push_back(vertex_half_edge(Point(5, 10), Point(5, 5), 1)); 1944 data.push_back(vertex_half_edge(Point(5, 10), Point(0, 10), 1)); 1945 1946 data.push_back(vertex_half_edge(Point(5, 2), Point(5, 5), -1)); 1947 data.push_back(vertex_half_edge(Point(5, 2), Point(7, 2), -1)); 1948 1949 data.push_back(vertex_half_edge(Point(5, 5), Point(5, 10), -1)); 1950 data.push_back(vertex_half_edge(Point(5, 5), Point(5, 2), 1)); 1951 data.push_back(vertex_half_edge(Point(5, 5), Point(10, 5), -1)); 1952 data.push_back(vertex_half_edge(Point(5, 5), Point(7, 2), 1)); 1953 1954 data.push_back(vertex_half_edge(Point(7, 2), Point(5, 5), -1)); 1955 data.push_back(vertex_half_edge(Point(7, 2), Point(5, 2), 1)); 1956 1957 polygon_sort(data.begin(), data.end()); 1958 pf.scan(polys, data.begin(), data.end()); 1959 stdcout << "result size: " << polys.size() << "\n"; 1960 for(std::size_t i = 0; i < polys.size(); ++i) { 1961 stdcout << polys[i] << "\n"; 1962 } 1963 stdcout << "done testing polygon formation\n"; 1964 return true; 1965 } 1966 1967 template <typename stream_type> testPolygonArbitraryFormationSelfTouch2(stream_type & stdcout)1968 static inline bool testPolygonArbitraryFormationSelfTouch2(stream_type& stdcout) { 1969 stdcout << "testing polygon formation self touch 2\n"; 1970 polygon_arbitrary_formation pf(true); 1971 std::vector<polygon_data<Unit> > polys; 1972 std::vector<vertex_half_edge> data; 1973 data.push_back(vertex_half_edge(Point(0, 0), Point(10, 0), 1)); 1974 data.push_back(vertex_half_edge(Point(0, 0), Point(0, 10), 1)); 1975 1976 data.push_back(vertex_half_edge(Point(0, 10), Point(0, 0), -1)); 1977 data.push_back(vertex_half_edge(Point(0, 10), Point(5, 10), -1)); 1978 1979 data.push_back(vertex_half_edge(Point(10, 0), Point(0, 0), -1)); 1980 data.push_back(vertex_half_edge(Point(10, 0), Point(10, 5), -1)); 1981 1982 data.push_back(vertex_half_edge(Point(10, 5), Point(10, 0), 1)); 1983 data.push_back(vertex_half_edge(Point(10, 5), Point(5, 5), 1)); 1984 1985 data.push_back(vertex_half_edge(Point(5, 10), Point(4, 1), -1)); 1986 data.push_back(vertex_half_edge(Point(5, 10), Point(0, 10), 1)); 1987 1988 data.push_back(vertex_half_edge(Point(4, 1), Point(5, 10), 1)); 1989 data.push_back(vertex_half_edge(Point(4, 1), Point(7, 2), -1)); 1990 1991 data.push_back(vertex_half_edge(Point(5, 5), Point(10, 5), -1)); 1992 data.push_back(vertex_half_edge(Point(5, 5), Point(7, 2), 1)); 1993 1994 data.push_back(vertex_half_edge(Point(7, 2), Point(5, 5), -1)); 1995 data.push_back(vertex_half_edge(Point(7, 2), Point(4, 1), 1)); 1996 1997 polygon_sort(data.begin(), data.end()); 1998 pf.scan(polys, data.begin(), data.end()); 1999 stdcout << "result size: " << polys.size() << "\n"; 2000 for(std::size_t i = 0; i < polys.size(); ++i) { 2001 stdcout << polys[i] << "\n"; 2002 } 2003 stdcout << "done testing polygon formation\n"; 2004 return true; 2005 } 2006 2007 template <typename stream_type> testPolygonArbitraryFormationSelfTouch3(stream_type & stdcout)2008 static inline bool testPolygonArbitraryFormationSelfTouch3(stream_type& stdcout) { 2009 stdcout << "testing polygon formation self touch 3\n"; 2010 polygon_arbitrary_formation pf(true); 2011 std::vector<polygon_data<Unit> > polys; 2012 std::vector<vertex_half_edge> data; 2013 data.push_back(vertex_half_edge(Point(0, 0), Point(10, 0), 1)); 2014 data.push_back(vertex_half_edge(Point(0, 0), Point(0, 10), 1)); 2015 2016 data.push_back(vertex_half_edge(Point(0, 10), Point(0, 0), -1)); 2017 data.push_back(vertex_half_edge(Point(0, 10), Point(6, 10), -1)); 2018 2019 data.push_back(vertex_half_edge(Point(10, 0), Point(0, 0), -1)); 2020 data.push_back(vertex_half_edge(Point(10, 0), Point(10, 5), -1)); 2021 2022 data.push_back(vertex_half_edge(Point(10, 5), Point(10, 0), 1)); 2023 data.push_back(vertex_half_edge(Point(10, 5), Point(5, 5), 1)); 2024 2025 data.push_back(vertex_half_edge(Point(6, 10), Point(4, 1), -1)); 2026 data.push_back(vertex_half_edge(Point(6, 10), Point(0, 10), 1)); 2027 2028 data.push_back(vertex_half_edge(Point(4, 1), Point(6, 10), 1)); 2029 data.push_back(vertex_half_edge(Point(4, 1), Point(7, 2), -1)); 2030 2031 data.push_back(vertex_half_edge(Point(5, 5), Point(10, 5), -1)); 2032 data.push_back(vertex_half_edge(Point(5, 5), Point(7, 2), 1)); 2033 2034 data.push_back(vertex_half_edge(Point(7, 2), Point(5, 5), -1)); 2035 data.push_back(vertex_half_edge(Point(7, 2), Point(4, 1), 1)); 2036 2037 polygon_sort(data.begin(), data.end()); 2038 pf.scan(polys, data.begin(), data.end()); 2039 stdcout << "result size: " << polys.size() << "\n"; 2040 for(std::size_t i = 0; i < polys.size(); ++i) { 2041 stdcout << polys[i] << "\n"; 2042 } 2043 stdcout << "done testing polygon formation\n"; 2044 return true; 2045 } 2046 2047 template <typename stream_type> testPolygonArbitraryFormationColinear(stream_type & stdcout)2048 static inline bool testPolygonArbitraryFormationColinear(stream_type& stdcout) { 2049 stdcout << "testing polygon formation colinear 3\n"; 2050 stdcout << "Polygon Set Data { <-3 2, -2 2>:1 <-3 2, -1 4>:-1 <-2 2, 0 2>:1 <-1 4, 0 2>:-1 } \n"; 2051 polygon_arbitrary_formation pf(true); 2052 std::vector<polygon_data<Unit> > polys; 2053 std::vector<vertex_half_edge> data; 2054 data.push_back(vertex_half_edge(Point(-3, 2), Point(-2, 2), 1)); 2055 data.push_back(vertex_half_edge(Point(-2, 2), Point(-3, 2), -1)); 2056 2057 data.push_back(vertex_half_edge(Point(-3, 2), Point(-1, 4), -1)); 2058 data.push_back(vertex_half_edge(Point(-1, 4), Point(-3, 2), 1)); 2059 2060 data.push_back(vertex_half_edge(Point(-2, 2), Point(0, 2), 1)); 2061 data.push_back(vertex_half_edge(Point(0, 2), Point(-2, 2), -1)); 2062 2063 data.push_back(vertex_half_edge(Point(-1, 4), Point(0, 2), -1)); 2064 data.push_back(vertex_half_edge(Point(0, 2), Point(-1, 4), 1)); 2065 polygon_sort(data.begin(), data.end()); 2066 pf.scan(polys, data.begin(), data.end()); 2067 stdcout << "result size: " << polys.size() << "\n"; 2068 for(std::size_t i = 0; i < polys.size(); ++i) { 2069 stdcout << polys[i] << "\n"; 2070 } 2071 stdcout << "done testing polygon formation\n"; 2072 return true; 2073 } 2074 2075 template <typename stream_type> testSegmentIntersection(stream_type & stdcout)2076 static inline bool testSegmentIntersection(stream_type& stdcout) { 2077 stdcout << "testing segment intersection\n"; 2078 half_edge he1, he2; 2079 he1.first = Point(0, 0); 2080 he1.second = Point(10, 10); 2081 he2.first = Point(0, 0); 2082 he2.second = Point(10, 20); 2083 Point result; 2084 bool b = scanline_base<Unit>::compute_intersection(result, he1, he2); 2085 if(!b || result != Point(0, 0)) return false; 2086 he1.first = Point(0, 10); 2087 b = scanline_base<Unit>::compute_intersection(result, he1, he2); 2088 if(!b || result != Point(5, 10)) return false; 2089 he1.first = Point(0, 11); 2090 b = scanline_base<Unit>::compute_intersection(result, he1, he2); 2091 if(!b || result != Point(5, 10)) return false; 2092 he1.first = Point(0, 0); 2093 he1.second = Point(1, 9); 2094 he2.first = Point(0, 9); 2095 he2.second = Point(1, 0); 2096 b = scanline_base<Unit>::compute_intersection(result, he1, he2); 2097 if(!b || result != Point(0, 4)) return false; 2098 2099 he1.first = Point(0, -10); 2100 he1.second = Point(1, -1); 2101 he2.first = Point(0, -1); 2102 he2.second = Point(1, -10); 2103 b = scanline_base<Unit>::compute_intersection(result, he1, he2); 2104 if(!b || result != Point(0, -5)) return false; 2105 he1.first = Point((std::numeric_limits<int>::max)(), (std::numeric_limits<int>::max)()-1); 2106 he1.second = Point((std::numeric_limits<int>::min)(), (std::numeric_limits<int>::max)()); 2107 //he1.second = Point(0, (std::numeric_limits<int>::max)()); 2108 he2.first = Point((std::numeric_limits<int>::max)()-1, (std::numeric_limits<int>::max)()); 2109 he2.second = Point((std::numeric_limits<int>::max)(), (std::numeric_limits<int>::min)()); 2110 //he2.second = Point((std::numeric_limits<int>::max)(), 0); 2111 b = scanline_base<Unit>::compute_intersection(result, he1, he2); 2112 //b is false because of overflow error 2113 he1.first = Point(1000, 2000); 2114 he1.second = Point(1010, 2010); 2115 he2.first = Point(1000, 2000); 2116 he2.second = Point(1010, 2020); 2117 b = scanline_base<Unit>::compute_intersection(result, he1, he2); 2118 if(!b || result != Point(1000, 2000)) return false; 2119 2120 return b; 2121 } 2122 2123 }; 2124 2125 template <typename Unit> 2126 class poly_line_arbitrary_hole_data { 2127 private: 2128 typedef typename polygon_arbitrary_formation<Unit>::active_tail_arbitrary active_tail_arbitrary; 2129 active_tail_arbitrary* p_; 2130 public: 2131 typedef point_data<Unit> Point; 2132 typedef Point point_type; 2133 typedef Unit coordinate_type; 2134 typedef typename active_tail_arbitrary::iterator iterator_type; 2135 //typedef iterator_points_to_compact<iterator_type, Point> compact_iterator_type; 2136 2137 typedef iterator_type iterator; poly_line_arbitrary_hole_data()2138 inline poly_line_arbitrary_hole_data() : p_(0) {} poly_line_arbitrary_hole_data(active_tail_arbitrary * p)2139 inline poly_line_arbitrary_hole_data(active_tail_arbitrary* p) : p_(p) {} 2140 //use default copy and assign begin() const2141 inline iterator begin() const { return p_->getTail()->begin(); } end() const2142 inline iterator end() const { return p_->getTail()->end(); } 2143 //inline compact_iterator_type begin_compact() const { return compact_iterator_type(begin()); } 2144 //inline compact_iterator_type end_compact() const { return compact_iterator_type(end()); } size() const2145 inline std::size_t size() const { return 0; } 2146 template<class iT> set(iT inputBegin,iT inputEnd)2147 inline poly_line_arbitrary_hole_data& set(iT inputBegin, iT inputEnd) { 2148 //assert this is not called 2149 return *this; 2150 } 2151 template<class iT> set_compact(iT inputBegin,iT inputEnd)2152 inline poly_line_arbitrary_hole_data& set_compact(iT inputBegin, iT inputEnd) { 2153 //assert this is not called 2154 return *this; 2155 } 2156 }; 2157 2158 template <typename Unit> 2159 class poly_line_arbitrary_polygon_data { 2160 private: 2161 typedef typename polygon_arbitrary_formation<Unit>::active_tail_arbitrary active_tail_arbitrary; 2162 active_tail_arbitrary* p_; 2163 public: 2164 typedef point_data<Unit> Point; 2165 typedef Point point_type; 2166 typedef Unit coordinate_type; 2167 typedef typename active_tail_arbitrary::iterator iterator_type; 2168 //typedef iterator_points_to_compact<iterator_type, Point> compact_iterator_type; 2169 typedef typename coordinate_traits<Unit>::coordinate_distance area_type; 2170 2171 class iterator_holes_type { 2172 private: 2173 typedef poly_line_arbitrary_hole_data<Unit> holeType; 2174 mutable holeType hole_; 2175 typename active_tail_arbitrary::iteratorHoles itr_; 2176 2177 public: 2178 typedef std::forward_iterator_tag iterator_category; 2179 typedef holeType value_type; 2180 typedef std::ptrdiff_t difference_type; 2181 typedef const holeType* pointer; //immutable 2182 typedef const holeType& reference; //immutable iterator_holes_type()2183 inline iterator_holes_type() : hole_(), itr_() {} iterator_holes_type(typename active_tail_arbitrary::iteratorHoles itr)2184 inline iterator_holes_type(typename active_tail_arbitrary::iteratorHoles itr) : hole_(), itr_(itr) {} iterator_holes_type(const iterator_holes_type & that)2185 inline iterator_holes_type(const iterator_holes_type& that) : hole_(that.hole_), itr_(that.itr_) {} operator =(const iterator_holes_type & that)2186 inline iterator_holes_type& operator=(const iterator_holes_type& that) { 2187 itr_ = that.itr_; 2188 return *this; 2189 } operator ==(const iterator_holes_type & that)2190 inline bool operator==(const iterator_holes_type& that) { return itr_ == that.itr_; } operator !=(const iterator_holes_type & that)2191 inline bool operator!=(const iterator_holes_type& that) { return itr_ != that.itr_; } operator ++()2192 inline iterator_holes_type& operator++() { 2193 ++itr_; 2194 return *this; 2195 } operator ++(int)2196 inline const iterator_holes_type operator++(int) { 2197 iterator_holes_type tmp = *this; 2198 ++(*this); 2199 return tmp; 2200 } operator *()2201 inline reference operator*() { 2202 hole_ = holeType(*itr_); 2203 return hole_; 2204 } 2205 }; 2206 2207 typedef poly_line_arbitrary_hole_data<Unit> hole_type; 2208 poly_line_arbitrary_polygon_data()2209 inline poly_line_arbitrary_polygon_data() : p_(0) {} poly_line_arbitrary_polygon_data(active_tail_arbitrary * p)2210 inline poly_line_arbitrary_polygon_data(active_tail_arbitrary* p) : p_(p) {} 2211 //use default copy and assign begin() const2212 inline iterator_type begin() const { return p_->getTail()->begin(); } end() const2213 inline iterator_type end() const { return p_->getTail()->end(); } 2214 //inline compact_iterator_type begin_compact() const { return p_->getTail()->begin(); } 2215 //inline compact_iterator_type end_compact() const { return p_->getTail()->end(); } begin_holes() const2216 inline iterator_holes_type begin_holes() const { return iterator_holes_type(p_->getHoles().begin()); } end_holes() const2217 inline iterator_holes_type end_holes() const { return iterator_holes_type(p_->getHoles().end()); } yield()2218 inline active_tail_arbitrary* yield() { return p_; } 2219 //stub out these four required functions that will not be used but are needed for the interface size_holes() const2220 inline std::size_t size_holes() const { return 0; } size() const2221 inline std::size_t size() const { return 0; } 2222 template<class iT> set(iT inputBegin,iT inputEnd)2223 inline poly_line_arbitrary_polygon_data& set(iT inputBegin, iT inputEnd) { 2224 return *this; 2225 } 2226 template<class iT> set_compact(iT inputBegin,iT inputEnd)2227 inline poly_line_arbitrary_polygon_data& set_compact(iT inputBegin, iT inputEnd) { 2228 return *this; 2229 } 2230 template<class iT> set_holes(iT inputBegin,iT inputEnd)2231 inline poly_line_arbitrary_polygon_data& set_holes(iT inputBegin, iT inputEnd) { 2232 return *this; 2233 } 2234 }; 2235 2236 template <typename Unit> 2237 class trapezoid_arbitrary_formation : public polygon_arbitrary_formation<Unit> { 2238 private: 2239 typedef typename scanline_base<Unit>::Point Point; 2240 typedef typename scanline_base<Unit>::half_edge half_edge; 2241 typedef typename scanline_base<Unit>::vertex_half_edge vertex_half_edge; 2242 typedef typename scanline_base<Unit>::less_vertex_half_edge less_vertex_half_edge; 2243 2244 typedef typename polygon_arbitrary_formation<Unit>::poly_line_arbitrary poly_line_arbitrary; 2245 2246 typedef typename polygon_arbitrary_formation<Unit>::active_tail_arbitrary active_tail_arbitrary; 2247 2248 typedef std::vector<std::pair<Point, int> > vertex_arbitrary_count; 2249 2250 typedef typename polygon_arbitrary_formation<Unit>::less_half_edge_count less_half_edge_count; 2251 2252 typedef std::vector<std::pair<std::pair<std::pair<Point, Point>, int>, active_tail_arbitrary*> > incoming_count; 2253 2254 typedef typename polygon_arbitrary_formation<Unit>::less_incoming_count less_incoming_count; 2255 2256 typedef typename polygon_arbitrary_formation<Unit>::vertex_arbitrary_compact vertex_arbitrary_compact; 2257 2258 private: 2259 //definitions 2260 typedef std::map<vertex_half_edge, active_tail_arbitrary*, less_vertex_half_edge> scanline_data; 2261 typedef typename scanline_data::iterator iterator; 2262 typedef typename scanline_data::const_iterator const_iterator; 2263 2264 //data 2265 public: trapezoid_arbitrary_formation()2266 inline trapezoid_arbitrary_formation() : polygon_arbitrary_formation<Unit>() {} trapezoid_arbitrary_formation(const trapezoid_arbitrary_formation & that)2267 inline trapezoid_arbitrary_formation(const trapezoid_arbitrary_formation& that) : polygon_arbitrary_formation<Unit>(that) {} operator =(const trapezoid_arbitrary_formation & that)2268 inline trapezoid_arbitrary_formation& operator=(const trapezoid_arbitrary_formation& that) { 2269 * static_cast<polygon_arbitrary_formation<Unit>*>(this) = * static_cast<polygon_arbitrary_formation<Unit>*>(&that); 2270 return *this; 2271 } 2272 2273 //cT is an output container of Polygon45 or Polygon45WithHoles 2274 //iT is an iterator over vertex_half_edge elements 2275 //inputBegin - inputEnd is a range of sorted iT that represents 2276 //one or more scanline stops worth of data 2277 template <class cT, class iT> scan(cT & output,iT inputBegin,iT inputEnd)2278 void scan(cT& output, iT inputBegin, iT inputEnd) { 2279 //std::cout << "1\n"; 2280 while(inputBegin != inputEnd) { 2281 //std::cout << "2\n"; 2282 polygon_arbitrary_formation<Unit>::x_ = (*inputBegin).pt.get(HORIZONTAL); 2283 //std::cout << "SCAN FORMATION " << x_ << "\n"; 2284 //std::cout << "x_ = " << x_ << "\n"; 2285 //std::cout << "scan line size: " << scanData_.size() << "\n"; 2286 inputBegin = processEvent_(output, inputBegin, inputEnd); 2287 } 2288 //std::cout << "scan line size: " << scanData_.size() << "\n"; 2289 } 2290 2291 private: 2292 //functions getVerticalPair_(std::pair<active_tail_arbitrary *,active_tail_arbitrary * > & verticalPair,iterator previter)2293 inline void getVerticalPair_(std::pair<active_tail_arbitrary*, 2294 active_tail_arbitrary*>& verticalPair, 2295 iterator previter) { 2296 active_tail_arbitrary* iterTail = (*previter).second; 2297 Point prevPoint(polygon_arbitrary_formation<Unit>::x_, 2298 convert_high_precision_type<Unit>(previter->first.evalAtX(polygon_arbitrary_formation<Unit>::x_))); 2299 iterTail->pushPoint(prevPoint); 2300 std::pair<active_tail_arbitrary*, active_tail_arbitrary*> tailPair = 2301 active_tail_arbitrary::createActiveTailsAsPair(prevPoint, true, 0, false); 2302 verticalPair.first = iterTail; 2303 verticalPair.second = tailPair.first; 2304 (*previter).second = tailPair.second; 2305 } 2306 2307 template <class cT, class cT2> 2308 inline std::pair<std::pair<Point, int>, active_tail_arbitrary*> processPoint_(cT & output,cT2 & elements,std::pair<active_tail_arbitrary *,active_tail_arbitrary * > & verticalPair,iterator previter,Point point,incoming_count & counts_from_scanline,vertex_arbitrary_count & incoming_count)2309 processPoint_(cT& output, cT2& elements, 2310 std::pair<active_tail_arbitrary*, active_tail_arbitrary*>& verticalPair, 2311 iterator previter, Point point, incoming_count& counts_from_scanline, 2312 vertex_arbitrary_count& incoming_count) { 2313 //std::cout << "\nAT POINT: " << point << "\n"; 2314 //join any closing solid corners 2315 std::vector<int> counts; 2316 std::vector<int> incoming; 2317 std::vector<active_tail_arbitrary*> tails; 2318 counts.reserve(counts_from_scanline.size()); 2319 tails.reserve(counts_from_scanline.size()); 2320 incoming.reserve(incoming_count.size()); 2321 for(std::size_t i = 0; i < counts_from_scanline.size(); ++i) { 2322 counts.push_back(counts_from_scanline[i].first.second); 2323 tails.push_back(counts_from_scanline[i].second); 2324 } 2325 for(std::size_t i = 0; i < incoming_count.size(); ++i) { 2326 incoming.push_back(incoming_count[i].second); 2327 if(incoming_count[i].first < point) { 2328 incoming.back() = 0; 2329 } 2330 } 2331 2332 active_tail_arbitrary* returnValue = 0; 2333 std::pair<active_tail_arbitrary*, active_tail_arbitrary*> verticalPairOut; 2334 verticalPairOut.first = 0; 2335 verticalPairOut.second = 0; 2336 std::pair<Point, int> returnCount(Point(0, 0), 0); 2337 int i_size_less_1 = (int)(incoming.size()) -1; 2338 int c_size_less_1 = (int)(counts.size()) -1; 2339 int i_size = incoming.size(); 2340 int c_size = counts.size(); 2341 2342 bool have_vertical_tail_from_below = false; 2343 if(c_size && 2344 scanline_base<Unit>::is_vertical(counts_from_scanline.back().first.first)) { 2345 have_vertical_tail_from_below = true; 2346 } 2347 //assert size = size_less_1 + 1 2348 //std::cout << tails.size() << " " << incoming.size() << " " << counts_from_scanline.size() << " " << incoming_count.size() << "\n"; 2349 // for(std::size_t i = 0; i < counts.size(); ++i) { 2350 // std::cout << counts_from_scanline[i].first.first.first.get(HORIZONTAL) << ","; 2351 // std::cout << counts_from_scanline[i].first.first.first.get(VERTICAL) << " "; 2352 // std::cout << counts_from_scanline[i].first.first.second.get(HORIZONTAL) << ","; 2353 // std::cout << counts_from_scanline[i].first.first.second.get(VERTICAL) << ":"; 2354 // std::cout << counts_from_scanline[i].first.second << " "; 2355 // } std::cout << "\n"; 2356 // print(incoming_count); 2357 { 2358 for(int i = 0; i < c_size_less_1; ++i) { 2359 //std::cout << i << "\n"; 2360 if(counts[i] == -1) { 2361 //std::cout << "fixed i\n"; 2362 for(int j = i + 1; j < c_size; ++j) { 2363 //std::cout << j << "\n"; 2364 if(counts[j]) { 2365 if(counts[j] == 1) { 2366 //std::cout << "case1: " << i << " " << j << "\n"; 2367 //if a figure is closed it will be written out by this function to output 2368 active_tail_arbitrary::joinChains(point, tails[i], tails[j], true, output); 2369 counts[i] = 0; 2370 counts[j] = 0; 2371 tails[i] = 0; 2372 tails[j] = 0; 2373 } 2374 break; 2375 } 2376 } 2377 } 2378 } 2379 } 2380 //find any pairs of incoming edges that need to create pair for leading solid 2381 //std::cout << "checking case2\n"; 2382 { 2383 for(int i = 0; i < i_size_less_1; ++i) { 2384 //std::cout << i << "\n"; 2385 if(incoming[i] == 1) { 2386 //std::cout << "fixed i\n"; 2387 for(int j = i + 1; j < i_size; ++j) { 2388 //std::cout << j << "\n"; 2389 if(incoming[j]) { 2390 //std::cout << incoming[j] << "\n"; 2391 if(incoming[j] == -1) { 2392 //std::cout << "case2: " << i << " " << j << "\n"; 2393 //std::cout << "creating active tail pair\n"; 2394 std::pair<active_tail_arbitrary*, active_tail_arbitrary*> tailPair = 2395 active_tail_arbitrary::createActiveTailsAsPair(point, true, 0, polygon_arbitrary_formation<Unit>::fractureHoles_ != 0); 2396 //tailPair.first->print(); 2397 //tailPair.second->print(); 2398 if(j == i_size_less_1 && incoming_count[j].first.get(HORIZONTAL) == point.get(HORIZONTAL)) { 2399 //vertical active tail becomes return value 2400 returnValue = tailPair.first; 2401 returnCount.first = point; 2402 returnCount.second = 1; 2403 } else { 2404 //std::cout << "new element " << j-1 << " " << -1 << "\n"; 2405 //std::cout << point << " " << incoming_count[j].first << "\n"; 2406 elements.push_back(std::pair<vertex_half_edge, 2407 active_tail_arbitrary*>(vertex_half_edge(point, 2408 incoming_count[j].first, -1), tailPair.first)); 2409 } 2410 //std::cout << "new element " << i-1 << " " << 1 << "\n"; 2411 //std::cout << point << " " << incoming_count[i].first << "\n"; 2412 elements.push_back(std::pair<vertex_half_edge, 2413 active_tail_arbitrary*>(vertex_half_edge(point, 2414 incoming_count[i].first, 1), tailPair.second)); 2415 incoming[i] = 0; 2416 incoming[j] = 0; 2417 } 2418 break; 2419 } 2420 } 2421 } 2422 } 2423 } 2424 //find any active tail that needs to pass through to an incoming edge 2425 //we expect to find no more than two pass through 2426 2427 //find pass through with solid on top 2428 { 2429 //std::cout << "checking case 3\n"; 2430 for(int i = 0; i < c_size; ++i) { 2431 //std::cout << i << "\n"; 2432 if(counts[i] != 0) { 2433 if(counts[i] == 1) { 2434 //std::cout << "fixed i\n"; 2435 for(int j = i_size_less_1; j >= 0; --j) { 2436 if(incoming[j] != 0) { 2437 if(incoming[j] == 1) { 2438 //std::cout << "case3: " << i << " " << j << "\n"; 2439 //tails[i]->print(); 2440 //pass through solid on top 2441 tails[i]->pushPoint(point); 2442 //std::cout << "after push\n"; 2443 if(j == i_size_less_1 && incoming_count[j].first.get(HORIZONTAL) == point.get(HORIZONTAL)) { 2444 returnValue = tails[i]; 2445 returnCount.first = point; 2446 returnCount.second = -1; 2447 } else { 2448 std::pair<active_tail_arbitrary*, active_tail_arbitrary*> tailPair = 2449 active_tail_arbitrary::createActiveTailsAsPair(point, true, 0, false); 2450 verticalPairOut.first = tails[i]; 2451 verticalPairOut.second = tailPair.first; 2452 elements.push_back(std::pair<vertex_half_edge, 2453 active_tail_arbitrary*>(vertex_half_edge(point, 2454 incoming_count[j].first, incoming[j]), tailPair.second)); 2455 } 2456 tails[i] = 0; 2457 counts[i] = 0; 2458 incoming[j] = 0; 2459 } 2460 break; 2461 } 2462 } 2463 } 2464 break; 2465 } 2466 } 2467 } 2468 //std::cout << "checking case 4\n"; 2469 //find pass through with solid on bottom 2470 { 2471 for(int i = c_size_less_1; i >= 0; --i) { 2472 //std::cout << "i = " << i << " with count " << counts[i] << "\n"; 2473 if(counts[i] != 0) { 2474 if(counts[i] == -1) { 2475 for(int j = 0; j < i_size; ++j) { 2476 if(incoming[j] != 0) { 2477 if(incoming[j] == -1) { 2478 //std::cout << "case4: " << i << " " << j << "\n"; 2479 //pass through solid on bottom 2480 2481 //if count from scanline is vertical 2482 if(i == c_size_less_1 && 2483 counts_from_scanline[i].first.first.first.get(HORIZONTAL) == 2484 point.get(HORIZONTAL)) { 2485 //if incoming count is vertical 2486 if(j == i_size_less_1 && 2487 incoming_count[j].first.get(HORIZONTAL) == point.get(HORIZONTAL)) { 2488 returnValue = tails[i]; 2489 returnCount.first = point; 2490 returnCount.second = 1; 2491 } else { 2492 tails[i]->pushPoint(point); 2493 elements.push_back(std::pair<vertex_half_edge, 2494 active_tail_arbitrary*>(vertex_half_edge(point, 2495 incoming_count[j].first, incoming[j]), tails[i])); 2496 } 2497 } else if(j == i_size_less_1 && 2498 incoming_count[j].first.get(HORIZONTAL) == 2499 point.get(HORIZONTAL)) { 2500 if(verticalPair.first == 0) { 2501 getVerticalPair_(verticalPair, previter); 2502 } 2503 active_tail_arbitrary::joinChains(point, tails[i], verticalPair.first, true, output); 2504 returnValue = verticalPair.second; 2505 returnCount.first = point; 2506 returnCount.second = 1; 2507 } else { 2508 //neither is vertical 2509 if(verticalPair.first == 0) { 2510 getVerticalPair_(verticalPair, previter); 2511 } 2512 active_tail_arbitrary::joinChains(point, tails[i], verticalPair.first, true, output); 2513 verticalPair.second->pushPoint(point); 2514 elements.push_back(std::pair<vertex_half_edge, 2515 active_tail_arbitrary*>(vertex_half_edge(point, 2516 incoming_count[j].first, incoming[j]), verticalPair.second)); 2517 } 2518 tails[i] = 0; 2519 counts[i] = 0; 2520 incoming[j] = 0; 2521 } 2522 break; 2523 } 2524 } 2525 } 2526 break; 2527 } 2528 } 2529 } 2530 //find the end of a hole or the beginning of a hole 2531 2532 //find end of a hole 2533 { 2534 for(int i = 0; i < c_size_less_1; ++i) { 2535 if(counts[i] != 0) { 2536 for(int j = i+1; j < c_size; ++j) { 2537 if(counts[j] != 0) { 2538 //std::cout << "case5: " << i << " " << j << "\n"; 2539 //we are ending a hole and may potentially close a figure and have to handle the hole 2540 tails[i]->pushPoint(point); 2541 verticalPairOut.first = tails[i]; 2542 if(j == c_size_less_1 && 2543 counts_from_scanline[j].first.first.first.get(HORIZONTAL) == 2544 point.get(HORIZONTAL)) { 2545 verticalPairOut.second = tails[j]; 2546 } else { 2547 //need to close a trapezoid below 2548 if(verticalPair.first == 0) { 2549 getVerticalPair_(verticalPair, previter); 2550 } 2551 active_tail_arbitrary::joinChains(point, tails[j], verticalPair.first, true, output); 2552 verticalPairOut.second = verticalPair.second; 2553 } 2554 tails[i] = 0; 2555 tails[j] = 0; 2556 counts[i] = 0; 2557 counts[j] = 0; 2558 break; 2559 } 2560 } 2561 break; 2562 } 2563 } 2564 } 2565 //find beginning of a hole 2566 { 2567 for(int i = 0; i < i_size_less_1; ++i) { 2568 if(incoming[i] != 0) { 2569 for(int j = i+1; j < i_size; ++j) { 2570 if(incoming[j] != 0) { 2571 //std::cout << "case6: " << i << " " << j << "\n"; 2572 //we are beginning a empty space 2573 if(verticalPair.first == 0) { 2574 getVerticalPair_(verticalPair, previter); 2575 } 2576 verticalPair.second->pushPoint(point); 2577 if(j == i_size_less_1 && 2578 incoming_count[j].first.get(HORIZONTAL) == point.get(HORIZONTAL)) { 2579 returnValue = verticalPair.first; 2580 returnCount.first = point; 2581 returnCount.second = -1; 2582 } else { 2583 std::pair<active_tail_arbitrary*, active_tail_arbitrary*> tailPair = 2584 active_tail_arbitrary::createActiveTailsAsPair(point, false, 0, false); 2585 elements.push_back(std::pair<vertex_half_edge, 2586 active_tail_arbitrary*>(vertex_half_edge(point, 2587 incoming_count[j].first, incoming[j]), tailPair.second)); 2588 verticalPairOut.second = tailPair.first; 2589 verticalPairOut.first = verticalPair.first; 2590 } 2591 elements.push_back(std::pair<vertex_half_edge, 2592 active_tail_arbitrary*>(vertex_half_edge(point, 2593 incoming_count[i].first, incoming[i]), verticalPair.second)); 2594 incoming[i] = 0; 2595 incoming[j] = 0; 2596 break; 2597 } 2598 } 2599 break; 2600 } 2601 } 2602 } 2603 if(have_vertical_tail_from_below) { 2604 if(tails.back()) { 2605 tails.back()->pushPoint(point); 2606 returnValue = tails.back(); 2607 returnCount.first = point; 2608 returnCount.second = counts.back(); 2609 } 2610 } 2611 verticalPair = verticalPairOut; 2612 //assert that tails, counts and incoming are all null 2613 return std::pair<std::pair<Point, int>, active_tail_arbitrary*>(returnCount, returnValue); 2614 } 2615 print(const vertex_arbitrary_count & count)2616 static inline void print(const vertex_arbitrary_count& count) { 2617 for(unsigned i = 0; i < count.size(); ++i) { 2618 //std::cout << count[i].first.get(HORIZONTAL) << ","; 2619 //std::cout << count[i].first.get(VERTICAL) << ":"; 2620 //std::cout << count[i].second << " "; 2621 } //std::cout << "\n"; 2622 } 2623 print(const scanline_data & data)2624 static inline void print(const scanline_data& data) { 2625 for(typename scanline_data::const_iterator itr = data.begin(); itr != data.end(); ++itr){ 2626 //std::cout << itr->first.pt << ", " << itr->first.other_pt << "; "; 2627 } //std::cout << "\n"; 2628 } 2629 2630 template <class cT, class iT> processEvent_(cT & output,iT inputBegin,iT inputEnd)2631 inline iT processEvent_(cT& output, iT inputBegin, iT inputEnd) { 2632 //typedef typename high_precision_type<Unit>::type high_precision; 2633 //std::cout << "processEvent_\n"; 2634 polygon_arbitrary_formation<Unit>::justBefore_ = true; 2635 //collect up all elements from the tree that are at the y 2636 //values of events in the input queue 2637 //create vector of new elements to add into tree 2638 active_tail_arbitrary* verticalTail = 0; 2639 std::pair<active_tail_arbitrary*, active_tail_arbitrary*> verticalPair; 2640 std::pair<Point, int> verticalCount(Point(0, 0), 0); 2641 iT currentIter = inputBegin; 2642 std::vector<iterator> elementIters; 2643 std::vector<std::pair<vertex_half_edge, active_tail_arbitrary*> > elements; 2644 while(currentIter != inputEnd && currentIter->pt.get(HORIZONTAL) == polygon_arbitrary_formation<Unit>::x_) { 2645 //std::cout << "loop\n"; 2646 Unit currentY = (*currentIter).pt.get(VERTICAL); 2647 //std::cout << "current Y " << currentY << "\n"; 2648 //std::cout << "scanline size " << scanData_.size() << "\n"; 2649 //print(scanData_); 2650 iterator iter = this->lookUp_(currentY); 2651 //std::cout << "found element in scanline " << (iter != scanData_.end()) << "\n"; 2652 //int counts[4] = {0, 0, 0, 0}; 2653 incoming_count counts_from_scanline; 2654 //std::cout << "finding elements in tree\n"; 2655 //if(iter != scanData_.end()) 2656 // std::cout << "first iter y is " << iter->first.evalAtX(x_) << "\n"; 2657 iterator previter = iter; 2658 if(previter != polygon_arbitrary_formation<Unit>::scanData_.end() && 2659 previter->first.evalAtX(polygon_arbitrary_formation<Unit>::x_) >= currentY && 2660 previter != polygon_arbitrary_formation<Unit>::scanData_.begin()) 2661 --previter; 2662 while(iter != polygon_arbitrary_formation<Unit>::scanData_.end() && 2663 ((iter->first.pt.x() == polygon_arbitrary_formation<Unit>::x_ && iter->first.pt.y() == currentY) || 2664 (iter->first.other_pt.x() == polygon_arbitrary_formation<Unit>::x_ && iter->first.other_pt.y() == currentY))) { 2665 //iter->first.evalAtX(polygon_arbitrary_formation<Unit>::x_) == (high_precision)currentY) { 2666 //std::cout << "loop2\n"; 2667 elementIters.push_back(iter); 2668 counts_from_scanline.push_back(std::pair<std::pair<std::pair<Point, Point>, int>, active_tail_arbitrary*> 2669 (std::pair<std::pair<Point, Point>, int>(std::pair<Point, Point>(iter->first.pt, 2670 iter->first.other_pt), 2671 iter->first.count), 2672 iter->second)); 2673 ++iter; 2674 } 2675 Point currentPoint(polygon_arbitrary_formation<Unit>::x_, currentY); 2676 //std::cout << "counts_from_scanline size " << counts_from_scanline.size() << "\n"; 2677 this->sort_incoming_count(counts_from_scanline, currentPoint); 2678 2679 vertex_arbitrary_count incoming; 2680 //std::cout << "aggregating\n"; 2681 do { 2682 //std::cout << "loop3\n"; 2683 const vertex_half_edge& elem = *currentIter; 2684 incoming.push_back(std::pair<Point, int>(elem.other_pt, elem.count)); 2685 ++currentIter; 2686 } while(currentIter != inputEnd && currentIter->pt.get(VERTICAL) == currentY && 2687 currentIter->pt.get(HORIZONTAL) == polygon_arbitrary_formation<Unit>::x_); 2688 //print(incoming); 2689 this->sort_vertex_arbitrary_count(incoming, currentPoint); 2690 //std::cout << currentPoint.get(HORIZONTAL) << "," << currentPoint.get(VERTICAL) << "\n"; 2691 //print(incoming); 2692 //std::cout << "incoming counts from input size " << incoming.size() << "\n"; 2693 //compact_vertex_arbitrary_count(currentPoint, incoming); 2694 vertex_arbitrary_count tmp; 2695 tmp.reserve(incoming.size()); 2696 for(std::size_t i = 0; i < incoming.size(); ++i) { 2697 if(currentPoint < incoming[i].first) { 2698 tmp.push_back(incoming[i]); 2699 } 2700 } 2701 incoming.swap(tmp); 2702 //std::cout << "incoming counts from input size " << incoming.size() << "\n"; 2703 //now counts_from_scanline has the data from the left and 2704 //incoming has the data from the right at this point 2705 //cancel out any end points 2706 if(verticalTail) { 2707 //std::cout << "adding vertical tail to counts from scanline\n"; 2708 //std::cout << -verticalCount.second << "\n"; 2709 counts_from_scanline.push_back(std::pair<std::pair<std::pair<Point, Point>, int>, active_tail_arbitrary*> 2710 (std::pair<std::pair<Point, Point>, int>(std::pair<Point, Point>(verticalCount.first, 2711 currentPoint), 2712 -verticalCount.second), 2713 verticalTail)); 2714 } 2715 if(!incoming.empty() && incoming.back().first.get(HORIZONTAL) == polygon_arbitrary_formation<Unit>::x_) { 2716 //std::cout << "inverted vertical event\n"; 2717 incoming.back().second *= -1; 2718 } 2719 //std::cout << "calling processPoint_\n"; 2720 std::pair<std::pair<Point, int>, active_tail_arbitrary*> result = processPoint_(output, elements, verticalPair, previter, Point(polygon_arbitrary_formation<Unit>::x_, currentY), counts_from_scanline, incoming); 2721 verticalCount = result.first; 2722 verticalTail = result.second; 2723 if(verticalPair.first != 0 && iter != polygon_arbitrary_formation<Unit>::scanData_.end() && 2724 (currentIter == inputEnd || currentIter->pt.x() != polygon_arbitrary_formation<Unit>::x_ || 2725 currentIter->pt.y() > (*iter).first.evalAtX(polygon_arbitrary_formation<Unit>::x_))) { 2726 //splice vertical pair into edge above 2727 active_tail_arbitrary* tailabove = (*iter).second; 2728 Point point(polygon_arbitrary_formation<Unit>::x_, 2729 convert_high_precision_type<Unit>((*iter).first.evalAtX(polygon_arbitrary_formation<Unit>::x_))); 2730 verticalPair.second->pushPoint(point); 2731 active_tail_arbitrary::joinChains(point, tailabove, verticalPair.first, true, output); 2732 (*iter).second = verticalPair.second; 2733 verticalPair.first = 0; 2734 verticalPair.second = 0; 2735 } 2736 } 2737 //std::cout << "erasing\n"; 2738 //erase all elements from the tree 2739 for(typename std::vector<iterator>::iterator iter = elementIters.begin(); 2740 iter != elementIters.end(); ++iter) { 2741 //std::cout << "erasing loop\n"; 2742 polygon_arbitrary_formation<Unit>::scanData_.erase(*iter); 2743 } 2744 //switch comparison tie breaking policy 2745 polygon_arbitrary_formation<Unit>::justBefore_ = false; 2746 //add new elements into tree 2747 //std::cout << "inserting\n"; 2748 for(typename std::vector<std::pair<vertex_half_edge, active_tail_arbitrary*> >::iterator iter = elements.begin(); 2749 iter != elements.end(); ++iter) { 2750 //std::cout << "inserting loop\n"; 2751 polygon_arbitrary_formation<Unit>::scanData_.insert(polygon_arbitrary_formation<Unit>::scanData_.end(), *iter); 2752 } 2753 //std::cout << "end processEvent\n"; 2754 return currentIter; 2755 } 2756 public: 2757 template <typename stream_type> testTrapezoidArbitraryFormationRect(stream_type & stdcout)2758 static inline bool testTrapezoidArbitraryFormationRect(stream_type& stdcout) { 2759 stdcout << "testing trapezoid formation\n"; 2760 trapezoid_arbitrary_formation pf; 2761 std::vector<polygon_data<Unit> > polys; 2762 std::vector<vertex_half_edge> data; 2763 data.push_back(vertex_half_edge(Point(0, 0), Point(10, 0), 1)); 2764 data.push_back(vertex_half_edge(Point(0, 0), Point(0, 10), 1)); 2765 data.push_back(vertex_half_edge(Point(0, 10), Point(0, 0), -1)); 2766 data.push_back(vertex_half_edge(Point(0, 10), Point(10, 10), -1)); 2767 data.push_back(vertex_half_edge(Point(10, 0), Point(0, 0), -1)); 2768 data.push_back(vertex_half_edge(Point(10, 0), Point(10, 10), -1)); 2769 data.push_back(vertex_half_edge(Point(10, 10), Point(10, 0), 1)); 2770 data.push_back(vertex_half_edge(Point(10, 10), Point(0, 10), 1)); 2771 polygon_sort(data.begin(), data.end()); 2772 pf.scan(polys, data.begin(), data.end()); 2773 stdcout << "result size: " << polys.size() << "\n"; 2774 for(std::size_t i = 0; i < polys.size(); ++i) { 2775 stdcout << polys[i] << "\n"; 2776 } 2777 stdcout << "done testing trapezoid formation\n"; 2778 return true; 2779 } 2780 template <typename stream_type> testTrapezoidArbitraryFormationP1(stream_type & stdcout)2781 static inline bool testTrapezoidArbitraryFormationP1(stream_type& stdcout) { 2782 stdcout << "testing trapezoid formation P1\n"; 2783 trapezoid_arbitrary_formation pf; 2784 std::vector<polygon_data<Unit> > polys; 2785 std::vector<vertex_half_edge> data; 2786 data.push_back(vertex_half_edge(Point(0, 0), Point(10, 10), 1)); 2787 data.push_back(vertex_half_edge(Point(0, 0), Point(0, 10), 1)); 2788 data.push_back(vertex_half_edge(Point(0, 10), Point(0, 0), -1)); 2789 data.push_back(vertex_half_edge(Point(0, 10), Point(10, 20), -1)); 2790 data.push_back(vertex_half_edge(Point(10, 10), Point(0, 0), -1)); 2791 data.push_back(vertex_half_edge(Point(10, 10), Point(10, 20), -1)); 2792 data.push_back(vertex_half_edge(Point(10, 20), Point(10, 10), 1)); 2793 data.push_back(vertex_half_edge(Point(10, 20), Point(0, 10), 1)); 2794 polygon_sort(data.begin(), data.end()); 2795 pf.scan(polys, data.begin(), data.end()); 2796 stdcout << "result size: " << polys.size() << "\n"; 2797 for(std::size_t i = 0; i < polys.size(); ++i) { 2798 stdcout << polys[i] << "\n"; 2799 } 2800 stdcout << "done testing trapezoid formation\n"; 2801 return true; 2802 } 2803 template <typename stream_type> testTrapezoidArbitraryFormationP2(stream_type & stdcout)2804 static inline bool testTrapezoidArbitraryFormationP2(stream_type& stdcout) { 2805 stdcout << "testing trapezoid formation P2\n"; 2806 trapezoid_arbitrary_formation pf; 2807 std::vector<polygon_data<Unit> > polys; 2808 std::vector<vertex_half_edge> data; 2809 data.push_back(vertex_half_edge(Point(-3, 1), Point(2, -4), 1)); 2810 data.push_back(vertex_half_edge(Point(-3, 1), Point(-2, 2), -1)); 2811 data.push_back(vertex_half_edge(Point(-2, 2), Point(2, 4), -1)); 2812 data.push_back(vertex_half_edge(Point(-2, 2), Point(-3, 1), 1)); 2813 data.push_back(vertex_half_edge(Point(2, -4), Point(-3, 1), -1)); 2814 data.push_back(vertex_half_edge(Point(2, -4), Point(2, 4), -1)); 2815 data.push_back(vertex_half_edge(Point(2, 4), Point(-2, 2), 1)); 2816 data.push_back(vertex_half_edge(Point(2, 4), Point(2, -4), 1)); 2817 polygon_sort(data.begin(), data.end()); 2818 pf.scan(polys, data.begin(), data.end()); 2819 stdcout << "result size: " << polys.size() << "\n"; 2820 for(std::size_t i = 0; i < polys.size(); ++i) { 2821 stdcout << polys[i] << "\n"; 2822 } 2823 stdcout << "done testing trapezoid formation\n"; 2824 return true; 2825 } 2826 2827 template <typename stream_type> testTrapezoidArbitraryFormationPolys(stream_type & stdcout)2828 static inline bool testTrapezoidArbitraryFormationPolys(stream_type& stdcout) { 2829 stdcout << "testing trapezoid formation polys\n"; 2830 trapezoid_arbitrary_formation pf; 2831 std::vector<polygon_with_holes_data<Unit> > polys; 2832 //trapezoid_arbitrary_formation pf2(true); 2833 //std::vector<polygon_with_holes_data<Unit> > polys2; 2834 std::vector<vertex_half_edge> data; 2835 data.push_back(vertex_half_edge(Point(0, 0), Point(100, 1), 1)); 2836 data.push_back(vertex_half_edge(Point(0, 0), Point(1, 100), -1)); 2837 data.push_back(vertex_half_edge(Point(1, 100), Point(0, 0), 1)); 2838 data.push_back(vertex_half_edge(Point(1, 100), Point(101, 101), -1)); 2839 data.push_back(vertex_half_edge(Point(100, 1), Point(0, 0), -1)); 2840 data.push_back(vertex_half_edge(Point(100, 1), Point(101, 101), 1)); 2841 data.push_back(vertex_half_edge(Point(101, 101), Point(100, 1), -1)); 2842 data.push_back(vertex_half_edge(Point(101, 101), Point(1, 100), 1)); 2843 2844 data.push_back(vertex_half_edge(Point(2, 2), Point(10, 2), -1)); 2845 data.push_back(vertex_half_edge(Point(2, 2), Point(2, 10), -1)); 2846 data.push_back(vertex_half_edge(Point(2, 10), Point(2, 2), 1)); 2847 data.push_back(vertex_half_edge(Point(2, 10), Point(10, 10), 1)); 2848 data.push_back(vertex_half_edge(Point(10, 2), Point(2, 2), 1)); 2849 data.push_back(vertex_half_edge(Point(10, 2), Point(10, 10), 1)); 2850 data.push_back(vertex_half_edge(Point(10, 10), Point(10, 2), -1)); 2851 data.push_back(vertex_half_edge(Point(10, 10), Point(2, 10), -1)); 2852 2853 data.push_back(vertex_half_edge(Point(2, 12), Point(10, 12), -1)); 2854 data.push_back(vertex_half_edge(Point(2, 12), Point(2, 22), -1)); 2855 data.push_back(vertex_half_edge(Point(2, 22), Point(2, 12), 1)); 2856 data.push_back(vertex_half_edge(Point(2, 22), Point(10, 22), 1)); 2857 data.push_back(vertex_half_edge(Point(10, 12), Point(2, 12), 1)); 2858 data.push_back(vertex_half_edge(Point(10, 12), Point(10, 22), 1)); 2859 data.push_back(vertex_half_edge(Point(10, 22), Point(10, 12), -1)); 2860 data.push_back(vertex_half_edge(Point(10, 22), Point(2, 22), -1)); 2861 2862 polygon_sort(data.begin(), data.end()); 2863 pf.scan(polys, data.begin(), data.end()); 2864 stdcout << "result size: " << polys.size() << "\n"; 2865 for(std::size_t i = 0; i < polys.size(); ++i) { 2866 stdcout << polys[i] << "\n"; 2867 } 2868 //pf2.scan(polys2, data.begin(), data.end()); 2869 //stdcout << "result size: " << polys2.size() << "\n"; 2870 //for(std::size_t i = 0; i < polys2.size(); ++i) { 2871 // stdcout << polys2[i] << "\n"; 2872 //} 2873 stdcout << "done testing trapezoid formation\n"; 2874 return true; 2875 } 2876 2877 template <typename stream_type> testTrapezoidArbitraryFormationSelfTouch1(stream_type & stdcout)2878 static inline bool testTrapezoidArbitraryFormationSelfTouch1(stream_type& stdcout) { 2879 stdcout << "testing trapezoid formation self touch 1\n"; 2880 trapezoid_arbitrary_formation pf; 2881 std::vector<polygon_data<Unit> > polys; 2882 std::vector<vertex_half_edge> data; 2883 data.push_back(vertex_half_edge(Point(0, 0), Point(10, 0), 1)); 2884 data.push_back(vertex_half_edge(Point(0, 0), Point(0, 10), 1)); 2885 2886 data.push_back(vertex_half_edge(Point(0, 10), Point(0, 0), -1)); 2887 data.push_back(vertex_half_edge(Point(0, 10), Point(5, 10), -1)); 2888 2889 data.push_back(vertex_half_edge(Point(10, 0), Point(0, 0), -1)); 2890 data.push_back(vertex_half_edge(Point(10, 0), Point(10, 5), -1)); 2891 2892 data.push_back(vertex_half_edge(Point(10, 5), Point(10, 0), 1)); 2893 data.push_back(vertex_half_edge(Point(10, 5), Point(5, 5), 1)); 2894 2895 data.push_back(vertex_half_edge(Point(5, 10), Point(5, 5), 1)); 2896 data.push_back(vertex_half_edge(Point(5, 10), Point(0, 10), 1)); 2897 2898 data.push_back(vertex_half_edge(Point(5, 2), Point(5, 5), -1)); 2899 data.push_back(vertex_half_edge(Point(5, 2), Point(7, 2), -1)); 2900 2901 data.push_back(vertex_half_edge(Point(5, 5), Point(5, 10), -1)); 2902 data.push_back(vertex_half_edge(Point(5, 5), Point(5, 2), 1)); 2903 data.push_back(vertex_half_edge(Point(5, 5), Point(10, 5), -1)); 2904 data.push_back(vertex_half_edge(Point(5, 5), Point(7, 2), 1)); 2905 2906 data.push_back(vertex_half_edge(Point(7, 2), Point(5, 5), -1)); 2907 data.push_back(vertex_half_edge(Point(7, 2), Point(5, 2), 1)); 2908 2909 polygon_sort(data.begin(), data.end()); 2910 pf.scan(polys, data.begin(), data.end()); 2911 stdcout << "result size: " << polys.size() << "\n"; 2912 for(std::size_t i = 0; i < polys.size(); ++i) { 2913 stdcout << polys[i] << "\n"; 2914 } 2915 stdcout << "done testing trapezoid formation\n"; 2916 return true; 2917 } 2918 }; 2919 2920 template <typename T> 2921 struct PolyLineArbitraryByConcept<T, polygon_with_holes_concept> { typedef poly_line_arbitrary_polygon_data<T> type; }; 2922 template <typename T> 2923 struct PolyLineArbitraryByConcept<T, polygon_concept> { typedef poly_line_arbitrary_hole_data<T> type; }; 2924 2925 template <typename T> 2926 struct geometry_concept<poly_line_arbitrary_polygon_data<T> > { typedef polygon_45_with_holes_concept type; }; 2927 template <typename T> 2928 struct geometry_concept<poly_line_arbitrary_hole_data<T> > { typedef polygon_45_concept type; }; 2929 } 2930 } 2931 #endif 2932