Geek asks and answers

Effective data structure for objects in 2D space

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

I want to get a list of objects that have a chance to collide (close neighbor, etc.), should be quick and easy to

O([number of objects with collision chance] * log([number of all objects]))Thus, when there are no closed objects, he should do it in O(1), and not in brute force mode, just iterate over all objects in O(n).

Ask if something is unclear.

Maybe you know some kind of link on this topic or some good ideas.

Thank.

+3
source share
4 answers

Chipmunk Physics and Box2D both offer effective 2D collision detection. You can either use one of them, or simply check their source.

+1
source

you can use quadtree to check all nearby objects.

+3
source

, , wikipedia . , , n- .

: ,

, 100x100.

6 A-F (25,25) (25,75), (25,85), D (75,75), (90,60)

4 , node . A, . 2 , B C, . 3 , - , . 2D-.

+1

You want to use a spatial pointer or quadrant. The quadrature can be a simple space filling curve (sfc) or a Hilbert curve. Sfc reduces complexity 2d to complexity 1d and is used in many card applications or heat cards. Sfc can also be used to store searches in zipcode. You want to find a Quadtree Nick hilbert spatial curve index blog.

+1
source

More articles:


All Articles