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

У меня есть вектор точек, хранящийся в экземпляре 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;
    }

c++ boost std bounding-box
person nkint    schedule 30.01.2012    source источник

Ответы (3)


arrow_upward
15
arrow_downward

Я думаю, проблема в том, что ваши функции сравнения делают слишком сильное предположение о форме ограничивающей рамки. Рассмотрим эти два момента:

          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 вместе с лямбда-выражениями:

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

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

person templatetypedef    schedule 30.01.2012
comment
все клар! спасибо за хорошее объяснение, но у меня нет С++ 11, поэтому я использовал 4 min_element.. - person nkint; 31.01.2012
comment
@nkint- Вместо того, чтобы определять четыре функции и каждый раз использовать min_element, почему бы просто не определить две функции сравнения, а затем использовать max_element, где это уместно? Это сэкономит вам много кода и сделает программу более удобной для чтения. - person templatetypedef; 31.01.2012

arrow_upward
3
arrow_downward

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

person Anteru    schedule 30.01.2012
comment
Но, тем не менее, даже с этими изменениями код все равно не будет работать, потому что функции сравнения не будут правильно улавливать углы во всех случаях. - person templatetypedef; 31.01.2012
comment
Начните с первой точки как min/max как в x/y, так и в вашем цикле, просто обновите x,y отдельно. - person Anteru; 31.01.2012

arrow_upward
2
arrow_downward

Если у вас нет С++ 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);
person Gianluigi    schedule 07.08.2012