Получение ограничивающего прямоугольника вектора точек?

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. Найти точку с помощьюмаксимальное значение x.
3. Найдите точку со значением min y.
4. Найдите точку со значением max y.
5. Объедините x и y из точек с помощьюзначения min x и y в одну угловую точку.
6. Объедините x и y из точек с максимальными значениями x и y в одну угловую точку.

Вы можете сделать этоиспользуя новый алгоритм C ++ 11 std::minmax_element вместе с лямбдами:

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

Надеюсь, это поможет!

Answer 2

Просто переберите все элементы и следите за текущими минимальными и максимальными значениями. Вы можете использовать boost::minmax для обновления обоих одновременно. На самом деле нет необходимости дважды повторять свой набор данных.

Answer 3

Если у вас нет c ++ 11, вы можете использовать boost ::gorith :: 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);