1/*
2 Copyright 2012 Lucanus Simonson
3
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).
7*/
8
9#ifndef BOOST_POLYGON_SEGMENT_UTILS_HPP
10#define BOOST_POLYGON_SEGMENT_UTILS_HPP
11
12#include <iterator>
13#include <set>
14#include <vector>
15
16#include "detail/scan_arbitrary.hpp"
17#include "isotropy.hpp"
18#include "rectangle_concept.hpp"
19#include "segment_concept.hpp"
20
21namespace boost {
22namespace polygon {
23
24template <typename Segment, typename SegmentIterator>
25typename enable_if<
26 typename gtl_and<
27 typename gtl_if<
28 typename is_segment_concept<
29 typename geometry_concept<
30 typename std::iterator_traits<SegmentIterator>::value_type
31 >::type
32 >::type
33 >::type,
34 typename gtl_if<
35 typename is_segment_concept<
36 typename geometry_concept<Segment>::type
37 >::type
38 >::type
39 >::type,
40 void
41>::type
42intersect_segments(
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;
51 segment_id id_in = 0;
52 half_edges.reserve(std::distance(first, last));
53 for (; first != last; ++first) {
54 Point l, h;
55 assign(l, low(*first));
56 assign(h, high(*first));
57 half_edges.push_back(std::make_pair(half_edge(l, h), id_in++));
58 }
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());
64 }
65
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)));
72 }
73}
74
75template <typename SegmentContainer, typename SegmentIterator>
76typename enable_if<
77 typename gtl_and<
78 typename gtl_if<
79 typename is_segment_concept<
80 typename geometry_concept<
81 typename std::iterator_traits<SegmentIterator>::value_type
82 >::type
83 >::type
84 >::type,
85 typename gtl_if<
86 typename is_segment_concept<
87 typename geometry_concept<
88 typename SegmentContainer::value_type
89 >::type
90 >::type
91 >::type
92 >::type,
93 void
94>::type
95intersect_segments(
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) {
109 Point l, h;
110 assign(l, low(*first));
111 assign(h, high(*first));
112 half_edges.push_back(std::make_pair(half_edge(l, h), id_in++));
113 }
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());
119 }
120
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));
126 }
127}
128
129template <typename Rectangle, typename SegmentIterator>
130typename enable_if<
131 typename gtl_and<
132 typename gtl_if<
133 typename is_rectangle_concept<
134 typename geometry_concept<Rectangle>::type
135 >::type
136 >::type,
137 typename gtl_if<
138 typename is_segment_concept<
139 typename geometry_concept<
140 typename std::iterator_traits<SegmentIterator>::value_type
141 >::type
142 >::type
143 >::type
144 >::type,
145 bool
146>::type
147envelope_segments(
148 Rectangle& rect,
149 SegmentIterator first,
150 SegmentIterator last) {
151 for (SegmentIterator it = first; it != last; ++it) {
152 if (it == first) {
153 set_points(rect, low(*it), high(*it));
154 } else {
155 encompass(rect, low(*it));
156 encompass(rect, high(*it));
157 }
158 }
159 return first != last;
160}
161} // polygon
162} // boost
163
164#endif // BOOST_POLYGON_SEGMENT_UTILS_HPP
165

source code of boost/boost/polygon/segment_utils.hpp