Как заменить мой цикл for для нахождения минимума / максимума алгоритмом STL MIMAX

Question

Как заменить мой цикл for для нахождения минимума / максимума алгоритмом STL MIMAX

Я должен найти минимальные / максимальные значения (мин х, мин у, макс х, макс у) из

vector<cv::Point>

Вот мой код:

vector<cv::Point> contour;

…

Min = Point(640, 480) ;
Max = Point(0,0) ;
for (int j=0; j<(int)contour.size(); j++)
{
if (contour[j].x < Min.x) Min.x = contour[j].x ;
if (contour[j].y < Min.y) Min.y = contour[j].y ;
if (contour[j].x > Max.x) Max.x = contour[j].x ;
if (contour[j].y > Max.y) Max.y = contour[j].y ;
}

Это отлично работает. Я разработал версию, используя mimmax STL:

auto XminXmax = minmax_element(contour.begin(), contour.end(), [](Point p1,Point p2) {return p1.x < p2.x; });
auto YminYmax = minmax_element(contour.begin(), contour.end(), [](Point p1,Point p2) {return p1.y < p2.y; });
Point Min = Point((*XminXmax.first).x, (*YminYmax.first).y );
Point Max = Point((*XminXmax.second).x, (*YminYmax.second).y );

Это также отлично работает и дает те же результаты.
Однако, так как алгоритм minmax вызывается дважды, время выполнения удваивается.
Можно ли оптимизировать это одним вызовом алгоритма minmax?

4

algorithm c++minmax stl

Решение

Другие решения

minmax_element выполняет сравнение на Point объекты и вернутся Point объекты.

x а также y значения являются независимыми, и вполне вероятно, что min(x) а также min(y) будет принадлежать к разным объектам.

я хотел бы использовать for range для этого конкретного случая.

Min = Point(640, 480) ;
Max = Point(0,0) ;
for (auto &p : contour)
{
Min.x = std::min(p.x, Min.x)
Min.y = std::min(p.y, Min.y)
Max.x = std::max(p.x, Max.x)
Max.y = std::max(p.y, Max.y)
}

6

Источник

Accepted Answer

Нет, это невозможно оптимизировать одним звонком minmax_element так как minmax_element не лучшее решение для этой проблемы.

Если вы настаиваете на каком-то алгоритме STL, используйте accumulate:

std::accumulate(begin(contour), end(contour), Bound{}, [](Bound acc, Point p)
{
return Bound{minpos(acc.bottomleft, p), maxpos(acc.topright, p)};
});

Но для этого нужны некоторые приготовления:

#include <numeric>

struct Point
{
int x;
int y;

Point(int x, int y)
: x(x), y(y) {}
};

Point minpos(Point a, Point b)
{
return {std::min(a.x, b.x), std::min(a.y, b.y)};
}

Point maxpos(Point a, Point b)
{
return {std::max(a.x, b.x), std::max(a.y, b.y)};
}

struct Bound
{
Point bottomleft;
Point topright;

Bound(Point bl = {640, 480}, Point tr = {0, 0})
: bottomleft(bl), topright(tr) {}
};

Сравнение accumulate Подход к диапазону для петлевого подхода, мы могли бы рассмотреть два аспекта:

Читаемость. accumulate подход немного лучше выражает намерение собрать одну ограничивающую рамку из нескольких точек. Но это приводит к немного более длинному коду.
Спектакль. Для обоих подходов gcc (5.3 и 6) генерирует практически идентичный код. Clang 3.8 может векторизовать диапазон для цикла, но не может сделать это для accumulate, Начиная с C ++ 17 мы получим стандартизированный параллелизм TS. Параллельный аналог accumulate было бы reduce алгоритм, так accumulate/reduce подход позволил бы немного больше гибкости.

Вывод: оба диапазона и accumulate/reduce иметь некоторые (не) преимущества. Но, вероятно, лучше использовать совершенно другой подход: если cv::Point в OP означает, что вы используете библиотеку openCV, то эта же библиотека имеет boundingRect функция, которая делает именно то, что вы пытаетесь реализовать.

1