VisualizationSilergytest

Canvas Collision Algo (碰撞避让)

Project: Silergy Data Insight BI
简历背景

"独创"动态碰撞避让"算法,确保高密度传感器数据在电视大屏上的无遮挡展示..."

面试题

在 BI 大屏中,你是如何实现 200+ 传感器数据的动态标签避让的?具体算法思路?

核心是针对 Label 的防重叠布局。我实现了一个简化的"贪心算法"配合"力导向"思想。首先按预定优先级排序传感器。绘制前,维护一个 OccupiedBoundingBox 列表。对新 Label 进行碰撞检测,如果碰撞,则尝试向四周做微小的位置偏移(Force),若多次尝试失败则隐藏低优先级 Label,保证核心数据展示。
**算法实现细节:** 1. **空间索引 (QuadTree):** 如果数据量更大(上千),我会上四叉树。但 200 个点,直接遍历 `OccupiedList` 性能足够 (<1ms)。 2. **包围盒检测 (AABB):** 判断两个矩形是否相交: `!(r2.left > r1.right || r2.right < r1.left || r2.top > r1.bottom || r2.bottom < r1.top)` 3. **退火策略 (Simulated Annealing):** 为了让布局更自然,不仅仅是不重叠。我引入了一个"能量函数",重叠是高能量。 通过迭代移动 label 位置来降低总能量。 但在前端渲染循环(rAF)中,为了性能,我简化为: - 预计算:根据坐标生成初始位置。 - 检测:与已绘制的 Boxes 检测。 - 修正:有冲突?尝试 4 个方向偏移 10px。 - 降级:还是冲突?opacity = 0,仅显示点。