2 Copyright 2012 Lucanus Simonson
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).
9 #ifndef BOOST_POLYGON_SEGMENT_UTILS_HPP
10 #define BOOST_POLYGON_SEGMENT_UTILS_HPP
16 #include "detail/scan_arbitrary.hpp"
17 #include "isotropy.hpp"
18 #include "rectangle_concept.hpp"
19 #include "segment_concept.hpp"
24 template <typename Segment, typename SegmentIterator>
28 typename is_segment_concept<
29 typename geometry_concept<
30 typename std::iterator_traits<SegmentIterator>::value_type
35 typename is_segment_concept<
36 typename geometry_concept<Segment>::type
43 std::vector<std::pair<std::size_t, Segment> >& result,
44 SegmentIterator first, SegmentIterator last) {
45 typedef typename segment_traits<Segment>::coordinate_type Unit;
46 typedef typename scanline_base<Unit>::Point Point;
47 typedef typename scanline_base<Unit>::half_edge half_edge;
48 typedef int segment_id;
49 std::vector<std::pair<half_edge, segment_id> > half_edges;
50 std::vector<std::pair<half_edge, segment_id> > half_edges_out;
52 half_edges.reserve(std::distance(first, last));
53 for (; first != last; ++first) {
55 assign(l, low(*first));
56 assign(h, high(*first));
57 half_edges.push_back(std::make_pair(half_edge(l, h), id_in++));
59 half_edges_out.reserve(half_edges.size());
60 // Apparently no need to pre-sort data when calling validate_scan.
61 if (half_edges.size() != 0) {
62 line_intersection<Unit>::validate_scan(
63 half_edges_out, half_edges.begin(), half_edges.end());
66 result.reserve(result.size() + half_edges_out.size());
67 for (std::size_t i = 0; i < half_edges_out.size(); ++i) {
68 std::size_t id = (std::size_t)(half_edges_out[i].second);
69 Point l = half_edges_out[i].first.first;
70 Point h = half_edges_out[i].first.second;
71 result.push_back(std::make_pair(id, construct<Segment>(l, h)));
75 template <typename SegmentContainer, typename SegmentIterator>
79 typename is_segment_concept<
80 typename geometry_concept<
81 typename std::iterator_traits<SegmentIterator>::value_type
86 typename is_segment_concept<
87 typename geometry_concept<
88 typename SegmentContainer::value_type
96 SegmentContainer& result,
97 SegmentIterator first,
98 SegmentIterator last) {
99 typedef typename SegmentContainer::value_type segment_type;
100 typedef typename segment_traits<segment_type>::coordinate_type Unit;
101 typedef typename scanline_base<Unit>::Point Point;
102 typedef typename scanline_base<Unit>::half_edge half_edge;
103 typedef int segment_id;
104 std::vector<std::pair<half_edge, segment_id> > half_edges;
105 std::vector<std::pair<half_edge, segment_id> > half_edges_out;
106 segment_id id_in = 0;
107 half_edges.reserve(std::distance(first, last));
108 for (; first != last; ++first) {
110 assign(l, low(*first));
111 assign(h, high(*first));
112 half_edges.push_back(std::make_pair(half_edge(l, h), id_in++));
114 half_edges_out.reserve(half_edges.size());
115 // Apparently no need to pre-sort data when calling validate_scan.
116 if (half_edges.size() != 0) {
117 line_intersection<Unit>::validate_scan(
118 half_edges_out, half_edges.begin(), half_edges.end());
121 result.reserve(result.size() + half_edges_out.size());
122 for (std::size_t i = 0; i < half_edges_out.size(); ++i) {
123 Point l = half_edges_out[i].first.first;
124 Point h = half_edges_out[i].first.second;
125 result.push_back(construct<segment_type>(l, h));
129 template <typename Rectangle, typename SegmentIterator>
133 typename is_rectangle_concept<
134 typename geometry_concept<Rectangle>::type
138 typename is_segment_concept<
139 typename geometry_concept<
140 typename std::iterator_traits<SegmentIterator>::value_type
149 SegmentIterator first,
150 SegmentIterator last) {
151 for (SegmentIterator it = first; it != last; ++it) {
153 set_points(rect, low(*it), high(*it));
155 encompass(rect, low(*it));
156 encompass(rect, high(*it));
159 return first != last;
164 #endif // BOOST_POLYGON_SEGMENT_UTILS_HPP