6

Tengo una serie de rectángulos almacenados en la siguiente clase:

struct rectangle
{
    rectangle(int x_, int y_, int w_, int h_) :
        x{ x_ },
        y{ y_ },
        w{ w_ },
        h{ h_ }
    {}

    bool contains(int x_, int y_) const
    {
        return (x_ >= x) &&
               (x_ <= (x + w)) &&
               (y_ >= y) &&
               (y_ <= (y + h));
    }

    int x{}, y{}, w{}, h{};
};

Una clase bastante sencilla que almacena las coordenadas de la esquina superior izquierda del rectángulo y su ancho y alto; proporciona también una función que indica si un punto determinado está dentro del rectángulo.

Necesito purgar mi colección de rectángulos de manera que cualquier rectángulo que esté contenido en otro rectángulo quede eliminado. Por ejemplo mis datos son los siguientes (colección completa de datos al final del hilo):

[00] X: 5  Y: 2  W: 3  H: 9
[01] X: 5  Y: 3  W: 3  H: 8
[02] X: 5  Y: 4  W: 4  H: 7
[03] X: 7  Y: 5  W: 7  H: 7
...
[28] X: 7  Y: 9  W: 3  H: 3
[29] X: 6  Y: 10 W: 3  H: 3

Y la representación visual de los primeros cuatro rectángulos sería la siguiente:



El rectángulo 0 (relleno con líneas verticales) contiene en su interior el rectángulo 1 (relleno con líneas horizontales), pero a pesar de que ambos (0 y 1) tocan a los rectángulos 2 (rellenado de azul) y 3 (rellenado de amarillo) no los contienen.

Así que el único rectángulo de entre los 4 primeros que debiera ser eliminado sería el 1. Había pensado que para conseguir la funcionalidad que deseo un std::set sería el contenedor adecuado ya que éste no permite duplicados... tan sólo tengo que modificar lo que significa duplicado en este contexto, para ello creo un operador libre de comparación de rectángulos:

bool operator <(const rectangle &l, const rectangle &r)
{
    return
        r.contains(l.x,       l.y) &&
        r.contains(l.x + l.w, l.y) &&
        r.contains(l.x,       l.y + l.h) &&
        r.contains(l.x + l.w, l.y + l.h);
}

El std::set usa preorden total mediante el concepto de comparación que usa el operador menor-que (<), así que la implementación anterior devolverá verdadero si el rectángulo a la derecha de la operación contiene en su interior todos los puntos del rectángulo a la izquierda de la operación, es decir que el rectángulo derecho es mayor al izquierdo. Con los datos de ejemplo el rectángulo 0 no sería menor que el rectángulo 1 pero el 1 sí sería menor al 0.

Pero al ejecutar el código no sólo no me elimina los rectángulos que son comidos por otros rectángulos si no que me elimina rectángulos que no debería eliminar. De mi colección de 30 rectángulos ¡el std::set sólo conserva el 0 y el 1!

No tengo claro si el problema está en mi código o en mi comprensión del contenedor std::set (o ambas cosas). Estoy pensando en cambiar a un std::vector y limpiar el contenido en una segunda pasada en lugar de confiar en los mecanismos de contenedores que no permiten duplicados, pero preferiría no hacerlo.

¿Existe alguna manera de conseguir el comportamiento que busco?


