Loading files
This file is pinned to the selected release. Download the original to open it in your design tool.
670d2a9c4This file is pinned to the selected release. Download the original to open it in your design tool.
"""Connectivity-driven component placement optimizer.
DRAFT — proposed new MCP capability.
The existing tools (place_component, move_component, align_components,
check_courtyard_overlaps) give you placement primitives plus *validation*, but
nothing turns the netlist into a suggested layout. This module adds a single
command, ``suggest_placement``, that does the heuristic an engineer does by
eye against the ratsnest:
1. Build a component-level connection graph from pad nets.
2. Force-directed relaxation (Fruchterman-Reingold flavoured, adapted for
PCB): nets pull connected parts together, overlapping courtyards push
apart, the board outline contains everything. Power/high-current nets
and IC<->decoupling links are weighted so those parts hug tightest.
3. Pin-facing rotation: each movable part is rotated (0/90/180/270) to the
orientation that minimises the pad-level wire length to its neighbours —
this is what removes airwire crossings.
4. Snap to grid and return *proposed* {ref:[x,y,rot]} positions. It does
NOT modify the board unless ``apply=true``.
It reuses ComponentCommands._footprint_courtyard_bbox so the collision model is
identical to check_courtyard_overlaps (AABB on the real courtyard polygon).
Intended loop:
suggest_placement(dryRun) -> check_courtyard_overlaps(positions=...) ->
apply -> autoroute(best-of-N) -> run_drc
Quality metric reported is pad-level HPWL (half-perimeter wire length), the
standard placement proxy for routed length — lower is better.
"""
from __future__ import annotations
import logging
import math
from typing import Any, Dict, List, Optional, Tuple
import pcbnew
logger = logging.getLogger("kicad_interface")
# Net-name fragments treated as high-current / power and pulled short & direct
# (step 4 of the placement priority order). Case-insensitive substring match.
DEFAULT_POWER_NETS = [
"VBAT",
"VBUS",
"VCC",
"VDD",
"VIN",
"VOUT",
"+5V",
"+3V3",
"+3.3V",
"3V3",
"5V",
"12V",
"PWR",
"BAT",
"VSYS",
"PVDD",
]
class PlacementOptimizerCommands:
"""Mixin providing suggest_placement.
Expects the host (ComponentCommands) to provide:
- self.board : the loaded BOARD
- self._footprint_courtyard_bbox : bbox in mm for a footprint
so it composes with the existing component handlers.
"""
# ------------------------------------------------------------------ #
# Public command #
# ------------------------------------------------------------------ #
def suggest_placement(self, params: Dict[str, Any]) -> Dict[str, Any]:
"""Propose an optimized placement that shortens net length, orients
parts toward their partners, and removes courtyard overlaps — without
committing unless asked.
Args:
refs: References to move. Default: every non-locked footprint.
locked: References to hold fixed (connectors, mounting-constrained,
RF, edge parts). They still pull movable parts. KiCad's own
IsLocked() footprints are auto-added here.
iterations: Relaxation passes (default 200).
grid_mm: Snap proposed positions to this grid (default 0.5).
margin_mm: Extra keepout between courtyards (default 0.3).
board_outline: Optional {x1,y1,x2,y2,unit} override; else Edge.Cuts.
spring_k / repel_k: attraction / repulsion gains.
power_nets: Net-name fragments to weight as high-current
(default DEFAULT_POWER_NETS). Set [] to disable.
power_weight: Pull multiplier for power nets (default 3.0).
decoupling_boost: Extra pull for 2-pin-passive <-> multi-pin-IC
links so caps/feedback parts hug their IC (default 2.0).
rotate: Enable pin-facing rotation (default True).
rotation_steps: Candidate orientations in degrees
(default [0, 90, 180, 270]).
rotation_passes: Greedy rotation sweeps (default 2).
apply: If True, move + rotate the components. Default False (dry run).
Returns:
{success, proposals:{ref:[x,y,rot]}, score:{hpwl_before_mm,
hpwl_after_mm, improvement_pct, overlaps_before, overlaps_after},
applied, summary}
"""
try:
if not getattr(self, "board", None):
return {
"success": False,
"message": "No board is loaded",
"errorDetails": "Load or create a board first",
}
iterations = int(params.get("iterations", 200))
grid_mm = float(params.get("grid_mm", 0.5))
margin_mm = float(params.get("margin_mm", 0.3))
spring_k = float(params.get("spring_k", 0.08))
repel_k = float(params.get("repel_k", 0.6))
power_nets = [s.upper() for s in params.get("power_nets", DEFAULT_POWER_NETS)]
power_weight = float(params.get("power_weight", 3.0))
decoupling_boost = float(params.get("decoupling_boost", 2.0))
do_rotate = bool(params.get("rotate", True))
rotation_steps = list(params.get("rotation_steps", [0, 90, 180, 270]))
rotation_passes = int(params.get("rotation_passes", 2))
apply = bool(params.get("apply", False))
locked = set(params.get("locked") or [])
ref_filter = params.get("refs")
ref_filter = set(ref_filter) if ref_filter is not None else None
outline = self._opt_resolve_outline(params.get("board_outline"))
# Optional tighter box confining the MOVABLE parts (e.g. the area
# beside one IC). Movers are clamped to this; falls back to outline.
region = self._opt_resolve_outline(params.get("bounds")) or outline
net_names = self._opt_net_name_map()
move_set = set(ref_filter) if ref_filter is not None else None
# --- Collect EVERY footprint so locked ICs / neighbours still
# anchor and pull, even in scoped (refs=...) mode. A part is
# "fixed" if it's in `locked`, KiCad-locked, or — when `refs` is
# given — not one of the parts we're allowed to move. ---
nodes: Dict[str, Dict[str, Any]] = {}
for fp in self.board.GetFootprints():
ref = fp.GetReference()
fixed = (ref in locked) or (move_set is not None and ref not in move_set)
node = self._opt_make_node(fp, fixed)
if node is not None:
nodes[ref] = node
if len([n for n in nodes.values() if not n["locked"]]) < 2:
return {
"success": False,
"message": "Nothing to optimize",
"errorDetails": "Need >= 2 movable footprints with courtyards.",
}
self._opt_jitter_coincident(nodes, 1.0)
edges = self._opt_build_edges(
nodes, net_names, power_nets, power_weight, decoupling_boost
)
hpwl_before = self._opt_hpwl(nodes)
overlaps_before = self._opt_count_overlaps(nodes, margin_mm)
# --- Relax, then alternate rotation + light re-relax ---
self._opt_relax(
nodes,
edges,
region,
iterations=iterations,
spring_k=spring_k,
repel_k=repel_k,
margin_mm=margin_mm,
)
if do_rotate:
for _ in range(max(rotation_passes, 0)):
self._opt_rotate_pass(nodes, rotation_steps)
self._opt_relax(
nodes,
edges,
region,
iterations=max(20, iterations // 4),
spring_k=spring_k,
repel_k=repel_k,
margin_mm=margin_mm,
)
# --- Spread: the springs pack parts into a blob denser than the
# silicon physically fits; diffuse them across free board area
# (transport, which local pairwise pushing cannot do) before
# the final legalize. Skip when explicitly disabled. ---
if bool(params.get("spread", True)):
self._opt_spread(
nodes,
region,
iterations=int(params.get("spread_iters", 80)),
strength=float(params.get("spread_strength", 0.08)),
margin_mm=margin_mm,
)
# --- Align: the force solve leaves parts at organic offsets; snap
# near-collinear centers onto shared row (Y) and column (X)
# lines so the result reads as tidy rows/columns with items
# centered — like KiCad's align+distribute. Default on. ---
if bool(params.get("align", True)):
self._opt_align(nodes, float(params.get("align_tol_mm", 1.5)))
# --- Snap to grid, THEN legalize so separation has the last word
# (snapping after legalize would re-introduce overlaps). ---
for n in nodes.values():
if n["locked"]:
continue
n["x"] = round(n["x"] / grid_mm) * grid_mm
n["y"] = round(n["y"] / grid_mm) * grid_mm
# Springs collapse parts into a pile; push overlapping courtyards
# apart until clear (or iterations run out).
legalize_iters = int(params.get("legalize_iters", 200))
self._opt_legalize(nodes, region, margin_mm, legalize_iters)
hpwl_after = self._opt_hpwl(nodes)
overlaps_after = self._opt_count_overlaps(nodes, margin_mm)
proposals = {
ref: [round(n["x"], 3), round(n["y"], 3), round(n["angle"] % 360, 1)]
for ref, n in nodes.items()
if not n["locked"]
}
applied = False
if apply:
for ref, (px, py, rot) in proposals.items():
fp = nodes[ref]["fp"]
fp.SetPosition(pcbnew.VECTOR2I(pcbnew.FromMM(px), pcbnew.FromMM(py)))
fp.SetOrientationDegrees(rot)
applied = True
improvement = (
100.0 * (hpwl_before - hpwl_after) / hpwl_before if hpwl_before > 0 else 0.0
)
return {
"success": True,
"proposals": proposals,
"applied": applied,
"score": {
"hpwl_before_mm": round(hpwl_before, 2),
"hpwl_after_mm": round(hpwl_after, 2),
"improvement_pct": round(improvement, 1),
"overlaps_before": overlaps_before,
"overlaps_after": overlaps_after,
},
"summary": {
"movable": len(proposals),
"locked": sum(1 for n in nodes.values() if n["locked"]),
"nets_considered": len(edges),
"iterations": iterations,
"rotated": do_rotate,
"grid_mm": grid_mm,
"margin_mm": margin_mm,
"note": (
(
"Dry run — board unchanged. Validate via "
"check_courtyard_overlaps(positions=proposals), "
"then re-run with apply=true."
)
if not applied
else "Applied to board (not saved)."
),
},
}
except Exception as e: # noqa: BLE001
logger.error(f"suggest_placement failed: {e}", exc_info=True)
return {
"success": False,
"message": "suggest_placement failed",
"errorDetails": str(e),
}
# ------------------------------------------------------------------ #
# Node construction #
# ------------------------------------------------------------------ #
def _opt_make_node(self, fp, force_locked) -> Optional[Dict[str, Any]]:
bbox = self._footprint_courtyard_bbox(fp, None)
if bbox is None:
return None
x1, y1, x2, y2 = bbox
anchor = fp.GetPosition()
ax, ay = pcbnew.ToMM(anchor.x), pcbnew.ToMM(anchor.y)
angle0 = fp.GetOrientationDegrees()
# Courtyard center expressed in the footprint's *local* (un-rotated)
# frame, so we can re-project it after a rotation.
cwx, cwy = (x1 + x2) / 2.0 - ax, (y1 + y2) / 2.0 - ay
lox, loy = self._opt_rot(cwx, cwy, -angle0)
hw0, hh0 = max((x2 - x1) / 2.0, 0.01), max((y2 - y1) / 2.0, 0.01)
# Pad geometry in the footprint-local (un-rotated) frame, so that
# world pad = anchor + R(angle)*local. PAD.GetPos0() isn't exposed on
# every KiCad SWIG build, so derive it from the absolute pad position:
# local = R(-angle0) * (pad_abs - anchor).
pads = []
for pad in fp.Pads():
code = pad.GetNetCode()
if code <= 0:
continue
pp = pad.GetPosition()
wx = pcbnew.ToMM(pp.x - anchor.x)
wy = pcbnew.ToMM(pp.y - anchor.y)
lx, ly = self._opt_rot(wx, wy, -angle0)
pads.append((code, lx, ly))
node = {
"fp": fp,
"x": ax,
"y": ay, # working position = footprint anchor (mm)
"angle": angle0,
"angle0": angle0,
"loff": (lox, loy), # courtyard-center offset, local frame
"hw0": hw0,
"hh0": hh0, # half-sizes at angle0
"pads": pads,
"pins": fp.GetPadCount() if hasattr(fp, "GetPadCount") else len(pads),
"locked": force_locked or bool(fp.IsLocked()),
}
self._opt_apply_angle(node, angle0) # sets cox/coy, hw/hh
return node
def _opt_apply_angle(self, n, angle) -> None:
"""Set a node's orientation and refresh courtyard center-offset + halfs."""
n["angle"] = angle
lox, loy = n["loff"]
n["cox"], n["coy"] = self._opt_rot(lox, loy, angle)
# Half-sizes swap on odd 90-degree multiples (exact for AABB courtyards).
quarter = int(round((angle - n["angle0"]) / 90.0)) % 2
if quarter:
n["hw"], n["hh"] = n["hh0"], n["hw0"]
else:
n["hw"], n["hh"] = n["hw0"], n["hh0"]
# ------------------------------------------------------------------ #
# Edges (weighted connectivity) #
# ------------------------------------------------------------------ #
def _opt_build_edges(
self, nodes, net_names, power_nets, power_weight, decoupling_boost
) -> List[Tuple[str, str, float]]:
"""Collapse pad nets into weighted component edges.
- Base weight 1/(fanout-1) so a star net (GND/VCC) contributes constant
total pull rather than O(n^2).
- Power/high-current nets multiplied by power_weight (short & direct).
- A 2-pin passive linked to a multi-pin IC gets decoupling_boost so the
cap / feedback resistor hugs the IC.
"""
net_to_refs: Dict[int, set] = {}
for ref, n in nodes.items():
for code, _, _ in n["pads"]:
net_to_refs.setdefault(code, set()).add(ref)
# Deterministic order: iterate nets and refs sorted, so edge build order
# (and thus float-summation order in the relaxation) is reproducible
# across runs — the dry-run proposal must match the applied run. Python
# set iteration order varies per process (string hash randomisation).
weights: Dict[Tuple[str, str], float] = {}
for code in sorted(net_to_refs):
refs = sorted(net_to_refs[code])
fanout = len(refs)
if fanout < 2:
continue
name = net_names.get(code, "").upper()
pmult = power_weight if any(p in name for p in power_nets) else 1.0
base = pmult / (fanout - 1)
for i in range(fanout):
for j in range(i + 1, fanout):
a, b = sorted((refs[i], refs[j]))
weights[(a, b)] = weights.get((a, b), 0.0) + base
edges = []
for (a, b), w in weights.items():
pa, pb = nodes[a]["pins"], nodes[b]["pins"]
if (pa <= 2 < pb) or (pb <= 2 < pa):
w *= decoupling_boost
edges.append((a, b, w))
return edges
# ------------------------------------------------------------------ #
# Force-directed translation #
# ------------------------------------------------------------------ #
def _opt_relax(self, nodes, edges, outline, *, iterations, spring_k, repel_k, margin_mm):
movable = [r for r, n in nodes.items() if not n["locked"]]
refs = list(nodes)
for it in range(iterations):
temp = 1.0 - (it / max(iterations, 1))
max_step = 5.0 * temp + 0.2 # mm
fx = {r: 0.0 for r in movable}
fy = {r: 0.0 for r in movable}
# Attraction along nets, with a rest length so connected parts
# settle *adjacent* (just touching + margin) instead of collapsing
# onto a single point. Spring force = k*w*(dist - rest) along the
# center-to-center unit vector: attract when farther than rest,
# gently repel when closer.
for a, b, w in edges:
na, nb = nodes[a], nodes[b]
dx = (nb["x"] + nb["cox"]) - (na["x"] + na["cox"])
dy = (nb["y"] + nb["coy"]) - (na["y"] + na["coy"])
dist = math.hypot(dx, dy) or 1e-6
ra = (na["hw"] + na["hh"]) / 2.0
rb = (nb["hw"] + nb["hh"]) / 2.0
rest = ra + rb + margin_mm
f = spring_k * w * (dist - rest)
ux, uy = dx / dist, dy / dist
if a in fx:
fx[a] += f * ux
fy[a] += f * uy
if b in fx:
fx[b] -= f * ux
fy[b] -= f * uy
# Repulsion only where courtyards (AABB + margin) overlap.
for i in range(len(refs)):
na = nodes[refs[i]]
for j in range(i + 1, len(refs)):
nb = nodes[refs[j]]
dx = (nb["x"] + nb["cox"]) - (na["x"] + na["cox"])
dy = (nb["y"] + nb["coy"]) - (na["y"] + na["coy"])
ox = (na["hw"] + nb["hw"] + margin_mm) - abs(dx)
oy = (na["hh"] + nb["hh"] + margin_mm) - abs(dy)
if ox <= 0 or oy <= 0:
continue
ra, rb = refs[i], refs[j]
if ox < oy: # push along least-penetration axis
push, s = repel_k * ox, (1.0 if dx >= 0 else -1.0)
if ra in fx:
fx[ra] -= push * s
if rb in fx:
fx[rb] += push * s
else:
push, s = repel_k * oy, (1.0 if dy >= 0 else -1.0)
if ra in fy:
fy[ra] -= push * s
if rb in fy:
fy[rb] += push * s
for r in movable:
n = nodes[r]
step = math.hypot(fx[r], fy[r])
if step > max_step and step > 0:
scale = max_step / step
fx[r] *= scale
fy[r] *= scale
n["x"] += fx[r]
n["y"] += fy[r]
if outline is not None:
ox1, oy1, ox2, oy2 = outline
n["x"] = min(max(n["x"], ox1 + n["hw"] - n["cox"]), ox2 - n["hw"] - n["cox"])
n["y"] = min(max(n["y"], oy1 + n["hh"] - n["coy"]), oy2 - n["hh"] - n["coy"])
# ------------------------------------------------------------------ #
# Alignment / tidy (rows + columns, centers aligned) #
# ------------------------------------------------------------------ #
def _opt_align(self, nodes, tol):
"""Snap near-collinear part centers onto shared row/column lines so the
layout reads as tidy rows and columns instead of organic offsets.
Parts whose center Y values fall within `tol` are pulled to a common Y
(a row); likewise center X for columns. Aligning on CENTERS means a big
IC and a small cap on the same line share a centerline — i.e. centered,
the way KiCad's Align Centers + Distribute leaves them. A final legalize
(run by the caller afterwards) fixes any spacing this tightens."""
movable = [n for n in nodes.values() if not n["locked"]]
if len(movable) < 2:
return
# Rows: cluster on Y (center), columns: cluster on X (center).
self._opt_cluster_snap(movable, "y", tol)
self._opt_cluster_snap(movable, "x", tol)
@staticmethod
def _opt_cluster_snap(parts, axis, tol):
"""Group parts whose center on `axis` is within tol of the running group,
then set every member's center to the group mean. Deterministic: sorted
by center, ties broken by the offset key so order is stable."""
off = "cox" if axis == "x" else "coy"
pos = "x" if axis == "x" else "y"
def center(n):
return n[pos] + n[off]
ordered = sorted(parts, key=lambda n: (center(n), n[off]))
i = 0
while i < len(ordered):
group = [ordered[i]]
j = i + 1
# Extend while the next center is within tol of the group's last.
while j < len(ordered) and center(ordered[j]) - center(group[-1]) <= tol:
group.append(ordered[j])
j += 1
mean = sum(center(g) for g in group) / len(group)
for g in group:
g[pos] = mean - g[off]
i = j
# ------------------------------------------------------------------ #
# Density spreading (cell diffusion) #
# ------------------------------------------------------------------ #
def _opt_spread(self, nodes, region, *, iterations, strength, margin_mm):
"""Diffuse movable parts down the area-density gradient so they occupy
the whole region instead of a single over-packed blob.
This is the 'global spreading' half of analytical placement: bin the
region, build a density field (movable + fixed parts as mass), and move
each movable part opposite the local gradient. Unlike pairwise pushing,
the gradient transports a part across many bins toward genuinely free
area — which is what fixes the whole-board over-pack. A light legalize
afterwards cleans the residual touching pairs."""
if region is None:
return
rx1, ry1, rx2, ry2 = region
rw, rh = rx2 - rx1, ry2 - ry1
if rw <= 0 or rh <= 0:
return
movable = [n for n in nodes.values() if not n["locked"]]
if not movable:
return
# Bin grid: aim for a few parts per bin; clamp to a sane range.
n = len(nodes)
nx = max(4, min(48, int(math.sqrt(max(n, 1)) * 1.5)))
ny = max(4, min(48, int(round(nx * rh / rw)))) if rw > 0 else nx
bw, bh = rw / nx, rh / ny
bin_area = max(bw * bh, 1e-6)
def bin_of(cx, cy):
i = min(max(int((cx - rx1) / bw), 0), nx - 1)
j = min(max(int((cy - ry1) / bh), 0), ny - 1)
return i, j
for it in range(iterations):
temp = 1.0 - (it / max(iterations, 1))
# Build density (mm^2 of courtyard area per bin), all parts count
# as mass so movers also flow around locked ICs.
dens = [[0.0] * ny for _ in range(nx)]
for nd in nodes.values():
area = (2 * nd["hw"]) * (2 * nd["hh"])
i, j = bin_of(nd["x"] + nd["cox"], nd["y"] + nd["coy"])
dens[i][j] += area
# One Jacobi blur pass to smooth the gradient.
sm = [[0.0] * ny for _ in range(nx)]
for i in range(nx):
for j in range(ny):
acc, cnt = 0.0, 0
for di in (-1, 0, 1):
for dj in (-1, 0, 1):
a, b = i + di, j + dj
if 0 <= a < nx and 0 <= b < ny:
acc += dens[a][b]
cnt += 1
sm[i][j] = acc / cnt
# Move each movable part opposite the local density gradient.
for nd in movable:
cx, cy = nd["x"] + nd["cox"], nd["y"] + nd["coy"]
i, j = bin_of(cx, cy)
ip, im = min(i + 1, nx - 1), max(i - 1, 0)
jp, jm = min(j + 1, ny - 1), max(j - 1, 0)
gx = (sm[ip][j] - sm[im][j]) / (2 * bw)
gy = (sm[i][jp] - sm[i][jm]) / (2 * bh)
# Only spread out of bins fuller than the region average; this
# keeps already-sparse areas from jittering.
over = sm[i][j] / bin_area
step_x = -strength * gx * over * temp
step_y = -strength * gy * over * temp
mag = math.hypot(step_x, step_y)
cap = 0.5 * min(bw, bh)
if mag > cap and mag > 0:
step_x *= cap / mag
step_y *= cap / mag
nd["x"] += step_x
nd["y"] += step_y
nd["x"] = min(max(nd["x"], rx1 + nd["hw"] - nd["cox"]), rx2 - nd["hw"] - nd["cox"])
nd["y"] = min(max(nd["y"], ry1 + nd["hh"] - nd["coy"]), ry2 - nd["hh"] - nd["coy"])
# ------------------------------------------------------------------ #
# Legalization (remove courtyard overlaps) #
# ------------------------------------------------------------------ #
def _opt_legalize(self, nodes, outline, margin_mm, iterations):
"""Push overlapping courtyards apart until none overlap (or iterations
run out). No spring pull here — this only separates, preserving the
relative arrangement the optimizer found. Locked parts don't move, so a
movable part overlapping a locked one takes the full push."""
refs = list(nodes)
prev_overlaps = None
stall = 0
for it in range(iterations):
# Accumulate (summed, not averaged) every pair's separation, then
# apply once. Summed opposing pushes don't cancel a part out of
# existence — they expand the whole cluster outward, which is what
# relieves a wedged part.
push = {r: [0.0, 0.0] for r in refs}
overlaps = 0
for i in range(len(refs)):
na = nodes[refs[i]]
for j in range(i + 1, len(refs)):
nb = nodes[refs[j]]
if na["locked"] and nb["locked"]:
continue
dx = (nb["x"] + nb["cox"]) - (na["x"] + na["cox"])
dy = (nb["y"] + nb["coy"]) - (na["y"] + na["coy"])
ox = (na["hw"] + nb["hw"] + margin_mm) - abs(dx)
oy = (na["hh"] + nb["hh"] + margin_mm) - abs(dy)
if ox <= 0 or oy <= 0:
continue
overlaps += 1
# Separate along the cheaper (least-penetration) axis.
if ox < oy:
sx = ox if dx >= 0 else -ox
sy = 0.0
else:
sx = 0.0
sy = oy if dy >= 0 else -oy
a_mov, b_mov = (not na["locked"]), (not nb["locked"])
share = 0.5 if (a_mov and b_mov) else 1.0
ra, rb = refs[i], refs[j]
if a_mov:
push[ra][0] -= sx * share
push[ra][1] -= sy * share
if b_mov:
push[rb][0] += sx * share
push[rb][1] += sy * share
if overlaps == 0:
break
# Stall detection: if the overlap count stops improving, nudge every
# contended part radially outward from the cluster centroid to break
# a symmetric wedge (deterministic — index-based, no RNG).
if prev_overlaps is not None and overlaps >= prev_overlaps:
stall += 1
else:
stall = 0
prev_overlaps = overlaps
if stall >= 3:
self._opt_explode(nodes, push, 0.4)
stall = 0
for r in refs:
n = nodes[r]
if n["locked"]:
continue
dx, dy = push[r]
# Cap per-iteration motion so a big summed push can't blow up.
mag = math.hypot(dx, dy)
if mag > 1.5 and mag > 0:
dx *= 1.5 / mag
dy *= 1.5 / mag
n["x"] += dx
n["y"] += dy
if outline is not None:
ox1, oy1, ox2, oy2 = outline
n["x"] = min(max(n["x"], ox1 + n["hw"] - n["cox"]), ox2 - n["hw"] - n["cox"])
n["y"] = min(max(n["y"], oy1 + n["hh"] - n["coy"]), oy2 - n["hh"] - n["coy"])
def _opt_explode(self, nodes, push, amount):
"""Add a small outward bias from the movable-parts centroid to any part
currently being pushed, to break a symmetric stall."""
movable = [n for n in nodes.values() if not n["locked"]]
if not movable:
return
cx = sum(n["x"] + n["cox"] for n in movable) / len(movable)
cy = sum(n["y"] + n["coy"] for n in movable) / len(movable)
for ref, n in nodes.items():
if n["locked"] or push[ref] == [0.0, 0.0]:
continue
vx = (n["x"] + n["cox"]) - cx
vy = (n["y"] + n["coy"]) - cy
d = math.hypot(vx, vy) or 1e-6
push[ref][0] += amount * vx / d
push[ref][1] += amount * vy / d
# ------------------------------------------------------------------ #
# Pin-facing rotation (greedy, pad-accurate) #
# ------------------------------------------------------------------ #
def _opt_rotate_pass(self, nodes, steps):
"""For each movable part, pick the orientation (from `steps`) that
minimises the pad-level HPWL of the nets it touches, holding every other
part fixed. Emergently orients 2-pad parts toward their partners and
unwinds crossings."""
movable = [r for r, n in nodes.items() if not n["locked"]]
for ref in movable:
n = nodes[ref]
nets = {c for c, _, _ in n["pads"]}
if not nets:
continue
# Fixed contribution from every OTHER node, per net.
other = self._opt_net_extents(nodes, exclude=ref, only=nets)
best_angle, best_cost = n["angle"], float("inf")
for da in steps:
angle = (n["angle0"] + da) % 360
cost = self._opt_rot_cost(n, angle, other)
if cost < best_cost - 1e-9:
best_cost, best_angle = cost, angle
self._opt_apply_angle(n, best_angle)
def _opt_rot_cost(self, n, angle, other_extents) -> float:
"""Sum of net bbox spans for this node's nets at the given orientation,
combined with the precomputed extents of all other nodes."""
ax, ay = n["x"], n["y"]
local = {} # net -> [minx, miny, maxx, maxy]
for code, px0, py0 in n["pads"]:
wx, wy = self._opt_rot(px0, py0, angle)
wx += ax
wy += ay
e = local.get(code)
if e is None:
local[code] = [wx, wy, wx, wy]
else:
e[0] = min(e[0], wx)
e[1] = min(e[1], wy)
e[2] = max(e[2], wx)
e[3] = max(e[3], wy)
total = 0.0
for code, e in local.items():
o = other_extents.get(code)
if o is None:
continue # net only on this part — no contribution
minx = min(e[0], o[0])
miny = min(e[1], o[1])
maxx = max(e[2], o[2])
maxy = max(e[3], o[3])
total += (maxx - minx) + (maxy - miny)
return total
def _opt_net_extents(self, nodes, *, exclude=None, only=None):
"""net code -> [minx,miny,maxx,maxy] of world pad positions, excluding
one ref, optionally restricted to a set of net codes."""
ext: Dict[int, List[float]] = {}
for ref, n in nodes.items():
if ref == exclude:
continue
ax, ay, angle = n["x"], n["y"], n["angle"]
for code, px0, py0 in n["pads"]:
if only is not None and code not in only:
continue
wx, wy = self._opt_rot(px0, py0, angle)
wx += ax
wy += ay
e = ext.get(code)
if e is None:
ext[code] = [wx, wy, wx, wy]
else:
e[0] = min(e[0], wx)
e[1] = min(e[1], wy)
e[2] = max(e[2], wx)
e[3] = max(e[3], wy)
return ext
# ------------------------------------------------------------------ #
# Scoring / metrics #
# ------------------------------------------------------------------ #
def _opt_hpwl(self, nodes) -> float:
"""Pad-level half-perimeter wire length over all nets (mm)."""
ext = self._opt_net_extents(nodes)
total = 0.0
for e in ext.values():
total += (e[2] - e[0]) + (e[3] - e[1])
return total
def _opt_count_overlaps(self, nodes, margin_mm) -> int:
refs = list(nodes)
count = 0
for i in range(len(refs)):
na = nodes[refs[i]]
for j in range(i + 1, len(refs)):
nb = nodes[refs[j]]
dx = abs((nb["x"] + nb["cox"]) - (na["x"] + na["cox"]))
dy = abs((nb["y"] + nb["coy"]) - (na["y"] + na["coy"]))
if dx < na["hw"] + nb["hw"] + margin_mm and dy < na["hh"] + nb["hh"] + margin_mm:
count += 1
return count
# ------------------------------------------------------------------ #
# Small helpers #
# ------------------------------------------------------------------ #
@staticmethod
def _opt_rot(x, y, deg) -> Tuple[float, float]:
rad = math.radians(deg)
c, s = math.cos(rad), math.sin(rad)
return (x * c - y * s, x * s + y * c)
def _opt_net_name_map(self) -> Dict[int, str]:
names: Dict[int, str] = {}
try:
for code, net in self.board.GetNetInfo().NetsByNetcode().items():
names[code] = net.GetNetname()
except Exception: # noqa: BLE001
pass
return names
def _opt_jitter_coincident(self, nodes, spread) -> None:
"""Deterministically separate parts sharing the exact same point so the
first repulsion pass has a direction to push (no RNG — index-based)."""
seen: Dict[Tuple[float, float], int] = {}
for ref, n in sorted(nodes.items()):
if n["locked"]:
continue
key = (round(n["x"], 3), round(n["y"], 3))
k = seen.get(key, 0)
if k:
ang = 2.0 * math.pi * (k / 8.0)
n["x"] += spread * math.cos(ang)
n["y"] += spread * math.sin(ang)
seen[key] = k + 1
def _opt_resolve_outline(self, override):
if override:
unit = override.get("unit", "mm")
f = {"inch": 25.4, "mil": 0.0254}.get(unit, 1.0) # -> mm
return (override["x1"] * f, override["y1"] * f, override["x2"] * f, override["y2"] * f)
try:
box = self.board.GetBoardEdgesBoundingBox()
if box.GetWidth() > 0 and box.GetHeight() > 0:
return (
pcbnew.ToMM(box.GetLeft()),
pcbnew.ToMM(box.GetTop()),
pcbnew.ToMM(box.GetRight()),
pcbnew.ToMM(box.GetBottom()),
)
except Exception: # noqa: BLE001
pass
return None