]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | /* |
2 | Copyright 2008 Intel Corporation | |
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 | #ifndef BOOST_POLYGON_PROPERTY_MERGE_45_HPP | |
9 | #define BOOST_POLYGON_PROPERTY_MERGE_45_HPP | |
10 | namespace boost { namespace polygon{ | |
11 | ||
12 | template <typename Unit, typename property_type> | |
13 | struct polygon_45_property_merge { | |
14 | ||
15 | typedef point_data<Unit> Point; | |
16 | typedef typename coordinate_traits<Unit>::manhattan_area_type LongUnit; | |
17 | ||
18 | template <typename property_map> | |
19 | static inline void merge_property_maps(property_map& mp, const property_map& mp2, bool subtract = false) { | |
20 | polygon_45_touch<Unit>::merge_property_maps(mp, mp2, subtract); | |
21 | } | |
22 | ||
23 | class CountMerge { | |
24 | public: | |
25 | inline CountMerge() : counts() {} | |
26 | //inline CountMerge(int count) { counts[0] = counts[1] = count; } | |
27 | //inline CountMerge(int count1, int count2) { counts[0] = count1; counts[1] = count2; } | |
28 | inline CountMerge(const CountMerge& count) : counts(count.counts) {} | |
29 | inline bool operator==(const CountMerge& count) const { return counts == count.counts; } | |
30 | inline bool operator!=(const CountMerge& count) const { return !((*this) == count); } | |
31 | //inline CountMerge& operator=(int count) { counts[0] = counts[1] = count; return *this; } | |
32 | inline CountMerge& operator=(const CountMerge& count) { counts = count.counts; return *this; } | |
33 | inline int& operator[](property_type index) { | |
34 | std::vector<std::pair<int, int> >::iterator itr = lower_bound(counts.begin(), counts.end(), std::make_pair(index, int(0))); | |
35 | if(itr != counts.end() && itr->first == index) { | |
36 | return itr->second; | |
37 | } | |
38 | itr = counts.insert(itr, std::make_pair(index, int(0))); | |
39 | return itr->second; | |
40 | } | |
41 | // inline int operator[](int index) const { | |
42 | // std::vector<std::pair<int, int> >::const_iterator itr = counts.begin(); | |
43 | // for( ; itr != counts.end() && itr->first <= index; ++itr) { | |
44 | // if(itr->first == index) { | |
45 | // return itr->second; | |
46 | // } | |
47 | // } | |
48 | // return 0; | |
49 | // } | |
50 | inline CountMerge& operator+=(const CountMerge& count){ | |
51 | merge_property_maps(counts, count.counts, false); | |
52 | return *this; | |
53 | } | |
54 | inline CountMerge& operator-=(const CountMerge& count){ | |
55 | merge_property_maps(counts, count.counts, true); | |
56 | return *this; | |
57 | } | |
58 | inline CountMerge operator+(const CountMerge& count) const { | |
59 | return CountMerge(*this)+=count; | |
60 | } | |
61 | inline CountMerge operator-(const CountMerge& count) const { | |
62 | return CountMerge(*this)-=count; | |
63 | } | |
64 | inline CountMerge invert() const { | |
65 | CountMerge retval; | |
66 | retval -= *this; | |
67 | return retval; | |
68 | } | |
69 | std::vector<std::pair<property_type, int> > counts; | |
70 | }; | |
71 | ||
72 | //output is a std::map<std::set<property_type>, polygon_45_set_data<Unit> > | |
73 | struct merge_45_output_functor { | |
74 | template <typename cT> | |
75 | void operator()(cT& output, const CountMerge& count1, const CountMerge& count2, | |
76 | const Point& pt, int rise, direction_1d end) { | |
77 | typedef typename cT::key_type keytype; | |
78 | keytype left; | |
79 | keytype right; | |
80 | int edgeType = end == LOW ? -1 : 1; | |
81 | for(typename std::vector<std::pair<property_type, int> >::const_iterator itr = count1.counts.begin(); | |
82 | itr != count1.counts.end(); ++itr) { | |
83 | left.insert(left.end(), (*itr).first); | |
84 | } | |
85 | for(typename std::vector<std::pair<property_type, int> >::const_iterator itr = count2.counts.begin(); | |
86 | itr != count2.counts.end(); ++itr) { | |
87 | right.insert(right.end(), (*itr).first); | |
88 | } | |
89 | if(left == right) return; | |
90 | if(!left.empty()) { | |
91 | //std::cout << pt.x() << " " << pt.y() << " " << rise << " " << edgeType << std::endl; | |
92 | output[left].insert_clean(typename boolean_op_45<Unit>::Vertex45(pt, rise, -edgeType)); | |
93 | } | |
94 | if(!right.empty()) { | |
95 | //std::cout << pt.x() << " " << pt.y() << " " << rise << " " << -edgeType << std::endl; | |
96 | output[right].insert_clean(typename boolean_op_45<Unit>::Vertex45(pt, rise, edgeType)); | |
97 | } | |
98 | } | |
99 | }; | |
100 | ||
101 | typedef typename std::pair<Point, | |
102 | typename boolean_op_45<Unit>::template Scan45CountT<CountMerge> > Vertex45Compact; | |
103 | typedef std::vector<Vertex45Compact> MergeSetData; | |
104 | ||
105 | struct lessVertex45Compact { | |
106 | bool operator()(const Vertex45Compact& l, const Vertex45Compact& r) { | |
107 | return l.first < r.first; | |
108 | } | |
109 | }; | |
110 | ||
111 | template <typename output_type> | |
112 | static void performMerge(output_type& result, MergeSetData& tsd) { | |
113 | ||
114 | polygon_sort(tsd.begin(), tsd.end(), lessVertex45Compact()); | |
115 | typedef std::vector<std::pair<Point, typename boolean_op_45<Unit>::template Scan45CountT<CountMerge> > > TSD; | |
116 | TSD tsd_; | |
117 | tsd_.reserve(tsd.size()); | |
118 | for(typename MergeSetData::iterator itr = tsd.begin(); itr != tsd.end(); ) { | |
119 | typename MergeSetData::iterator itr2 = itr; | |
120 | ++itr2; | |
121 | for(; itr2 != tsd.end() && itr2->first == itr->first; ++itr2) { | |
122 | (itr->second) += (itr2->second); //accumulate | |
123 | } | |
124 | tsd_.push_back(std::make_pair(itr->first, itr->second)); | |
125 | itr = itr2; | |
126 | } | |
127 | typename boolean_op_45<Unit>::template Scan45<CountMerge, merge_45_output_functor> scanline; | |
128 | for(typename TSD::iterator itr = tsd_.begin(); itr != tsd_.end(); ) { | |
129 | typename TSD::iterator itr2 = itr; | |
130 | ++itr2; | |
131 | while(itr2 != tsd_.end() && itr2->first.x() == itr->first.x()) { | |
132 | ++itr2; | |
133 | } | |
134 | scanline.scan(result, itr, itr2); | |
135 | itr = itr2; | |
136 | } | |
137 | } | |
138 | ||
139 | template <typename iT> | |
140 | static void populateMergeSetData(MergeSetData& tsd, iT begin, iT end, property_type property) { | |
141 | for( ; begin != end; ++begin) { | |
142 | Vertex45Compact vertex; | |
143 | vertex.first = typename Vertex45Compact::first_type(begin->pt.x() * 2, begin->pt.y() * 2); | |
144 | tsd.push_back(vertex); | |
145 | for(unsigned int i = 0; i < 4; ++i) { | |
146 | if(begin->count[i]) { | |
147 | tsd.back().second[i][property] += begin->count[i]; | |
148 | } | |
149 | } | |
150 | } | |
151 | } | |
152 | ||
153 | }; | |
154 | ||
155 | ||
156 | ||
157 | } | |
158 | } | |
159 | ||
160 | #endif |