1

Topic: To optimize object search on a plane

The program works with the certain objects drawn on the screen. Objects can be tens and even hundreds. It is possible to take one of them a mouse to drag is problems does not cause, to sort out one hundred objects and to learn in what got simply. But in the course of driving of the mouse the object can face other objects then it is necessary to push them too. And those, in turn, with others, etc. As a result of MouseMove starts to brake. It is insulting, what the majority of objects are certainly further that point with which it is worked, whether it is impossible to define somehow it and not to check hit? To invent any two-dimensional indexing?

2

Re: To optimize object search on a plane

Hello, 777777w, you wrote: 7> It is insulting, what the majority of objects are certainly further that point with which it is worked, whether it is impossible to define somehow it and not to check hit? To invent any two-dimensional indexing? Such methods to make spatial index already it is invented much. Begin with quadtree, as with the most simple variant.

3

Re: To optimize object search on a plane

Hello, 777777w, you wrote: 7> to Invent any two-dimensional indexing? Quadtree

4

Re: To optimize object search on a plane

Hello, 777777w, you wrote: 7> the Program works with the certain objects drawn on the screen. Objects can be tens and even hundreds. It is possible to take one of them a mouse to drag is problems does not cause, to sort out one hundred objects and to learn in what got simply. But in the course of driving of the mouse the object can face other objects then it is necessary to push them too. And those, in turn, with others, etc. As a result of MouseMove starts to brake. It is insulting, what the majority of objects are certainly further that point with which it is worked, whether it is impossible to define somehow it and not to check hit? To invent any two-dimensional indexing? If to generalize - dig aside Collision Detection. It is a lot of variants - spatial subdivision, bounding hierarchy (is called BVH for 3d), spatial sort...

5

Re: To optimize object search on a plane

6

Re: To optimize object search on a plane

Hello, 777777w, you wrote: 7> But in the course of driving of the mouse the object can face other objects then it is necessary to push them too. And those, in turn, with others, etc. And generally, for these purposes it can appear easier to take Box2D or its port under your platform.

7

Re: To optimize object search on a plane

Hello, 777777w, you wrote: 7> the Program works with the certain objects drawn on the screen. Objects can be tens and even hundreds. It is possible to take one of them a mouse to drag is problems does not cause, to sort out one hundred objects and to learn in what got simply. But in the course of driving of the mouse the object can face other objects then it is necessary to push them too. And those, in turn, with others, etc. As a result of MouseMove starts to brake. It is insulting, what the majority of objects are certainly further that point with which it is worked, whether it is impossible to define somehow it and not to check hit? To invent any two-dimensional indexing? The simple grid 10x10 allows to reduce an amount of checks a hundred times. It is a rough estimate, at (1) uniform allocation and (2) cells considerably the big sizes of objects. Other digit really turns out, however in practice of such simple optimization it can appear enough.

8

Re: To optimize object search on a plane

Hello, watchmaker, you wrote: W> Begin with quadtree, as with the most simple variant. It not the idle time. A grid 3232 in which each cell stores the list of the objects which have touched it, easier.

9

Re: To optimize object search on a plane

Hello, T4r4sB, you wrote: W>> Begin with quadtree, as with the most simple variant. TB> it not the idle time. A grid 3232 in which each cell stores the list of the objects which have touched it, easier. Aha. Plus for each object the list of the touched cells. And the size of a grid should be selected for a place. At us for one objects the size of a cell 1/4 ", for others - 0.5".

10

Re: To optimize object search on a plane

Hello, V. Zudin, you wrote: SVZ> Aha. Plus for each object the list of the touched cells. And it is not necessary, on AABB object this list turns out several elementary operations.

11

Re: To optimize object search on a plane

Hello, T4r4sB, you wrote: SVZ>> Aha. Plus for each object the list of the touched cells. TB> and it is not necessary, on AABB object this list turns out several elementary operations. For square-topped objects it turns out beautifully, and for direct segments many superfluous cells at an angle will be selected.