Example standard-cell placement engine for the LibrEDA-Rust framework. This placement algorithm simulates the movement of electric charges that are sparsely connected by springs (wires).
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

83 lines
3.0 KiB

* Copyright (c) 2019-2020 Thomas Kramer.
* This file is part of LibrEDA
* (see https://codeberg.org/libreda).
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU Affero General Public License as
* published by the Free Software Foundation, either version 3 of the
* License, or (at your option) any later version.
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* GNU Affero General Public License for more details.
* You should have received a copy of the GNU Affero General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
//! Compute electro-static repulsion between many particles using a quad-tree for approximation.
use super::types::*;
use super::quadtree::QuadTree;
/// Compute electro-static repulsion between many particles using a quad-tree aproximation
/// for efficient computation.
/// * `particles`: All the particles.
/// * `threshold`: Accurracy setting for the quad tree. `0` is the most inaccurate `1` is very accurate but slow.
/// Decent values are around `0.5`.
pub fn calculate_electric_forces(particles: &Vec<Particle>, threshold: f64) -> Vec<Cost> {
if particles.is_empty() {
} else {
// Find upper right and lower left corner by finding maxima and minima of x and y coordinates.
let (lower_left, upper_right) =
// Use first particle as the starting value to find minimum and maximum.
let loc0 = (particles[0].location.x, particles[0].location.y);
// Find lower-left and upper-right corner of the bounding box around the particles.
.fold((loc0, loc0),
|((xmin, ymin), (xmax, ymax)), p|
let l = p.location;
((xmin.min(l.x), ymin.min(l.y)),
(xmax.max(l.x), ymax.max(l.y)))
// Find minimum side length for the square-shaped quad-tree such that all particles fit in.
let side_length = {
let (x1, y1) = lower_left;
let (x2, y2) = upper_right;
(x2 - x1).max(y2 - y1)
} * 1.001;
// Create an empty quad-tree.
let mut qt = QuadTree::new(lower_left, side_length);
// Insert particles into the tree.
for &p in particles.iter() {
// Pre-calculate centers of charge.
// Calculate the force on each particle.
let f_df = particles.iter()
.map(|p| {
qt.force_onto_particle(&p, threshold)
// Return (force, force_derivative)