boost/polygon/segment_utils.hpp

0001 /*
0002   Copyright 2012 Lucanus Simonson
0003
0004   Use, modification and distribution are subject to the Boost Software License,
0005   Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0006   http://www.boost.org/LICENSE_1_0.txt).
0007 */
0008
0009 #ifndef BOOST_POLYGON_SEGMENT_UTILS_HPP
0010 #define BOOST_POLYGON_SEGMENT_UTILS_HPP
0011
0012 #include <iterator>
0013 #include <set>
0014 #include <vector>
0015
0016 #include "detail/scan_arbitrary.hpp"
0017 #include "isotropy.hpp"
0018 #include "rectangle_concept.hpp"
0019 #include "segment_concept.hpp"
0020
0021 namespace boost {
0022 namespace polygon {
0023
0024 template <typename Segment, typename SegmentIterator>
0025 typename enable_if<
0026   typename gtl_and<
0027     typename gtl_if<
0028       typename is_segment_concept<
0029         typename geometry_concept<
0030           typename std::iterator_traits<SegmentIterator>::value_type
0031         >::type
0032       >::type
0033     >::type,
0034     typename gtl_if<
0035       typename is_segment_concept<
0036         typename geometry_concept<Segment>::type
0037       >::type
0038     >::type
0039   >::type,
0040   void
0041 >::type
0042 intersect_segments(
0043     std::vector<std::pair<std::size_t, Segment> >& result,
0044     SegmentIterator first, SegmentIterator last) {
0045   typedef typename segment_traits<Segment>::coordinate_type Unit;
0046   typedef typename scanline_base<Unit>::Point Point;
0047   typedef typename scanline_base<Unit>::half_edge half_edge;
0048   typedef int segment_id;
0049   std::vector<std::pair<half_edge, segment_id> > half_edges;
0050   std::vector<std::pair<half_edge, segment_id> > half_edges_out;
0051   segment_id id_in = 0;
0052   half_edges.reserve(std::distance(first, last));
0053   for (; first != last; ++first) {
0054     Point l, h;
0055     assign(l, low(*first));
0056     assign(h, high(*first));
0057     half_edges.push_back(std::make_pair(half_edge(l, h), id_in++));
0058   }
0059   half_edges_out.reserve(half_edges.size());
0060   // Apparently no need to pre-sort data when calling validate_scan.
0061   if (half_edges.size() != 0) {
0062     line_intersection<Unit>::validate_scan(
0063         half_edges_out, half_edges.begin(), half_edges.end());
0064   }
0065
0066   result.reserve(result.size() + half_edges_out.size());
0067   for (std::size_t i = 0; i < half_edges_out.size(); ++i) {
0068     std::size_t id = (std::size_t)(half_edges_out[i].second);
0069     Point l = half_edges_out[i].first.first;
0070     Point h = half_edges_out[i].first.second;
0071     result.push_back(std::make_pair(id, construct<Segment>(l, h)));
0072   }
0073 }
0074
0075 template <typename SegmentContainer, typename SegmentIterator>
0076 typename enable_if<
0077   typename gtl_and<
0078     typename gtl_if<
0079       typename is_segment_concept<
0080         typename geometry_concept<
0081           typename std::iterator_traits<SegmentIterator>::value_type
0082         >::type
0083       >::type
0084     >::type,
0085     typename gtl_if<
0086       typename is_segment_concept<
0087         typename geometry_concept<
0088           typename SegmentContainer::value_type
0089         >::type
0090       >::type
0091     >::type
0092   >::type,
0093   void
0094 >::type
0095 intersect_segments(
0096     SegmentContainer& result,
0097     SegmentIterator first,
0098     SegmentIterator last) {
0099   typedef typename SegmentContainer::value_type segment_type;
0100   typedef typename segment_traits<segment_type>::coordinate_type Unit;
0101   typedef typename scanline_base<Unit>::Point Point;
0102   typedef typename scanline_base<Unit>::half_edge half_edge;
0103   typedef int segment_id;
0104   std::vector<std::pair<half_edge, segment_id> > half_edges;
0105   std::vector<std::pair<half_edge, segment_id> > half_edges_out;
0106   segment_id id_in = 0;
0107   half_edges.reserve(std::distance(first, last));
0108   for (; first != last; ++first) {
0109     Point l, h;
0110     assign(l, low(*first));
0111     assign(h, high(*first));
0112     half_edges.push_back(std::make_pair(half_edge(l, h), id_in++));
0113   }
0114   half_edges_out.reserve(half_edges.size());
0115   // Apparently no need to pre-sort data when calling validate_scan.
0116   if (half_edges.size() != 0) {
0117     line_intersection<Unit>::validate_scan(
0118         half_edges_out, half_edges.begin(), half_edges.end());
0119   }
0120
0121   result.reserve(result.size() + half_edges_out.size());
0122   for (std::size_t i = 0; i < half_edges_out.size(); ++i) {
0123     Point l = half_edges_out[i].first.first;
0124     Point h = half_edges_out[i].first.second;
0125     result.push_back(construct<segment_type>(l, h));
0126   }
0127 }
0128
0129 template <typename Rectangle, typename SegmentIterator>
0130 typename enable_if<
0131   typename gtl_and<
0132     typename gtl_if<
0133       typename is_rectangle_concept<
0134         typename geometry_concept<Rectangle>::type
0135       >::type
0136     >::type,
0137     typename gtl_if<
0138       typename is_segment_concept<
0139         typename geometry_concept<
0140           typename std::iterator_traits<SegmentIterator>::value_type
0141         >::type
0142       >::type
0143     >::type
0144   >::type,
0145   bool
0146 >::type
0147 envelope_segments(
0148     Rectangle& rect,
0149     SegmentIterator first,
0150     SegmentIterator last) {
0151   for (SegmentIterator it = first; it != last; ++it) {
0152     if (it == first) {
0153       set_points(rect, low(*it), high(*it));
0154     } else {
0155       encompass(rect, low(*it));
0156       encompass(rect, high(*it));
0157     }
0158   }
0159   return first != last;
0160 }
0161 }  // polygon
0162 }  // boost
0163
0164 #endif  // BOOST_POLYGON_SEGMENT_UTILS_HPP