iPhone -矩形的交集
iPhone -矩形的交集
提问于 2012-02-10 08:02:28
我有这个NSMutableArray，它是在屏幕上移动的对象的集合。当一个对象与另一个对象相交时，我需要构造一个与此对象相交的数组。如果这个对象本身与另一个对象相交，则此对象必须包含在该数组中，依此类推，直到我知道所有对象都与另一个相交的对象相交，依此类推。
例如:我正在移动object1，并且我与object2相交，但是object2与与4相交的object3相交，与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问题是这只给了我两个层次的深度。
我如何在这里创建一个递归，它将到达整个可能性树？
谢谢。
回答 4
Stack Overflow用户
回答已采纳
发布于 2012-02-10 08:46:55
因为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];
}
}
}然后，对于驱动程序，只需初始化一个可变数组，并传入对原始对象的引用。
Stack Overflow用户
发布于 2012-02-10 08:46:25
[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;
}Stack Overflow用户
发布于 2012-02-10 08:53:51
下面是一个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];
}
}
}
}为了更快，你必须做一些索引。递归在这里不一定更好，除非您有一个按位置索引的对象的数据结构。但维护该索引需要一定的工作(通常是在更新位置时)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/9220861
复制相关文章
相似问题
腾讯云开发者
