3

I have a 2D space with objects, each object has coordinate vector and an array of vertexes relative to his coordinate, now I need an efficiency way of storing the objects, this store should be able to add and remove objects, also the most important part is the collision detection:

I want to get a list of objects which have a chance to collide (close neighbor etc.), should be fast and simple in about

O([number of objects with collision chance] * log([number of all objects])) so that way when there is no close objects it should do it in O(1) and not the brute force way of just going over all of the objects in O(n).

Ask if something not clear.

Maybe you know some link on the subject or any good ideas.

Thanks.

Improve this question

4 Answers 4

Reset to default
3

you could use a quadtree for this to check all the nearby objects.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

Chipmunk Physics and Box2D both offer efficient 2D collision detection. You could either use one of them, or just inspect their source.

Improve this answer

Comments

1

You can use a tree data structure by using binary space partitioning, here is a wikipedia article about it. This is the most efficient way to my knowledge, of storing information about location of objects in an n-dimensional space.

Here is how it works: Let's say you've got the following field

Let's say you've got a space of 100x100.

You've got 6 objects in there with named A to F the co-ordinates A(25,25) B(25,75), C(25,85), D(75,75), E(90,60)

Now, we divide our space into 4 parts, each part will be a childnode of the root node in the tree. The top left corner only contains point A, so that's a chield with one leafnode. the bottom left corner contains 2 objects, B and C, so they'll be leaf nodes of the second chield. Now the bottom right corner will have 3 elements in them, which we do not want because of the idea of a binary tree, so we make another subdivision. By doing that recursively, you get a very efficient data structure for finding objects in a 2D space.

Improve this answer

Comments

1

You want to use a spatial index or a quadtree. A quadtree can be simple a space-filling-curve (sfc) or a hilbert curve. A sfc reduce the 2d complexity to a 1d complexity and is used in many maps applications or heat maps. A sfc can be used to store a zipcode search, too. You want to search for Nick's hilbert curve quadtree spatial index blog.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.