Files
vibemake-pcb-studio/pcbnew/convert_shape_list_to_polygon.ts
likang 7e01147566
CI / typecheck + test + build (push) Has been cancelled
Initial commit: import VibeMake PCB Studio
2026-11-03 11:20:08 +08:00

1731 lines
51 KiB
TypeScript

// SPDX-License-Identifier: GPL-3.0-or-later
// Copyright (C) 2026 ZiroEDA and contributors.
// Portions derived from KiCad, copyright The KiCad Developers. See NOTICE.md.
/**
* `pcbnew/convert_shape_list_to_polygon.h` / `.cpp`: `ConvertOutlineToPolygon`,
* a polygon set with holes from a `PCB_SHAPE` list, and the helpers it chains
* shapes with.
*
* The nanoflann KD-tree of the C++ answers "the two nearest shape endpoints";
* `nearestTwoEndpoints` answers the same question by scanning the endpoint
* list, which is the answer the tree gives without the tree.
*
*/
import { SKIP_STRUCT } from '@ziroeda/common/eda_item_flags.js';
import { SHAPE_T } from '@ziroeda/common/eda_shape.js';
import { ANGLE_360 } from '@ziroeda/kimath/src/geometry/eda_angle.js';
import { ROUNDRECT } from '@ziroeda/kimath/src/geometry/roundrect.js';
import { SEG } from '@ziroeda/kimath/src/geometry/seg.js';
import { SHAPE_ARC } from '@ziroeda/kimath/src/geometry/shape_arc.js';
import {
type INTERSECTIONS,
SHAPE_LINE_CHAIN,
} from '@ziroeda/kimath/src/geometry/shape_line_chain.js';
import { SHAPE_POLY_SET } from '@ziroeda/kimath/src/geometry/shape_poly_set.js';
import { SHAPE_RECT } from '@ziroeda/kimath/src/geometry/shape_rect.js';
import {
LexicographicalCompare,
type VECTOR2I,
equal,
sub,
} from '@ziroeda/kimath/src/math/vector2.js';
import { ERROR_LOC } from '@ziroeda/kimath/src/convert_basic_shapes_to_polygon.js';
import { pcbIUScale } from '@ziroeda/common/eda_units.js';
import { PCB_LAYER_ID } from '@ziroeda/common/layer_id.js';
import { KICAD_T } from '@ziroeda/core/typeinfo.js';
import { EuclideanNormI } from '@ziroeda/kimath/src/math/vector2.js';
import type { BOARD } from './board.js';
import type { BOARD_ITEM } from './board_item.js';
import { PCB_TYPE_COLLECTOR } from './collectors.js';
import type { FOOTPRINT } from './footprint.js';
import type { PCB_SHAPE } from './pcb_shape.js';
export type OUTLINE_ERROR_HANDLER = (
msg: string,
itemA: BOARD_ITEM | null,
itemB: BOARD_ITEM | null,
pt: VECTOR2I,
) => void;
/** `class SCOPED_FLAGS_CLEANER : public std::unordered_set<EDA_ITEM*>`: clears the flags of every item it holds on exit. */
class SCOPED_FLAGS_CLEANER extends Set<BOARD_ITEM> {
private m_flagsToClear: number;
constructor(aFlagsToClear: number) {
super();
this.m_flagsToClear = aFlagsToClear;
}
/** The destructor. */
dispose(): void {
for (const item of this) item.ClearFlags(this.m_flagsToClear);
}
}
/**
* Local and tunable method of qualifying the proximity of two points.
*
* @param aLeft is the first point.
* @param aRight is the second point.
* @param aLimit is a measure of proximity that the caller knows about.
* @return true if the two points are close enough, else false.
*/
function close_enough(aLeft: VECTOR2I, aRight: VECTOR2I, aLimit: number): boolean {
const d = sub(aLeft, aRight);
return d.x * d.x + d.y * d.y <= SEG.Square(aLimit);
}
/**
* Local method which qualifies whether the start or end point of a segment is closest to a point.
*
* @param aRef is the reference point
* @param aFirst is the first point
* @param aSecond is the second point
* @return true if the first point is closest to the reference, otherwise false.
*/
function closer_to_first(aRef: VECTOR2I, aFirst: VECTOR2I, aSecond: VECTOR2I): boolean {
const d1 = sub(aRef, aFirst);
const d2 = sub(aRef, aSecond);
return d1.x * d1.x + d1.y * d1.y < d2.x * d2.x + d2.y * d2.y;
}
/** `PCB_SHAPE_ENDPOINTS_ADAPTOR`: the start and end of every shape, as the KD-tree indexes them. */
class PCB_SHAPE_ENDPOINTS_ADAPTOR {
endpoints: [VECTOR2I, PCB_SHAPE][] = [];
constructor(shapes: readonly PCB_SHAPE[]) {
for (const shape of shapes) {
this.endpoints.push([shape.GetStart(), shape]);
this.endpoints.push([shape.GetEnd(), shape]);
}
}
}
/** `kdTree.knnSearch( query_pt, 2, indices, distances )`: the two nearest endpoints, squared distances. */
function nearestTwoEndpoints(
adaptor: PCB_SHAPE_ENDPOINTS_ADAPTOR,
aPoint: VECTOR2I,
): { indices: number[]; distances: number[] } {
let i0 = -1;
let i1 = -1;
let d0 = Number.MAX_VALUE;
let d1 = Number.MAX_VALUE;
for (let i = 0; i < adaptor.endpoints.length; ++i) {
const p = adaptor.endpoints[i]![0];
const dx = p.x - aPoint.x;
const dy = p.y - aPoint.y;
const d = dx * dx + dy * dy;
if (d < d0) {
i1 = i0;
d1 = d0;
i0 = i;
d0 = d;
} else if (d < d1) {
i1 = i;
d1 = d;
}
}
return { indices: [i0, i1], distances: [d0, d1] };
}
/** `std::map<std::pair<VECTOR2I, VECTOR2I>, PCB_SHAPE*>`, keyed by the two points. */
type SHAPE_OWNERS = Map<string, PCB_SHAPE>;
const ownerKey = (a: VECTOR2I, b: VECTOR2I): string => `${a.x},${a.y}|${b.x},${b.y}`;
function processClosedShape(
aShape: PCB_SHAPE,
aContour: SHAPE_LINE_CHAIN,
aShapeOwners: SHAPE_OWNERS,
aErrorMax: number,
aAllowUseArcsInPolygons: boolean,
): void {
switch (aShape.GetShape()) {
case SHAPE_T.POLY: {
let prevPt: VECTOR2I = { x: 0, y: 0 };
let firstPt = true;
for (const pt of aShape.GetPolyShape().CIterate()) {
aContour.Append(pt);
if (firstPt) firstPt = false;
else aShapeOwners.set(ownerKey(prevPt, pt), aShape);
prevPt = pt;
}
aContour.SetClosed(true);
break;
}
case SHAPE_T.CIRCLE: {
const center = aShape.GetCenter();
const radius = aShape.GetRadius();
const start = { x: center.x + radius, y: center.y };
const arc360 = new SHAPE_ARC(center, start, ANGLE_360, 0);
aContour.Append(arc360, aErrorMax);
aContour.SetClosed(true);
for (let ii = 1; ii < aContour.PointCount(); ++ii)
aShapeOwners.set(ownerKey(aContour.CPoint(ii - 1), aContour.CPoint(ii)), aShape);
if (!aAllowUseArcsInPolygons) aContour.ClearArcs();
break;
}
case SHAPE_T.RECTANGLE: {
if (aShape.GetCornerRadius() > 0) {
const rr = new ROUNDRECT(
new SHAPE_RECT(
aShape.GetStart(),
aShape.GetRectangleWidth(),
aShape.GetRectangleHeight(),
),
aShape.GetCornerRadius(),
true /* normalize */,
);
const poly = new SHAPE_POLY_SET();
rr.TransformToPolygon(poly, aShape.GetMaxError());
aContour.Append(poly.Outline(0));
for (let ii = 1; ii < aContour.PointCount(); ++ii)
aShapeOwners.set(ownerKey(aContour.CPoint(ii - 1), aContour.CPoint(ii)), aShape);
if (!aAllowUseArcsInPolygons) aContour.ClearArcs();
aContour.SetClosed(true);
break;
}
const pts = aShape.GetRectCorners();
let prevPt: VECTOR2I = { x: 0, y: 0 };
let firstPt = true;
for (const pt of pts) {
aContour.Append(pt);
if (firstPt) firstPt = false;
else aShapeOwners.set(ownerKey(prevPt, pt), aShape);
prevPt = pt;
}
aContour.SetClosed(true);
break;
}
default:
break;
}
}
function processShapeSegment(
aShape: PCB_SHAPE,
aContour: SHAPE_LINE_CHAIN,
aPrevPt: { value: VECTOR2I },
aShapeOwners: SHAPE_OWNERS,
aErrorMax: number,
aChainingEpsilon: number,
aAllowUseArcsInPolygons: boolean,
): void {
switch (aShape.GetShape()) {
case SHAPE_T.SEGMENT: {
let nextPt: VECTOR2I;
if (closer_to_first(aPrevPt.value, aShape.GetStart(), aShape.GetEnd()))
nextPt = aShape.GetEnd();
else nextPt = aShape.GetStart();
aContour.Append(nextPt);
aShapeOwners.set(ownerKey(aPrevPt.value, nextPt), aShape);
aPrevPt.value = nextPt;
break;
}
case SHAPE_T.ARC: {
let pstart = aShape.GetStart();
const pmid = aShape.GetArcMid();
let pend = aShape.GetEnd();
if (!close_enough(aPrevPt.value, pstart, aChainingEpsilon)) {
if (!close_enough(aPrevPt.value, aShape.GetEnd(), aChainingEpsilon)) return;
[pstart, pend] = [pend, pstart];
}
pstart = aPrevPt.value;
const sarc = new SHAPE_ARC(pstart, pmid, pend, 0);
const arcChain = new SHAPE_LINE_CHAIN();
arcChain.Append(sarc, aErrorMax);
if (!aAllowUseArcsInPolygons) arcChain.ClearArcs();
for (let ii = 1; ii < arcChain.PointCount(); ++ii) {
aShapeOwners.set(ownerKey(arcChain.CPoint(ii - 1), arcChain.CPoint(ii)), aShape);
}
aContour.Append(arcChain);
aPrevPt.value = pend;
break;
}
case SHAPE_T.BEZIER: {
let nextPt: VECTOR2I;
let reverse = false;
if (closer_to_first(aPrevPt.value, aShape.GetStart(), aShape.GetEnd())) {
nextPt = aShape.GetEnd();
} else {
nextPt = aShape.GetStart();
reverse = true;
}
aShape.RebuildBezierToSegmentsPointsList(aErrorMax);
if (reverse) {
for (let jj = aShape.GetBezierPoints().length - 1; jj >= 0; jj--) {
const pt = aShape.GetBezierPoints()[jj]!;
if (equal(aPrevPt.value, pt)) continue;
aContour.Append(pt);
aShapeOwners.set(ownerKey(aPrevPt.value, pt), aShape);
aPrevPt.value = pt;
}
} else {
for (const pt of aShape.GetBezierPoints()) {
if (equal(aPrevPt.value, pt)) continue;
aContour.Append(pt);
aShapeOwners.set(ownerKey(aPrevPt.value, pt), aShape);
aPrevPt.value = pt;
}
}
aPrevPt.value = nextPt;
break;
}
default:
break;
}
}
function buildContourHierarchy(aContours: readonly SHAPE_LINE_CHAIN[]): Map<number, number[]> {
const contourToParentIndexesMap = new Map<number, number[]>();
for (let ii = 0; ii < aContours.length; ++ii) {
if (aContours[ii]!.PointCount() < 1)
// malformed/empty SHAPE_LINE_CHAIN
continue;
const firstPt = aContours[ii]!.GetPoint(0);
const parents: number[] = [];
for (let jj = 0; jj < aContours.length; ++jj) {
if (jj === ii) continue;
const parentCandidate = aContours[jj]!;
if (parentCandidate.PointInside(firstPt, 0, true)) parents.push(jj);
}
contourToParentIndexesMap.set(ii, parents);
}
return contourToParentIndexesMap;
}
function addOutlinesToPolygon(
aContours: readonly SHAPE_LINE_CHAIN[],
aContourHierarchy: Map<number, number[]>,
aPolygons: SHAPE_POLY_SET,
aAllowDisjoint: boolean,
aErrorHandler: OUTLINE_ERROR_HANDLER | null,
aFetchOwner: (aSeg: SEG) => PCB_SHAPE | null,
aContourToOutlineIdxMap: Map<number, number>,
): boolean {
for (const [contourIndex, parentIndexes] of aContourHierarchy) {
if (parentIndexes.length % 2 === 0) {
// Even number of parents; top-level outline
if (!aAllowDisjoint && !aPolygons.IsEmpty()) {
if (aErrorHandler) {
const a = aFetchOwner(aPolygons.Outline(0).GetSegment(0));
const b = aFetchOwner(aContours[contourIndex]!.GetSegment(0));
if (a && b) {
aErrorHandler(
'(multiple board outlines not supported)',
a,
b,
aContours[contourIndex]!.GetPoint(0),
);
return false;
}
}
}
aPolygons.AddOutline(aContours[contourIndex]!);
aContourToOutlineIdxMap.set(contourIndex, aPolygons.OutlineCount() - 1);
}
}
return true;
}
function addHolesToPolygon(
aContours: readonly SHAPE_LINE_CHAIN[],
aContourHierarchy: Map<number, number[]>,
aContourToOutlineIdxMap: Map<number, number>,
aPolygons: SHAPE_POLY_SET,
aAllowUseArcsInPolygons: boolean,
aHasMalformedOverlap: boolean,
): void {
if (aAllowUseArcsInPolygons || !aHasMalformedOverlap) {
for (const [contourIndex, parentIndexes] of aContourHierarchy) {
if (parentIndexes.length % 2 === 1) {
// Odd number of parents; we're a hole in the parent which has one fewer parents
const hole = aContours[contourIndex]!;
for (const parentContourIdx of parentIndexes) {
if (aContourHierarchy.get(parentContourIdx)!.length === parentIndexes.length - 1) {
const outlineIdx = aContourToOutlineIdxMap.get(parentContourIdx)!;
aPolygons.AddHole(hole, outlineIdx);
break;
}
}
}
}
return;
}
// Malformed overlapping contours in the polygonized path.
const cutoutCandidates = new SHAPE_POLY_SET();
const islandCandidates = new SHAPE_POLY_SET();
for (const [contourIndex, parentIndexes] of aContourHierarchy) {
if (parentIndexes.length === 0) continue;
if (parentIndexes.length % 2 === 1) cutoutCandidates.AddOutline(aContours[contourIndex]!);
else islandCandidates.AddOutline(aContours[contourIndex]!);
}
if (cutoutCandidates.OutlineCount()) {
cutoutCandidates.Simplify();
aPolygons.BooleanSubtract(cutoutCandidates);
}
if (islandCandidates.OutlineCount()) {
islandCandidates.Simplify();
aPolygons.BooleanAdd(islandCandidates);
}
}
function checkSelfIntersections(
aPolygons: SHAPE_POLY_SET,
aErrorHandler: OUTLINE_ERROR_HANDLER | null,
aFetchOwner: (aSeg: SEG) => PCB_SHAPE | null,
): boolean {
let selfIntersecting = false;
const segments: SEG[] = [];
for (const seg of aPolygons.IterateSegmentsWithHoles()) {
const segment = new SEG(seg);
if (LexicographicalCompare(segment.A, segment.B) > 0)
[segment.A, segment.B] = [segment.B, segment.A];
segments.push(segment);
}
segments.sort((a, b) => {
if (!equal(a.A, b.A)) return LexicographicalCompare(a.A, b.A);
return LexicographicalCompare(a.B, b.B);
});
for (let i = 0; i < segments.length; ++i) {
const seg1 = segments[i]!;
for (let j = i + 1; j < segments.length; ++j) {
const seg2 = segments[j]!;
// VECTOR2::operator>: lexicographical on x then y
if (LexicographicalCompare(seg2.A, seg1.B) > 0) break;
if (
(equal(seg1.A, seg2.A) && equal(seg1.B, seg2.B)) ||
(equal(seg1.A, seg2.B) && equal(seg1.B, seg2.A))
) {
if (aErrorHandler) {
const a = aFetchOwner(seg1);
const b = aFetchOwner(seg2);
aErrorHandler('(self-intersecting)', a, b, seg1.A);
}
selfIntersecting = true;
} else {
const pt = seg1.Intersect(seg2, true);
if (pt) {
if (aErrorHandler) {
const a = aFetchOwner(seg1);
const b = aFetchOwner(seg2);
aErrorHandler('(self-intersecting)', a, b, pt);
}
selfIntersecting = true;
}
}
}
}
return !selfIntersecting;
}
// Helper function to find next shape using KD-tree
function findNext(
aShape: PCB_SHAPE,
aPoint: VECTOR2I,
adaptor: PCB_SHAPE_ENDPOINTS_ADAPTOR,
aChainingEpsilon: number,
): PCB_SHAPE | null {
const { indices, distances } = nearestTwoEndpoints(adaptor, aPoint);
if (distances[0] === Number.MAX_VALUE) return null;
// Find the closest valid candidate
let closest_graphic: PCB_SHAPE | null = null;
let closest_dist_sq = aChainingEpsilon * aChainingEpsilon;
for (let i = 0; i < 2; ++i) {
if (distances[i] === Number.MAX_VALUE) continue;
const candidate = adaptor.endpoints[indices[i]!]![1];
if (candidate === aShape) continue;
if (distances[i]! < closest_dist_sq) {
closest_dist_sq = distances[i]!;
closest_graphic = candidate;
}
}
return closest_graphic;
}
function hasOverlappingClosedContours(aContours: readonly SHAPE_LINE_CHAIN[]): boolean {
for (let ii = 0; ii < aContours.length; ++ii) {
for (let jj = ii + 1; jj < aContours.length; ++jj) {
const intersections: INTERSECTIONS = [];
if (aContours[ii]!.Intersect(aContours[jj]!, intersections, true) !== 0) return true;
}
}
return false;
}
// Walk a chain of open shapes (segments/arcs/beziers) starting from aStart, and produce a
// closed SHAPE_LINE_CHAIN if the chain forms a closed loop. Shapes that are consumed are
// removed from aRemaining. Returns true and populates aContour and aOwnerShape only if a
// closed contour is produced. Used to detect cross-contour intersections of bezier-bounded
// slots which would otherwise be missed by the closed-shape-only intersection test.
export function buildChainedClosedContour(
aStart: PCB_SHAPE,
aRemaining: Set<PCB_SHAPE>,
aAdaptor: PCB_SHAPE_ENDPOINTS_ADAPTOR,
aErrorMax: number,
aChainingEpsilon: number,
aContour: SHAPE_LINE_CHAIN,
aOwnerShape: { value: PCB_SHAPE | null },
): boolean {
const chain: PCB_SHAPE[] = [];
chain.push(aStart);
let closed = false;
let frontPt = aStart.GetStart();
let backPt = aStart.GetEnd();
const visited = new Set<PCB_SHAPE>();
visited.add(aStart);
const extendChain = (forward: boolean): void => {
let curr = forward ? chain[chain.length - 1]! : chain[0]!;
let prev = forward ? backPt : frontPt;
for (;;) {
let next = findNext(curr, prev, aAdaptor, aChainingEpsilon);
// The KD-tree spans the original openShapes set, so it still returns shapes
// already consumed by an earlier chain. Filter against aRemaining to avoid
// accidentally absorbing those into this chain.
if (next && !aRemaining.has(next)) next = null;
if (next && !visited.has(next)) {
visited.add(next);
if (forward) chain.push(next);
else chain.unshift(next);
if (closer_to_first(prev, next.GetStart(), next.GetEnd())) prev = next.GetEnd();
else prev = next.GetStart();
curr = next;
continue;
}
if (next) {
const chainEnd = forward ? chain[0]! : chain[chain.length - 1]!;
const chainPt = forward ? frontPt : backPt;
if (next === chainEnd && close_enough(prev, chainPt, aChainingEpsilon)) closed = true;
}
if (forward) backPt = prev;
else frontPt = prev;
break;
}
};
extendChain(true);
if (!closed) extendChain(false);
if (!closed) return false;
// Build the contour from the closed chain, mirroring doConvertOutlineToPolygon().
const shapeOwners: SHAPE_OWNERS = new Map();
const first = chain[0]!;
let startPt: VECTOR2I;
if (chain.length > 1) {
const second = chain[1]!;
if (
close_enough(first.GetStart(), second.GetStart(), aChainingEpsilon) ||
close_enough(first.GetStart(), second.GetEnd(), aChainingEpsilon)
)
startPt = first.GetEnd();
else startPt = first.GetStart();
} else {
startPt = first.GetStart();
}
aContour.Clear();
aContour.Append(startPt);
const prevPt = { value: startPt };
for (const shapeInChain of chain)
processShapeSegment(
shapeInChain,
aContour,
prevPt,
shapeOwners,
aErrorMax,
aChainingEpsilon,
false,
);
if (aContour.PointCount() < 3) return false;
if (!equal(aContour.CPoint(0), aContour.CLastPoint())) aContour.SetPoint(-1, aContour.CPoint(0));
aContour.SetClosed(true);
for (const consumed of chain) aRemaining.delete(consumed);
aOwnerShape.value = first;
return true;
}
export function doConvertOutlineToPolygon(
aShapeList: PCB_SHAPE[],
aPolygons: SHAPE_POLY_SET,
aErrorMax: number,
aChainingEpsilon: number,
aAllowDisjoint: boolean,
aErrorHandler: OUTLINE_ERROR_HANDLER | null,
aAllowUseArcsInPolygons: boolean,
aCleaner: SCOPED_FLAGS_CLEANER,
): boolean {
if (aShapeList.length === 0) return true;
let selfIntersecting = false;
let graphic: PCB_SHAPE | null = null;
// std::set<PCB_SHAPE*>: pointer order; insertion order here
const startCandidates = new Set<PCB_SHAPE>(aShapeList);
// Pre-build KD-tree
const adaptor = new PCB_SHAPE_ENDPOINTS_ADAPTOR(aShapeList);
// Keep a list of where the various shapes came from
const shapeOwners: SHAPE_OWNERS = new Map();
const fetchOwner = (seg: SEG): PCB_SHAPE | null => {
return shapeOwners.get(ownerKey(seg.A, seg.B)) ?? null;
};
const reportedGaps = new Set<string>();
const shapeIndex = new Map<PCB_SHAPE, number>();
aShapeList.forEach((s, i) => shapeIndex.set(s, i));
const contours: SHAPE_LINE_CHAIN[] = [];
for (const shape of startCandidates) shape.ClearFlags(SKIP_STRUCT);
// Process each shape to build contours
while (startCandidates.size) {
graphic = startCandidates.values().next().value!;
graphic.SetFlags(SKIP_STRUCT);
aCleaner.add(graphic);
startCandidates.delete(graphic);
const currContour = new SHAPE_LINE_CHAIN();
contours.push(currContour);
currContour.SetWidth(graphic.GetWidth());
// Handle closed shapes (circles, rects, polygons)
if (
graphic.GetShape() === SHAPE_T.POLY ||
graphic.GetShape() === SHAPE_T.CIRCLE ||
graphic.GetShape() === SHAPE_T.RECTANGLE
) {
processClosedShape(graphic, currContour, shapeOwners, aErrorMax, aAllowUseArcsInPolygons);
} else {
// Build chains for open shapes
const chain: PCB_SHAPE[] = [];
chain.push(graphic);
let closed = false;
let frontPt = graphic.GetStart();
let backPt = graphic.GetEnd();
const extendChain = (forward: boolean): void => {
let curr = forward ? chain[chain.length - 1]! : chain[0]!;
let prev = forward ? backPt : frontPt;
for (;;) {
const next = findNext(curr, prev, adaptor, aChainingEpsilon);
if (next && !(next.GetFlags() & SKIP_STRUCT)) {
next.SetFlags(SKIP_STRUCT);
aCleaner.add(next);
startCandidates.delete(next);
if (forward) chain.push(next);
else chain.unshift(next);
if (closer_to_first(prev, next.GetStart(), next.GetEnd())) prev = next.GetEnd();
else prev = next.GetStart();
curr = next;
continue;
}
if (next) {
const chainEnd = forward ? chain[0]! : chain[chain.length - 1]!;
const chainPt = forward ? frontPt : backPt;
if (next === chainEnd && close_enough(prev, chainPt, aChainingEpsilon)) {
closed = true;
} else {
if (aErrorHandler) aErrorHandler('(self-intersecting)', curr, next, prev);
selfIntersecting = true;
}
}
if (forward) backPt = prev;
else frontPt = prev;
break;
}
};
extendChain(true);
if (!closed) extendChain(false);
// Process the chain to build the contour
const first = chain[0]!;
let startPt: VECTOR2I;
if (chain.length > 1) {
const second = chain[1]!;
if (
close_enough(first.GetStart(), second.GetStart(), aChainingEpsilon) ||
close_enough(first.GetStart(), second.GetEnd(), aChainingEpsilon)
)
startPt = first.GetEnd();
else startPt = first.GetStart();
} else {
startPt = first.GetStart();
}
currContour.Append(startPt);
const prevPt = { value: startPt };
for (const shapeInChain of chain) {
processShapeSegment(
shapeInChain,
currContour,
prevPt,
shapeOwners,
aErrorMax,
aChainingEpsilon,
aAllowUseArcsInPolygons,
);
}
// Handle contour closure
if (close_enough(currContour.CPoint(0), currContour.CLastPoint(), aChainingEpsilon)) {
if (
!equal(currContour.CPoint(0), currContour.CLastPoint()) &&
currContour.PointCount() > 2
) {
const owner = fetchOwner(currContour.CSegment(-1));
if (currContour.IsArcEnd(currContour.PointCount() - 1)) {
const arc = currContour.Arc(currContour.ArcIndex(currContour.PointCount() - 1));
const sarc = new SHAPE_ARC(arc.GetP0(), arc.GetArcMid(), currContour.CPoint(0), 0);
const arcChain = new SHAPE_LINE_CHAIN();
arcChain.Append(sarc, aErrorMax);
if (!aAllowUseArcsInPolygons) arcChain.ClearArcs();
for (let ii = 1; ii < arcChain.PointCount(); ++ii) {
if (owner)
shapeOwners.set(ownerKey(arcChain.CPoint(ii - 1), arcChain.CPoint(ii)), owner);
else shapeOwners.delete(ownerKey(arcChain.CPoint(ii - 1), arcChain.CPoint(ii)));
}
currContour.RemoveShape(currContour.PointCount() - 1);
currContour.Append(arcChain);
} else {
currContour.SetPoint(-1, currContour.CPoint(0));
const key = ownerKey(
currContour.CPoints()[currContour.PointCount() - 2]!,
currContour.CLastPoint(),
);
if (owner) shapeOwners.set(key, owner);
else shapeOwners.delete(key);
}
}
currContour.SetClosed(true);
} else {
const report_gap = (pt: VECTOR2I): void => {
if (!aErrorHandler) return;
// Find the two closest items to the given point using kdtree
const { indices } = nearestTwoEndpoints(adaptor, pt);
const shapeA = adaptor.endpoints[indices[0]!]![1];
const shapeB = adaptor.endpoints[indices[1]!]![1];
// Avoid reporting the same pair twice
const ia = shapeIndex.get(shapeA)!;
const ib = shapeIndex.get(shapeB)!;
const key = `${Math.min(ia, ib)}:${Math.max(ia, ib)}`;
if (reportedGaps.has(key)) return;
reportedGaps.add(key);
// Find the nearest points between the two shapes and calculate midpoint
const effectiveShapeA = shapeA.GetEffectiveShape();
const effectiveShapeB = shapeB.GetEffectiveShape();
const ptA: VECTOR2I = { x: 0, y: 0 };
const ptB: VECTOR2I = { x: 0, y: 0 };
let midpoint = pt; // fallback to original point
if (
effectiveShapeA &&
effectiveShapeB &&
effectiveShapeA.NearestPoints(effectiveShapeB, ptA, ptB)
) {
midpoint = { x: Math.trunc((ptA.x + ptB.x) / 2), y: Math.trunc((ptA.y + ptB.y) / 2) };
}
aErrorHandler('(not a closed shape)', shapeA, shapeB, midpoint);
};
report_gap(currContour.CPoint(0));
report_gap(currContour.CLastPoint());
}
}
}
// Ensure all contours are closed
for (const contour of contours) {
if (!contour.IsClosed()) return false;
}
// Generate bounding boxes for hierarchy calculations
for (let ii = 0; ii < contours.length; ++ii) {
const contour = contours[ii]!;
if (!contour.GetCachedBBox().IsValid()) contour.GenerateBBoxCache();
}
// Build contour hierarchy
const contourHierarchy = buildContourHierarchy(contours);
const hasMalformedOverlap = !aAllowUseArcsInPolygons && hasOverlappingClosedContours(contours);
// Add outlines to polygon set
const contourToOutlineIdxMap = new Map<number, number>();
if (
!addOutlinesToPolygon(
contours,
contourHierarchy,
aPolygons,
aAllowDisjoint,
aErrorHandler,
fetchOwner,
contourToOutlineIdxMap,
)
) {
return false;
}
// Add holes to polygon set
addHolesToPolygon(
contours,
contourHierarchy,
contourToOutlineIdxMap,
aPolygons,
aAllowUseArcsInPolygons,
hasMalformedOverlap,
);
// Check for self-intersections
// (`selfIntersecting` is set above but does not reach the return in the C++ either)
void selfIntersecting;
return checkSelfIntersections(aPolygons, aErrorHandler, fetchOwner);
}
/**
* Build a polygon set with holes from a #PCB_SHAPE list.
*
* The shape list is expected to be one or more top-level closed outlines with zero or more
* holes in each. Optionally, it can be limited to a single top-level closed outline.
*
* @param aShapeList the initial list of drawsegments (only lines, circles and arcs).
* @param aPolygons will contain the complex polygon.
* @param aErrorMax is the max error distance when polygonizing a curve (internal units).
* @param aChainingEpsilon is the max distance from one endPt to the next startPt (internal units).
* @param aAllowDisjoint indicates multiple top-level outlines are allowed.
* @param aErrorHandler is an optional error handler.
* @param aAllowUseArcsInPolygons is an option to allow adding arcs in #SHAPE_LINE_CHAIN
* polylines/polygons when building outlines from aShapeList
* This is mainly for export to STEP files.
* @return true if success, false if a contour is not valid (self intersecting).
*/
export function ConvertOutlineToPolygon(
aShapeList: PCB_SHAPE[],
aPolygons: SHAPE_POLY_SET,
aErrorMax: number,
aChainingEpsilon: number,
aAllowDisjoint: boolean,
aErrorHandler: OUTLINE_ERROR_HANDLER | null,
aAllowUseArcsInPolygons = false,
): boolean {
const cleaner = new SCOPED_FLAGS_CLEANER(SKIP_STRUCT);
try {
return doConvertOutlineToPolygon(
aShapeList,
aPolygons,
aErrorMax,
aChainingEpsilon,
aAllowDisjoint,
aErrorHandler,
aAllowUseArcsInPolygons,
cleaner,
);
} finally {
cleaner.dispose();
}
}
function isCopperOutside(aFootprint: FOOTPRINT, aShape: SHAPE_POLY_SET): boolean {
let padOutside = false;
for (const pad of aFootprint.Pads()) {
pad.Padstack().ForEachUniqueLayer((aLayer: PCB_LAYER_ID) => {
const poly = aShape.CloneDropTriangulation();
poly.ClearArcs();
poly.BooleanIntersection(pad.GetEffectivePolygon(aLayer, ERROR_LOC.ERROR_INSIDE));
if (poly.OutlineCount() === 0) {
padOutside = true;
}
});
if (padOutside) break;
}
return padOutside;
}
/**
* Check a board outline is valid.
*
* Every shape must be a closed contour or joined to the next with a gap at
* most aMinDist, and no closed contour may cross another.
*/
export function TestBoardOutlinesGraphicItems(
aBoard: BOARD,
aMinDist: number,
aErrorHandler: OUTLINE_ERROR_HANDLER | null,
): boolean {
let success = true;
const items = new PCB_TYPE_COLLECTOR();
const min_dist = Math.max(0, aMinDist);
// Get all the shapes into 'items', then keep only those on layer == Edge_Cuts.
items.Collect(aBoard, [KICAD_T.PCB_SHAPE_T]);
const shapeList: PCB_SHAPE[] = [];
for (let ii = 0; ii < items.GetCount(); ii++) {
const seg = items.at(ii) as PCB_SHAPE;
if (seg.GetLayer() === PCB_LAYER_ID.Edge_Cuts) shapeList.push(seg);
}
// Now Test validity of collected items
for (const shape of shapeList) {
switch (shape.GetShape()) {
case SHAPE_T.RECTANGLE: {
const seg = sub(shape.GetEnd(), shape.GetStart());
const dim = EuclideanNormI(seg);
if (dim <= min_dist) {
success = false;
if (aErrorHandler) {
aErrorHandler(
`(rectangle has null or very small size: ${dim} nm)`,
shape,
null,
shape.GetStart(),
);
}
}
break;
}
case SHAPE_T.CIRCLE: {
const r = shape.GetRadius();
if (r <= min_dist) {
success = false;
if (aErrorHandler) {
aErrorHandler(
`(circle has null or very small radius: ${r} nm)`,
shape,
null,
shape.GetStart(),
);
}
}
break;
}
case SHAPE_T.SEGMENT: {
const seg = sub(shape.GetEnd(), shape.GetStart());
const dim = EuclideanNormI(seg);
if (dim <= min_dist) {
success = false;
if (aErrorHandler) {
aErrorHandler(
`(segment has null or very small length: ${dim} nm)`,
shape,
null,
shape.GetStart(),
);
}
}
break;
}
case SHAPE_T.ARC: {
// Arc size can be evaluated from the distance between arc middle point and arc ends
// We do not need a precise value, just an idea of its size
const arcMiddle = shape.GetArcMid();
const seg1 = sub(arcMiddle, shape.GetStart());
const seg2 = sub(shape.GetEnd(), arcMiddle);
const dim = EuclideanNormI(seg1) + EuclideanNormI(seg2);
if (dim <= min_dist) {
success = false;
if (aErrorHandler) {
aErrorHandler(
`(arc has null or very small size: ${dim} nm)`,
shape,
null,
shape.GetStart(),
);
}
}
break;
}
case SHAPE_T.POLY:
break;
case SHAPE_T.BEZIER:
break;
default:
throw new Error(`UNIMPLEMENTED_FOR( ${shape.SHAPE_T_asString()} )`);
}
}
const closedContours: [PCB_SHAPE, SHAPE_LINE_CHAIN][] = [];
// std::set<PCB_SHAPE*>: pointer order; insertion order stands in for it
const openShapes = new Set<PCB_SHAPE>();
for (const shape of shapeList) {
if (
shape.GetShape() === SHAPE_T.POLY ||
shape.GetShape() === SHAPE_T.CIRCLE ||
shape.GetShape() === SHAPE_T.RECTANGLE
) {
const contour = new SHAPE_LINE_CHAIN();
const shapeOwners: SHAPE_OWNERS = new Map();
processClosedShape(shape, contour, shapeOwners, shape.GetMaxError(), true);
closedContours.push([shape, contour]);
} else if (
shape.GetShape() === SHAPE_T.SEGMENT ||
shape.GetShape() === SHAPE_T.ARC ||
shape.GetShape() === SHAPE_T.BEZIER
) {
openShapes.add(shape);
}
}
// Gather closed contours from chained open shapes (slots formed by segments/arcs/beziers).
// Without this, malformed-outline detection misses overlaps involving such slots.
if (openShapes.size > 0) {
const openShapeList = [...openShapes];
const adaptor = new PCB_SHAPE_ENDPOINTS_ADAPTOR(openShapeList);
const chainingEpsilon = aBoard.GetOutlinesChainingEpsilon();
const maxError = aBoard.GetDesignSettings().m_MaxError;
while (openShapes.size > 0) {
const start = openShapes.values().next().value as PCB_SHAPE;
const contour = new SHAPE_LINE_CHAIN();
const owner: { value: PCB_SHAPE | null } = { value: null };
if (
buildChainedClosedContour(
start,
openShapes,
adaptor,
maxError,
chainingEpsilon,
contour,
owner,
)
) {
closedContours.push([owner.value!, contour]);
} else {
openShapes.delete(start);
}
}
}
for (let ii = 0; ii < closedContours.length; ++ii) {
const contourA = closedContours[ii]![1];
for (let jj = ii + 1; jj < closedContours.length; ++jj) {
const contourB = closedContours[jj]![1];
const intersections: INTERSECTIONS = [];
// Ignore touching-only cases; report only real overlap/crossing.
if (contourA.Intersect(contourB, intersections, true) === 0) continue;
success = false;
if (aErrorHandler) {
const shapeA = closedContours[ii]![0];
const shapeB = closedContours[jj]![0];
let midpoint = intersections[0]!.p;
const effectiveShapeA = shapeA.GetEffectiveShape();
const effectiveShapeB = shapeB.GetEffectiveShape();
if (effectiveShapeA && effectiveShapeB) {
const bboxA = effectiveShapeA.BBox();
const bboxB = effectiveShapeB.BBox();
const overlapBox = bboxA.Intersect(bboxB);
if (overlapBox.GetWidth() > 0 && overlapBox.GetHeight() > 0)
midpoint = overlapBox.Centre();
}
aErrorHandler('(self-intersecting)', shapeA, shapeB, midpoint);
}
}
}
return success;
}
/**
* Extract the board outlines and build a closed polygon from lines, arcs and circle items
* on edge cut layer.
*
* Any closed outline inside the main outline is a hole. All contours should be closed,
* i.e. have valid vertices to build a closed polygon.
*
* @param aBoard is the board to build outlines from.
* @param aOutlines is the SHAPE_POLY_SET to fill in with outlines/holes.
* @param aErrorMax is the max error distance when polygonizing a curve (internal units).
* @param aChainingEpsilon is the max distance from one endPt to the next startPt (internal units).
* @param aInferOutlineIfNecessary is true to build a rectangle outline from the board or
* items bounding box when no valid outline is found.
* @param aErrorHandler is an optional error handler.
* @param aAllowUseArcsInPolygons is an option to allow adding arcs in SHAPE_LINE_CHAIN
* polylines/polygons when building outlines from aShapeList
* This is mainly for export to STEP files.
* @return true if success, false if a contour is not valid (self intersecting).
*/
export function BuildBoardPolygonOutlines(
aBoard: BOARD,
aOutlines: SHAPE_POLY_SET,
aErrorMax: number,
aChainingEpsilon: number,
aInferOutlineIfNecessary: boolean,
aErrorHandler: OUTLINE_ERROR_HANDLER | null,
aAllowUseArcsInPolygons: boolean,
): boolean {
const items = new PCB_TYPE_COLLECTOR();
const fpHoles = new SHAPE_POLY_SET();
let success = false;
const cleaner = new SCOPED_FLAGS_CLEANER(SKIP_STRUCT);
try {
// Get all the shapes into 'items', then keep only those on layer == Edge_Cuts.
items.Collect(aBoard, [KICAD_T.PCB_SHAPE_T]);
for (let ii = 0; ii < items.GetCount(); ++ii) items.at(ii)!.ClearFlags(SKIP_STRUCT);
for (const fp of aBoard.Footprints()) {
const fpItems = new PCB_TYPE_COLLECTOR();
fpItems.Collect(fp, [KICAD_T.PCB_SHAPE_T]);
const fpSegList: PCB_SHAPE[] = [];
for (let ii = 0; ii < fpItems.GetCount(); ii++) {
const fpSeg = fpItems.at(ii) as PCB_SHAPE;
if (fpSeg.GetLayer() === PCB_LAYER_ID.Edge_Cuts) fpSegList.push(fpSeg);
}
if (fpSegList.length > 0) {
const fpOutlines = new SHAPE_POLY_SET();
success = doConvertOutlineToPolygon(
fpSegList,
fpOutlines,
aErrorMax,
aChainingEpsilon,
false,
null, // don't report errors here; the second pass also
// gets an opportunity to use these segments
aAllowUseArcsInPolygons,
cleaner,
);
// Test to see if we should make holes or outlines. Holes are made if the footprint
// has copper outside of a single, closed outline. If there are multiple outlines,
// we assume that the footprint edges represent holes as we do not support multiple
// boards. Similarly, if any of the footprint pads are located outside of the edges,
// then the edges are holes
if (success && (isCopperOutside(fp, fpOutlines) || fpOutlines.OutlineCount() > 1)) {
fpHoles.Append(fpOutlines);
} else {
// If it wasn't a closed area, or wasn't a hole, the we want to keep the fpSegs
// in contention for the board outline builds.
for (let ii = 0; ii < fpItems.GetCount(); ++ii) fpItems.at(ii)!.ClearFlags(SKIP_STRUCT);
}
}
}
// Make a working copy of aSegList, because the list is modified during calculations
const segList: PCB_SHAPE[] = [];
for (let ii = 0; ii < items.GetCount(); ii++) {
const seg = items.at(ii) as PCB_SHAPE;
// Skip anything already used to generate footprint holes (above)
if (seg.GetFlags() & SKIP_STRUCT) continue;
if (seg.GetLayer() === PCB_LAYER_ID.Edge_Cuts) segList.push(seg);
}
if (segList.length) {
success = doConvertOutlineToPolygon(
segList,
aOutlines,
aErrorMax,
aChainingEpsilon,
true,
aErrorHandler,
aAllowUseArcsInPolygons,
cleaner,
);
}
if ((!success || !aOutlines.OutlineCount()) && aInferOutlineIfNecessary) {
// Couldn't create a valid polygon outline. Use the board edge cuts bounding box to
// create a rectangular outline, or, failing that, the bounding box of the items on
// the board.
let bbbox = aBoard.GetBoardEdgesBoundingBox();
// If null area, uses the global bounding box.
if (bbbox.GetWidth() === 0 || bbbox.GetHeight() === 0)
bbbox = aBoard.ComputeBoundingBox(false, true);
// Ensure non null area. If happen, gives a minimal size.
if (bbbox.GetWidth() === 0 || bbbox.GetHeight() === 0) bbbox.Inflate(pcbIUScale.mmToIU(1.0));
aOutlines.RemoveAllContours();
aOutlines.NewOutline();
aOutlines.Append(bbbox.GetOrigin());
aOutlines.Append({ x: bbbox.GetOrigin().x, y: bbbox.GetEnd().y });
aOutlines.Append(bbbox.GetEnd());
aOutlines.Append({ x: bbbox.GetEnd().x, y: bbbox.GetOrigin().y });
}
if (aAllowUseArcsInPolygons) {
for (let ii = 0; ii < fpHoles.OutlineCount(); ++ii) {
const holePt = fpHoles.Outline(ii).CPoint(0);
for (let jj = 0; jj < aOutlines.OutlineCount(); ++jj) {
if (aOutlines.Outline(jj).PointInside(holePt)) {
aOutlines.AddHole(fpHoles.Outline(ii), jj);
break;
}
}
}
} else {
fpHoles.Simplify();
aOutlines.BooleanSubtract(fpHoles);
}
return success;
} finally {
cleaner.dispose();
}
}
/**
* Get the complete bounding box of the board (including all items).
*
* The vertex numbers and segment numbers of the rectangle returned.
* 1
* *---------------*
* |1 2|
* 0| |2
* |0 3|
* *---------------*
* 3
*/
export function buildBoardBoundingBoxPoly(aBoard: BOARD, aOutline: SHAPE_POLY_SET): void {
let bbbox = aBoard.GetBoundingBox();
const chain = new SHAPE_LINE_CHAIN();
// If null area, uses the global bounding box.
if (bbbox.GetWidth() === 0 || bbbox.GetHeight() === 0)
bbbox = aBoard.ComputeBoundingBox(false, true);
// Ensure non null area. If happen, gives a minimal size.
if (bbbox.GetWidth() === 0 || bbbox.GetHeight() === 0) bbbox.Inflate(pcbIUScale.mmToIU(1.0));
// Inflate slightly (by 1/10th the size of the box)
bbbox.Inflate(Math.trunc(bbbox.GetWidth() / 10), Math.trunc(bbbox.GetHeight() / 10));
chain.Append(bbbox.GetOrigin());
chain.Append(bbbox.GetOrigin().x, bbbox.GetEnd().y);
chain.Append(bbbox.GetEnd());
chain.Append(bbbox.GetEnd().x, bbbox.GetOrigin().y);
chain.SetClosed(true);
aOutline.RemoveAllContours();
aOutline.AddOutline(chain);
}
export function projectPointOnSegment(
aEndPoint: VECTOR2I,
aOutline: SHAPE_POLY_SET,
aOutlineNum = 0,
): VECTOR2I {
let minDistance = -1;
let projPoint: VECTOR2I = { x: 0, y: 0 };
for (const it = aOutline.CIterateSegments(aOutlineNum); it.valid(); it.Advance()) {
const seg = it.Get();
const dis = seg.Distance(aEndPoint);
if (minDistance < 0 || dis < minDistance) {
minDistance = dis;
projPoint = seg.NearestPoint(aEndPoint);
}
}
return projPoint;
}
export function findEndSegments(aChain: SHAPE_LINE_CHAIN, aEnds: { start: SEG; end: SEG }): number {
let foundSegs = 0;
for (let i = 0; i < aChain.SegmentCount(); i++) {
const seg = aChain.Segment(i);
let foundA = false;
let foundB = false;
for (let j = 0; j < aChain.SegmentCount(); j++) {
// Don't test the segment against itself
if (i === j) continue;
const testSeg = aChain.Segment(j);
if (testSeg.Contains(seg.A)) foundA = true;
if (testSeg.Contains(seg.B)) foundB = true;
}
// This segment isn't a start or end
if (foundA && foundB) continue;
if (foundSegs === 0) {
// The first segment we encounter is the "start" segment
aEnds.start = seg;
foundSegs++;
} else {
// Once we find both start and end, we can stop
aEnds.end = seg;
foundSegs++;
break;
}
}
return foundSegs;
}
/**
* Extract a board outline for a footprint view.
*/
export function BuildFootprintPolygonOutlines(
aBoard: BOARD,
aOutlines: SHAPE_POLY_SET,
aErrorMax: number,
aChainingEpsilon: number,
aErrorHandler: OUTLINE_ERROR_HANDLER | null,
): boolean {
const footprint = aBoard.GetFirstFootprint();
// No footprint loaded
if (!footprint) {
return false;
}
const items = new PCB_TYPE_COLLECTOR();
const outlines = new SHAPE_POLY_SET();
let success = false;
const cleaner = new SCOPED_FLAGS_CLEANER(SKIP_STRUCT);
try {
// Get all the SHAPEs into 'items', then keep only those on layer == Edge_Cuts.
items.Collect(aBoard, [KICAD_T.PCB_SHAPE_T]);
// Make a working copy of aSegList, because the list is modified during calculations
const segList: PCB_SHAPE[] = [];
for (let ii = 0; ii < items.GetCount(); ii++) {
if (items.at(ii)!.GetLayer() === PCB_LAYER_ID.Edge_Cuts)
segList.push(items.at(ii) as PCB_SHAPE);
}
if (segList.length > 0) {
success = doConvertOutlineToPolygon(
segList,
outlines,
aErrorMax,
aChainingEpsilon,
true,
aErrorHandler,
false,
cleaner,
);
}
// A closed outline was found on Edge_Cuts
if (success) {
// If copper is outside a closed polygon, treat it as a hole
// If there are multiple outlines in the footprint, they are also holes
if (isCopperOutside(footprint, outlines) || outlines.OutlineCount() > 1) {
buildBoardBoundingBoxPoly(aBoard, aOutlines);
// Copy all outlines from the conversion as holes into the new outline
for (let i = 0; i < outlines.OutlineCount(); i++) {
const out = outlines.Outline(i);
if (out.IsClosed()) aOutlines.AddHole(out, -1);
for (let j = 0; j < outlines.HoleCount(i); j++) {
const hole = outlines.Hole(i, j);
if (hole.IsClosed()) aOutlines.AddHole(hole, -1);
}
}
}
// If all copper is inside, then the computed outline is the board outline
else {
aOutlines.assign(outlines);
}
return true;
}
// No board outlines were found, so use the bounding box
if (outlines.OutlineCount() === 0) {
buildBoardBoundingBoxPoly(aBoard, aOutlines);
return true;
}
// There is an outline present, but it is not closed
const closedChains: SHAPE_LINE_CHAIN[] = [];
const openChains: SHAPE_LINE_CHAIN[] = [];
// The ConvertOutlineToPolygon function returns only one main outline and the rest as
// holes, so we promote the holes and process them
openChains.push(outlines.Outline(0));
for (let j = 0; j < outlines.HoleCount(0); j++) {
const hole = outlines.Hole(0, j);
if (hole.IsClosed()) {
closedChains.push(hole);
} else {
openChains.push(hole);
}
}
const bbox = new SHAPE_POLY_SET();
buildBoardBoundingBoxPoly(aBoard, bbox);
// Treat the open polys as the board edge
const chain = new SHAPE_LINE_CHAIN(openChains[0]!);
const rect = bbox.Outline(0);
// We know the outline chain is open, so set to non-closed to get better segment count
chain.SetClosed(false);
const ends = { start: new SEG(), end: new SEG() };
// The two possible board outlines
const upper = new SHAPE_LINE_CHAIN();
const lower = new SHAPE_LINE_CHAIN();
findEndSegments(chain, ends);
if (chain.SegmentCount() === 0) {
// Something is wrong, bail out with the overall footprint bounding box
aOutlines.assign(bbox);
return true;
}
if (chain.SegmentCount() === 1) {
// This case means there is only 1 line segment making up the edge cuts of the
// footprint, so we just need to use it to cut the bounding box in half.
const startSeg = chain.Segment(0);
// Intersect with all the sides of the rectangle
const inter0 = startSeg.IntersectLines(rect.Segment(0));
const inter1 = startSeg.IntersectLines(rect.Segment(1));
const inter2 = startSeg.IntersectLines(rect.Segment(2));
const inter3 = startSeg.IntersectLines(rect.Segment(3));
if (inter0 && inter2 && !inter1 && !inter3) {
// Intersects the vertical rectangle sides only
// The upper half
upper.Append(inter0);
upper.Append(rect.GetPoint(1));
upper.Append(rect.GetPoint(2));
upper.Append(inter2);
upper.SetClosed(true);
// The lower half
lower.Append(inter0);
lower.Append(rect.GetPoint(0));
lower.Append(rect.GetPoint(3));
lower.Append(inter2);
lower.SetClosed(true);
} else if (inter1 && inter3 && !inter0 && !inter2) {
// Intersects the horizontal rectangle sides only
// The left half
upper.Append(inter1);
upper.Append(rect.GetPoint(1));
upper.Append(rect.GetPoint(0));
upper.Append(inter3);
upper.SetClosed(true);
// The right half
lower.Append(inter1);
lower.Append(rect.GetPoint(2));
lower.Append(rect.GetPoint(3));
lower.Append(inter3);
lower.SetClosed(true);
} else {
// Angled line segment that cuts across a corner
// Figure out which actual lines are intersected, since IntersectLines assumes
// an infinite line
const hit0 = rect.Segment(0).Contains(inter0!);
const hit1 = rect.Segment(1).Contains(inter1!);
const hit2 = rect.Segment(2).Contains(inter2!);
const hit3 = rect.Segment(3).Contains(inter3!);
if (hit0 && hit1) {
// Cut across the upper left corner
// The upper half
upper.Append(inter0!);
upper.Append(rect.GetPoint(1));
upper.Append(inter1!);
upper.SetClosed(true);
// The lower half
lower.Append(inter0!);
lower.Append(rect.GetPoint(0));
lower.Append(rect.GetPoint(3));
lower.Append(rect.GetPoint(2));
lower.Append(inter1!);
lower.SetClosed(true);
} else if (hit1 && hit2) {
// Cut across the upper right corner
// The upper half
upper.Append(inter1!);
upper.Append(rect.GetPoint(2));
upper.Append(inter2!);
upper.SetClosed(true);
// The lower half
lower.Append(inter1!);
lower.Append(rect.GetPoint(1));
lower.Append(rect.GetPoint(0));
lower.Append(rect.GetPoint(3));
lower.Append(inter2!);
lower.SetClosed(true);
} else if (hit2 && hit3) {
// Cut across the lower right corner
// The upper half
upper.Append(inter2!);
upper.Append(rect.GetPoint(2));
upper.Append(rect.GetPoint(1));
upper.Append(rect.GetPoint(0));
upper.Append(inter3!);
upper.SetClosed(true);
// The bottom half
lower.Append(inter2!);
lower.Append(rect.GetPoint(3));
lower.Append(inter3!);
lower.SetClosed(true);
} else {
// Cut across the lower left corner
// The upper half
upper.Append(inter0!);
upper.Append(rect.GetPoint(1));
upper.Append(rect.GetPoint(2));
upper.Append(rect.GetPoint(3));
upper.Append(inter3!);
upper.SetClosed(true);
// The bottom half
lower.Append(inter0!);
lower.Append(rect.GetPoint(0));
lower.Append(inter3!);
lower.SetClosed(true);
}
}
} else {
// More than 1 segment
// Just a temporary thing
aOutlines.assign(bbox);
return true;
}
// Figure out which is the correct outline
const poly1 = new SHAPE_POLY_SET();
const poly2 = new SHAPE_POLY_SET();
// `Append( upper )` takes the SHAPE_LINE_CHAIN through SHAPE_POLY_SET's
// converting constructor: the chain lands as a second outline after the
// empty one NewOutline() made.
poly1.NewOutline();
poly1.Append(new SHAPE_POLY_SET(upper));
poly2.NewOutline();
poly2.Append(new SHAPE_POLY_SET(lower));
if (isCopperOutside(footprint, poly1)) {
aOutlines.assign(poly2);
} else {
aOutlines.assign(poly1);
}
// Add all closed polys as holes to the main outline
for (const closedChain of closedChains) {
aOutlines.AddHole(closedChain, -1);
}
return true;
} finally {
cleaner.dispose();
}
}