Shapes dragging problem

I need to design a software where user can drag shapes in a window. The problem is that there might be thousands of shapes and there might be some restrictions, e.g. one shape cannot be over another shape.

So I actually need to know how to organize data storage and some algorithm to quickly determine if a shape can be placed in some particular position. I think this problem was solved many times, but I don't know how to google i开发者_运维技巧t properly. Could you please provide me with some information on this topic? Thanks!

A quadtree (2D, octree if 3D) is often used in collision detection. Idea is to recursively divide the space in squares/cubes and place the shapes into the correct squares/cubes. When you need to perform collision detection on a given shape, you can then test only the shapes in the same square/cube.

There are other structures, each having pros/cons depending on the constraints you have. If the other shapes are static, BSP Trees can be also a good structure.