NSSet -member to check equality of NSValue

Question

I have a NSSet containing many thousands of NSValue objects (wrapping CGPoints). I would like to very quickly find if a given CGPoint value exists in the NSSet. It seems to me that the member: method of an NSSet might do the job here, except that it checks for equality using isEqual:. NSValue objects use isEqualToValue:, and so when I execute the code:

[mySet member:valueToCheck];

it actually causes Xcode to crash.

1) Is there some way to use a custom equality check to make this work for NSValue objects?

2) Is this even the best approach (i.e. is member: quick enough in the first place)? The scenario is that I have a NSSet containing a large number of points representing pixels on the screen (iPad). Later on I need to bombard that set with many thousands of points per second to see if they exist in the set. My approach seems crude for achieving this. I thought about creating something like a huge 2-dimensional bit array, with each index representing a pixel on screen. Once I know the point I'm testing for, I can just jump straight to that point in the array and check for a 1 or 0... does this sound better or worse?

Thanks

Answer 1

Can you get this to a simple reproducible case? For example, I just tried:

NSValue *v = [NSValue valueWithCGPoint:CGPointMake(1, 1)];
NSSet *s = [NSSet setWithObject:v];
NSLog(@"%@", [s member:[NSValue valueWithCGPoint:CGPointMake(1, 1)]]);

But it works just fine.

edit

-isEqual: is not the problem:

NSValue *v1 = [NSValue valueWithPoint:NSMakePoint(1, 1)];
NSValue *v2 = [NSValue valueWithPoint:NSMakePoint(1, 1)];
NSLog(@"%d", [v1 isEqual:v2]); //logs "1"

-hash is not the problem:

NSLog(@"%d", ([v1 hash] == [v2 hash])); //logs "1"

They are different objects:

NSLog(@"%d", (v1 != v2)); //logs "1"

The problem is in your code. Try cleaning and rebuilding.

Answer 2

To answer no. 2:

I don't know how NSSet is implemented internally, but considering that you know you are storing points (with X and Y), I think you would be better by implementing your own partitioning algorithm. Personally I would choose my own implementation over NSSet if you say you have thousands of points.

Storing huge 2-dimensional arrays for each pixel, would probably be the fastest way, but it will kill you in terms of memory consumption. You need something fast, but also lightweight.

There are a lot of algorithms out there and you can find them by searching "spatial partitioning algorithms" on wikipedia or google. It also depends on your programming skills, and how much time you are willing to invest in this.

For example, a pretty simple one would be to implement a quad-tree, where you start by diving your screen(or area) in 4 equal parts. Then if and where is needed, you divide that specific cell also in 4 parts. And you do this until each cell contains a small enough number of points so that you can brute-force test all of them. You can find a very good description on wiki: http://en.wikipedia.org/wiki/Quadtree

Hope this helps,