Mercurial > hg > vamp-build-and-test

annotate DEPENDENCIES/generic/include/boost/polygon/segment_utils.hpp @ 16:2665513ce2d3

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add boost headers
author Chris Cannam
date Tue, 05 Aug 2014 11:11:38 +0100
parents
children c530137014c0
rev   line source
Chris@16 1 /*
Chris@16 2 Copyright 2012 Lucanus Simonson
Chris@16 3
Chris@16 4 Use, modification and distribution are subject to the Boost Software License,
Chris@16 5 Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
Chris@16 6 http://www.boost.org/LICENSE_1_0.txt).
Chris@16 7 */
Chris@16 8
Chris@16 9 #ifndef BOOST_POLYGON_SEGMENT_UTILS_HPP
Chris@16 10 #define BOOST_POLYGON_SEGMENT_UTILS_HPP
Chris@16 11
Chris@16 12 #include <set>
Chris@16 13 #include <vector>
Chris@16 14 #include <utility>
Chris@16 15
Chris@16 16 namespace boost {
Chris@16 17 namespace polygon {
Chris@16 18
Chris@16 19 template <typename Segment, typename SegmentIterator>
Chris@16 20 typename enable_if<
Chris@16 21 typename gtl_and<
Chris@16 22 typename gtl_if<
Chris@16 23 typename is_segment_concept<
Chris@16 24 typename geometry_concept<
Chris@16 25 typename std::iterator_traits<SegmentIterator>::value_type
Chris@16 26 >::type
Chris@16 27 >::type
Chris@16 28 >::type,
Chris@16 29 typename gtl_if<
Chris@16 30 typename is_segment_concept<
Chris@16 31 typename geometry_concept<Segment>::type
Chris@16 32 >::type
Chris@16 33 >::type
Chris@16 34 >::type,
Chris@16 35 void
Chris@16 36 >::type
Chris@16 37 intersect_segments(
Chris@16 38 std::vector<std::pair<std::size_t, Segment> >& result,
Chris@16 39 SegmentIterator first, SegmentIterator last) {
Chris@16 40 typedef typename segment_traits<Segment>::coordinate_type Unit;
Chris@16 41 typedef typename scanline_base<Unit>::Point Point;
Chris@16 42 typedef typename scanline_base<Unit>::half_edge half_edge;
Chris@16 43 typedef int segment_id;
Chris@16 44 std::vector<std::pair<half_edge, segment_id> > half_edges;
Chris@16 45 std::vector<std::pair<half_edge, segment_id> > half_edges_out;
Chris@16 46 segment_id id_in = 0;
Chris@16 47 half_edges.reserve(std::distance(first, last));
Chris@16 48 for (; first != last; ++first) {
Chris@16 49 Point l, h;
Chris@16 50 assign(l, low(*first));
Chris@16 51 assign(h, high(*first));
Chris@16 52 half_edges.push_back(std::make_pair(half_edge(l, h), id_in++));
Chris@16 53 }
Chris@16 54 half_edges_out.reserve(half_edges.size());
Chris@16 55 // Apparently no need to pre-sort data when calling validate_scan.
Chris@16 56 if (half_edges.size() != 0) {
Chris@16 57 line_intersection<Unit>::validate_scan(
Chris@16 58 half_edges_out, half_edges.begin(), half_edges.end());
Chris@16 59 }
Chris@16 60
Chris@16 61 result.reserve(result.size() + half_edges_out.size());
Chris@16 62 for (std::size_t i = 0; i < half_edges_out.size(); ++i) {
Chris@16 63 std::size_t id = (std::size_t)(half_edges_out[i].second);
Chris@16 64 Point l = half_edges_out[i].first.first;
Chris@16 65 Point h = half_edges_out[i].first.second;
Chris@16 66 result.push_back(std::make_pair(id, construct<Segment>(l, h)));
Chris@16 67 }
Chris@16 68 }
Chris@16 69
Chris@16 70 template <typename SegmentContainer, typename SegmentIterator>
Chris@16 71 typename enable_if<
Chris@16 72 typename gtl_and<
Chris@16 73 typename gtl_if<
Chris@16 74 typename is_segment_concept<
Chris@16 75 typename geometry_concept<
Chris@16 76 typename std::iterator_traits<SegmentIterator>::value_type
Chris@16 77 >::type
Chris@16 78 >::type
Chris@16 79 >::type,
Chris@16 80 typename gtl_if<
Chris@16 81 typename is_segment_concept<
Chris@16 82 typename geometry_concept<
Chris@16 83 typename SegmentContainer::value_type
Chris@16 84 >::type
Chris@16 85 >::type
Chris@16 86 >::type
Chris@16 87 >::type,
Chris@16 88 void
Chris@16 89 >::type
Chris@16 90 intersect_segments(
Chris@16 91 SegmentContainer& result,
Chris@16 92 SegmentIterator first,
Chris@16 93 SegmentIterator last) {
Chris@16 94 typedef typename SegmentContainer::value_type segment_type;
Chris@16 95 typedef typename segment_traits<segment_type>::coordinate_type Unit;
Chris@16 96 typedef typename scanline_base<Unit>::Point Point;
Chris@16 97 typedef typename scanline_base<Unit>::half_edge half_edge;
Chris@16 98 typedef int segment_id;
Chris@16 99 std::vector<std::pair<half_edge, segment_id> > half_edges;
Chris@16 100 std::vector<std::pair<half_edge, segment_id> > half_edges_out;
Chris@16 101 segment_id id_in = 0;
Chris@16 102 half_edges.reserve(std::distance(first, last));
Chris@16 103 for (; first != last; ++first) {
Chris@16 104 Point l, h;
Chris@16 105 assign(l, low(*first));
Chris@16 106 assign(h, high(*first));
Chris@16 107 half_edges.push_back(std::make_pair(half_edge(l, h), id_in++));
Chris@16 108 }
Chris@16 109 half_edges_out.reserve(half_edges.size());
Chris@16 110 // Apparently no need to pre-sort data when calling validate_scan.
Chris@16 111 if (half_edges.size() != 0) {
Chris@16 112 line_intersection<Unit>::validate_scan(
Chris@16 113 half_edges_out, half_edges.begin(), half_edges.end());
Chris@16 114 }
Chris@16 115
Chris@16 116 result.reserve(result.size() + half_edges_out.size());
Chris@16 117 for (std::size_t i = 0; i < half_edges_out.size(); ++i) {
Chris@16 118 Point l = half_edges_out[i].first.first;
Chris@16 119 Point h = half_edges_out[i].first.second;
Chris@16 120 result.push_back(construct<segment_type>(l, h));
Chris@16 121 }
Chris@16 122 }
Chris@16 123
Chris@16 124 template <typename Rectangle, typename SegmentIterator>
Chris@16 125 typename enable_if<
Chris@16 126 typename gtl_and<
Chris@16 127 typename gtl_if<
Chris@16 128 typename is_rectangle_concept<
Chris@16 129 typename geometry_concept<Rectangle>::type
Chris@16 130 >::type
Chris@16 131 >::type,
Chris@16 132 typename gtl_if<
Chris@16 133 typename is_segment_concept<
Chris@16 134 typename geometry_concept<
Chris@16 135 typename std::iterator_traits<SegmentIterator>::value_type
Chris@16 136 >::type
Chris@16 137 >::type
Chris@16 138 >::type
Chris@16 139 >::type,
Chris@16 140 bool
Chris@16 141 >::type
Chris@16 142 envelope_segments(
Chris@16 143 Rectangle& rect,
Chris@16 144 SegmentIterator first,
Chris@16 145 SegmentIterator last) {
Chris@16 146 for (SegmentIterator it = first; it != last; ++it) {
Chris@16 147 if (it == first) {
Chris@16 148 set_points(rect, low(*it), high(*it));
Chris@16 149 } else {
Chris@16 150 encompass(rect, low(*it));
Chris@16 151 encompass(rect, high(*it));
Chris@16 152 }
Chris@16 153 }
Chris@16 154 return first != last;
Chris@16 155 }
Chris@16 156 } // polygon
Chris@16 157 } // boost
Chris@16 158
Chris@16 159 #endif // BOOST_POLYGON_SEGMENT_UTILS_HPP