快速实体分组（按位置）算法

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?

有什么想法或想法吗?

3 个解决方案

#1

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.

我相信你要找的是一个“聚类算法”。有很多可用的。一个好的开始可能是K-means算法。最终虽然听起来你想要一种某种类型的分层聚类算法。

#2

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...

如果您将实体预先分配到实体组中,或者某个“视野”中的所有实体都自动在“组”中,那么您可以使用“中心”为实体组分配“位置”。质量“算法,有效地纬度只是所有包含纬度的平均值,对于经度也是如此...对于两个维度,将em加起来除以计数...

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.

如果您希望算法“创建”分组,那么当“视图”中有两个候选组时,您需要指定一些业务规则来决定实体应该属于哪两个或更多个潜在组。你正在进行计算的高度。

#3

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/

计算鸡群时,“Boids”似乎在同一个街区。 http://www.red3d.com/cwr/boids/

#1