Getting bounding box of a point vector?

Question

I have a vector of points stored in an instance of std::vector . I want to calculate the bounding box of these points. I tried with this code:

 bool _compare1(ofPoint const &p1, ofPoint const &p2) { return p1.x < p2.x && p1.y < p2.y; } bool _compare4(ofPoint const &p1, ofPoint const &p2) { return p1.x > p2.x && p1.y > p2.y; } vector<ofPoint> points; // ... if(points.size()>1) { ofPoint p_min = *std::min_element(points.begin(), points.end(), &_compare1); ofPoint p_max = *std::min_element(points.begin(), points.end(), &_compare4); } 

But this code creates strange results. In fact, I am only interested in the first and last points of my bounding box:

 1------2 |\ | | \ | | \ | | \ | | \ | | \| 3------4 

If my points represent a diagonal line, I am only interested in points 1 and 4.

Are there any reasonable ways to get this with standard libraries or Boost?

---

CURRENT DECISION:

 bool _compare_min_x(ofPoint const &p1, ofPoint const &p2) { return p1.x < p2.x; } bool _compare_min_y(ofPoint const &p1, ofPoint const &p2) { return p1.y < p2.y; } // .... if(points.size()>1) { min_x = (*std::min_element(points.begin(), points.end(), &_compare_min_x)).x; min_y = (*std::min_element(points.begin(), points.end(), &_compare_min_y)).y; max_x = (*std::max_element(points.begin(), points.end(), &_compare_min_x)).x; max_y = (*std::max_element(points.begin(), points.end(), &_compare_min_y)).y; } 

Answer 1

I think the problem is that your comparison functions make too strong an assumption about the shape of the bounding box. Consider these two points:

  1 / / / 2 

Correct bounding box

  +---1 | /| | / | |/ | 2---+ 

Note that the corners of the bounding box are not points of your vector. Instead, they are points formed by combining coordinates from different points of the vector. Moreover, if you look at your two comparison functions, you will find that, given these two points, not one point is compared less or more than the other point, since each of them has one coordinate that is higher than the other, and lower than the other.

To get your bounding box, you must do the following:

• Find the point with the minimum x value.
• Find the point with the maximum value.
• Find the point with the minimum value.
• Find the point with the maximum value.
• Combine x and y from points with a minimum value of x and y into one corner point.
• Combine x and y from the points with the maximum value of x and y into one corner point.

You can do this using the new C ++ 11 std::minmax_element , along with lambdas:

 auto xExtremes = std::minmax_element(v.begin(), v.end(), [](const ofPoint& lhs, const ofPoint& rhs) { return lhs.x < rhs.x; }); auto yExtremes = std::minmax_element(v.begin(), v.end(), [](const ofPoint& lhs, const ofPoint& rhs) { return lhs.y < rhs.y; }); ofPoint upperLeft(xExtremes.first->x, yExtremes.first->y); ofPoint lowerRight(xExtremes.second->x, yExtremes.second->y); 

Hope this helps!

Answer 2

Just iterate over all the elements and track the current min / max. You can use boost::minmax to update both at the same time. Actually there is no need to repeat twice over your data set.

Answer 3

If you do not have C ++ 11, you can use boost :: algorithm :: minmax_element.

 #include <boost/algorithm/minmax_element.hpp> bool compareX(ofPoint lhs, ofPoint rhs) { return lhs.x < rhs.x; }; bool compareY(ofPoint lhs, ofPoint rhs) { return lhs.y < rhs.y; }; // .... pair<vector<ofPoint>::iterator, vector<ofPoint>::iterator> xExtremes, yExtremes; xExtremes = boost::minmax_element(overlap_point.begin(), overlap_point.end(), compareX); yExtremes = boost::minmax_element(overlap_point.begin(), overlap_point.end(), compareY); ofPoint upperLeft(xExtremes.first->x, yExtremes.first->y); ofPoint lowerRight(xExtremes.second->x, yExtremes.second->y);