dymokomi/luce-cad
Source of release 0.9.3
0.9.3 / src / sketch / crossings.lucb
## Where curves cross: each place another curve crosses or touches a
## line, circle or arc (exactly for lines and circles, by sampling and
## bisection for splines, ellipses and conics), sorted along it, and the
## crossings around a place (Trim's and Break's pieces).
## Where curve `other` crosses (or touches) a curve: the place along it and
## the point.
struct Crossing:
var place: f64
var x: f64
var y: f64
var other: i64
## Every place other curves cross or touch curve `curve`, sorted.
func crossings(sketch: const Sketch*, curve: i64, out: Growing[Crossing]*) -> !:
for other in 0..<(i64)sketch.entities.count:
# Lines, circles, arcs, splines, ellipses and conics cut it.
# (Not the origin's axes: they are references, not curves to cut at.)
if other == curve or sketch.entity(other).kind == EntityKind.point or sketch.entity(other).kind == EntityKind.text or sketch.entity(other).origin != 0: continue
try meet(sketch, curve, other, false, out)
# Places sorted, near repeats once.
for i in 1..<out.count:
let v = out.items[i]
var j = i
while j > 0 and out.items[j - 1].place > v.place:
out.items[j] = out.items[j - 1]
j -= 1
out.items[j] = v
var kept: usize = 0
for at in 0..<out.count:
if kept > 0 and math.abs(out.items[at].place - out.items[kept - 1].place) <= 1e-9: continue
out.items[kept] = out.items[at]
kept += 1
out.count = kept
## Where curve `other` meets curve `curve` (as places along `curve`); with
## `beyond`, `curve` counts as running on past its ends (lines as lines,
## arcs round their circle), for Extend.
func meet(sketch: const Sketch*, curve: i64, other: i64, beyond: bool, out: Growing[Crossing]*) -> !:
let a = sketch.entity(curve)
let b = sketch.entity(other)
if is_sampled(a.kind) or a.kind == EntityKind.point or b.kind == EntityKind.point or b.kind == EntityKind.text: return
let size = size_of(sketch)
let tolerance = 1e-9 * size
var hits = Growing[f64]()
defer hits.close()
# Points (x, y) common to both carriers.
if is_free_form(b.kind):
try free_hits(sketch, curve, b, &hits)
elif a.kind == EntityKind.line and b.kind == EntityKind.line:
let (ax, ay, dx, dy) = line_of(sketch, a)
let (bx, by, ex, ey) = line_of(sketch, b)
let d = dx * ey - dy * ex
if math.abs(d) <= 1e-12 * math.hypot(dx, dy) * math.hypot(ex, ey): return
let t = ((bx - ax) * ey - (by - ay) * ex) / d
try hits.push(ax + t * dx)
try hits.push(ay + t * dy)
elif a.kind == EntityKind.line or b.kind == EntityKind.line:
let line = a if a.kind == EntityKind.line else b
let round = b if a.kind == EntityKind.line else a
let (sx, sy, dx, dy) = line_of(sketch, line)
let cx = sketch.x(round.first)
let cy = sketch.y(round.first)
let r = sketch.params.items[(usize)round.second]
let l2 = dx * dx + dy * dy
let fx = sx - cx
let fy = sy - cy
let half_b = fx * dx + fy * dy
let disc = half_b * half_b - l2 * (fx * fx + fy * fy - r * r)
if disc < -2.0 * r * tolerance * l2: return
let root = math.sqrt(math.max(0.0, disc))
for t in [(-half_b - root) / l2, (-half_b + root) / l2]:
try hits.push(sx + t * dx)
try hits.push(sy + t * dy)
if root == 0.0: break
else:
let c1x = sketch.x(a.first)
let c1y = sketch.y(a.first)
let c2x = sketch.x(b.first)
let c2y = sketch.y(b.first)
let r1 = sketch.params.items[(usize)a.second]
let r2 = sketch.params.items[(usize)b.second]
let d = math.hypot(c2x - c1x, c2y - c1y)
if d <= tolerance or d > r1 + r2 + tolerance or d < math.abs(r1 - r2) - tolerance: return
let along = (r1 * r1 - r2 * r2 + d * d) / (2.0 * d)
let h = math.sqrt(math.max(0.0, r1 * r1 - along * along))
let ux = (c2x - c1x) / d
let uy = (c2y - c1y) / d
for s in [-1.0, 1.0]:
try hits.push(c1x + along * ux - s * h * uy)
try hits.push(c1y + along * uy + s * h * ux)
if h == 0.0: break
var at: usize = 0
while at + 1 < hits.count:
let x = hits.items[at]
let y = hits.items[at + 1]
at += 2
# On `other` as it is, on `curve` (as far as it runs).
if not on_curve(sketch, other, x, y, tolerance * 1000.0, false): continue
if not on_curve(sketch, curve, x, y, tolerance * 1000.0, beyond): continue
try out.push(Crossing(place_of(sketch, curve, x, y), x, y, other))
## Where spline, ellipse or conic `b` crosses line, circle or arc
## `curve`'s carrier (the whole line or circle, so Extend's `beyond`
## holds), onto `hits` as x, y: its samples' sign changes against the
## carrier, each refined by bisection along it to the sketch's precision.
func free_hits(sketch: const Sketch*, curve: i64, b: SketchEntity, hits: Growing[f64]*) -> !:
var net = new_net()
defer net.close()
try net_of(sketch, b, &net)
let (low, high) = net.range()
let steps: usize = 256
var previous = side_at(sketch, curve, net.at(low))
for k in 1..<steps + 1:
let t1 = low + (high - low) * (f64)k / (f64)steps
let now = side_at(sketch, curve, net.at(t1))
if (previous < 0.0) != (now < 0.0) or now == 0.0:
var lo = t1 - (high - low) / (f64)steps
var hi = t1
let below = previous < 0.0
for i in 0..<(usize)60:
let middle = (lo + hi) * 0.5
if (side_at(sketch, curve, net.at(middle)) < 0.0) == below: lo = middle
else: hi = middle
let (x, y) = net.at((lo + hi) * 0.5)
try hits.push(x)
try hits.push(y)
previous = now
## Which side of line, circle or arc `curve`'s carrier point `at` is.
func side_at(sketch: const Sketch*, curve: i64, at: (f64, f64)) -> f64:
let (x, y) = at
return signed_side(sketch, curve, x, y)
## Whether (`x`, `y`) on its curve's carrier lies on curve `curve` itself
## (with `beyond`, anywhere on a line's line or an arc's circle).
func on_curve(sketch: const Sketch*, curve: i64, x: f64, y: f64, slack: f64, beyond: bool) -> bool:
let e = sketch.entity(curve)
# A free-form curve's hits come from its own samples: on it.
if e.kind == EntityKind.circle or beyond or is_free_form(e.kind): return true
let length = curve_length(sketch, curve)
let place = place_of(sketch, curve, x, y)
return place >= -slack / length and place <= 1.0 + slack / length
## The crossings just before and after place `here` (-1: none, the curve's
## own end).
func around(found: const Growing[Crossing]*, here: f64) -> (i64, i64):
var low: i64 = -1
var high: i64 = -1
for at in 0..<found.count:
let p = found.items[at].place
# Crossings at a curve's own ends are its ends.
if p <= 1e-9 or p >= 1.0 - 1e-9: continue
if p < here: low = (i64)at
elif high < 0: high = (i64)at
return (low, high)
## On a circle: the crossings before and after angle `here`, round.
func around_angle(found: const Growing[Crossing]*, here: f64) -> (usize, usize):
var after: usize = 0
var seen = false
for at in 0..<found.count:
if found.items[at].place > here and not seen:
after = at
seen = true
if not seen: after = 0
let before = (after + found.count - 1) % found.count
return (before, after)
# -- Edits.