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

Question

我正在处理一组存储位置的实体，它们在地图上显示。我试图想出一种有效的方法，在从较高的位置查看时将附近的实体分组为一个实体。例如，如果您处于很高的位置并向下看，则会看到代表该区域内紧密相邻的实体组的一个实体。当放大到足够接近时，该实体将被拆分为其包含的实体。

是否有一种有效的算法可以实现这一点？我考虑根据高度将视图分成网格，并根据位置将实体放入网格框中，然后渲染框点。我的唯一担忧是如果所有实体都在该框的右上方，则用于表示它们的实体可能居中而不是实体组的位置。

有什么想法或建议吗？

- scubabbl

Answer 1

如果您已经将实体分配到实体组中，或者所有在某个“视野范围”内的实体自动属于该“组”，那么您可以使用“质心”算法为实体组分配一个“位置”，实际上纬度只是包含的所有纬度的平均值，经度也是如此...将它们加起来，然后按两个维度进行计数和除以总数...

如果您想要一个算法来“创建”分组，则需要指定一些业务规则，以决定当您在计算高度时从两个或多个潜在的组中选择一个实体应该属于哪个组。

- Charles Bretana

Answer 2

我认为群集可以帮助在这里创建这些组。因为不同的实体想要聚集在一起，应该成为一个群体。

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

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

“Boids” 在计算群集时似乎处于同一邻域。 http://www.red3d.com/cwr/boids/

- Stefan

Answer 3

我相信你正在寻找的是“聚类算法”。有许多可用的算法。一个好的起点可能是K-means算法。但最终听起来你想要某种层次聚类算法。

- ceretullis