javascript - 重新排列彼此太近的点

Question

我的情况是，我在静态地图图像上动态定位一堆图标，每个图标都由 CSS 绝对定位。现在经常会出现两个甚至更多点距离太近，图标重叠，无法区分的情况。

我正在寻找一种算法来找到这些“彼此太近”的点，然后以它们不再相互重叠的方式展开它们的图标。

我正在考虑径向扩散，例如找到所有太近的点的平均中间点，然后将它们相对于该点展开。

对于这样的问题，您可能知道有什么模式吗？

提前非常感谢。

Answer 1

以下是一些可能解决您的问题的解决方案：

• 使用最接近点对问题的解决方案来找到彼此最接近的两个图标。如果根据您的定义，最接近的一对“太近”，您可以将它们彼此分开并重复此过程。

• 使用空间数据结构，如 kd 树或 R-tree 来存储所有点。然后，您可以执行快速最近邻搜索以找到彼此靠近的点并将它们分开。

• 使用力导向布局算法来找到全局最小化某些能量函数的点的布局。像 Fruchterman-Reingold 这样的算法很容易编码并产生良好的结果。

希望这可以帮助！