Chris@16: /*
Chris@16:   Copyright 2012 Lucanus Simonson
Chris@16:  
Chris@16:   Use, modification and distribution are 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: 
Chris@16: #ifndef BOOST_POLYGON_SEGMENT_UTILS_HPP
Chris@16: #define BOOST_POLYGON_SEGMENT_UTILS_HPP
Chris@16: 
Chris@101: #include <iterator>
Chris@16: #include <set>
Chris@16: #include <vector>
Chris@101: 
Chris@101: #include "detail/scan_arbitrary.hpp"
Chris@101: #include "isotropy.hpp"
Chris@101: #include "rectangle_concept.hpp"
Chris@101: #include "segment_concept.hpp"
Chris@16: 
Chris@16: namespace boost {
Chris@16: namespace polygon {
Chris@16: 
Chris@16: template <typename Segment, typename SegmentIterator>
Chris@16: typename enable_if<
Chris@16:   typename gtl_and<
Chris@16:     typename gtl_if<
Chris@16:       typename is_segment_concept<
Chris@16:         typename geometry_concept<
Chris@16:           typename std::iterator_traits<SegmentIterator>::value_type
Chris@16:         >::type
Chris@16:       >::type
Chris@16:     >::type,
Chris@16:     typename gtl_if<
Chris@16:       typename is_segment_concept<
Chris@16:         typename geometry_concept<Segment>::type
Chris@16:       >::type
Chris@16:     >::type
Chris@16:   >::type,
Chris@16:   void
Chris@16: >::type
Chris@16: intersect_segments(
Chris@16:     std::vector<std::pair<std::size_t, Segment> >& result,
Chris@16:     SegmentIterator first, SegmentIterator last) {
Chris@16:   typedef typename segment_traits<Segment>::coordinate_type Unit;
Chris@16:   typedef typename scanline_base<Unit>::Point Point;
Chris@16:   typedef typename scanline_base<Unit>::half_edge half_edge;
Chris@16:   typedef int segment_id;
Chris@16:   std::vector<std::pair<half_edge, segment_id> > half_edges;
Chris@16:   std::vector<std::pair<half_edge, segment_id> > half_edges_out;
Chris@16:   segment_id id_in = 0;
Chris@16:   half_edges.reserve(std::distance(first, last));
Chris@16:   for (; first != last; ++first) {
Chris@16:     Point l, h;
Chris@16:     assign(l, low(*first));
Chris@16:     assign(h, high(*first));
Chris@16:     half_edges.push_back(std::make_pair(half_edge(l, h), id_in++));
Chris@16:   }
Chris@16:   half_edges_out.reserve(half_edges.size());
Chris@16:   // Apparently no need to pre-sort data when calling validate_scan.
Chris@16:   if (half_edges.size() != 0) {
Chris@16:     line_intersection<Unit>::validate_scan(
Chris@16:         half_edges_out, half_edges.begin(), half_edges.end());
Chris@16:   }
Chris@16: 
Chris@16:   result.reserve(result.size() + half_edges_out.size());
Chris@16:   for (std::size_t i = 0; i < half_edges_out.size(); ++i) {
Chris@16:     std::size_t id = (std::size_t)(half_edges_out[i].second);
Chris@16:     Point l = half_edges_out[i].first.first;
Chris@16:     Point h = half_edges_out[i].first.second;
Chris@16:     result.push_back(std::make_pair(id, construct<Segment>(l, h)));
Chris@16:   }
Chris@16: }
Chris@16: 
Chris@16: template <typename SegmentContainer, typename SegmentIterator>
Chris@16: typename enable_if<
Chris@16:   typename gtl_and<
Chris@16:     typename gtl_if<
Chris@16:       typename is_segment_concept<
Chris@16:         typename geometry_concept<
Chris@16:           typename std::iterator_traits<SegmentIterator>::value_type
Chris@16:         >::type
Chris@16:       >::type
Chris@16:     >::type,
Chris@16:     typename gtl_if<
Chris@16:       typename is_segment_concept<
Chris@16:         typename geometry_concept<
Chris@16:           typename SegmentContainer::value_type
Chris@16:         >::type
Chris@16:       >::type
Chris@16:     >::type
Chris@16:   >::type,
Chris@16:   void
Chris@16: >::type
Chris@16: intersect_segments(
Chris@16:     SegmentContainer& result,
Chris@16:     SegmentIterator first,
Chris@16:     SegmentIterator last) {
Chris@16:   typedef typename SegmentContainer::value_type segment_type;
Chris@16:   typedef typename segment_traits<segment_type>::coordinate_type Unit;
Chris@16:   typedef typename scanline_base<Unit>::Point Point;
Chris@16:   typedef typename scanline_base<Unit>::half_edge half_edge;
Chris@16:   typedef int segment_id;
Chris@16:   std::vector<std::pair<half_edge, segment_id> > half_edges;
Chris@16:   std::vector<std::pair<half_edge, segment_id> > half_edges_out;
Chris@16:   segment_id id_in = 0;
Chris@16:   half_edges.reserve(std::distance(first, last));
Chris@16:   for (; first != last; ++first) {
Chris@16:     Point l, h;
Chris@16:     assign(l, low(*first));
Chris@16:     assign(h, high(*first));
Chris@16:     half_edges.push_back(std::make_pair(half_edge(l, h), id_in++));
Chris@16:   }
Chris@16:   half_edges_out.reserve(half_edges.size());
Chris@16:   // Apparently no need to pre-sort data when calling validate_scan.
Chris@16:   if (half_edges.size() != 0) {
Chris@16:     line_intersection<Unit>::validate_scan(
Chris@16:         half_edges_out, half_edges.begin(), half_edges.end());
Chris@16:   }
Chris@16: 
Chris@16:   result.reserve(result.size() + half_edges_out.size());
Chris@16:   for (std::size_t i = 0; i < half_edges_out.size(); ++i) {
Chris@16:     Point l = half_edges_out[i].first.first;
Chris@16:     Point h = half_edges_out[i].first.second;
Chris@16:     result.push_back(construct<segment_type>(l, h));
Chris@16:   }
Chris@16: }
Chris@16: 
Chris@16: template <typename Rectangle, typename SegmentIterator>
Chris@16: typename enable_if<
Chris@16:   typename gtl_and<
Chris@16:     typename gtl_if<
Chris@16:       typename is_rectangle_concept<
Chris@16:         typename geometry_concept<Rectangle>::type
Chris@16:       >::type
Chris@16:     >::type,
Chris@16:     typename gtl_if<
Chris@16:       typename is_segment_concept<
Chris@16:         typename geometry_concept<
Chris@16:           typename std::iterator_traits<SegmentIterator>::value_type
Chris@16:         >::type
Chris@16:       >::type
Chris@16:     >::type
Chris@16:   >::type,
Chris@16:   bool
Chris@16: >::type
Chris@16: envelope_segments(
Chris@16:     Rectangle& rect,
Chris@16:     SegmentIterator first,
Chris@16:     SegmentIterator last) {
Chris@16:   for (SegmentIterator it = first; it != last; ++it) {
Chris@16:     if (it == first) {
Chris@16:       set_points(rect, low(*it), high(*it));
Chris@16:     } else {
Chris@16:       encompass(rect, low(*it));
Chris@16:       encompass(rect, high(*it));
Chris@16:     }
Chris@16:   }
Chris@16:   return first != last;
Chris@16: }
Chris@16: }  // polygon
Chris@16: }  // boost
Chris@16: 
Chris@16: #endif  // BOOST_POLYGON_SEGMENT_UTILS_HPP