Fast Entity Grouping Algorithm (by Location)

Question

I am dealing with a large group of entities that store locations. They are displayed on the map. I am trying to find an effective way to group nearby objects into one entity when viewing from a higher location. So, for example, if you are very tall, when looking down you will see one entity representing a group of closely spaced objects in an area. Scaling close enough would divide this entity into the objects it contains.

Is there an efficient algorithm for this? I thought of simply hiding a view based on height and dropping objects into grid rectangles based on location, and then displaying the box. My only problem is that all entities are in the upper right corner of this window, and the object that will represent them can be centered in the middle instead of the location of the group of objects.

Any thoughts or ideas?

Answer 1

I believe that you are looking for a "clustering algorithm." There are many available. A good start might be the K-mean Algorithm . Ultimately, although it seems like you want some sort of hierarchical clustering algorithm.

Answer 2

If you have to reassign objects to groups of entities or all entities in a certain “field of view” automatically to a “group”, you can assign a “location” to a group of entities using the “center of mass” algorithm, effectively latitude is just the average of all latitudes contained and the same for longitude ... Add em and divide by count for both dimensions ...

If you want the algorithm to “create” groups, you need to specify some business rules to determine which of two or more potential groups an entity should belong to when there are two groups in the “two candidates” group, view “from a height that you are fulfilling.

Answer 3

I think flocking can help create these groups here. Because it seems that different entities that would like to flock to each other should be part of a group.

http://arxiv.org/abs/math?papernum=0502342

http://flashorbit.com/?page_id=40

The Boys seem to be in the same area when the packs are counting. http://www.red3d.com/cwr/boids/