iPhone - пересечение прямоугольников

Question

У меня есть этот NSMutableArray, который представляет собой коллекцию объектов, которые перемещаются на экране. Когда объект пересекает другой, мне нужно построить массив с этим объектом, пересеченным. Если этот объект сам по себе пересекается с другим, этот должен быть включен в этот массив и так далее, рекурсивно, пока я не узнаю все объекты, пересекающиеся с объектом, который пересекается с другим и так далее.

Пример: Я перемещаю объект1 и пересекаю объект2, но object2 пересекает объект3, который пересекает 4, который пересекает 5 и т. Д.

Я хочу собрать все эти объекты в одном массиве.

То, что я сделал это:

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 discovered the objects that were intersecting with the first block 

Проблема это только дает мне 2-х уровней в глубину.

Как создать рекурсию здесь, которая пойдет на все дерево возможностей?

спасибо.

Answer 1

Поскольку вычисление 1 раз будет на порядок O (N^2), Я хотел бы предложить поддержание NSMutableArray для каждого объекта, который содержит объекты, в настоящее время она пересекающиеся непосредственно. Затем порядок для каждого нового вычисления изменяется на O (n), просто беря объединение элементов в дереве.

Однако, если вы хотите продолжить метод O (n^2), вот пример. Я предполагаю, что Obj является подклассом 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]; 
     } 
    } 
} 

Затем для драйвера просто инициализируйте изменяемый массив и передайте ссылку на исходный объект.

Answer 2

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

Answer 3

Вот N^2 подхода (хорошо для малых 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]; 
      } 
     } 
    } 
} 

Чтобы быть быстрее, вы должны были бы сделать некоторую индексацию своего рода. Рекурсия здесь не всегда лучше, если у вас нет структуры данных объектов, индексированных по местоположению. Но для поддержания этого индекса требуется работа (обычно при обновлении местоположений).

Answer 4

Я написал приложение, которое делает это довольно хорошо, оно называется QColor - присылайте мне запрос на промо-код, если вы хотите его увидеть.

По моему опыту, iPhone прекратил обновление вживую с помощью неэффективного алгоритма. Вот что я поселился (псевдокод - извините, у полного источника есть много других вещей, которые происходят).

Следует отметить, что этот алгоритм содержит несколько перекрывающихся прямоугольников, поэтому, когда вы обновляете экран, вам нужно вывестиSubviewToFront: на пересечениях с большинством прямоугольников.

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

Это не так красиво, как рекурсивный алгоритм, но важно, чтобы общее количество пересечений было низким. Теперь я впервые попробовал это с помощью n! алгоритм, поэтому, конечно, он задохнулся. N^2 выше, я не уверен, будет ли это адекватно. Насколько я понимаю, мой алгоритм каждый раз проходит через порядок n, хотя некоторые примеры худших случаев со всем перекрывающимся (но не полностью) могут быть n! (это данные, а не алгоритм).

У меня есть несколько скриншотов на моей странице приложения, если вы хотите визуализировать прямоугольники: http://itunes.apple.com/ph/app/qcolor/id490077718?mt=8

я должен бежать - извините за любые опечатки!

Damien