Mercurial > hg > vamp-build-and-test

annotate DEPENDENCIES/generic/include/boost/polygon/segment_utils.hpp @ 125:34e428693f5d vext

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