[00] X: 5  Y: 2  W: 3  H: 9
[01] X: 5  Y: 3  W: 3  H: 8
[02] X: 5  Y: 4  W: 4  H: 7
[03] X: 7  Y: 5  W: 7  H: 7
[04] X: 8  Y: 5  W: 6  H: 6
[05] X: 9  Y: 5  W: 5  H: 5
[06] X: 10 Y: 5  W: 4  H: 4
[07] X: 11 Y: 5  W: 3  H: 4
[08] X: 5  Y: 6  W: 9  H: 5
[09] X: 6  Y: 6  W: 8  H: 7
[10] X: 7  Y: 6  W: 7  H: 6
[11] X: 8  Y: 6  W: 6  H: 5
[12] X: 9  Y: 6  W: 5  H: 4
[13] X: 10 Y: 6  W: 4  H: 3
[14] X: 11 Y: 6  W: 3  H: 3
[15] X: 5  Y: 7  W: 12 H: 4
[16] X: 6  Y: 7  W: 11 H: 6
[17] X: 7  Y: 7  W: 10 H: 5
[18] X: 8  Y: 7  W: 9  H: 4
[19] X: 9  Y: 7  W: 8  H: 3
[20] X: 13 Y: 7  W: 4  H: 3
[21] X: 14 Y: 7  W: 3  H: 4
[22] X: 5  Y: 8  W: 13 H: 3
[23] X: 6  Y: 8  W: 12 H: 5
[24] X: 7  Y: 8  W: 11 H: 4
[25] X: 8  Y: 8  W: 10 H: 3
[26] X: 14 Y: 8  W: 4  H: 3
[27] X: 6  Y: 9  W: 4  H: 4
[28] X: 7  Y: 9  W: 3  H: 3
[29] X: 6  Y: 10 W: 3  H: 3

2 respuestas 2

5

std::set (y std::map, std::sort, etc), no requiere que el comparador (llamémosle comp) implemente un preorden total; de hecho, ni le exige ser preorden, ni le exige ser total. Lo que se le exige a los comparadores, cuando implementan <, es que implementen un strict weak ordering, es decir, un órden estricto débil.

Un par de definiciones antes:

  • Dos elementos son comparables sii comp(a, b) == true o comp(b, a) == true. Dependiendo de las propiedades que tenga comp, implementará <, <=, ==, etc.

  • Dos elementos son iguales sii ocupan la misma posición en el rango (si it1 == it2, entonces *it1 y *it2 son el mismo elemento). Ser equivalente es otra cosa. Ser igual es ser el mismo elemento.

Si un algoritmo de la STL espera que comp defina una relación de equivalencia (std::equal), entonces dos elementos son equivalentes sii son comparables, y por tanto, se espera que comp(*it, *it) == true, ya que se asume que dos elementos iguales lo son. Por supuesto, elementos diferentes también podrían ser equivalentes, eso ya lo decide comp, pero se espera que comp, como mínimo, sea reflexivo, ya que una relación de equivalencia lo es.

Análogamente, si se espera que comp implemente <, entonces un elemento es menor a otro si son comparables solo en una dirección. Por tanto, comp(*it, *it) == false, ya que < debe filtrarnos elementos equivalentes.

Y std::set necesita que comp implemente <.

Un preorden exige que todo elemento sea comparable consigo mismo (no lo queremos), mientras que un órden estricto exige que ningún elemento sea comparable consigo mismo (lo queremos). Además, < nunca puede ser un órden total. Un órden total nos exige que para toda pareja de elementos, comp(a, b) || comp(b, a), sin importar quienes sean a y b. Por tanto, si a == b, entonces comp(a, a) == true, lo que tampoco nos permite implementar <. Por eso std::set no le existe a comp que sea ni preorden, ni total.

comp debe ser irreflexivo (un preorden es reflexivo), lo que prohibe explícitamente que cualquier elemento sea comparable consigo mismo, lo que implica además que el órden no puede ser total. Por eso creo que se le llama órden estricto, porque es estrictamente parcial.

¿Y qué es eso de órden estricto débil? Date cuenta que, al ser el orden parcial (al no poder exigir que toda pareja sea comparable), el comparador puede formar un "árbol" en vez de una línea de orden, donde un padre tenga varios hijos (todos menores que él, pero no comparables entre sí). Entonces hay que añadir una condición extra para conseguir nuestra línea (es decir, conseguir un órden total excepto autocomparaciones).

