Force directed algorithm to solve rect overlaps

arrange.rs

  fn arrange(&self, ui: &mut Ui, state: &mut DashboardState, repulsion_steps: usize, compaction_steps: usize) {
    if state.block_rect.is_empty() {
      return;
    }
    let original = state.block_rect.clone();
    let mut debug_copy = state.block_rect.clone();
    let rects = &mut state.block_rect;
    let keys: Vec<BlockKey> = rects.keys().collect();
    let keys = keys.iter().copied();

    let mut rng = rand::thread_rng();

    // First pass, resolve overlaps
    for _ in 0..repulsion_steps {
      let mut forces = SecondaryMap::<BlockKey, Vec2>::new();

      for b1 in keys.clone() {
        for b2 in keys.clone() {
          if b1 == b2 {
            continue;
          }
          let r1 = rects[b1];
          let r2 = rects[b2];
          let overlap = r1.intersect(r2);
          if overlap.is_positive() {
            let overlap = overlap.expand(10.0);
            let mut accumulated = forces.get(b1).copied().unwrap_or_default();

            // Small random perturbation to handle blocks that perfectly overlap
            let perturbation = vec2(rng.gen(), rng.gen());
            let direction = (r1.center() + perturbation - overlap.center()).normalized();

            // Divide by area so "heavier" blocks move less
            let force = direction * overlap.area() / r1.area() * 50.0;
            forces.insert(b1, accumulated + force);
          }
        }
      }

      if forces.is_empty() {
        break;
      }

      // Apply forces
      for (b, force) in forces {
        rects[b] = rects[b].translate(force);
      }
    }

    // Find the average center
    let center = rects
      .values()
      .map(|r| r.center().to_vec2())
      .reduce(|a, b| a + b)
      .map(|v| (v / rects.len() as f32).to_pos2())
      .expect("no rects");

    // Find block closest to center and keep it fixed
    let center_block = rects.keys().min_by_key(|&b1| center.distance_sq(rects[b1].center()) as u64).unwrap();
    let center = rects[center_block].center();

    // Compaction pass
    for i in 0..compaction_steps {
      let mut sorted_keys = rects.keys().clone().collect::<Vec<_>>();
      for b1 in keys.clone() {
        if b1 == center_block {
          continue;
        }
        let mut r1 = rects[b1];
        let to_center = center - r1.center();
        let step = to_center.normalized() * r1.width().min(r1.height()).min(to_center.length()) * 0.1;
        r1 = r1.translate(step);

        // Solve collisions
        for b2 in keys.clone() {
          if b1 == b2 {
            continue;
          }
          let r2 = rects[b2];
          let overlap = r1.intersect(r2);
          if overlap.is_positive() {
            if overlap.width() >= overlap.height() {
              r1 = r1.translate(vec2(0.0, -overlap.height() * step.y.signum()));
            } else {
              r1 = r1.translate(vec2(-overlap.width() * step.x.signum(), 0.0));
            }
          }
        }

        rects[b1] = r1;
      }
    }

    // Animate the transitions
    for b in keys {
      let layer = Area::new(block_area_id(self.id, b)).layer();
      AreaTransition::trigger(ui.ctx(), layer, original[b].min);
    }
  }