Chris@16: // Boost.Polygon library segment_concept.hpp header file
Chris@16: 
Chris@16: // Copyright (c) Intel Corporation 2008.
Chris@16: // Copyright (c) 2008-2012 Simonson Lucanus.
Chris@16: // Copyright (c) 2012-2012 Andrii Sydorchuk.
Chris@16: 
Chris@16: // See http://www.boost.org for updates, documentation, and revision history.
Chris@16: // Use, modification and distribution is subject to the Boost Software License,
Chris@16: // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: #ifndef BOOST_POLYGON_SEGMENT_CONCEPT_HPP
Chris@16: #define BOOST_POLYGON_SEGMENT_CONCEPT_HPP
Chris@16: 
Chris@16: #include "isotropy.hpp"
Chris@16: #include "segment_traits.hpp"
Chris@16: #include "rectangle_concept.hpp"
Chris@16: 
Chris@16: namespace boost {
Chris@16: namespace polygon {
Chris@16: 
Chris@16: struct segment_concept {};
Chris@16: 
Chris@16: template <typename ConceptType>
Chris@16: struct is_segment_concept {
Chris@16:   typedef gtl_no type;
Chris@16: };
Chris@16: 
Chris@16: template <>
Chris@16: struct is_segment_concept<segment_concept> {
Chris@16:   typedef gtl_yes type;
Chris@16: };
Chris@16: 
Chris@16: template <typename ConceptType>
Chris@16: struct is_mutable_segment_concept {
Chris@16:   typedef gtl_no type;
Chris@16: };
Chris@16: 
Chris@16: template <>
Chris@16: struct is_mutable_segment_concept<segment_concept> {
Chris@16:   typedef gtl_yes type;
Chris@16: };
Chris@16: 
Chris@16: template <typename GeometryType, typename BoolType>
Chris@16: struct segment_distance_type_by_concept {
Chris@16:   typedef void type;
Chris@16: };
Chris@16: 
Chris@16: template <typename GeometryType>
Chris@16: struct segment_distance_type_by_concept<GeometryType, gtl_yes> {
Chris@16:   typedef typename coordinate_traits<
Chris@16:     typename segment_traits<GeometryType>::coordinate_type
Chris@16:   >::coordinate_distance type;
Chris@16: };
Chris@16: 
Chris@16: template <typename GeometryType>
Chris@16: struct segment_distance_type {
Chris@16:   typedef typename segment_distance_type_by_concept<
Chris@16:     GeometryType,
Chris@16:     typename is_segment_concept<
Chris@16:       typename geometry_concept<GeometryType>::type
Chris@16:     >::type
Chris@16:   >::type type;
Chris@16: };
Chris@16: 
Chris@16: template <typename GeometryType, typename BoolType>
Chris@16: struct segment_point_type_by_concept {
Chris@16:   typedef void type;
Chris@16: };
Chris@16: 
Chris@16: template <typename GeometryType>
Chris@16: struct segment_point_type_by_concept<GeometryType, gtl_yes> {
Chris@16:   typedef typename segment_traits<GeometryType>::point_type type;
Chris@16: };
Chris@16: 
Chris@16: template <typename GeometryType>
Chris@16: struct segment_point_type {
Chris@16:   typedef typename segment_point_type_by_concept<
Chris@16:     GeometryType,
Chris@16:     typename is_segment_concept<
Chris@16:       typename geometry_concept<GeometryType>::type
Chris@16:     >::type
Chris@16:   >::type type;
Chris@16: };
Chris@16: 
Chris@16: template <typename GeometryType, typename BoolType>
Chris@16: struct segment_coordinate_type_by_concept {
Chris@16:   typedef void type;
Chris@16: };
Chris@16: 
Chris@16: template <typename GeometryType>
Chris@16: struct segment_coordinate_type_by_concept<GeometryType, gtl_yes> {
Chris@16:   typedef typename segment_traits<GeometryType>::coordinate_type type;
Chris@16: };
Chris@16: 
Chris@16: template <typename GeometryType>
Chris@16: struct segment_coordinate_type {
Chris@16:   typedef typename segment_coordinate_type_by_concept<
Chris@16:     GeometryType,
Chris@16:     typename is_segment_concept<
Chris@16:       typename geometry_concept<GeometryType>::type
Chris@16:     >::type
Chris@16:   >::type type;
Chris@16: };
Chris@16: 
Chris@16: struct y_s_get : gtl_yes {};
Chris@16: 
Chris@16: template <typename Segment>
Chris@16: typename enable_if<
Chris@16:   typename gtl_and<
Chris@16:     y_s_get,
Chris@16:     typename is_segment_concept<
Chris@16:       typename geometry_concept<Segment>::type
Chris@16:     >::type
Chris@16:   >::type,
Chris@16: typename segment_point_type<Segment>::type>::type
Chris@16: get(const Segment& segment, direction_1d dir) {
Chris@16:   return segment_traits<Segment>::get(segment, dir);
Chris@16: }
Chris@16: 
Chris@16: struct y_s_set : gtl_yes {};
Chris@16: 
Chris@16: template <typename Segment, typename Point>
Chris@16: typename enable_if<
Chris@16:   typename gtl_and_3<
Chris@16:     y_s_set,
Chris@16:     typename is_mutable_segment_concept<
Chris@16:       typename geometry_concept<Segment>::type
Chris@16:     >::type,
Chris@16:     typename is_point_concept<
Chris@16:       typename geometry_concept<Point>::type
Chris@16:     >::type
Chris@16:   >::type,
Chris@16: void>::type set(Segment& segment, direction_1d dir, const Point& point) {
Chris@16:   segment_mutable_traits<Segment>::set(segment, dir, point);
Chris@16: }
Chris@16: 
Chris@16: struct y_s_construct : gtl_yes {};
Chris@16: 
Chris@16: template <typename Segment, typename Point1, typename Point2>
Chris@16: typename enable_if<
Chris@16:   typename gtl_and_4<
Chris@16:     y_s_construct,
Chris@16:     typename is_mutable_segment_concept<
Chris@16:       typename geometry_concept<Segment>::type
Chris@16:     >::type,
Chris@16:     typename is_point_concept<
Chris@16:       typename geometry_concept<Point1>::type
Chris@16:     >::type,
Chris@16:     typename is_point_concept<
Chris@16:       typename geometry_concept<Point2>::type
Chris@16:     >::type
Chris@16:   >::type,
Chris@16: Segment>::type construct(const Point1& low, const Point2& high) {
Chris@16:   return segment_mutable_traits<Segment>::construct(low, high);
Chris@16: }
Chris@16: 
Chris@16: struct y_s_copy_construct : gtl_yes {};
Chris@16: 
Chris@16: template <typename Segment1, typename Segment2>
Chris@16: typename enable_if<
Chris@16:   typename gtl_and_3<
Chris@16:     y_s_copy_construct,
Chris@16:     typename is_mutable_segment_concept<
Chris@16:       typename geometry_concept<Segment1>::type
Chris@16:     >::type,
Chris@16:     typename is_segment_concept<
Chris@16:       typename geometry_concept<Segment2>::type
Chris@16:     >::type
Chris@16:   >::type,
Chris@16: Segment1>::type copy_construct(const Segment2& segment) {
Chris@16:   return construct<Segment1>(get(segment, LOW), get(segment, HIGH));
Chris@16: }
Chris@16: 
Chris@16: struct y_s_assign : gtl_yes {};
Chris@16: 
Chris@16: template <typename Segment1, typename Segment2>
Chris@16: typename enable_if<
Chris@16:   typename gtl_and_3<
Chris@16:     y_s_assign,
Chris@16:     typename is_mutable_segment_concept<
Chris@16:       typename geometry_concept<Segment1>::type
Chris@16:     >::type,
Chris@16:     typename is_segment_concept<
Chris@16:       typename geometry_concept<Segment2>::type
Chris@16:     >::type
Chris@16:   >::type,
Chris@16: Segment1>::type& assign(Segment1& segment1, const Segment2& segment2) {
Chris@16:   return segment1 = copy_construct<Segment1>(segment2);
Chris@16: }
Chris@16: 
Chris@16: struct y_s_equivalence : gtl_yes {};
Chris@16: 
Chris@16: template <typename Segment1, typename Segment2>
Chris@16: typename enable_if<
Chris@16:   typename gtl_and_3<
Chris@16:     y_s_equivalence,
Chris@16:     typename is_segment_concept<
Chris@16:       typename geometry_concept<Segment1>::type
Chris@16:     >::type,
Chris@16:     typename is_segment_concept<
Chris@16:       typename geometry_concept<Segment2>::type
Chris@16:     >::type
Chris@16:   >::type,
Chris@16: bool>::type equivalence(const Segment1& segment1, const Segment2& segment2) {
Chris@16:   return get(segment1, LOW) == get(segment2, LOW) &&
Chris@16:          get(segment1, HIGH) == get(segment2, HIGH);
Chris@16: }
Chris@16: 
Chris@16: struct y_s_low : gtl_yes {};
Chris@16: 
Chris@16: template <typename Segment>
Chris@16: typename enable_if<
Chris@16:   typename gtl_and<
Chris@16:     y_s_low,
Chris@16:     typename is_segment_concept<
Chris@16:       typename geometry_concept<Segment>::type
Chris@16:     >::type
Chris@16:   >::type,
Chris@16: typename segment_point_type<Segment>::type>::type low(const Segment& segment) {
Chris@16:   return get(segment, LOW);
Chris@16: }
Chris@16: 
Chris@16: struct y_s_high : gtl_yes {};
Chris@16: 
Chris@16: template <typename Segment>
Chris@16: typename enable_if<
Chris@16:   typename gtl_and<
Chris@16:     y_s_high,
Chris@16:     typename is_segment_concept<
Chris@16:       typename geometry_concept<Segment>::type
Chris@16:     >::type
Chris@16:   >::type,
Chris@16: typename segment_point_type<Segment>::type>::type high(const Segment& segment) {
Chris@16:   return get(segment, HIGH);
Chris@16: }
Chris@16: 
Chris@16: struct y_s_center : gtl_yes {};
Chris@16: 
Chris@16: template <typename Segment>
Chris@16: typename enable_if<
Chris@16:   typename gtl_and<
Chris@16:     y_s_center,
Chris@16:     typename is_segment_concept<
Chris@16:       typename geometry_concept<Segment>::type
Chris@16:     >::type
Chris@16:   >::type,
Chris@16: typename segment_point_type<Segment>::type>::type
Chris@16: center(const Segment& segment) {
Chris@16:   return construct<typename segment_point_type<Segment>::type>(
Chris@16:       (x(high(segment)) + x(low(segment)))/2,
Chris@16:       (y(high(segment)) + y(low(segment)))/2);
Chris@16: }
Chris@16: 
Chris@16: struct y_s_low2 : gtl_yes {};
Chris@16: 
Chris@16: template <typename Segment, typename Point>
Chris@16: typename enable_if<
Chris@16:   typename gtl_and_3<
Chris@16:     y_s_low2,
Chris@16:     typename is_mutable_segment_concept<
Chris@16:       typename geometry_concept<Segment>::type
Chris@16:     >::type,
Chris@16:     typename is_point_concept<
Chris@16:       typename geometry_concept<Point>::type
Chris@16:     >::type
Chris@16:   >::type,
Chris@16: void>::type low(Segment& segment, const Point& point) {
Chris@16:   set(segment, LOW, point);
Chris@16: }
Chris@16: 
Chris@16: struct y_s_high2 : gtl_yes {};
Chris@16: 
Chris@16: template <typename Segment, typename Point>
Chris@16: typename enable_if<
Chris@16:   typename gtl_and_3<
Chris@16:     y_s_high2,
Chris@16:     typename is_mutable_segment_concept<
Chris@16:       typename geometry_concept<Segment>::type
Chris@16:     >::type,
Chris@16:     typename is_point_concept<
Chris@16:       typename geometry_concept<Point>::type
Chris@16:     >::type
Chris@16:   >::type,
Chris@16: void>::type high(Segment& segment, const Point& point) {
Chris@16:   set(segment, HIGH, point);
Chris@16: }
Chris@16: 
Chris@16: struct y_s_orientation1 : gtl_yes {};
Chris@16: 
Chris@16: // -1 for CW, 0 for collinear and 1 for CCW.
Chris@16: template <typename Segment1, typename Segment2>
Chris@16: typename enable_if<
Chris@16:   typename gtl_and_3<
Chris@16:     y_s_orientation1,
Chris@16:     typename is_segment_concept<
Chris@16:       typename geometry_concept<Segment1>::type
Chris@16:     >::type,
Chris@16:     typename is_segment_concept<
Chris@16:       typename geometry_concept<Segment2>::type
Chris@16:     >::type
Chris@16:   >::type,
Chris@16: int>::type orientation(const Segment1& segment1, const Segment2& segment2) {
Chris@16:   typedef typename coordinate_traits<
Chris@16:     typename segment_traits<Segment1>::coordinate_type
Chris@16:   >::manhattan_area_type int_x2;
Chris@16:   typedef typename coordinate_traits<
Chris@16:     typename segment_traits<Segment1>::coordinate_type
Chris@16:   >::unsigned_area_type uint_x2;
Chris@16:   int_x2 a1 = (int_x2)x(high(segment1)) - (int_x2)x(low(segment1));
Chris@16:   int_x2 b1 = (int_x2)y(high(segment1)) - (int_x2)y(low(segment1));
Chris@16:   int_x2 a2 = (int_x2)x(high(segment2)) - (int_x2)x(low(segment2));
Chris@16:   int_x2 b2 = (int_x2)y(high(segment2)) - (int_x2)y(low(segment2));
Chris@16: 
Chris@16:   int sign1 = 0;
Chris@16:   int sign2 = 0;
Chris@16:   if (a1 && b2)
Chris@16:     sign1 = ((a1 > 0) ^ (b2 > 0)) ? -1 : 1;
Chris@16:   if (a2 && b1)
Chris@16:     sign2 = ((a2 > 0) ^ (b1 > 0)) ? -1 : 1;
Chris@16: 
Chris@16:   if (sign1 != sign2)
Chris@16:     return (sign1 < sign2) ? -1 : 1;
Chris@16:   uint_x2 a3 = (uint_x2)(a1 < 0 ? -a1 : a1) * (uint_x2)(b2 < 0 ? -b2 : b2);
Chris@16:   uint_x2 b3 = (uint_x2)(b1 < 0 ? -b1 : b1) * (uint_x2)(a2 < 0 ? -a2 : a2);
Chris@16:   if (a3 == b3)
Chris@16:     return 0;
Chris@16:   return ((a3 < b3) ^ (sign1 == 1)) ? 1 : -1;
Chris@16: }
Chris@16: 
Chris@16: struct y_s_orientation2 : gtl_yes {};
Chris@16: 
Chris@16: // -1 for right, 0 for collinear and 1 for left.
Chris@16: template <typename Segment, typename Point>
Chris@16: typename enable_if<
Chris@16:   typename gtl_and_3<
Chris@16:     y_s_orientation2,
Chris@16:     typename is_segment_concept<
Chris@16:       typename geometry_concept<Segment>::type
Chris@16:     >::type,
Chris@16:     typename is_point_concept<
Chris@16:       typename geometry_concept<Point>::type
Chris@16:     >::type
Chris@16:   >::type,
Chris@16: int>::type orientation(const Segment& segment, const Point& point) {
Chris@16:   Segment segment2 = construct<Segment>(high(segment), point);
Chris@16:   return orientation(segment, segment2);
Chris@16: }
Chris@16: 
Chris@16: struct y_s_contains : gtl_yes {};
Chris@16: 
Chris@16: template <typename Segment, typename Point>
Chris@16: typename enable_if<
Chris@16:   typename gtl_and_3<
Chris@16:     y_s_contains,
Chris@16:     typename is_segment_concept<
Chris@16:       typename geometry_concept<Segment>::type
Chris@16:     >::type,
Chris@16:     typename is_point_concept<
Chris@16:       typename geometry_concept<Point>::type
Chris@16:     >::type
Chris@16:   >::type,
Chris@16: bool>::type contains(const Segment& segment,
Chris@16:     const Point& point, bool consider_touch = true ) {
Chris@16:   if (orientation(segment, point))
Chris@16:     return false;
Chris@16:   rectangle_data<typename segment_coordinate_type<Segment>::type> rect;
Chris@16:   set_points(rect, low(segment), high(segment));
Chris@16:   if (!contains(rect, point, true))
Chris@16:     return false;
Chris@16:   if (!consider_touch &&
Chris@16:       (equivalence(low(segment), point) ||
Chris@16:        equivalence(high(segment), point)))
Chris@16:     return false;
Chris@16:   return true;
Chris@16: }
Chris@16: 
Chris@16: struct y_s_contains2 : gtl_yes {};
Chris@16: 
Chris@16: template <typename Segment1, typename Segment2>
Chris@16: typename enable_if<
Chris@16:   typename gtl_and_3<
Chris@16:     y_s_contains2,
Chris@16:     typename is_segment_concept<
Chris@16:       typename geometry_concept<Segment1>::type
Chris@16:     >::type,
Chris@16:     typename is_segment_concept<
Chris@16:       typename geometry_concept<Segment2>::type
Chris@16:     >::type
Chris@16:   >::type,
Chris@16: bool>::type contains(const Segment1& segment1,
Chris@16:     const Segment2& segment2, bool consider_touch = true) {
Chris@16:   return contains(segment1, get(segment2, LOW), consider_touch) &&
Chris@16:          contains(segment1, get(segment2, HIGH), consider_touch);
Chris@16: }
Chris@16: 
Chris@16: struct y_s_length : gtl_yes {};
Chris@16: 
Chris@16: template <typename Segment>
Chris@16: typename enable_if<
Chris@16:   typename gtl_and<
Chris@16:     y_s_length,
Chris@16:     typename is_segment_concept<
Chris@16:       typename geometry_concept<Segment>::type
Chris@16:     >::type
Chris@16:   >::type,
Chris@16: typename segment_distance_type<Segment>::type>::type
Chris@16: length(const Segment& segment) {
Chris@16:   return euclidean_distance(low(segment), high(segment));
Chris@16: }
Chris@16: 
Chris@16: struct y_s_scale_up : gtl_yes {};
Chris@16: 
Chris@16: template <typename Segment>
Chris@16: typename enable_if<
Chris@16:   typename gtl_and<
Chris@16:     y_s_scale_up,
Chris@16:     typename is_mutable_segment_concept<
Chris@16:       typename geometry_concept<Segment>::type
Chris@16:     >::type
Chris@16:   >::type,
Chris@16: Segment>::type& scale_up(Segment& segment,
Chris@16:     typename coordinate_traits<
Chris@16:       typename segment_coordinate_type<Segment>::type
Chris@16:     >::unsigned_area_type factor) {
Chris@16:   typename segment_point_type<Segment>::type l = low(segment);
Chris@16:   typename segment_point_type<Segment>::type h = high(segment);
Chris@16:   low(segment, scale_up(l, factor));
Chris@16:   high(segment, scale_up(h, factor));
Chris@16:   return segment;
Chris@16: }
Chris@16: 
Chris@16: struct y_s_scale_down : gtl_yes {};
Chris@16: 
Chris@16: template <typename Segment>
Chris@16: typename enable_if<
Chris@16:   typename gtl_and<
Chris@16:     y_s_scale_down,
Chris@16:     typename is_mutable_segment_concept<
Chris@16:       typename geometry_concept<Segment>::type
Chris@16:     >::type
Chris@16:   >::type,
Chris@16: Segment>::type& scale_down(Segment& segment,
Chris@16:     typename coordinate_traits<
Chris@16:       typename segment_coordinate_type<Segment>::type
Chris@16:     >::unsigned_area_type factor) {
Chris@16:   typename segment_point_type<Segment>::type l = low(segment);
Chris@16:   typename segment_point_type<Segment>::type h = high(segment);
Chris@16:   low(segment, scale_down(l, factor));
Chris@16:   high(segment, scale_down(h, factor));
Chris@16:   return segment;
Chris@16: }
Chris@16: 
Chris@16: struct y_s_scale : gtl_yes {};
Chris@16: 
Chris@16: template <typename Segment, typename Scale>
Chris@16: typename enable_if<
Chris@16:   typename gtl_and<
Chris@16:     y_s_scale,
Chris@16:     typename is_mutable_segment_concept<
Chris@16:       typename geometry_concept<Segment>::type
Chris@16:     >::type
Chris@16:   >::type,
Chris@16: Segment>::type& scale(Segment& segment, const Scale& sc) {
Chris@16:   typename segment_point_type<Segment>::type l = low(segment);
Chris@16:   typename segment_point_type<Segment>::type h = high(segment);
Chris@16:   low(segment, scale(l, sc));
Chris@16:   high(segment, scale(h, sc));
Chris@16:   return segment;
Chris@16: }
Chris@16: 
Chris@16: struct y_s_transform : gtl_yes {};
Chris@16: 
Chris@16: template <typename Segment, typename Transform>
Chris@16: typename enable_if<
Chris@16:   typename gtl_and<
Chris@16:     y_s_transform,
Chris@16:     typename is_mutable_segment_concept<
Chris@16:       typename geometry_concept<Segment>::type
Chris@16:     >::type
Chris@16:   >::type,
Chris@16: Segment>::type& transform(Segment& segment, const Transform& tr) {
Chris@16:   typename segment_point_type<Segment>::type l = low(segment);
Chris@16:   typename segment_point_type<Segment>::type h = high(segment);
Chris@16:   low(segment, transform(l, tr));
Chris@16:   high(segment, transform(h, tr));
Chris@16:   return segment;
Chris@16: }
Chris@16: 
Chris@16: struct y_s_move : gtl_yes {};
Chris@16: 
Chris@16: template <typename Segment>
Chris@16: typename enable_if<
Chris@16:   typename gtl_and<
Chris@16:     y_s_move,
Chris@16:     typename is_mutable_segment_concept<
Chris@16:       typename geometry_concept<Segment>::type
Chris@16:     >::type
Chris@16:   >::type,
Chris@16: Segment>::type& move(Segment& segment, orientation_2d orient,
Chris@16:     typename segment_coordinate_type<Segment>::type displacement) {
Chris@16:   typename segment_point_type<Segment>::type l = low(segment);
Chris@16:   typename segment_point_type<Segment>::type h = high(segment);
Chris@16:   low(segment, move(l, orient, displacement));
Chris@16:   high(segment, move(h, orient, displacement));
Chris@16:   return segment;
Chris@16: }
Chris@16: 
Chris@16: struct y_s_convolve : gtl_yes {};
Chris@16: 
Chris@16: template <typename Segment, typename Point>
Chris@16: typename enable_if<
Chris@16:   typename gtl_and_3<
Chris@16:     y_s_convolve,
Chris@16:     typename is_mutable_segment_concept<
Chris@16:       typename geometry_concept<Segment>::type
Chris@16:     >::type,
Chris@16:     typename is_point_concept<
Chris@16:       typename geometry_concept<Point>::type
Chris@16:     >::type
Chris@16:   >::type,
Chris@16: Segment>::type& convolve(Segment& segment, const Point& point) {
Chris@16:   typename segment_point_type<Segment>::type l = low(segment);
Chris@16:   typename segment_point_type<Segment>::type h = high(segment);
Chris@16:   low(segment, convolve(l, point));
Chris@16:   high(segment, convolve(h, point));
Chris@16:   return segment;
Chris@16: }
Chris@16: 
Chris@16: struct y_s_deconvolve : gtl_yes {};
Chris@16: 
Chris@16: template <typename Segment, typename Point>
Chris@16: typename enable_if<
Chris@16:   typename gtl_and_3<
Chris@16:     y_s_deconvolve,
Chris@16:     typename is_mutable_segment_concept<
Chris@16:       typename geometry_concept<Segment>::type
Chris@16:     >::type,
Chris@16:     typename is_point_concept<
Chris@16:       typename geometry_concept<Point>::type
Chris@16:     >::type
Chris@16:   >::type,
Chris@16: Segment>::type& deconvolve(Segment& segment, const Point& point) {
Chris@16:   typename segment_point_type<Segment>::type l = low(segment);
Chris@16:   typename segment_point_type<Segment>::type h = high(segment);
Chris@16:   low(segment, deconvolve(l, point));
Chris@16:   high(segment, deconvolve(h, point));
Chris@16:   return segment;
Chris@16: }
Chris@16: 
Chris@16: struct y_s_abuts1 : gtl_yes {};
Chris@16: 
Chris@16: template <typename Segment1, typename Segment2>
Chris@16: typename enable_if<
Chris@16:   typename gtl_and_3<
Chris@16:     y_s_abuts1,
Chris@16:     typename is_segment_concept<
Chris@16:       typename geometry_concept<Segment1>::type
Chris@16:     >::type,
Chris@16:     typename is_segment_concept<
Chris@16:       typename geometry_concept<Segment2>::type
Chris@16:     >::type
Chris@16:   >::type,
Chris@16: bool>::type abuts(const Segment1& segment1,
Chris@16:     const Segment2& segment2, direction_1d dir) {
Chris@16:   return dir.to_int() ? equivalence(low(segment2) , high(segment1)) :
Chris@16:                         equivalence(low(segment1) , high(segment2));
Chris@16: }
Chris@16: 
Chris@16: struct y_s_abuts2 : gtl_yes {};
Chris@16: 
Chris@16: template <typename Segment1, typename Segment2>
Chris@16: typename enable_if<
Chris@16:   typename gtl_and_3<
Chris@16:     y_s_abuts2,
Chris@16:     typename is_segment_concept<
Chris@16:       typename geometry_concept<Segment1>::type
Chris@16:     >::type,
Chris@16:     typename is_segment_concept<
Chris@16:       typename geometry_concept<Segment2>::type
Chris@16:     >::type
Chris@16:   >::type,
Chris@16: bool>::type abuts(const Segment1& segment1, const Segment2& segment2) {
Chris@16:   return abuts(segment1, segment2, HIGH) || abuts(segment1, segment2, LOW);
Chris@16: }
Chris@16: 
Chris@16: struct y_s_e_intersects : gtl_yes {};
Chris@16: 
Chris@16: template <typename Segment1, typename Segment2>
Chris@16: typename enable_if<
Chris@16:   typename gtl_and_3<
Chris@16:     y_s_e_intersects,
Chris@16:     typename is_segment_concept<
Chris@16:       typename geometry_concept<Segment1>::type
Chris@16:     >::type,
Chris@16:     typename is_segment_concept<
Chris@16:       typename geometry_concept<Segment2>::type
Chris@16:     >::type
Chris@16:   >::type,
Chris@16: bool
Chris@16: >::type intersects(const Segment1& segment1, const Segment2& segment2,
Chris@16:     bool consider_touch = true) {
Chris@16:   rectangle_data<typename segment_coordinate_type<Segment1>::type> rect1, rect2;
Chris@16:   set_points(rect1, low(segment1), high(segment1));
Chris@16:   set_points(rect2, low(segment2), high(segment2));
Chris@16:   // Check if axis-parallel rectangles containing segments intersect.
Chris@16:   if (!intersects(rect1, rect2, true))
Chris@16:     return false;
Chris@16:   int or1_1 = orientation(segment1, low(segment2));
Chris@16:   int or1_2 = orientation(segment1, high(segment2));
Chris@16:   if (or1_1 * or1_2 > 0)
Chris@16:     return false;
Chris@16:   int or2_1 = orientation(segment2, low(segment1));
Chris@16:   int or2_2 = orientation(segment2, high(segment1));
Chris@16:   if (or2_1 * or2_2 > 0)
Chris@16:     return false;
Chris@16:   if (consider_touch || (or1_1 && or1_2) || (or2_1 && or2_2))
Chris@16:     return true;
Chris@16:   if (or1_1 || or1_2)
Chris@16:     return false;
Chris@16:   return intersects(vertical(rect1), vertical(rect2), false) ||
Chris@16:          intersects(horizontal(rect1), horizontal(rect2), false);
Chris@16: }
Chris@16: 
Chris@16: struct y_s_e_dist : gtl_yes {};
Chris@16: 
Chris@16: template <typename Segment, typename Point>
Chris@16: typename enable_if<
Chris@16:   typename gtl_and_3<
Chris@16:     y_s_e_dist,
Chris@16:     typename is_segment_concept<
Chris@16:       typename geometry_concept<Segment>::type
Chris@16:     >::type,
Chris@16:     typename is_point_concept<
Chris@16:       typename geometry_concept<Point>::type
Chris@16:     >::type
Chris@16:   >::type,
Chris@16: typename segment_distance_type<Segment>::type>::type
Chris@16: euclidean_distance(const Segment& segment, const Point& point) {
Chris@16:   typedef typename segment_distance_type<Segment>::type Unit;
Chris@16:   Unit x1 = x(low(segment));
Chris@16:   Unit y1 = y(low(segment));
Chris@16:   Unit x2 = x(high(segment));
Chris@16:   Unit y2 = y(high(segment));
Chris@16:   Unit X = x(point);
Chris@16:   Unit Y = y(point);
Chris@16:   Unit A = X - x1;
Chris@16:   Unit B = Y - y1;
Chris@16:   Unit C = x2 - x1;
Chris@16:   Unit D = y2 - y1;
Chris@16:   Unit param = (A * C + B * D);
Chris@16:   Unit length_sq = C * C + D * D;
Chris@16:   if (param > length_sq) {
Chris@16:     return euclidean_distance(high(segment), point);
Chris@16:   } else if (param < 0.0) {
Chris@16:     return euclidean_distance(low(segment), point);
Chris@16:   }
Chris@16:   if (length_sq == 0.0)
Chris@16:     return 0.0;
Chris@16:   Unit denom = std::sqrt(length_sq);
Chris@16:   Unit result = (A * D - C * B) / denom;
Chris@16:   return (result < 0.0) ? -result : result;
Chris@16: }
Chris@16: 
Chris@16: struct y_s_e_dist2 : gtl_yes {};
Chris@16: 
Chris@16: template <typename Segment1, typename Segment2>
Chris@16: typename enable_if<
Chris@16:   typename gtl_and_3<
Chris@16:     y_s_e_dist2,
Chris@16:     typename is_segment_concept<
Chris@16:       typename geometry_concept<Segment1>::type
Chris@16:     >::type,
Chris@16:     typename is_segment_concept<
Chris@16:       typename geometry_concept<Segment2>::type
Chris@16:     >::type
Chris@16:   >::type,
Chris@16: typename segment_distance_type<Segment1>::type>::type
Chris@16: euclidean_distance(const Segment1& segment1, const Segment2& segment2) {
Chris@16:   if (intersects(segment1, segment2))
Chris@16:     return 0.0;
Chris@16:   typename segment_distance_type<Segment1>::type
Chris@16:       result1 = euclidean_distance(segment1, low(segment2)),
Chris@16:       result2 = euclidean_distance(segment1, high(segment2)),
Chris@16:       result3 = euclidean_distance(segment2, low(segment1)),
Chris@16:       result4 = euclidean_distance(segment2, high(segment1));
Chris@16:   if (result2 < result1)
Chris@16:     result1 = result2;
Chris@16:   if (result4 < result3)
Chris@16:     result3 = result4;
Chris@16:   return (result1 < result3) ? result1 : result3;
Chris@16: }
Chris@16: }  // polygon
Chris@16: }  // boost
Chris@16: 
Chris@16: #endif  // BOOST_POLYGON_SEGMENT_CONCEPT_HPP