27 #ifndef SHARK_ALGORITHMS_DIRECTSEARCH_HYPERVOLUME_CONTRIBUTION_3D_H 28 #define SHARK_ALGORITHMS_DIRECTSEARCH_HYPERVOLUME_CONTRIBUTION_3D_H 55 Point(
double f1,
double f2,
double f3, std::size_t index)
62 bool operator<(Point
const& rhs)
const{
68 s<<
"("<<p.f1<<
","<<p.f2<<
","<<p.f3<<
")";
90 return (upper.f1-lower.f1)*(upper.f2-lower.f2)*(upper.f3-lower.f3);
101 double cutBoxesOnTheRight(std::deque<Box>& rightList, Point
const& point, Point
const& right)
const{
102 if(rightList.empty())
return 0;
104 double addedContribution = 0;
105 double xright = right.f1;
107 while(!rightList.empty()){
108 Box& b = rightList.front();
110 if(b.upper.f2 <= point.f2)
114 b.upper.f3 = point.f3;
115 addedContribution += b.volume();
117 rightList.pop_front();
119 if(xright != right.f1){
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;
130 rightList.push_front(rightBox);
132 return addedContribution;
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 ){
146 b.upper.f3 = point.f3;
147 addedContribution += b.volume();
149 }
else if(point.f1 < b.upper.f1 ){
151 b.upper.f3 = point.f3;
152 addedContribution += b.volume();
154 b.upper.f1 = point.f1;
155 b.lower.f3 = point.f3;
161 return addedContribution;
164 std::vector<KeyValuePair<double,std::size_t> > allContributions(std::vector<Point>
const& points)
const{
166 std::size_t n = points.size();
169 std::vector<std::deque<Box> > boxlists(n+1);
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;
179 std::multiset<Point> xyFront;
183 double inf = std::numeric_limits<double>::max();
184 xyFront.insert(Point(-inf,0,-inf,n));
185 xyFront.insert(Point(0,-inf,-inf,n));
188 for(std::size_t i = 0; i != n; ++i){
189 Point
const& point = points[i];
192 auto left = xyFront.lower_bound(point);
196 if(left->f2 < point.f2)
202 std::vector<std::size_t> dominatedPoints;
203 auto right= left; ++right;
204 while((*right).f2 > point.f2){
205 dominatedPoints.push_back(right->index);
211 xyFront.erase(std::next(left),right);
214 xyFront.insert(Point(point.f1,point.f2,point.f3,i));
216 std::reverse(dominatedPoints.begin(),dominatedPoints.end());
220 contributions[left->index].key += cutBoxesOnTheLeft(boxlists[left->index],point);
221 contributions[right->index].key += cutBoxesOnTheRight(boxlists[right->index],point,*right);
225 double xright = right->f1;
226 for(std::size_t domIndex:dominatedPoints){
227 Point dominated = points[domIndex];
228 auto& domList = boxlists[domIndex];
230 b.upper.f3 = point.f3;
231 contributions[domIndex].key += b.volume();
234 leftBox.lower.f1 = dominated.f1;
235 leftBox.lower.f2 = point.f2;
236 leftBox.lower.f3 = point.f3;
238 leftBox.upper.f1 = xright;
239 leftBox.upper.f2 = dominated.f2;
240 leftBox.upper.f3 = leftBox.lower.f3;
242 boxlists[i].push_front(leftBox);
244 xright = dominated.f1;
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);
258 for(Point
const& p: xyFront){
259 std::size_t index = p.index;
260 for(Box & b: boxlists[index]){
262 contributions[index].key +=b.volume();
267 contributions.pop_back();
268 std::sort(contributions.begin(),contributions.end());
270 return contributions;
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{
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);
287 front.begin(),front.end(),
288 [](Point
const& lhs, Point
const& rhs){
289 return lhs.f3 < rhs.f3;
293 auto result = allContributions(front);
294 result.erase(result.begin()+k,result.end());
305 std::vector<KeyValuePair<double,std::size_t> >
smallest(Set
const& points, std::size_t k)
const{
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);
317 ref[j] = std::max(ref[j],points[i](j));
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);
327 front.begin(),front.end(),
328 [](Point
const& lhs, Point
const& rhs){
329 return lhs.f3 < rhs.f3;
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(),
338 return p.value == minIndex[j];
341 if(pos != result.end())
344 result.erase(result.begin()+k,result.end());
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);
360 front.begin(),front.end(),
361 [](Point
const& lhs, Point
const& rhs){
362 return lhs.f3 < rhs.f3;
366 auto result = allContributions(front);
367 result.erase(result.begin(),result.end()-k);
368 std::reverse(result.begin(),result.end());
380 std::vector<KeyValuePair<double,std::size_t> >
largest(Set
const& points, std::size_t k)
const{
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);
392 ref[j] = std::max(ref[j],points[i](j));
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);
402 front.begin(),front.end(),
403 [](Point
const& lhs, Point
const& rhs){
404 return lhs.f3 < rhs.f3;
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(),
413 return p.value == minIndex[j];
416 if(pos != result.end())
419 if(result.size() > k)
420 result.erase(result.begin(),result.end()-k);
421 std::reverse(result.begin(),result.end());