HypervolumeContribution3D.h
Go to the documentation of this file.
1 /*!
2  *
3  * \author O.Krause, T. Glasmachers
4  * \date 2014-2016
5  *
6  *
7  * \par Copyright 1995-2017 Shark Development Team
8  *
9  * <BR><HR>
10  * This file is part of Shark.
11  * <http://shark-ml.org/>
12  *
13  * Shark is free software: you can redistribute it and/or modify
14  * it under the terms of the GNU Lesser General Public License as published
15  * by the Free Software Foundation, either version 3 of the License, or
16  * (at your option) any later version.
17  *
18  * Shark is distributed in the hope that it will be useful,
19  * but WITHOUT ANY WARRANTY; without even the implied warranty of
20  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
21  * GNU Lesser General Public License for more details.
22  *
23  * You should have received a copy of the GNU Lesser General Public License
24  * along with Shark. If not, see <http://www.gnu.org/licenses/>.
25  *
26  */
27 #ifndef SHARK_ALGORITHMS_DIRECTSEARCH_HYPERVOLUME_CONTRIBUTION_3D_H
28 #define SHARK_ALGORITHMS_DIRECTSEARCH_HYPERVOLUME_CONTRIBUTION_3D_H
29 
30 #include <shark/LinAlg/Base.h>
32 
33 #include <algorithm>
34 #include <vector>
35 #include <deque>
36 #include <set>
37 #include <utility>
38 
39 namespace shark {
40 /// \brief Finds the hypervolume contribution for points in 3DD
41 ///
42 /// The algorithm sweeps ascending through the z-direction and keeps track of
43 /// of the current cut through the volume at a given z-value.
44 /// the cut is partitioned in boxes representing parts of the hypervolume
45 /// that is not hared with any other point. thus the sum of
46 /// the volume of all boxes belonging to a point is making
47 /// up its hypervolume.
48 ///
49 /// The algorithm runs in O(n log(n)) time.
51 private:
52  struct Point{
53  Point(){}
54 
55  Point(double f1, double f2, double f3, std::size_t index)
56  : f1(f1)
57  , f2(f2)
58  , f3(f3)
59  , index(index)
60  {}
61 
62  bool operator<(Point const& rhs) const{//sort by x1 coordinate
63  return f1 < rhs.f1;
64  }
65 
66  template<class S>
67  friend S& operator<<(S& s,Point const& p){
68  s<<"("<<p.f1<<","<<p.f2<<","<<p.f3<<")";
69  return s;
70  }
71 
72  double f1;
73  double f2;
74  double f3;
75  std::size_t index;
76  };
77 
78  ///\brief Box representing part of the hypervolume of a point
79  ///
80  /// by convention a unclosed box has lower.f3=upper.f3 and when its
81  /// upper boundary is found, it is set to the right value and its volume
82  /// is computed.
83  ///
84  /// Boxes are stored in boxlists sorted ascending by x-coordinate.
85  struct Box{
86  Point lower;
87  Point upper;
88 
89  double volume()const{
90  return (upper.f1-lower.f1)*(upper.f2-lower.f2)*(upper.f3-lower.f3);
91  }
92  };
93 
94 
95  /// \brief Updates the volumes of the first nondominated neighbour of the new point to the right
96  ///
97  /// The volume of the newly added point intersects with boxes of its neighbour in the front.
98  /// Thus we remove all boxes intersecting with this one, compute their volume and add it to
99  /// the total volume of right. The boxes are replaced by one new box representing the non-intersecting
100  /// contribution that is still to be determined.
101  double cutBoxesOnTheRight(std::deque<Box>& rightList, Point const& point, Point const& right)const{
102  if(rightList.empty()) return 0;//nothing to do
103 
104  double addedContribution = 0;
105  double xright = right.f1;
106  //iterate through all partly covered boxes
107  while(!rightList.empty()){
108  Box& b = rightList.front();
109  //if the box is not partially covered, we are done as by sorting all other boxes have smaller y-value
110  if(b.upper.f2 <= point.f2)
111  break;
112 
113  //add volume of box
114  b.upper.f3 = point.f3;
115  addedContribution += b.volume();
116  xright = b.upper.f1;
117  rightList.pop_front();
118  }
119  if(xright != right.f1){//if we removed a box
120  //in the last step, we have removed boxes that were only partially
121  //covered. replace them by a box that covers their area
122  Box rightBox;
123  rightBox.lower.f1 = right.f1;
124  rightBox.lower.f2 = right.f2;
125  rightBox.lower.f3 = point.f3;
126  rightBox.upper.f1 = xright;
127  rightBox.upper.f2 = point.f2;
128  rightBox.upper.f3 = point.f3;
129  //upper.f3 remains unspecified until the box is completed
130  rightList.push_front(rightBox);
131  }
132  return addedContribution;
133  }
134 
135  /// \brief Updates the volumes of the first neighbour of the new point to the left
136  ///
137  /// The volume of the newly added point intersects with boxes of its neighbours in the front.
138  /// On the left side, we can even completely dominate whole boxes which are removed.
139  /// Otherwise, the boxes are intersected with the volume of the new point and shrunk to the remainder
140  /// This method removes the volume of boxes removed that way.
141  double cutBoxesOnTheLeft(std::deque<Box>& leftList, Point const& point)const{
142  double addedContribution = 0;
143  while(!leftList.empty()){
144  Box& b= leftList.back();
145  if(point.f1 < b.lower.f1 ){//is the box completely covered?
146  b.upper.f3 = point.f3;
147  addedContribution += b.volume();
148  leftList.pop_back();
149  }else if(point.f1 < b.upper.f1 ){//is the box partly covered?
150  //Add contribution
151  b.upper.f3 = point.f3;
152  addedContribution += b.volume();
153  //replace box by the new box that starts from the height of p
154  b.upper.f1 = point.f1;
155  b.lower.f3 = point.f3;
156  break;
157  }else{
158  break;//uncovered
159  }
160  }
161  return addedContribution;
162  }
163 
164  std::vector<KeyValuePair<double,std::size_t> > allContributions(std::vector<Point> const& points)const{
165 
166  std::size_t n = points.size();
167  //for every point we have a list of boxes that make up its contribution, L in the paper.
168  //the list stores the boxes ordered by x-value + one additional (empty) list for the added corner points
169  std::vector<std::deque<Box> > boxlists(n+1);
170  //contributions are accumulated here for every point
171  std::vector<KeyValuePair<double,std::size_t> > contributions(n+1,makeKeyValuePair(0.0,1));
172  for(std::size_t i = 0; i != n; ++i){
173  contributions[i].value = points[i].index;
174  }
175 
176  //The tree stores values ordered by x-value and is our xy front.
177  // even though we store 3D points, the third component is not relevant
178  // thus the values are also ordered by y-component.
179  std::multiset<Point> xyFront;
180  //insert points indiating the reference frame, required for setting up the boxes.
181  //The 0 stands for the reference point (0,0) in x-y coordinate
182  //the -inf ensures that the point never becomes dominated
183  double inf = std::numeric_limits<double>::max();//inf can be more costly to work with!
184  xyFront.insert(Point(-inf,0,-inf,n));
185  xyFront.insert(Point(0,-inf,-inf,n));
186 
187  //main loop
188  for(std::size_t i = 0; i != n; ++i){
189  Point const& point = points[i];
190 
191  //position of the point with next smaller x-value in the front
192  auto left = xyFront.lower_bound(point);//gives larger or equal
193  --left;//first smaller element
194 
195  //check if the new point is dominated
196  if(left->f2 < point.f2)
197  continue;
198 
199  //find the indizes of all points dominated by the new point
200  //and find the position of the next nondominated neighbour
201  //with larger x-value
202  std::vector<std::size_t> dominatedPoints;
203  auto right= left; ++right;
204  while((*right).f2 > point.f2){
205  dominatedPoints.push_back(right->index);
206  ++right;
207  }
208 
209 
210  //erase all dominated points from the front
211  xyFront.erase(std::next(left),right);
212 
213  //add point to the front
214  xyFront.insert(Point(point.f1,point.f2,point.f3,i));
215  //reorder dominated points so that the largest x-values are at the front
216  std::reverse(dominatedPoints.begin(),dominatedPoints.end());
217 
218 
219  //cut and remove neighbouring boxes
220  contributions[left->index].key += cutBoxesOnTheLeft(boxlists[left->index],point);
221  contributions[right->index].key += cutBoxesOnTheRight(boxlists[right->index],point,*right);
222 
223  //Remove dominated points with their boxes
224  //and create new boxes for the new point
225  double xright = right->f1;
226  for(std::size_t domIndex:dominatedPoints){
227  Point dominated = points[domIndex];
228  auto& domList = boxlists[domIndex];
229  for(Box& b:domList){
230  b.upper.f3 = point.f3;
231  contributions[domIndex].key += b.volume();
232  }
233  Box leftBox;
234  leftBox.lower.f1 = dominated.f1;
235  leftBox.lower.f2 = point.f2;
236  leftBox.lower.f3 = point.f3;
237 
238  leftBox.upper.f1 = xright;
239  leftBox.upper.f2 = dominated.f2;
240  leftBox.upper.f3 = leftBox.lower.f3;
241  //upper.f3 remains unspecified until the box is completed
242  boxlists[i].push_front(leftBox);
243 
244  xright = dominated.f1;
245  }
246  //Add the new box created by this point
247  Box newBox;
248  newBox.lower.f1 = point.f1;
249  newBox.lower.f2 = point.f2;
250  newBox.lower.f3 = point.f3;
251  newBox.upper.f1 = xright;
252  newBox.upper.f2 = left->f2;
253  newBox.upper.f3 = newBox.lower.f3;
254  boxlists[i].push_front(newBox);
255  }
256 
257  //go through the front and close all remaining boxes
258  for(Point const& p: xyFront){
259  std::size_t index = p.index;
260  for(Box & b: boxlists[index]){
261  b.upper.f3 = 0.0;
262  contributions[index].key +=b.volume();
263  }
264  }
265 
266  //finally sort contributions descending and return it
267  contributions.pop_back();//remove the superfluous last element
268  std::sort(contributions.begin(),contributions.end());
269 
270  return contributions;
271  }
272 
273 public:
274  /// \brief Returns the index of the points with smallest contribution as well as their contribution.
275  ///
276  /// \param [in] points The set \f$S\f$ of points from which to select the smallest contributor.
277  /// \param [in] k The number of points to select.
278  /// \param [in] referencePointThe reference Point\f$\vec{r} \in \mathbb{R}^2\f$ for the hypervolume calculation, needs to fulfill: \f$ \forall s \in S: s \preceq \vec{r}\f$.
279  template<class Set, typename VectorType>
280  std::vector<KeyValuePair<double,std::size_t> > smallest(Set const& points, std::size_t k, VectorType const& ref)const{
281  SHARK_RUNTIME_CHECK(points.size() >= k, "There must be at least k points in the set");
282  std::vector<Point> front;
283  for(std::size_t i = 0; i != points.size(); ++i){
284  front.emplace_back(points[i](0)-ref(0),points[i](1)-ref(1),points[i](2)-ref(2),i);
285  }
286  std::sort(
287  front.begin(),front.end(),
288  [](Point const& lhs, Point const& rhs){
289  return lhs.f3 < rhs.f3;
290  }
291  );
292 
293  auto result = allContributions(front);
294  result.erase(result.begin()+k,result.end());
295  return result;
296  }
297 
298  /// \brief Returns the index of the points with smallest contribution as well as their contribution.
299  ///
300  /// As no reference point is given, the extremum points can not be computed and are never selected.
301  ///
302  /// \param [in] points The set \f$S\f$ of points from which to select the smallest contributor.
303  /// \param [in] k The number of points to select.
304  template<class Set>
305  std::vector<KeyValuePair<double,std::size_t> > smallest(Set const& points, std::size_t k)const{
306  SHARK_RUNTIME_CHECK(points.size() >= k, "There must be at least k points in the set");
307  //reference point computation, and obtain the indizes of the extremum elements
308  std::size_t minIndex[]={0,0,0};
309  double minVal[]={points[0](0),points[0](1),points[0](2)};
310  double ref[]={points[0](0),points[0](1),points[0](2)};
311  for(std::size_t i = 0; i != points.size(); ++i){
312  for(std::size_t j = 0; j != 3; ++j){
313  if(points[i](j)< minVal[j]){
314  minVal[j] = points[i](j);
315  minIndex[j]=i;
316  }
317  ref[j] = std::max(ref[j],points[i](j));
318  }
319  }
320 
321 
322  std::vector<Point> front;
323  for(std::size_t i = 0; i != points.size(); ++i){
324  front.emplace_back(points[i](0)-ref[0],points[i](1)-ref[1],points[i](2)-ref[2],i);
325  }
326  std::sort(
327  front.begin(),front.end(),
328  [](Point const& lhs, Point const& rhs){
329  return lhs.f3 < rhs.f3;
330  }
331  );
332 
333  auto result = allContributions(front);
334  for(std::size_t j = 0; j != 3; ++j){
335  auto pos = std::find_if(
336  result.begin(),result.end(),
337  [&](KeyValuePair<double,std::size_t> const& p){
338  return p.value == minIndex[j];
339  }
340  );
341  if(pos != result.end())
342  result.erase(pos);
343  }
344  result.erase(result.begin()+k,result.end());
345  return result;
346  }
347 
348 
349  /// \brief Returns the index of the points with largest contribution as well as their contribution.
350  ///
351  /// \param [in] points The set \f$S\f$ of points from which to select the largest contributor.
352  /// \param [in] referencePointThe reference Point\f$\vec{r} \in \mathbb{R}^2\f$ for the hypervolume calculation, needs to fulfill: \f$ \forall s \in S: s \preceq \vec{r}\f$.
353  template<class Set, typename VectorType>
354  std::vector<KeyValuePair<double,std::size_t> > largest(Set const& points, std::size_t k, VectorType const& ref)const{
355  std::vector<Point> front;
356  for(std::size_t i = 0; i != points.size(); ++i){
357  front.emplace_back(points[i](0)-ref(0),points[i](1)-ref(1),points[i](2)-ref(2),i);
358  }
359  std::sort(
360  front.begin(),front.end(),
361  [](Point const& lhs, Point const& rhs){
362  return lhs.f3 < rhs.f3;
363  }
364  );
365 
366  auto result = allContributions(front);
367  result.erase(result.begin(),result.end()-k);
368  std::reverse(result.begin(),result.end());
369  return result;
370  }
371 
372 
373  /// \brief Returns the index of the points with largest contribution as well as their contribution.
374  ///
375  /// As no reference point is given, the extremum points can not be computed and are never selected.
376  ///
377  /// \param [in] points The set \f$S\f$ of points from which to select the largest contributor.
378  /// \param [in] k The number of points to select.
379  template<class Set>
380  std::vector<KeyValuePair<double,std::size_t> > largest(Set const& points, std::size_t k)const{
381  SHARK_RUNTIME_CHECK(points.size() >= k, "There must be at least k points in the set");
382  //reference point computation, and obtain the indizes of the extremum elements
383  std::size_t minIndex[]={0,0,0};
384  double minVal[]={points[0](0),points[0](1),points[0](2)};
385  double ref[]={points[0](0),points[0](1),points[0](2)};
386  for(std::size_t i = 0; i != points.size(); ++i){
387  for(std::size_t j = 0; j != 3; ++j){
388  if(points[i](j)< minVal[j]){
389  minVal[j] = points[i](j);
390  minIndex[j]=i;
391  }
392  ref[j] = std::max(ref[j],points[i](j));
393  }
394  }
395 
396 
397  std::vector<Point> front;
398  for(std::size_t i = 0; i != points.size(); ++i){
399  front.emplace_back(points[i](0)-ref[0],points[i](1)-ref[1],points[i](2)-ref[2],i);
400  }
401  std::sort(
402  front.begin(),front.end(),
403  [](Point const& lhs, Point const& rhs){
404  return lhs.f3 < rhs.f3;
405  }
406  );
407 
408  auto result = allContributions(front);
409  for(std::size_t j = 0; j != 3; ++j){
410  auto pos = std::find_if(
411  result.begin(),result.end(),
412  [&](KeyValuePair<double,std::size_t> const& p){
413  return p.value == minIndex[j];
414  }
415  );
416  if(pos != result.end())
417  result.erase(pos);
418  }
419  if(result.size() > k)
420  result.erase(result.begin(),result.end()-k);
421  std::reverse(result.begin(),result.end());
422  return result;
423  }
424 };
425 
426 }
427 #endif