2d sweep and prune
Author
For each instance, I want to find all other instances within a given distance of that instance. The most efficient way I can think to do this is to sort the instances on the x or y axis and then check the instances after until the distance along the axis is greater than the d possible distance.
The problem is that there are a lot of instances within the given distance that are so far away on the y axis that I should somehow be able to not include them, but I can't think of a way to eliminate them.
I'm checking the squared distance, so calculating the distance isn't that expensive. The problem is that for every instance that is reasonable to consider there are 20 fold that I shouldn't even need to consider.
Any suggestions?
Thank you
You'll want to store your points in some kind of spatial structure, such as a grid or quadtree. The idea is that you first check if a given cell or node touches your search radius - if it doesn't, then you can safely ignore all the points inside of it.
Author
I thought of doing that, but won't the points that touch the search radius need to perform an n^2-like search with the touching cell's instances?
No - for each point, you check it's radius against the spatial structure, and then agains the points in the matching cells/nodes. That gives you all points within the radius of that specific point.
Either way, a naive approach would only need roughly n^2/2 checks, not n^2 checks.
Either way, a naive approach would only need roughly n^2/2 checks, not n^2 checks.
You can do sweep and prune on both axes, and then perform a set intersection on the results to generate a list of objects that could possibly intersect on both axes. This could help if you're generating tons of false hits on the y-axis.
Author
Quote:No - for each point, you check it's radius against the spatial structure, and then agains the points in the matching cells/nodes. That gives you all points within the radius of that specific point.
Either way, a naive approach would only need roughly n^2/2 checks, not n^2 checks.
I know how to do it without breaking it up into cells. It's pretty straight forward. When broken into cells, if a points radius extends into another cell, I could binary search through the cells points to find the location I should check from. That would just add a log(n) to the algorithm. That isn't too bad. Is this what you were talking about?
Quote:You can do sweep and prune on both axes, and then perform a set intersection on the results to generate a list of objects that could possibly intersect on both axes. This could help if you're generating tons of false hits on the y-axis.
I thought of doing this, but the problem is that there are way too many points around the axis that are being considered. Adding another axis just adds more points that shouldn't be considered. At least that's the only way I can see it.
Quote:Original post by yahnQuote:You can do sweep and prune on both axes, and then perform a set intersection on the results to generate a list of objects that could possibly intersect on both axes. This could help if you're generating tons of false hits on the y-axis.
I thought of doing this, but the problem is that there are way too many points around the axis that are being considered. Adding another axis just adds more points that shouldn't be considered. At least that's the only way I can see it.
I'm not sure what you mean by 'around the axis.'
As I understand it, you're doing sweep and prune on one axis, and your problem is that you're generating too many false overlaps on the other axis. Performing sweep and prune on both axes and intersecting the resulting sets will eliminate all of these false overlaps except those caused by differences between bounding objects and actual geometry. In fact, if your objects are box-shaped and you're working in 2D, this kind of double axis sweep and prune should just give you the intersections outright.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
