获取点的矢量的边界框？ [英] Getting the bounding box of a vector of points?

问题描述

我有存储在的std ::矢量实例点的矢量。我想计算这些点的边框。我试过这个code：

 布尔_compare1（ofPoint常量和放大器; P1，ofPoint常量和放大器; P2）{
    返回p1.x＆LT; p2.x＆功放;＆安培; p1.y＆LT; p2.y;
}
布尔_compare4（ofPoint常量和放大器; P1，ofPoint常量和放大器; P2）{
    返回p1.x＆GT; p2.x＆功放;＆安培; p1.y＆GT; p2.y;
}
矢量＆lt; ofPoint＆GT;点;// ...
如果（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）;
}
 

但是，这code会产生奇怪的结果。在现实中，我只关心我的边框的第一个和最后一个点：

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

如果我的观点重新present对角线我感兴趣的只是点1和4。

是否有聪明的方法与标准库得到这个或Boost？

---

当前的解决方案：

 布尔_compare_min_x（ofPoint常量和放大器; P1，ofPoint常量和放大器; P2）{返回p1.x＆LT; p2.x; }
布尔_compare_min_y（ofPoint常量和放大器; P1，ofPoint常量和放大器; P2）{返回p1.y＆LT; p2.y; }// ....    如果（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））。ÿ;        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））。ÿ;
    }
 

解决方案

我认为问题是，你的比较函数正在过强的左右边框的形状的假设。考虑以下两点：

  1
         /
        /
       /
      2
 

正确的边框

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

请注意，边框棱角并没有实际的矢量点。相反，它们是由在载体中组合来自不同点的坐标形成的点。此外，如果你看看你的两个比较函数，你会发现，鉴于这两点，一点都不比相比较其他点小于或更高，因为每个人都有一个坐标比其他的高，一个是低比其他

要得到你的边框，你应该做到以下几点：

1. 找到的最小x值的点。


2. 找到的最大x值的位置。


3. 找到的最小y值的点。


4. 找到的最大y值的点。


5. 从具有最小x和y的值成一个角点的点结合的x和y。


6. 从具有最大x和y的值成一个角点的点结合的x和y。

您可以做到这一点使用新的C ++ 11 的std :: minmax_element 算法，具有沿lambda表达式：

 自动xExtremes =的std :: minmax_element（v.begin（），v.end（）
                                     []（常量ofPoint＆放大器; LHS，常量ofPoint和放大器; RHS）{
                                        返回lhs.x＆LT; rhs.x;
                                     }）;汽车yExtremes =的std :: minmax_element（v.begin（），v.end（）
                                     []（常量ofPoint＆放大器; LHS，常量ofPoint和放大器; RHS）{
                                        返回lhs.y＆LT; rhs.y;
                                     }）;ofPoint upperLeft（xExtremes.first-＆GT; X，yExtremes.first-＆GT; Y）;
ofPoint lowerRight（xExtremes.second-＆GT; X，yExtremes.second-＆GT; Y）;
 

希望这有助于！

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

解决方案

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!

这篇关于获取点的矢量的边界框？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！