Fast Entity Grouping (by location) algorithm

Question

I'm dealing with a large group of entities that store locations. They are displayed on a map. I'm trying to come up with an efficient way to group near located entities into one entity when viewed from a higher location. So, for example, if you are very high, when looking down, you will see one entity that represents a group of closely located entities in an area. Zooming in close enough would split that entity out into its contained entities.

Is there an efficient algorithm for doing this? I thought about just griding off the view based on height and dropping entities into grid boxes based on location then rendering the box point. My only concern is if all the entities are in the upper right of that box, the entity rendered to represent them might be centered in the middle instead of the location of the group of entities.

Any thoughts or ideas?

Answer 1

If you will have preassignment of the entities into the entity groups, or of all entities in a certain "field of view" are automatically in the "group", then you could assign a "location" for the entity group using a "center of mass" algorithm, effectively the latitude is just the average of all the contained latitudes, and same for longitudes... Add em up and divide by the count, for both dimensions...

If you want an algorithm to "create" the groupings, then you'll need to specifyt some business rules for how to decide which of two or more potential groups an entity should belong to, when there are two candidate groups in "view" from the height you are doing the calculation.

Answer 2

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

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

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

"Boids" seems to be in the same neighborhood when calculate flocks. http://www.red3d.com/cwr/boids/

Answer 3

I believe what you are looking for is a "clustering algorithm". There are numerous available. A good start might be the K-means Algorithm. Ultimately though it sounds like you want a Hierarchical clustering algorithm of some kind.