///|
priv struct ClearObject {
index : Int32
feature : GerberFeature
bounds : GerberBounds
}
///|
priv struct ClearanceBranch {
bounds : GerberBounds
latest : Int32
contents : ClearanceTree
}
///|
priv enum ClearanceTree {
Leaf(Array[ClearObject])
Children(ClearanceBranch, ClearanceBranch)
}
///|
fn center_axis(bounds : GerberBounds, by_x : Bool) -> Double {
if by_x {
bounds.lower.x * 0.5 + bounds.upper.x * 0.5
} else {
bounds.lower.y * 0.5 + bounds.upper.y * 0.5
}
}
///|
fn clearance_index(items : Array[ClearObject]) -> ClearanceBranch {
let mut bounds = items[0].bounds
let mut latest = 0
for item in items {
bounds = bounds.union(item.bounds)
latest = latest.max(item.index)
}
if items.length() <= 16 {
return { bounds, latest, contents: Leaf(items), }
}
let by_x = bounds.upper.x - bounds.lower.x >= bounds.upper.y - bounds.lower.y
items.sort_by((a, b) => {
let x = center_axis(a.bounds, by_x)
let y = center_axis(b.bounds, by_x)
if x < y {
-1
} else if x > y {
1
} else {
a.index.compare(b.index)
}
})
let mid = items.length() / 2
let left = clearance_index(items[:mid].to_owned())
let right = clearance_index(items[mid:].to_owned())
let contents = if left.latest >= right.latest {
Children(left, right)
} else {
Children(right, left)
}
{ bounds, latest, contents, }
}
///|
fn find_clearance(
branch : ClearanceBranch,
pad : GerberBounds,
center : Point,
radius : Double,
after : Int32,
best : ClearObject?,
) -> ClearObject? {
let minimum = match best {
Some(item) => item.index
None => after
}
if branch.latest <= minimum || !branch.bounds.overlaps(pad) {
return best
}
match branch.contents {
Leaf(items) => {
let mut found = best
let mut index = minimum
for item in items {
if item.index > index &&
item.bounds.overlaps(pad) &&
clear_may_cover(item.feature.kind, center, radius) {
index = item.index
found = Some(item)
}
}
found
}
Children(left, right) => {
let found = find_clearance(left, pad, center, radius, after, best)
find_clearance(right, pad, center, radius, after, found)
}
}
}