muse examples english book algorithms algorithm

examples - algorithms book



intersección de rectángulos con ejes alineados (3)

Aquí hay una breve descripción del algoritmo de intersección presentado en el enlace de DuduAlul .

La solución requiere el uso de un árbol de búsqueda capaz de realizar consultas de rango. Una consulta de rango solicita todos los elementos con valores entre K1 y K2, y debe ser una operación O (R + log N), donde N es el número total de elementos del árbol y R es el número de resultados.

El algoritmo utiliza el enfoque de barrido:

1) Ordene todos los bordes rectangulares izquierdo y derecho, de acuerdo con su valor X, en la lista L.

2) Cree un nuevo árbol de búsqueda de rango vacío T, para el orden en Y de tops / bottom de rectángulo

3) Crear un nuevo conjunto de resultados vacío RS de pares de rectángulos únicos

4) Recorrer L en orden ascendente. Para toda V en L:

Si V.isRightEdge ()

T.remove (V.rectangle.top)

T.remove (V.rectangle.bottom)

más

Para todas las U en T.getRange (V.rectangle.top, V.rectangle.bottom)

RS.add (<V.rectangle, U.rectangle>)

T.add (V.rectangle.top)

T.add (V.rectangle.bottom)

5) devuelve RS

La complejidad del tiempo es O (R + N log N) donde R es el número real de intersecciones.

- EDITAR -

Acabo de descubrir que la solución no es completamente correcta: la prueba de intersección en el árbol T falla en algunos casos. El árbol debe mantener intervalos de Y en lugar de valores de Y, e idealmente debería ser un Árbol de intervalo .

Necesito un algoritmo que tome una matriz sin clasificar de rectángulos alineados con ejes y devuelva cualquier par de rectángulos que se superpongan

Cada rectángulo tiene dos variables, las coordenadas de la esquina superior izquierda y la esquina inferior derecha