• Create Account

14 years ago on June 15th Gamedev.net was first launched! We want to thank all of you for being part of our community and hope the best years are ahead of us. Happy birthday Gamedev.net!

### #Actualalvaro

Posted 23 April 2012 - 09:10 AM

I don't know what is "optimal" in this case, but space partitioning methods can give you pretty fast solutions. For instance, you can put your rectangles in a k-d tree and then for each point descend the k-d tree until you reach a leaf, where you'll have either a single rectangle or a few rectangles to test against, depending on the details of your implementation.

Even faster, you can also superimpose a fine grid, and have a list of rectangles that touch each cell (typically 1 or 2). To find out which rectangle a point belongs to, simply look up its cell and test against the corresponding rectangles.

### #2alvaro

Posted 23 April 2012 - 09:10 AM

I don't know what is "optimal" in this case, but space partitioning methods can give you pretty fast solutions. For instance, you can put your rectangles in a k-d tree and then for each point descend the k-d tree until you reach a leaf, where you'll have either a single rectangle or a few rectangles to test against, depending on the details of your implementation.

Even faster, you can also superimpose a fine grid, and have a list of rectangles that touch each cell (typically 1 or 2 for edges). To find out which rectangle a point belongs to, simply look up its cell and test against the corresponding rectangles.

### #1alvaro

Posted 23 April 2012 - 09:09 AM

I don't know what is "optimal" in this case, but space partitioning methods can give you pretty fast solutions. For instance, you can put your rectangles in a k-d tree and then for each point descend the k-d tree until you reach a leaf, where you'll have either a single rectangle or a few rectangles to test against, depending on the details of your implementation.

You can also superimpose a fine grid, and have a list of rectangles that touch each cell (typically 1 or 2 for edges). To find out which rectangle a point belongs to, simply look up its cell and test against the corresponding rectangles.

PARTNERS