"""Work out what copper a layer's filled shapes actually image.
A source object's holes are not a description of the copper; they are an
artifact of how the shape was authored. If a same-net shape overlaps
another's hole, the real copper has no hole there, and replaying that hole as
a clear region asserts an absence that does not exist - `dark(P)`, `dark(O)`,
`clear(H)` punches the hole straight back into copper `O` had correctly
filled. Reordering cannot fix it in general: two same-net shapes can each
hole the other, which has no valid order at all.
So the union is not a repair applied to awkward inputs, it is how the image
is determined. Union the copper, and the holes that survive are the only
holes that are real. Ordering runs on the result.
Two graphs over the same layer, not one. The connectivity graph holds
everything conducting, including pads, because net attribution depends on
what a shape touches and the canonical net tie touches pads and nothing else.
The union takes region-imaged copper only: a pad contributes no region
geometry, and its own holes live in its aperture, where they are transparent.
"""
from __future__ import annotations
from dataclasses import dataclass, field
from logging import getLogger
import shapely
from shapely import STRtree
from shapely.geometry.base import BaseGeometry
logger = getLogger(__name__)
GRID = 1e-6
"""The 1 nm output grid, as a shapely `grid_size`.
Every predicate and every union runs on it, so adjacency is decided on the
same grid the file is written on. Shapely is float-exact otherwise: two
rectangles abutting at a shared edge intersect, the same pair with a 1e-12
gap do not, and the two answers give different connected components.
"""
[docs]
@dataclass(frozen=True)
class Piece:
"""One piece of copper on one layer, as the region builder sees it.
Args:
geom: the placed geometry, already snapped to the output grid.
nets: the nets the design declares for it. Empty means the design
has no net object for it, which is not the same as unknown - the
exporter never promotes a shape to a neighbour's net.
tie: the piece came from `OverlappableCopper`, so a cross-net contact
through it is a declared bridge rather than a short.
filled: the piece images as a region and takes part in the union.
Pads, vias and stroked traces are in the graph but not the union.
"""
geom: BaseGeometry
nets: frozenset[str] = frozenset()
tie: bool = False
filled: bool = True
[docs]
@dataclass(frozen=True)
class Island:
"""A resolved island of the layer image, with the holes that are real.
Args:
nets: the nets to declare on it. A tie carries every net of the
component it bridges, which is 5.6.13's list form.
tie: the island is a net tie and carries `TA.AperFunction,
EtchedComponent`. That attribute attaches to an object, which is
why a tie cannot be merged away into the copper it bridges.
"""
outer: shapely.Polygon
holes: tuple[shapely.Polygon, ...]
nets: frozenset[str]
tie: bool
[docs]
@dataclass
class Report:
"""What the analysis found worth complaining about."""
shorts: int = 0
overlaps: int = 0
pairs: list[tuple[frozenset[str], frozenset[str]]] = field(default_factory=list)
[docs]
def build(pieces: list[Piece], report: Report | None = None) -> list[Island]:
"""Resolve a layer's copper into islands, ordered for emission.
The order is a depth-first walk of the containment tree, so an island
always follows the hole that would otherwise have erased it.
"""
report = report if report is not None else Report()
groups = _components(pieces, report)
islands: list[Island] = []
for group in groups:
islands += _component_islands(group)
_check_overlaps(islands, report)
return _ordered(islands)
# --------------------------------------------------------------------------
# connectivity
def _components(pieces: list[Piece], report: Report) -> list[list[Piece]]:
"""Connected components of touching copper.
Same-net contact always joins. Different-net contact joins only through a
tie, which is a declared, intentional bridge; different-net contact
without one is a DRC problem in the source design and is complained about
rather than merged silently. Copper the design gives no net joins
whatever it touches without taking that neighbour's net: it is physically
continuous, and it still declares the reserved empty `.N`.
"""
if not pieces:
return []
tree = STRtree([piece.geom for piece in pieces])
parent = list(range(len(pieces)))
def find(index: int) -> int:
while parent[index] != index:
parent[index] = parent[parent[index]]
index = parent[index]
return index
def union(a: int, b: int) -> None:
ra, rb = find(a), find(b)
if ra != rb:
parent[max(ra, rb)] = min(ra, rb)
for i, piece in enumerate(pieces):
for j in tree.query(piece.geom, predicate="intersects"):
j = int(j)
if j <= i:
continue
other = pieces[j]
if piece.tie or other.tie or not piece.nets or not other.nets:
union(i, j)
elif piece.nets & other.nets:
union(i, j)
else:
report.shorts += 1
report.pairs.append((piece.nets, other.nets))
grouped: dict[int, list[Piece]] = {}
for index, piece in enumerate(pieces):
grouped.setdefault(find(index), []).append(piece)
return list(grouped.values())
# --------------------------------------------------------------------------
# union
def _component_islands(group: list[Piece]) -> list[Island]:
"""Union one component and read its real holes off the result.
The component's whole filled area is unioned for the analysis, but the
emission stays per net: a bridged component holds two nets whose pours
each keep their own single-net `.N`, and the tie keeps its identity
because `EtchedComponent` attaches to an object and a merged region
cannot be one.
"""
filled = [piece for piece in group if piece.filled]
if not filled:
return []
whole = shapely.union_all([piece.geom for piece in filled], grid_size=GRID)
every_net = frozenset().union(*(piece.nets for piece in group))
buckets: dict[tuple[bool, frozenset[str]], list[BaseGeometry]] = {}
for piece in filled:
key = (piece.tie, every_net if piece.tie else piece.nets)
buckets.setdefault(key, []).append(piece.geom)
islands: list[Island] = []
for (tie, nets), geoms in buckets.items():
merged = shapely.union_all(geoms, grid_size=GRID)
for polygon in _polygons(merged):
holes = tuple(_real_holes(polygon, whole))
islands.append(Island(shapely.Polygon(polygon.exterior), holes, nets, tie))
return islands
def _polygons(geom: BaseGeometry) -> list[shapely.Polygon]:
if isinstance(geom, shapely.Polygon):
return [geom] if not geom.is_empty else []
if isinstance(geom, shapely.MultiPolygon):
return [p for p in geom.geoms if not p.is_empty]
if isinstance(geom, shapely.GeometryCollection):
out: list[shapely.Polygon] = []
for part in geom.geoms:
out += _polygons(part)
return out
return []
def _real_holes(polygon: shapely.Polygon, whole: BaseGeometry):
"""The holes of one net's union that are still holes in the component's.
A hole another piece of the component fills is not a hole in the copper,
so emitting it as a clear region would erase copper that belongs there.
This is the case that makes the tie take part in the union analysis: a
tie can overlap a hole in the copper it bridges, and the tie is not
hole-free itself.
"""
for ring in polygon.interiors:
hole = shapely.Polygon(ring)
if hole.is_empty:
continue
if whole.contains(hole):
continue
yield hole
# --------------------------------------------------------------------------
# ordering
def _ordered(islands: list[Island]) -> list[Island]:
"""Depth-first over the containment tree of the outer rings.
An `STRtree` rather than pairwise `contains`: a plane layer with several
hundred foreign islands sitting in its clearances is ordinary, and the
naive version is quadratic in exactly that case.
"""
if len(islands) < 2:
return list(islands)
outers = [island.outer for island in islands]
tree = STRtree(outers)
children: dict[int, list[int]] = {i: [] for i in range(len(islands))}
roots: list[int] = []
for index, outer in enumerate(outers):
parent = None
for candidate in tree.query(outer, predicate="within"):
candidate = int(candidate)
if candidate == index:
continue
if parent is None or outers[candidate].within(outers[parent]):
parent = candidate
if parent is None:
roots.append(index)
else:
children[parent].append(index)
out: list[Island] = []
def walk(index: int) -> None:
out.append(islands[index])
for child in sorted(children[index], key=lambda c: -outers[c].area):
walk(child)
for root in sorted(roots, key=lambda r: -outers[r].area):
walk(root)
return out
def _copper(island: Island) -> shapely.Polygon | BaseGeometry:
"""The copper an island actually images: its ring minus its holes.
Distinct from `island.outer`, and the distinction is the whole of a pour.
A pour's ring spans the board and its clearances are holes, so anything
routed in a clearance lies inside the ring while touching none of the
copper.
Only `_check_overlaps` wants this. `_ordered` compares rings on purpose -
an island sitting in a pour's clearance *is* contained by the pour and
has to be emitted after it, or the pour's clear region erases it.
"""
if not island.holes:
return island.outer
return island.outer.difference(shapely.unary_union(island.holes))
def _check_overlaps(islands: list[Island], report: Report) -> None:
"""Complain when two different nets' copper overlaps after unioning.
Narrower than it looks: the union has already absorbed every same-net
overlap and every declared bridge, so what is left indicates a broken
source design rather than an exporter limitation. Copper originating from
`OverlappableCopper` is exempt, or every net tie in every design raises.
"""
real = [i for i in islands if not i.tie and i.nets]
if len(real) < 2:
return
# holes are subtracted once per island rather than once per pair: a plane
# layer's islands are compared many times over, and only a holed island
# pays for the difference at all
copper = [_copper(island) for island in real]
tree = STRtree(copper)
for index, island in enumerate(real):
for other in tree.query(copper[index], predicate="intersects"):
other = int(other)
if other <= index:
continue
partner = real[other]
if island.nets & partner.nets:
continue
if copper[index].intersection(copper[other]).area <= 0:
continue
report.overlaps += 1
report.pairs.append((island.nets, partner.nets))
[docs]
def complain(report: Report, layer: str) -> None:
"""Log what the analysis found, once per layer."""
if report.shorts:
logger.error(
"%s: %d contacts between copper on different nets that are not "
"declared net ties; the fabricator will report these as shorts. "
"Nets involved: %s",
layer,
report.shorts,
_pairs(report.pairs),
)
if report.overlaps:
logger.error(
"%s: %d overlaps between copper on different nets after unioning: %s",
layer,
report.overlaps,
_pairs(report.pairs),
)
def _pairs(pairs: list[tuple[frozenset[str], frozenset[str]]]) -> str:
shown = sorted(
{
" / ".join(sorted(",".join(sorted(side)) or "<no net>" for side in pair))
for pair in pairs
}
)
return "; ".join(shown[:8]) + (" ..." if len(shown) > 8 else "")