I have a panel in C# with 50 (or more) small rectangles in it drawn using Graphics. Given a Point in the panel, is there a way to determine if there is a rectangle in that point?
I can only think of looping through the rectangles but that might not be practical in terms of running time. Know of any method/object in C# that can help?
Edit: The shapes are objects.
Edit: The real problem here is that I'll be checking for collisions between rectangles, meaning I'll be checking for intersections of two or more unknown rectangles per timer-tick.
Edit: This is the algorithm that I thought of in order to avoid collision:
No need to sweat the small stuff. Just iterate and call Rectangle.Contains(..).
Iterating over 50 rectangles wouldn't be a significant performance hit. I wouldn't bother with fancier algorithms unless I'm dealing with maybe 10,000+ or so objects. And even then, I would profile the app first and confirm if that section is really a bottleneck.
Remember these words from a wise man - "Premature optimization is the root of all evil."
answered Jan 01 '10 at 07:50
You're doing collision-detection, a well-studied problem in game development.
Check out the documentation of the Chipmunk 2d physics library as well as the Box2d physics library. The Chipmunk documentation mentioned Spatial Hashing, the optimization that the others mentioned to discard unnecessary collision checks.
Box2d has been ported almost everywhere, including .NET, so you're probably more interested in that.
answered Jan 02 '10 at 13:50
You can start by sorting the coordinates of the corners of the rectangles. Given a point (x,y), you can start with the middle and determine if your point is to the left or to the right of your coordinate sets, essentially cutting in half the amount of coordinate sets you need to compare. Iterate until you get to the nearest rectangle.
Of course, sorting has a cost and so it depends on what part of your code is inefficient and the data set :)
I'll give it a shot. EDIT: See my comment below of not having to check R[i] against R..R[i-1]. It saves more than a few cycles from O(n^2)
Assume that all rectangle coordinates are normalized.
That is, given a target rectangle
For each other rectangle
In either case, you can safely skip that rectangle and move on to the next.
Otherwise, fallback to
If you really want a 'fast' implementation (when dealing with > 1000 rectangles), you might want to look at the concept of Interval Trees.
You could use a form of space partitioning, essentially a hash table and lists, where the panel is divided into 4 or more equal partitions. Like so:
Your hash will then be a function mapping the coordinates of the partition to the corresponding bin. With a good hash function you won't even have to do a loop to find which bin your coordinate hits, but given the low number of bins there won't be much of a performance increase there anyway.
So, given a coordinate, you pass this to your hash function to get the appropriate bin. This hash function can be a nifty calculation to map coordinates to a specific index, or just brute force if...thens... A hash function for a w x h panel partitioned into m columns and n rows might be:
You get an index into the bin (partition) you want to search. From there you only have to search the lists in each bin, which can be up to 1/4th of the total number of objects in the panel. Then just do your obj.Contains(coord) on each item in the array.
If you are moving the rectangles around, a cheap method of collision detection is to test specific corners or edges depending upon the direction of moving rectangle, i.e. if moving up and right your test coordinate would be the top-right corner. If moving up you would need to test the top two coordinates (pretty sure they will hit something before the bottom ones will).
In this case you will also have to monitor whether a rectangle leaves a partition and moves into another, and prune and graft it to the appropriate list.
answered Mar 02 '10 at 12:19