Getting the bounding box of a vector of points?

Question

I have a vector of points stored in a std::vector instance. I want to calculate the bounding box of these points. I've 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 produces weird results. In reality I'm interested only the first and last points of my bounding box:

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

If my points represent the diagonal line I'm interested only in point 1 and 4.

Are there smart ways to get this with the standard libraries or Boost?

---

CURRENT SOLUTION:

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 are making too strong an assumption about the shape of the bounding box. Consider these two points:

          1
         /
        /
       /
      2

The correct bounding box is

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

Notice that the bounding box corners aren't actually points in your vector. Instead, they're points formed by combining coordinates from different points in the vector. Moreover, if you look at your two comparison functions, you'll find that given these two points, neither point compares less than or greater than the other point, since each one has one coordinate that is higher than the other and one that is lower than the other.

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

1. Find the point with the min x value.
2. Find the point with the max x value.
3. Find the point with the min y value.
4. Find the point with the max y value.
5. Combine the x and y from the points with the min x and y value into one corner point.
6. Combine the x and y from the points with the max x and y value into one corner point.

You can do this using the new C++11 std::minmax_element algorithm, 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

Simply iterate over all elements and keep track of the current min/max. You can use boost::minmax to update both at the same time. Really no need to iterate twice over your dataset.