La condición extra es que, la propiedad de ser equivalente (es decir, de no ser comparable: !comp(*it1, *it2) and !comp(*it2, *it1)), debe ser transitiva. Supón el siguiente arbolito:

 a -> b -> c // a < b; b < c
           d //        b < d
      e -> f // a < e; e < f
           g //        e < g

b y e son equivalentes, porque no se pueden comparar, y e y c también, por tanto, b y c deben ser equivalentes, y por tanto, no comparables. Lo que significa que e también debe ser padre de c, para romper la transitividad. Y también padre de d. Y b, padre de f, y de g. De esta manera, si dos elementos son equivalentes, todo elemento menor a uno, debe ser menor al otro, colapsando el árbol de la siguiente forma:

a -> b -> c
     e    d
          e
          f

donde cada nivel del árbol original es ahora como un único nodo de elementos equivalentes, y ya tenemos una línea de órden. Por eso, aunque la definición parezca "rara" o relajada, el comparador exigido es la relación < usual.

Es resumen, necesitas que tu comparador forme una línea de rectángulos, porque es exactamente lo que exige set, y nada menos. Debes inventarte una relación de órden de modo que todos tus rectángulos formen una línea ordenada, incluso si colisionan, excepto que cuando uno está incluído en el otro, sean equivalentes, para que la STL lo tome como elemento repetido.

Por tanto, necesitas determinar, primero, si dos cuadrados son equivalentes (si uno está incluído en el otro, para que set no los elimine), y si lo son, devolver falso. Si no lo son, debes ordenarlos, por ejemplo, según la esquina inferior izquierda.

De todas formas, hay otras soluciones. Todo depende de cómo vayas a utilizar tu estructura. ¿Necesitas buscarlos frecuentemente, o necesitas tenerlos siempre ordenados, por ejemplo para borrar cuadrados a medida que aparecen y se van? Si es sí, entonces utiliza un std::set, pero ten cuidado en qué orden metes los elementos, y que de cada grupo de cuadrados contenidos, el primero que llegue sea el más grande. O si la inserción falla, borra y reinsertas el nuevo si es más grande:

struct rectangle
{
    rectangle(int x_, int y_, int w_, int h_) :
        x{ x_ },
        y{ y_ },
        w{ w_ },
        h{ h_ }
    {}

    bool contains(int x_, int y_) const
    {
        return (x_ >= x) &&
               (x_ <= (x + w)) &&
               (y_ >= y) &&
               (y_ <= (y + h));
    }

    bool contains(rectangle const& r) const
    {
        return x <= r.x and x + w >= r.x + r.w and
             y <= r.y and y + h <= r.y + r.h; 
    }

    friend
    bool operator<(rectangle const& r1, rectangle const& r2) const
    {
        return r1.x < r2.x and r1.y < r2.y;
    }

    int x{}, y{}, w{}, h{};
};

int main()
{
    auto equiv_rect = [](rectangle const& r1, rectangle const& r2) {
         return r1.contains(r2) or r2.contains(r1);
    };

    auto set_comp = [equiv_rect] (rectangle const& r1,
                                  rectangle const& r2) {
         return !equiv_rect(r1, r2) and r1 < r2;
    };

    // Asumimos que uno está contenido en el otro.
    auto bigger = [](rectangulo const& r1, rectangulo const& r2) {
          return r1.contains(r2);
    };

    std::set<rectangulo, decltype(set_comp)> rects;

    while(your_cond()) {
        rectangulo rect = next_rect();

        do {
        // Mientras haya alguien contenido en rect, o que contenga a
        // rect, seguirá dando vueltas.
           auto pair = rects.insert(rect);

           if (!pair.second and bigger(rect, *pair.first))
                rects.erase(pair.first);
           else
                break;

        } while(1);
    }
};

Si no necesitas tener los rectángulos continuamente ordenados, y solo quieres colapsarlos una vez, simplemente pásale un std::sort a la estructura que utilices como almacenamiento final (por ejemplo, std::vector), y luego un std::unique para borrar elementos repetidos.

