Mercurial > hg > vamp-build-and-test

annotate DEPENDENCIES/generic/include/boost/polygon/segment_concept.hpp @ 133:4acb5d8d80b6 tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Don't fail environmental check if README.md exists (but .txt and no-suffix don't)
author Chris Cannam
date Tue, 30 Jul 2019 12:25:44 +0100
parents 2665513ce2d3
children
rev   line source
Chris@16 1 // Boost.Polygon library segment_concept.hpp header file
Chris@16 2
Chris@16 3 // Copyright (c) Intel Corporation 2008.
Chris@16 4 // Copyright (c) 2008-2012 Simonson Lucanus.
Chris@16 5 // Copyright (c) 2012-2012 Andrii Sydorchuk.
Chris@16 6
Chris@16 7 // See http://www.boost.org for updates, documentation, and revision history.
Chris@16 8 // Use, modification and distribution is subject to the Boost Software License,
Chris@16 9 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
Chris@16 10 // http://www.boost.org/LICENSE_1_0.txt)
Chris@16 11
Chris@16 12 #ifndef BOOST_POLYGON_SEGMENT_CONCEPT_HPP
Chris@16 13 #define BOOST_POLYGON_SEGMENT_CONCEPT_HPP
Chris@16 14
Chris@16 15 #include "isotropy.hpp"
Chris@16 16 #include "segment_traits.hpp"
Chris@16 17 #include "rectangle_concept.hpp"
Chris@16 18
Chris@16 19 namespace boost {
Chris@16 20 namespace polygon {
Chris@16 21
Chris@16 22 struct segment_concept {};
Chris@16 23
Chris@16 24 template <typename ConceptType>
Chris@16 25 struct is_segment_concept {
Chris@16 26 typedef gtl_no type;
Chris@16 27 };
Chris@16 28
Chris@16 29 template <>
Chris@16 30 struct is_segment_concept<segment_concept> {
Chris@16 31 typedef gtl_yes type;
Chris@16 32 };
Chris@16 33
Chris@16 34 template <typename ConceptType>
Chris@16 35 struct is_mutable_segment_concept {
Chris@16 36 typedef gtl_no type;
Chris@16 37 };
Chris@16 38
Chris@16 39 template <>
Chris@16 40 struct is_mutable_segment_concept<segment_concept> {
Chris@16 41 typedef gtl_yes type;
Chris@16 42 };
Chris@16 43
Chris@16 44 template <typename GeometryType, typename BoolType>
Chris@16 45 struct segment_distance_type_by_concept {
Chris@16 46 typedef void type;
Chris@16 47 };
Chris@16 48
Chris@16 49 template <typename GeometryType>
Chris@16 50 struct segment_distance_type_by_concept<GeometryType, gtl_yes> {
Chris@16 51 typedef typename coordinate_traits<
Chris@16 52 typename segment_traits<GeometryType>::coordinate_type
Chris@16 53 >::coordinate_distance type;
Chris@16 54 };
Chris@16 55
Chris@16 56 template <typename GeometryType>
Chris@16 57 struct segment_distance_type {
Chris@16 58 typedef typename segment_distance_type_by_concept<
Chris@16 59 GeometryType,
Chris@16 60 typename is_segment_concept<
Chris@16 61 typename geometry_concept<GeometryType>::type
Chris@16 62 >::type
Chris@16 63 >::type type;
Chris@16 64 };
Chris@16 65
Chris@16 66 template <typename GeometryType, typename BoolType>
Chris@16 67 struct segment_point_type_by_concept {
Chris@16 68 typedef void type;
Chris@16 69 };
Chris@16 70
Chris@16 71 template <typename GeometryType>
Chris@16 72 struct segment_point_type_by_concept<GeometryType, gtl_yes> {
Chris@16 73 typedef typename segment_traits<GeometryType>::point_type type;
Chris@16 74 };
Chris@16 75
Chris@16 76 template <typename GeometryType>
Chris@16 77 struct segment_point_type {
Chris@16 78 typedef typename segment_point_type_by_concept<
Chris@16 79 GeometryType,
Chris@16 80 typename is_segment_concept<
Chris@16 81 typename geometry_concept<GeometryType>::type
Chris@16 82 >::type
Chris@16 83 >::type type;
Chris@16 84 };
Chris@16 85
Chris@16 86 template <typename GeometryType, typename BoolType>
Chris@16 87 struct segment_coordinate_type_by_concept {
Chris@16 88 typedef void type;
Chris@16 89 };
Chris@16 90
Chris@16 91 template <typename GeometryType>
Chris@16 92 struct segment_coordinate_type_by_concept<GeometryType, gtl_yes> {
Chris@16 93 typedef typename segment_traits<GeometryType>::coordinate_type type;
Chris@16 94 };
Chris@16 95
Chris@16 96 template <typename GeometryType>
Chris@16 97 struct segment_coordinate_type {
Chris@16 98 typedef typename segment_coordinate_type_by_concept<
Chris@16 99 GeometryType,
Chris@16 100 typename is_segment_concept<
Chris@16 101 typename geometry_concept<GeometryType>::type
Chris@16 102 >::type
Chris@16 103 >::type type;
Chris@16 104 };
Chris@16 105
Chris@16 106 struct y_s_get : gtl_yes {};
Chris@16 107
Chris@16 108 template <typename Segment>
Chris@16 109 typename enable_if<
Chris@16 110 typename gtl_and<
Chris@16 111 y_s_get,
Chris@16 112 typename is_segment_concept<
Chris@16 113 typename geometry_concept<Segment>::type
Chris@16 114 >::type
Chris@16 115 >::type,
Chris@16 116 typename segment_point_type<Segment>::type>::type
Chris@16 117 get(const Segment& segment, direction_1d dir) {
Chris@16 118 return segment_traits<Segment>::get(segment, dir);
Chris@16 119 }
Chris@16 120
Chris@16 121 struct y_s_set : gtl_yes {};
Chris@16 122
Chris@16 123 template <typename Segment, typename Point>
Chris@16 124 typename enable_if<
Chris@16 125 typename gtl_and_3<
Chris@16 126 y_s_set,
Chris@16 127 typename is_mutable_segment_concept<
Chris@16 128 typename geometry_concept<Segment>::type
Chris@16 129 >::type,
Chris@16 130 typename is_point_concept<
Chris@16 131 typename geometry_concept<Point>::type
Chris@16 132 >::type
Chris@16 133 >::type,
Chris@16 134 void>::type set(Segment& segment, direction_1d dir, const Point& point) {
Chris@16 135 segment_mutable_traits<Segment>::set(segment, dir, point);
Chris@16 136 }
Chris@16 137
Chris@16 138 struct y_s_construct : gtl_yes {};
Chris@16 139
Chris@16 140 template <typename Segment, typename Point1, typename Point2>
Chris@16 141 typename enable_if<
Chris@16 142 typename gtl_and_4<
Chris@16 143 y_s_construct,
Chris@16 144 typename is_mutable_segment_concept<
Chris@16 145 typename geometry_concept<Segment>::type
Chris@16 146 >::type,
Chris@16 147 typename is_point_concept<
Chris@16 148 typename geometry_concept<Point1>::type
Chris@16 149 >::type,
Chris@16 150 typename is_point_concept<
Chris@16 151 typename geometry_concept<Point2>::type
Chris@16 152 >::type
Chris@16 153 >::type,
Chris@16 154 Segment>::type construct(const Point1& low, const Point2& high) {
Chris@16 155 return segment_mutable_traits<Segment>::construct(low, high);
Chris@16 156 }
Chris@16 157
Chris@16 158 struct y_s_copy_construct : gtl_yes {};
Chris@16 159
Chris@16 160 template <typename Segment1, typename Segment2>
Chris@16 161 typename enable_if<
Chris@16 162 typename gtl_and_3<
Chris@16 163 y_s_copy_construct,
Chris@16 164 typename is_mutable_segment_concept<
Chris@16 165 typename geometry_concept<Segment1>::type
Chris@16 166 >::type,
Chris@16 167 typename is_segment_concept<
Chris@16 168 typename geometry_concept<Segment2>::type
Chris@16 169 >::type
Chris@16 170 >::type,
Chris@16 171 Segment1>::type copy_construct(const Segment2& segment) {
Chris@16 172 return construct<Segment1>(get(segment, LOW), get(segment, HIGH));
Chris@16 173 }
Chris@16 174
Chris@16 175 struct y_s_assign : gtl_yes {};
Chris@16 176
Chris@16 177 template <typename Segment1, typename Segment2>
Chris@16 178 typename enable_if<
Chris@16 179 typename gtl_and_3<
Chris@16 180 y_s_assign,
Chris@16 181 typename is_mutable_segment_concept<
Chris@16 182 typename geometry_concept<Segment1>::type
Chris@16 183 >::type,
Chris@16 184 typename is_segment_concept<
Chris@16 185 typename geometry_concept<Segment2>::type
Chris@16 186 >::type
Chris@16 187 >::type,
Chris@16 188 Segment1>::type& assign(Segment1& segment1, const Segment2& segment2) {
Chris@16 189 return segment1 = copy_construct<Segment1>(segment2);
Chris@16 190 }
Chris@16 191
Chris@16 192 struct y_s_equivalence : gtl_yes {};
Chris@16 193
Chris@16 194 template <typename Segment1, typename Segment2>
Chris@16 195 typename enable_if<
Chris@16 196 typename gtl_and_3<
Chris@16 197 y_s_equivalence,
Chris@16 198 typename is_segment_concept<
Chris@16 199 typename geometry_concept<Segment1>::type
Chris@16 200 >::type,
Chris@16 201 typename is_segment_concept<
Chris@16 202 typename geometry_concept<Segment2>::type
Chris@16 203 >::type
Chris@16 204 >::type,
Chris@16 205 bool>::type equivalence(const Segment1& segment1, const Segment2& segment2) {
Chris@16 206 return get(segment1, LOW) == get(segment2, LOW) &&
Chris@16 207 get(segment1, HIGH) == get(segment2, HIGH);
Chris@16 208 }
Chris@16 209
Chris@16 210 struct y_s_low : gtl_yes {};
Chris@16 211
Chris@16 212 template <typename Segment>
Chris@16 213 typename enable_if<
Chris@16 214 typename gtl_and<
Chris@16 215 y_s_low,
Chris@16 216 typename is_segment_concept<
Chris@16 217 typename geometry_concept<Segment>::type
Chris@16 218 >::type
Chris@16 219 >::type,
Chris@16 220 typename segment_point_type<Segment>::type>::type low(const Segment& segment) {
Chris@16 221 return get(segment, LOW);
Chris@16 222 }
Chris@16 223
Chris@16 224 struct y_s_high : gtl_yes {};
Chris@16 225
Chris@16 226 template <typename Segment>
Chris@16 227 typename enable_if<
Chris@16 228 typename gtl_and<
Chris@16 229 y_s_high,
Chris@16 230 typename is_segment_concept<
Chris@16 231 typename geometry_concept<Segment>::type
Chris@16 232 >::type
Chris@16 233 >::type,
Chris@16 234 typename segment_point_type<Segment>::type>::type high(const Segment& segment) {
Chris@16 235 return get(segment, HIGH);
Chris@16 236 }
Chris@16 237
Chris@16 238 struct y_s_center : gtl_yes {};
Chris@16 239
Chris@16 240 template <typename Segment>
Chris@16 241 typename enable_if<
Chris@16 242 typename gtl_and<
Chris@16 243 y_s_center,
Chris@16 244 typename is_segment_concept<
Chris@16 245 typename geometry_concept<Segment>::type
Chris@16 246 >::type
Chris@16 247 >::type,
Chris@16 248 typename segment_point_type<Segment>::type>::type
Chris@16 249 center(const Segment& segment) {
Chris@16 250 return construct<typename segment_point_type<Segment>::type>(
Chris@16 251 (x(high(segment)) + x(low(segment)))/2,
Chris@16 252 (y(high(segment)) + y(low(segment)))/2);
Chris@16 253 }
Chris@16 254
Chris@16 255 struct y_s_low2 : gtl_yes {};
Chris@16 256
Chris@16 257 template <typename Segment, typename Point>
Chris@16 258 typename enable_if<
Chris@16 259 typename gtl_and_3<
Chris@16 260 y_s_low2,
Chris@16 261 typename is_mutable_segment_concept<
Chris@16 262 typename geometry_concept<Segment>::type
Chris@16 263 >::type,
Chris@16 264 typename is_point_concept<
Chris@16 265 typename geometry_concept<Point>::type
Chris@16 266 >::type
Chris@16 267 >::type,
Chris@16 268 void>::type low(Segment& segment, const Point& point) {
Chris@16 269 set(segment, LOW, point);
Chris@16 270 }
Chris@16 271
Chris@16 272 struct y_s_high2 : gtl_yes {};
Chris@16 273
Chris@16 274 template <typename Segment, typename Point>
Chris@16 275 typename enable_if<
Chris@16 276 typename gtl_and_3<
Chris@16 277 y_s_high2,
Chris@16 278 typename is_mutable_segment_concept<
Chris@16 279 typename geometry_concept<Segment>::type
Chris@16 280 >::type,
Chris@16 281 typename is_point_concept<
Chris@16 282 typename geometry_concept<Point>::type
Chris@16 283 >::type
Chris@16 284 >::type,
Chris@16 285 void>::type high(Segment& segment, const Point& point) {
Chris@16 286 set(segment, HIGH, point);
Chris@16 287 }
Chris@16 288
Chris@16 289 struct y_s_orientation1 : gtl_yes {};
Chris@16 290
Chris@16 291 // -1 for CW, 0 for collinear and 1 for CCW.
Chris@16 292 template <typename Segment1, typename Segment2>
Chris@16 293 typename enable_if<
Chris@16 294 typename gtl_and_3<
Chris@16 295 y_s_orientation1,
Chris@16 296 typename is_segment_concept<
Chris@16 297 typename geometry_concept<Segment1>::type
Chris@16 298 >::type,
Chris@16 299 typename is_segment_concept<
Chris@16 300 typename geometry_concept<Segment2>::type
Chris@16 301 >::type
Chris@16 302 >::type,
Chris@16 303 int>::type orientation(const Segment1& segment1, const Segment2& segment2) {
Chris@16 304 typedef typename coordinate_traits<
Chris@16 305 typename segment_traits<Segment1>::coordinate_type
Chris@16 306 >::manhattan_area_type int_x2;
Chris@16 307 typedef typename coordinate_traits<
Chris@16 308 typename segment_traits<Segment1>::coordinate_type
Chris@16 309 >::unsigned_area_type uint_x2;
Chris@16 310 int_x2 a1 = (int_x2)x(high(segment1)) - (int_x2)x(low(segment1));
Chris@16 311 int_x2 b1 = (int_x2)y(high(segment1)) - (int_x2)y(low(segment1));
Chris@16 312 int_x2 a2 = (int_x2)x(high(segment2)) - (int_x2)x(low(segment2));
Chris@16 313 int_x2 b2 = (int_x2)y(high(segment2)) - (int_x2)y(low(segment2));
Chris@16 314
Chris@16 315 int sign1 = 0;
Chris@16 316 int sign2 = 0;
Chris@16 317 if (a1 && b2)
Chris@16 318 sign1 = ((a1 > 0) ^ (b2 > 0)) ? -1 : 1;
Chris@16 319 if (a2 && b1)
Chris@16 320 sign2 = ((a2 > 0) ^ (b1 > 0)) ? -1 : 1;
Chris@16 321
Chris@16 322 if (sign1 != sign2)
Chris@16 323 return (sign1 < sign2) ? -1 : 1;
Chris@16 324 uint_x2 a3 = (uint_x2)(a1 < 0 ? -a1 : a1) * (uint_x2)(b2 < 0 ? -b2 : b2);
Chris@16 325 uint_x2 b3 = (uint_x2)(b1 < 0 ? -b1 : b1) * (uint_x2)(a2 < 0 ? -a2 : a2);
Chris@16 326 if (a3 == b3)
Chris@16 327 return 0;
Chris@16 328 return ((a3 < b3) ^ (sign1 == 1)) ? 1 : -1;
Chris@16 329 }
Chris@16 330
Chris@16 331 struct y_s_orientation2 : gtl_yes {};
Chris@16 332
Chris@16 333 // -1 for right, 0 for collinear and 1 for left.
Chris@16 334 template <typename Segment, typename Point>
Chris@16 335 typename enable_if<
Chris@16 336 typename gtl_and_3<
Chris@16 337 y_s_orientation2,
Chris@16 338 typename is_segment_concept<
Chris@16 339 typename geometry_concept<Segment>::type
Chris@16 340 >::type,
Chris@16 341 typename is_point_concept<
Chris@16 342 typename geometry_concept<Point>::type
Chris@16 343 >::type
Chris@16 344 >::type,
Chris@16 345 int>::type orientation(const Segment& segment, const Point& point) {
Chris@16 346 Segment segment2 = construct<Segment>(high(segment), point);
Chris@16 347 return orientation(segment, segment2);
Chris@16 348 }
Chris@16 349
Chris@16 350 struct y_s_contains : gtl_yes {};
Chris@16 351
Chris@16 352 template <typename Segment, typename Point>
Chris@16 353 typename enable_if<
Chris@16 354 typename gtl_and_3<
Chris@16 355 y_s_contains,
Chris@16 356 typename is_segment_concept<
Chris@16 357 typename geometry_concept<Segment>::type
Chris@16 358 >::type,
Chris@16 359 typename is_point_concept<
Chris@16 360 typename geometry_concept<Point>::type
Chris@16 361 >::type
Chris@16 362 >::type,
Chris@16 363 bool>::type contains(const Segment& segment,
Chris@16 364 const Point& point, bool consider_touch = true ) {
Chris@16 365 if (orientation(segment, point))
Chris@16 366 return false;
Chris@16 367 rectangle_data<typename segment_coordinate_type<Segment>::type> rect;
Chris@16 368 set_points(rect, low(segment), high(segment));
Chris@16 369 if (!contains(rect, point, true))
Chris@16 370 return false;
Chris@16 371 if (!consider_touch &&
Chris@16 372 (equivalence(low(segment), point) ||
Chris@16 373 equivalence(high(segment), point)))
Chris@16 374 return false;
Chris@16 375 return true;
Chris@16 376 }
Chris@16 377
Chris@16 378 struct y_s_contains2 : gtl_yes {};
Chris@16 379
Chris@16 380 template <typename Segment1, typename Segment2>
Chris@16 381 typename enable_if<
Chris@16 382 typename gtl_and_3<
Chris@16 383 y_s_contains2,
Chris@16 384 typename is_segment_concept<
Chris@16 385 typename geometry_concept<Segment1>::type
Chris@16 386 >::type,
Chris@16 387 typename is_segment_concept<
Chris@16 388 typename geometry_concept<Segment2>::type
Chris@16 389 >::type
Chris@16 390 >::type,
Chris@16 391 bool>::type contains(const Segment1& segment1,
Chris@16 392 const Segment2& segment2, bool consider_touch = true) {
Chris@16 393 return contains(segment1, get(segment2, LOW), consider_touch) &&
Chris@16 394 contains(segment1, get(segment2, HIGH), consider_touch);
Chris@16 395 }
Chris@16 396
Chris@16 397 struct y_s_length : gtl_yes {};
Chris@16 398
Chris@16 399 template <typename Segment>
Chris@16 400 typename enable_if<
Chris@16 401 typename gtl_and<
Chris@16 402 y_s_length,
Chris@16 403 typename is_segment_concept<
Chris@16 404 typename geometry_concept<Segment>::type
Chris@16 405 >::type
Chris@16 406 >::type,
Chris@16 407 typename segment_distance_type<Segment>::type>::type
Chris@16 408 length(const Segment& segment) {
Chris@16 409 return euclidean_distance(low(segment), high(segment));
Chris@16 410 }
Chris@16 411
Chris@16 412 struct y_s_scale_up : gtl_yes {};
Chris@16 413
Chris@16 414 template <typename Segment>
Chris@16 415 typename enable_if<
Chris@16 416 typename gtl_and<
Chris@16 417 y_s_scale_up,
Chris@16 418 typename is_mutable_segment_concept<
Chris@16 419 typename geometry_concept<Segment>::type
Chris@16 420 >::type
Chris@16 421 >::type,
Chris@16 422 Segment>::type& scale_up(Segment& segment,
Chris@16 423 typename coordinate_traits<
Chris@16 424 typename segment_coordinate_type<Segment>::type
Chris@16 425 >::unsigned_area_type factor) {
Chris@16 426 typename segment_point_type<Segment>::type l = low(segment);
Chris@16 427 typename segment_point_type<Segment>::type h = high(segment);
Chris@16 428 low(segment, scale_up(l, factor));
Chris@16 429 high(segment, scale_up(h, factor));
Chris@16 430 return segment;
Chris@16 431 }
Chris@16 432
Chris@16 433 struct y_s_scale_down : gtl_yes {};
Chris@16 434
Chris@16 435 template <typename Segment>
Chris@16 436 typename enable_if<
Chris@16 437 typename gtl_and<
Chris@16 438 y_s_scale_down,
Chris@16 439 typename is_mutable_segment_concept<
Chris@16 440 typename geometry_concept<Segment>::type
Chris@16 441 >::type
Chris@16 442 >::type,
Chris@16 443 Segment>::type& scale_down(Segment& segment,
Chris@16 444 typename coordinate_traits<
Chris@16 445 typename segment_coordinate_type<Segment>::type
Chris@16 446 >::unsigned_area_type factor) {
Chris@16 447 typename segment_point_type<Segment>::type l = low(segment);
Chris@16 448 typename segment_point_type<Segment>::type h = high(segment);
Chris@16 449 low(segment, scale_down(l, factor));
Chris@16 450 high(segment, scale_down(h, factor));
Chris@16 451 return segment;
Chris@16 452 }
Chris@16 453
Chris@16 454 struct y_s_scale : gtl_yes {};
Chris@16 455
Chris@16 456 template <typename Segment, typename Scale>
Chris@16 457 typename enable_if<
Chris@16 458 typename gtl_and<
Chris@16 459 y_s_scale,
Chris@16 460 typename is_mutable_segment_concept<
Chris@16 461 typename geometry_concept<Segment>::type
Chris@16 462 >::type
Chris@16 463 >::type,
Chris@16 464 Segment>::type& scale(Segment& segment, const Scale& sc) {
Chris@16 465 typename segment_point_type<Segment>::type l = low(segment);
Chris@16 466 typename segment_point_type<Segment>::type h = high(segment);
Chris@16 467 low(segment, scale(l, sc));
Chris@16 468 high(segment, scale(h, sc));
Chris@16 469 return segment;
Chris@16 470 }
Chris@16 471
Chris@16 472 struct y_s_transform : gtl_yes {};
Chris@16 473
Chris@16 474 template <typename Segment, typename Transform>
Chris@16 475 typename enable_if<
Chris@16 476 typename gtl_and<
Chris@16 477 y_s_transform,
Chris@16 478 typename is_mutable_segment_concept<
Chris@16 479 typename geometry_concept<Segment>::type
Chris@16 480 >::type
Chris@16 481 >::type,
Chris@16 482 Segment>::type& transform(Segment& segment, const Transform& tr) {
Chris@16 483 typename segment_point_type<Segment>::type l = low(segment);
Chris@16 484 typename segment_point_type<Segment>::type h = high(segment);
Chris@16 485 low(segment, transform(l, tr));
Chris@16 486 high(segment, transform(h, tr));
Chris@16 487 return segment;
Chris@16 488 }
Chris@16 489
Chris@16 490 struct y_s_move : gtl_yes {};
Chris@16 491
Chris@16 492 template <typename Segment>
Chris@16 493 typename enable_if<
Chris@16 494 typename gtl_and<
Chris@16 495 y_s_move,
Chris@16 496 typename is_mutable_segment_concept<
Chris@16 497 typename geometry_concept<Segment>::type
Chris@16 498 >::type
Chris@16 499 >::type,
Chris@16 500 Segment>::type& move(Segment& segment, orientation_2d orient,
Chris@16 501 typename segment_coordinate_type<Segment>::type displacement) {
Chris@16 502 typename segment_point_type<Segment>::type l = low(segment);
Chris@16 503 typename segment_point_type<Segment>::type h = high(segment);
Chris@16 504 low(segment, move(l, orient, displacement));
Chris@16 505 high(segment, move(h, orient, displacement));
Chris@16 506 return segment;
Chris@16 507 }
Chris@16 508
Chris@16 509 struct y_s_convolve : gtl_yes {};
Chris@16 510
Chris@16 511 template <typename Segment, typename Point>
Chris@16 512 typename enable_if<
Chris@16 513 typename gtl_and_3<
Chris@16 514 y_s_convolve,
Chris@16 515 typename is_mutable_segment_concept<
Chris@16 516 typename geometry_concept<Segment>::type
Chris@16 517 >::type,
Chris@16 518 typename is_point_concept<
Chris@16 519 typename geometry_concept<Point>::type
Chris@16 520 >::type
Chris@16 521 >::type,
Chris@16 522 Segment>::type& convolve(Segment& segment, const Point& point) {
Chris@16 523 typename segment_point_type<Segment>::type l = low(segment);
Chris@16 524 typename segment_point_type<Segment>::type h = high(segment);
Chris@16 525 low(segment, convolve(l, point));
Chris@16 526 high(segment, convolve(h, point));
Chris@16 527 return segment;
Chris@16 528 }
Chris@16 529
Chris@16 530 struct y_s_deconvolve : gtl_yes {};
Chris@16 531
Chris@16 532 template <typename Segment, typename Point>
Chris@16 533 typename enable_if<
Chris@16 534 typename gtl_and_3<
Chris@16 535 y_s_deconvolve,
Chris@16 536 typename is_mutable_segment_concept<
Chris@16 537 typename geometry_concept<Segment>::type
Chris@16 538 >::type,
Chris@16 539 typename is_point_concept<
Chris@16 540 typename geometry_concept<Point>::type
Chris@16 541 >::type
Chris@16 542 >::type,
Chris@16 543 Segment>::type& deconvolve(Segment& segment, const Point& point) {
Chris@16 544 typename segment_point_type<Segment>::type l = low(segment);
Chris@16 545 typename segment_point_type<Segment>::type h = high(segment);
Chris@16 546 low(segment, deconvolve(l, point));
Chris@16 547 high(segment, deconvolve(h, point));
Chris@16 548 return segment;
Chris@16 549 }
Chris@16 550
Chris@16 551 struct y_s_abuts1 : gtl_yes {};
Chris@16 552
Chris@16 553 template <typename Segment1, typename Segment2>
Chris@16 554 typename enable_if<
Chris@16 555 typename gtl_and_3<
Chris@16 556 y_s_abuts1,
Chris@16 557 typename is_segment_concept<
Chris@16 558 typename geometry_concept<Segment1>::type
Chris@16 559 >::type,
Chris@16 560 typename is_segment_concept<
Chris@16 561 typename geometry_concept<Segment2>::type
Chris@16 562 >::type
Chris@16 563 >::type,
Chris@16 564 bool>::type abuts(const Segment1& segment1,
Chris@16 565 const Segment2& segment2, direction_1d dir) {
Chris@16 566 return dir.to_int() ? equivalence(low(segment2) , high(segment1)) :
Chris@16 567 equivalence(low(segment1) , high(segment2));
Chris@16 568 }
Chris@16 569
Chris@16 570 struct y_s_abuts2 : gtl_yes {};
Chris@16 571
Chris@16 572 template <typename Segment1, typename Segment2>
Chris@16 573 typename enable_if<
Chris@16 574 typename gtl_and_3<
Chris@16 575 y_s_abuts2,
Chris@16 576 typename is_segment_concept<
Chris@16 577 typename geometry_concept<Segment1>::type
Chris@16 578 >::type,
Chris@16 579 typename is_segment_concept<
Chris@16 580 typename geometry_concept<Segment2>::type
Chris@16 581 >::type
Chris@16 582 >::type,
Chris@16 583 bool>::type abuts(const Segment1& segment1, const Segment2& segment2) {
Chris@16 584 return abuts(segment1, segment2, HIGH) || abuts(segment1, segment2, LOW);
Chris@16 585 }
Chris@16 586
Chris@16 587 struct y_s_e_intersects : gtl_yes {};
Chris@16 588
Chris@16 589 template <typename Segment1, typename Segment2>
Chris@16 590 typename enable_if<
Chris@16 591 typename gtl_and_3<
Chris@16 592 y_s_e_intersects,
Chris@16 593 typename is_segment_concept<
Chris@16 594 typename geometry_concept<Segment1>::type
Chris@16 595 >::type,
Chris@16 596 typename is_segment_concept<
Chris@16 597 typename geometry_concept<Segment2>::type
Chris@16 598 >::type
Chris@16 599 >::type,
Chris@16 600 bool
Chris@16 601 >::type intersects(const Segment1& segment1, const Segment2& segment2,
Chris@16 602 bool consider_touch = true) {
Chris@16 603 rectangle_data<typename segment_coordinate_type<Segment1>::type> rect1, rect2;
Chris@16 604 set_points(rect1, low(segment1), high(segment1));
Chris@16 605 set_points(rect2, low(segment2), high(segment2));
Chris@16 606 // Check if axis-parallel rectangles containing segments intersect.
Chris@16 607 if (!intersects(rect1, rect2, true))
Chris@16 608 return false;
Chris@16 609 int or1_1 = orientation(segment1, low(segment2));
Chris@16 610 int or1_2 = orientation(segment1, high(segment2));
Chris@16 611 if (or1_1 * or1_2 > 0)
Chris@16 612 return false;
Chris@16 613 int or2_1 = orientation(segment2, low(segment1));
Chris@16 614 int or2_2 = orientation(segment2, high(segment1));
Chris@16 615 if (or2_1 * or2_2 > 0)
Chris@16 616 return false;
Chris@16 617 if (consider_touch || (or1_1 && or1_2) || (or2_1 && or2_2))
Chris@16 618 return true;
Chris@16 619 if (or1_1 || or1_2)
Chris@16 620 return false;
Chris@16 621 return intersects(vertical(rect1), vertical(rect2), false) ||
Chris@16 622 intersects(horizontal(rect1), horizontal(rect2), false);
Chris@16 623 }
Chris@16 624
Chris@16 625 struct y_s_e_dist : gtl_yes {};
Chris@16 626
Chris@16 627 template <typename Segment, typename Point>
Chris@16 628 typename enable_if<
Chris@16 629 typename gtl_and_3<
Chris@16 630 y_s_e_dist,
Chris@16 631 typename is_segment_concept<
Chris@16 632 typename geometry_concept<Segment>::type
Chris@16 633 >::type,
Chris@16 634 typename is_point_concept<
Chris@16 635 typename geometry_concept<Point>::type
Chris@16 636 >::type
Chris@16 637 >::type,
Chris@16 638 typename segment_distance_type<Segment>::type>::type
Chris@16 639 euclidean_distance(const Segment& segment, const Point& point) {
Chris@16 640 typedef typename segment_distance_type<Segment>::type Unit;
Chris@16 641 Unit x1 = x(low(segment));
Chris@16 642 Unit y1 = y(low(segment));
Chris@16 643 Unit x2 = x(high(segment));
Chris@16 644 Unit y2 = y(high(segment));
Chris@16 645 Unit X = x(point);
Chris@16 646 Unit Y = y(point);
Chris@16 647 Unit A = X - x1;
Chris@16 648 Unit B = Y - y1;
Chris@16 649 Unit C = x2 - x1;
Chris@16 650 Unit D = y2 - y1;
Chris@16 651 Unit param = (A * C + B * D);
Chris@16 652 Unit length_sq = C * C + D * D;
Chris@16 653 if (param > length_sq) {
Chris@16 654 return euclidean_distance(high(segment), point);
Chris@16 655 } else if (param < 0.0) {
Chris@16 656 return euclidean_distance(low(segment), point);
Chris@16 657 }
Chris@16 658 if (length_sq == 0.0)
Chris@16 659 return 0.0;
Chris@16 660 Unit denom = std::sqrt(length_sq);
Chris@16 661 Unit result = (A * D - C * B) / denom;
Chris@16 662 return (result < 0.0) ? -result : result;
Chris@16 663 }
Chris@16 664
Chris@16 665 struct y_s_e_dist2 : gtl_yes {};
Chris@16 666
Chris@16 667 template <typename Segment1, typename Segment2>
Chris@16 668 typename enable_if<
Chris@16 669 typename gtl_and_3<
Chris@16 670 y_s_e_dist2,
Chris@16 671 typename is_segment_concept<
Chris@16 672 typename geometry_concept<Segment1>::type
Chris@16 673 >::type,
Chris@16 674 typename is_segment_concept<
Chris@16 675 typename geometry_concept<Segment2>::type
Chris@16 676 >::type
Chris@16 677 >::type,
Chris@16 678 typename segment_distance_type<Segment1>::type>::type
Chris@16 679 euclidean_distance(const Segment1& segment1, const Segment2& segment2) {
Chris@16 680 if (intersects(segment1, segment2))
Chris@16 681 return 0.0;
Chris@16 682 typename segment_distance_type<Segment1>::type
Chris@16 683 result1 = euclidean_distance(segment1, low(segment2)),
Chris@16 684 result2 = euclidean_distance(segment1, high(segment2)),
Chris@16 685 result3 = euclidean_distance(segment2, low(segment1)),
Chris@16 686 result4 = euclidean_distance(segment2, high(segment1));
Chris@16 687 if (result2 < result1)
Chris@16 688 result1 = result2;
Chris@16 689 if (result4 < result3)
Chris@16 690 result3 = result4;
Chris@16 691 return (result1 < result3) ? result1 : result3;
Chris@16 692 }
Chris@16 693 } // polygon
Chris@16 694 } // boost
Chris@16 695
Chris@16 696 #endif // BOOST_POLYGON_SEGMENT_CONCEPT_HPP