c++ - 获取点向量的边界框？

Question

我有一个存储在std::vector实例中的点向量。我想计算这些点的边界框。我试过这段代码：

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);
}

但是这段代码会产生奇怪的结果。实际上，我只对边界框的第一个和最后一个点感兴趣：

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

如果我的点代表对角线，我只对第 1 点和第 4 点感兴趣。

有没有聪明的方法可以通过标准库或 Boost 来实现这一点？

当前解决方案：

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;
    }

score 15 · Accepted Answer

我认为问题在于您的比较函数对边界框的形状做出了过于强烈的假设。考虑以下两点：

正确的边界框是

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

请注意，边界框角实际上并不是向量中的点。相反，它们是由向量中不同点的坐标组合而成的点。此外，如果您查看您的两个比较函数，您会发现给定这两个点，没有一个点比较小于或大于另一个点，因为每个点都有一个坐标高于另一个坐标，一个坐标低于另一个比另一个。

要获得边界框，您应该执行以下操作：

找到具有最小 x 值的点。
找到具有最大 x 值的点。
找到具有最小 y 值的点。
找到具有最大 y 值的点。
将点中的 x 和 y 与最小 x 和 y 值组合成一个角点。
将具有最大 x 和 y 值的点的 x 和 y 组合成一个角点。

您可以使用新的 C++11std::minmax_element算法和 lambda 来做到这一点：

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);

希望这可以帮助！

score 3 · Accepted Answer

只需遍历所有元素并跟踪当前的最小值/最大值。您可以使用boost::minmax同时更新两者。真的不需要在你的数据集上迭代两次。

score 2 · Accepted Answer

如果你没有 c++11，你可以使用 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);

c++ - 获取点向量的边界框？

当前解决方案：

3 回答 3

Related

Reference