int main()
{
    auto equiv_rect = [](rectangle const& r1, rectangle const& r2) {
         return r1.contains(r2) or r2.contains(r1);
    };

    // Asumimos que uno está contenido en el otro.
    auto bigger = [](rectangulo const& r1, rectangulo const& r2) {
          return r1.contains(r2);
    };

    // Cuadrados equivalentes solo si son exáctamente iguales.
    // Si no lo son, r1 < r2 or r2 < r1. Si uno está contenido en
    // otro, el más grande va primero, para que `std::unique` no
    // lo borre.
    auto sort_comp = [equiv_rect] (rectangle const& r1,
                                   rectangle const& r2) {
         return (equiv_rect(r1, r2) and bigger(r1, r2)) or r1 < r2;
    };


    std::vector<rectangulo> rects;
    // Rellena rects.

    std::sort(rects.begin(), rects.end(), sort_comp);

    rects.erase(std::unique(rects.begin(), rects.end(), equiv_rect),
                rects.end());

    // Usar `rects` a partir de ahora, que es muy eficiente para 
    // recorrer.
}

NOTA: Internamente, std::set utiliza un árbol internamente, porque utiliza un árbol rojo-negro, una estructura que permite implementar árboles binarios de búsqueda completos eficientemente, y no porque tu comparador forme un árbol (de ahí quizás que pensaras que comp fuera un preorden, confundiéndolo con órden parcial).

NOTA2: No sé si algo de esto funcionará. Es muy tarde y no lo he compilado :)

NOTA3: std::unordered_set también es una opción, pero no lo he recomendado porque yo al menos no sé como utilizarlos adecuadamente. O mejor dicho, no sé como crear una función de hash adecuadamente. Quizás pasar los cuatro atributos del rectangulo a string, y devolver el hash del string concatenado, pero quizás es una solución muy poco eficiente.

2
  • 2
    más o menos es lo mismo que iba a poner yo... lo único que si hablas de eficiencia sería mejor un vector a un list... menos indirección, menos consumo de memoria y más localidad de los datos, ¿no?
    – eferion
    Commented el 17 abr. 2017 a las 6:28
  • @eferion Pues sí. En este contexto, es obvio que el contenedor de rectángulos se va a recorrer mucho más frecuentemente que modificar/insertar. De hecho, en mi ejemplo asumo que solo se rellena una vez, así que std::vector es la elección obvia y más eficiente. Me he contradecido a mí mismo en el código. Además, std::sort requiere random access iterators y lo que ofrecen las listas son forward iterators, así que mi código ni siquiera funciona. Lo rectifico. Gracias por remarcarlo.
    – ABu
    Commented el 17 abr. 2017 a las 10:55
2

En un std::set se determina que un elemento es igual a otro usando el operator<() cuando este devuelve falso en ambos sentido de comparación. Es decir, si tienes dos rectángulos a y b, estos serán iguales si operator<(a, b) y operator<(b, a) son falsos.

En tu caso inicial la comparación es falsa para todos los rectángulos entre ellos, excepto precisamente entre los dos primeros entre los que se puede establecer un orden dada la función de comparación.

Has pensado en usar std::unordered_set redefiniendo la función de comparación? En este caso tendría mas sentido ya que no estableces un orden entre rectángulos sino que quieres saber cuales con "equivalentes".

3
  • 1
    Tu razonamiento es muy interesante y además coincide con el comportamiento que estoy observando ¿puedes añadir código para ampliar tu respuesta? Commented el 12 abr. 2017 a las 14:55
  • Creo que el codigo que has usado en operator<() valdría como comparación entre claves, quizás cambiarle el nombre, sin necesidad que sea un operator. Commented el 12 abr. 2017 a las 14:59
  • ah, y necesitarás una función de hash. En este caso puedes intentar alguna operación aritmética entre las coordenadas del rectángulo, o siempre puedes guardar en el set el puntero a cada rectángulo que ya sería un numero diferente para cada uno. Commented el 12 abr. 2017 a las 15:03

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.