L'obtention de la boîte englobante d'un vecteur de points?

J'ai un vecteur de points stockés dans un std::vector instance. Je veux calculer la boîte englobante de ces points. J'ai essayé avec ce 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);
}

Mais ce code génère des résultats bizarres. En réalité, je suis intéressé uniquement les premier et dernier points de ma boîte englobante:

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

Si mes points représentent la ligne diagonale, je suis intéressé uniquement dans les points 1 et 4.

Sont là des moyens intelligents pour l'obtenir avec les bibliothèques standard ou coup de pouce?

SOLUTION ACTUELLE:

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

OriginalL'auteur nkint | 2012-01-30

boost bounding-box c++std

14

Je pense que le problème est que vos fonctions de comparaison sont trop fort une hypothèse sur la forme de la boîte englobante. Tenir compte de ces deux points:
```
          1
         /
        /
       /
      2
```
La bonne boîte englobante est
```
      +---1
      |  /|
      | / |
      |/  |
      2---+
```
Avis que la boîte englobante coins ne sont pas réellement de points sur votre vecteur. Au lieu de cela, ils sont des points formés par la combinaison de coordonnées à partir de différents points dans le vecteur. Par ailleurs, si vous regardez vos deux fonctions de comparaison, vous trouverez que, compte tenu de ces deux points, ni point compare plus ou moins grande que l'autre, puisque chacun a une coordonnée qui est plus haut que l'autre et celui qui est plus bas que l'autre.

Pour obtenir votre boîte englobante, vous devez effectuer les opérations suivantes:
1. Trouver le point avec le min x valeur.
2. Trouver le point avec le max x valeur.
3. Trouver le point avec le min valeur de y.
4. Trouver le point avec le max de valeur y.
5. Combiner les x et y à partir de points avec le min de valeur x et y dans un coin.
6. Combiner les x et y à partir de points avec le max de valeur x et y dans un coin.
Vous pouvez faire cela en utilisant le C++11 std::minmax_element algorithme, ainsi que les 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);
```
Espérons que cette aide!

alles klar! merci pour la bonne explication, mais je n'ai pas de C++11, donc j'ai utilisé 4 min_element..
ok, j'ai mis à jour la solution
Plutôt que de définir quatre fonctions et l'utilisation de min_element à chaque fois, pourquoi ne pas simplement de définir deux fonctions de comparaison et ensuite utiliser max_element le cas échéant? Cela vous permet d'économiser beaucoup de code et rend le programme plus facile à lire.
ouh, la droite! édité. merci!

OriginalL'auteur templatetypedef
3

Simplement itérer sur tous les éléments, et de suivre le courant min./max. Vous pouvez utiliser boost::minmax de mettre à jour les deux en même temps. Vraiment pas besoin d'itérer deux fois plus de votre jeu de données.

Mais cela dit, même avec ces modifications, le code ne fonctionne toujours pas, parce que la comparaison des fonctions ne sera pas correctement ramasser les coins, dans tous les cas.
Commencer par le premier point que min/max à la fois sur x/y, et dans ta boucle, il suffit de remplacer x,y séparément.

OriginalL'auteur Anteru

Si vous n'avez pas de c++11, vous pouvez utiliser boost::algorithme::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);

OriginalL'auteur Gianluigi

Vous devez vous connecter pour publier un commentaire.