c++ - vectores - puntos de ancla illustrator

Obteniendo el cuadro delimitador de un vector de puntos?

Question

Tengo un vector de puntos almacenados en una instancia std::vector . Quiero calcular el cuadro delimitador de estos puntos. Lo he intentado con este código:

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

Pero este código produce resultados extraños. En realidad, me interesan solo los primeros y los últimos puntos de mi cuadro delimitador:

1------2
|/     |
| /    |
|  /   |
|   /  |
|    / |
|     /|
3------4

Si mis puntos representan la línea diagonal, solo me interesan los puntos 1 y 4.

¿Hay formas inteligentes de obtener esto con las bibliotecas estándar o Boost?

SOLUCIÓN ACTUAL:

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

Creo que el problema es que sus funciones de comparación están haciendo una suposición demasiado fuerte sobre la forma del cuadro delimitador. Considere estos dos puntos:

          1
         /
        /
       /
      2

El cuadro delimitador correcto es

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

Tenga en cuenta que las esquinas del cuadro delimitador no son puntos en su vector. En cambio, son puntos formados por la combinación de coordenadas de diferentes puntos en el vector. Además, si observa sus dos funciones de comparación, encontrará que dados estos dos puntos, ningún punto se compara menor o mayor que el otro punto, ya que cada uno tiene una coordenada que es más alta que la otra y una que es más baja que el otro.

Para obtener su cuadro delimitador, debe hacer lo siguiente:

1. Encuentra el punto con el valor mínimo x.
2. Encuentra el punto con el valor x máximo.
3. Encuentra el punto con el valor min y.
4. Encuentra el punto con el valor máximo y.
5. Combina la xey de los puntos con los valores min x e y en un punto de esquina.
6. Combina la xey de los puntos con los valores de max xey en un punto de esquina.

Puede hacerlo utilizando el nuevo algoritmo C ++ 11 std::minmax_element , junto con 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);

¡Espero que esto ayude!

Answer 2

Si no tiene c ++ 11, puede usar 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);

Answer 3

Simplemente itere sobre todos los elementos y realice un seguimiento de la corriente mínima / máxima actual. Puede usar boost::minmax para actualizar ambos al mismo tiempo. Realmente no hay necesidad de iterar dos veces sobre su conjunto de datos.