获得点矢量的边界框？

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

Answer 1

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

          1
         /
        /
       /
      2

正确的边界框是

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

请注意,边界框角实际上不是向量中的点.相反,它们是通过组合矢量中不同点的坐标而形成的点.此外,如果你看看你的两个比较函数,你会发现给定这两个点,这两个点都不会比另一个点小于或大于另一个点,因为每个点都有一个高于另一个的坐标和一个低于另一个的坐标.比另一个.

要获取边界框,您应该执行以下操作:

1. 找到min x值的点.
2. 找到max x值的点.
3. 找到具有最小值的点.
4. 找到具有最大y值的点.
5. 将具有最小x和y值的点中的x和y组合成一个角点.
6. 将具有最大x和y值的点中的x和y组合成一个角点.

你可以使用新的C++ 11 std::minmax_element算法和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);

希望这可以帮助!