I necesitan un algoritmo que toma una matriz sin clasificar de rectángulos eje alineado y rendimientos cualquier par de rectángulos que se superponerectángulos ejes alineados intersección
Cada rectángulo tiene dos variables, coordenadas de la esquina superior izquierda y la parte inferior derecha esquina
podría ser un poco complicado para una entrevista de trabajo, depende de qué tipo de trabajo, es una especie de cálculo geométrico del algoritmo,
la respuesta se puede encontrar aquí: http://www.cs.princeton.edu/~rs/AlgsDS07/17GeometricSearch.pdf
Aquí se presenta una breve descripción del algoritmo presentado en la intersección DuduAlul enlace 's.
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 de árbol, y R es el número de resultados.
El algoritmo utiliza el enfoque de barrido:
1) Ordenar todos los bordes izquierdo y derecho del rectángulo, en función de su valor de X, en la lista L.
2) Crear un nuevo árbol de búsqueda gama T vacía, para Y ordenamiento de las tapas de rectángulo/fondos
3) crear un nuevo conjunto de resultados vacío RS de pares rectángulo únicas
4) Traverse L en orden ascendente. Para todos V en L:
Si V.isRightEdge()
T.remove (V.rectangle.top)
T .remove (V.rectangle.bottom)
demás
Para todos U en T.getRange (V.rectangle.top, V.rectangle.bottom)
RS.add (< V.rectangle, U.rectangle>)
T.add (V.rectangle.superior)
T.add (V.rectangle.bottom)
5) volver RS
La complejidad de tiempo es O (R + N log N) donde R es el número real de intersecciones.
- EDITAR -
simplemente me di cuenta de que la solución no es totalmente correcto - la prueba de intersección en el árbol T no alcanza algunos casos. El árbol debe mantener los intervalos Y en lugar de los valores Y, e idealmente debería ser un Interval Tree.
Sweep and prune es el método que muchos motores de física para resolver este tipo de problema.
Hay una buena explicación en David Baraff's SIGGRAPH notes, en la sección 7.2 Cajas acotadas.
Esta es una buena respuesta. También lo encontré en el folleto de la clase _Hacking a Google Interview_ de csail.mit.edu –