iPhone – intersección de rectangularjs

Tengo este NSMutableArray que es una colección de objects que se están moviendo en la pantalla. Cuando un object se cruza con otro, necesito build una matriz con este object interceptado. Si este object se cruza por sí mismo con otro, éste debe estar incluido en esa matriz y así sucesivamente hasta que conozca todos los objects que se cruzan con el object que se estaba cruzando con el otro y así sucesivamente.

Ejemplo: estoy moviendo object1 y intersecto object2, pero object2 intersecta object3 que intersecta 4, intersecta 5 y así sucesivamente.

Quiero recostackr todos estos objects en una matriz.

Lo que hice fue esto:

NSMutableArray *intersectingObjects = [NSMutableArray array]; for (Obj *oneObj in allObjects) { if (oneObj != movingObject) { if (CGRectIntersectsRect(movingObject.frame, oneObj)) { [intersectingObjects addObject:oneObj]; } } } // at this point I got an array of all objects intersecting with the // moving object, then I created a similar block to // test all these intersecting objects against all objects again, // then I discovenetworking the objects that were intersecting with the first block 

El problema es que me da 2 niveles de profundidad.

¿Cómo creo aquí una recursión que vaya a todo el tree de posibilidades?

Gracias.

Debido a que el cálculo de 1 vez sería del order de O (n ^ 2), sugeriría mantener un NSMutableArray para cada object que contenga los objects que actualmente se está cruzando directamente. Entonces, el order para cada nuevo cálculo cambia a O (n), simplemente tomando una unión de los elementos en el tree.

Sin embargo, si aún desea seguir el método O (n ^ 2), aquí hay un ejemplo. Estoy asumiendo que Obj es una subclass de UIView?

 - (void) addViewsWhichIntersectView:(Obj*)movingObject toArray:(NSMutableArray*) intersectingObjects { for (Obj *oneObj in allObjects) { if (movingObject != oneObj && //assuming you only care about address comparison, override isEqual and use that method otherwise ![intersectingObjects containsObject:oneObj) && CGRectIntersectsRect(movingObject.frame, oneObj.frame) { [intersectingObjects addObject:oneObj]; [self addViewsWhichIntersectView: oneObj toArray:intersectingObjects]; } } } 

Luego, para el controller, solo inicialice una matriz mutable y pase su reference al object original.

 [self intersectingObjects:allObjects withObject:movingObject]; - (NSMutableArray*) intersectingObjects:(NSArray*)objects withObject:(id)obj{ NSMutableArray * objectsToCheck = [NSMutableArray arrayWithArray:objects]; [objectsToCheck removeObject:obj]; NSMutableArray * intersectingWith = [NSMutableArray array]; for (id oneStepObj in objectsToCheck) { if (CGRectIntersectsRect(obj.frame, oneStepObj)) { //This object intersected with the provided object [intersectingWith addObject:oneStepObj]; //Also add all the objects that intersect with oneStepObj, take care of duplicates for(id nStepObj in [self intersectingObjects:objectsToCheck withObject:oneStepObj]){ if(![intersectingWith containsObject:nStepObj]){ [intersectingWith addObject:nStepObj]; } } } } } return intersectingWith; } 

Aquí hay un enfoque N ^ 2 (bueno para una pequeña N):

 *intersectingObjects = [NSMutableArray array]; for (Obj *oneObj in allObjects) { for (Obj* twoObj in allObjects) { if ( oneObj != twoObj ) { if (CGRectIntersectsRect(movingObject.frame, oneObj)) { [intersectingObjects addObject:oneObj]; } } } } 

Para ser más rápido, deberías hacer algún tipo de indexing. La recursión no es necesariamente mejor aquí a less que tenga una estructura de datos de objects indexada por location. Pero hace falta trabajar para mantener ese índice (generalmente cuando actualiza ubicaciones).

Escribí una aplicación que hace esto bastante bien, se llama QColor, envíame una request de un código de promoción si quieres verla.

En mi experiencia, el iPhone dejó de actualizarse en vivo con un algorithm ineficiente. Esto es lo que decidí (pseudocódigo: perdón, la fuente completa tiene muchas otras cosas en marcha).

Una cosa a tener en count, este algorithm mantiene múltiples rectangularjs superpuestos, por lo que cuando actualiza la pantalla debe traerSubviewToFront: en las intersecciones con la mayoría de los rectangularjs.

 NSArray intersections; // each Intersection is an array of rectangles with a calculated rect - contact me if you want code that can do this (it's not glorious). - (void) addRect: newRect { intersections addObject: newRect; for (Intersection *intersection in intersections) { if (intersection intersects newRect) { create new intersection of intersection + newRect // note, do NOT modify the intersection - add a NEW one. Important point. } } } - (void) removeRect: aRect { remove every intersection that contains aRect - careful, don't use fast enumeration while editing the data structure. } - (void) moveRect: aRect { for (Intersection *intersection in intersections) { if (intersection contains aRect) { recompute the intersection with the moved aRect. If ANY rectangle no longer intersects, delete the entire intersection (compare count before and after recalculation) } else { if (intersection intersects newRect) { create new intersection of intersection + newRect } } } } 

Esto no es tan bonito como un algorithm recursivo, pero es importante mantener baja la cantidad total de intersecciones. ¡Ahora probé por primera vez con una n! Algoritmo, por supuesto, se atragantó. El n ^ 2 uno arriba, no estoy seguro si será adecuado. Según entiendo mi algorithm, cada vez que lo hago es order n, aunque algunos ejemplos de casos más desfavorables con todo superposition (pero no completamente) podrían ser n! (esos son los datos, no el algorithm).

Tengo algunas capturas de pantalla en la página de mi aplicación si desea visualizar los rectangularjs: http://itunes.apple.com/ph/app/qcolor/id490077718?mt=8

Tengo que correr, ¡perdón por cualquier error tipográfico!

Damien