Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-cad

Source of release 0.9.2

0.9.2 / src / sketch / geometry.lucb

## Geometry of a sketch's curves shared by its tools: a line's start and
## direction, unit vectors, lengths, which side of a curve a point is, the
## place along a curve and the point at a place, how far a point is from
## an entity and the entity nearest it (picking), points along any curve
## (sampling) and the place on a curve nearest a point.
##
## A place along a curve: a line's from 0 at its start to 1 at its end; an
## arc's the same along its sweep; a circle's an angle (radians).

## Whether entity kind `kind` is a spline, an ellipse or a conic (a NURBS:
## shapes.lucb), and whether it is known by its samples (those, and text).
pub func is_free_form(kind: EntityKind) -> bool:
    return kind == EntityKind.spline or kind == EntityKind.ellipse or kind == EntityKind.conic

pub func is_sampled(kind: EntityKind) -> bool:
    return is_free_form(kind) or kind == EntityKind.text

## A curve's start (`start`) or end point: a line's, an arc's, a spline's
## first or last, a conic's; -1 for a curve without ends (a circle, an
## ellipse, a text) or a point.
pub func end_point(sketch: const Sketch*, e: SketchEntity, start: bool) -> i64:
    if e.kind == EntityKind.line: return e.first if start else e.second
    if e.kind == EntityKind.arc: return e.third if start else e.fourth
    if e.kind == EntityKind.conic: return e.first if start else e.third
    if e.kind == EntityKind.spline: return sketch.spline_point(e, 0 if start else e.second - 1)
    return -1

## Arc `e`'s start angle and its counterclockwise sweep (0, 2π].
pub func arc_sweep(sketch: const Sketch*, e: SketchEntity) -> (f64, f64):
    let cx = sketch.x(e.first)
    let cy = sketch.y(e.first)
    let start = math.atan2(sketch.y(e.third) - cy, sketch.x(e.third) - cx)
    var sweep = math.atan2(sketch.y(e.fourth) - cy, sketch.x(e.fourth) - cx) - start
    while sweep <= 0.0: sweep += 2.0 * math.pi
    while sweep > 2.0 * math.pi: sweep -= 2.0 * math.pi
    return (start, sweep)

## A line's start and direction.
func line_of(sketch: const Sketch*, e: SketchEntity) -> (f64, f64, f64, f64):
    let ax = sketch.x(e.first)
    let ay = sketch.y(e.first)
    return (ax, ay, sketch.x(e.second) - ax, sketch.y(e.second) - ay)

func unit_vector(x: f64, y: f64) -> (f64, f64):
    let l = math.max(math.hypot(x, y), 1e-300)
    return (x / l, y / l)

## Point `point` scaled from `center` by `factor`.
func scaled_from(sketch: const Sketch*, center: i64, point: i64, factor: f64) -> (f64, f64):
    let cx = sketch.x(center)
    let cy = sketch.y(center)
    return (cx + (sketch.x(point) - cx) * factor, cy + (sketch.y(point) - cy) * factor)

## How long line, circle or arc `curve` is.
func curve_length(sketch: const Sketch*, curve: i64) -> f64:
    let e = sketch.entity(curve)
    if e.kind == EntityKind.line: return math.max(math.hypot(sketch.x(e.second) - sketch.x(e.first), sketch.y(e.second) - sketch.y(e.first)), 1e-300)
    if e.kind == EntityKind.circle: return math.max(sketch.radius_of(curve) * 2.0 * math.pi, 1e-300)
    let (_, sweep) = arc_sweep(sketch, e)
    return math.max(sketch.radius_of(curve) * sweep, 1e-300)

## How far left of curve `curve` (`x`, `y`) is (a line: of its direction;
## an arc or circle: outside it is positive).
func signed_side(sketch: const Sketch*, curve: i64, x: f64, y: f64) -> f64:
    let e = sketch.entity(curve)
    if e.kind == EntityKind.line:
        let (ax, ay, dx, dy) = line_of(sketch, e)
        return (dx * (y - ay) - dy * (x - ax)) / math.max(math.hypot(dx, dy), 1e-300)
    if is_sampled(e.kind):
        # Left (+) or right of the curve where it passes nearest.
        var samples = Growing[f64]()
        defer samples.close()
        sample_curve(sketch, e, 96, &samples) catch failure:
            return 1.0
        var best = 1e300
        var cross = 1.0
        for k in 0..<samples.count // 2 - 1:
            let (ax, ay, bx, by) = (samples.items[2 * k], samples.items[2 * k + 1], samples.items[2 * k + 2], samples.items[2 * k + 3])
            let d = segment_distance(x, y, ax, ay, bx, by)
            if d < best:
                best = d
                cross = (bx - ax) * (y - ay) - (by - ay) * (x - ax)
        return cross
    return math.hypot(x - sketch.x(e.first), y - sketch.y(e.first)) - sketch.radius_of(curve)

## The point at place `place` along line, circle or arc `curve`.
func at_place(sketch: const Sketch*, curve: i64, place: f64) -> (f64, f64):
    let e = sketch.entity(curve)
    if e.kind == EntityKind.line:
        let (ax, ay, dx, dy) = line_of(sketch, e)
        return (ax + dx * place, ay + dy * place)
    let cx = sketch.x(e.first)
    let cy = sketch.y(e.first)
    let r = sketch.radius_of(curve)
    var angle = place
    if e.kind == EntityKind.arc:
        let (start, sweep) = arc_sweep(sketch, e)
        angle = start + sweep * place
    return (cx + r * math.cos(angle), cy + r * math.sin(angle))

## The place along curve `curve` nearest (`x`, `y`) (not limited to the
## curve: a line's place can be below 0 or above 1, an arc's past its
## sweep counts round from its start).
func place_of(sketch: const Sketch*, curve: i64, x: f64, y: f64) -> f64:
    let e = sketch.entity(curve)
    if e.kind == EntityKind.line:
        let (ax, ay, dx, dy) = line_of(sketch, e)
        return ((x - ax) * dx + (y - ay) * dy) / math.max(dx * dx + dy * dy, 1e-300)
    let cx = sketch.x(e.first)
    let cy = sketch.y(e.first)
    let angle = math.atan2(y - cy, x - cx)
    if e.kind == EntityKind.circle:
        return angle if angle >= 0.0 else angle + 2.0 * math.pi
    let (start, sweep) = arc_sweep(sketch, e)
    var turn = angle - start
    while turn < 0.0: turn += 2.0 * math.pi
    # Past the end: the shorter way, before the start (negative) or after
    # the end.
    if turn > sweep and turn - sweep > 2.0 * math.pi - turn: turn -= 2.0 * math.pi
    return turn / sweep

## Whether a point can be held on a curve of kind `kind`.
func holds_points(kind: EntityKind) -> bool:
    return kind == EntityKind.line or kind == EntityKind.circle or kind == EntityKind.arc or kind == EntityKind.ellipse

func require_curve(sketch: const Sketch*, curve: i64) -> !:
    if curve < 0 or curve >= (i64)sketch.entities.count or sketch.entity(curve).kind == EntityKind.point:
        error(invalid, "this works on a sketch's curves")
    if is_sampled(sketch.entity(curve).kind):
        error(invalid, "this works on lines, circles and arcs (a spline, ellipse or conic goes whole with Delete)")

## The entity of `sketch` nearest (`x`, `y`) within `reach`: a point if one
## is that near, else the nearest curve (`only` as pick has it).
func nearest(sketch: const Sketch*, x: f64, y: f64, reach: f64, only: i64) -> i64:
    var best: i64 = -1
    var best_distance = reach
    for pass in 0..<(usize)2:
        if (only == 1 and pass == 1) or (only == 2 and pass == 0): continue
        for index in 0..<sketch.entities.count:
            let e = sketch.entities.items[index]
            if (pass == 0) != (e.kind == EntityKind.point): continue
            let d = distance_to(sketch, e, (i64)index, x, y)
            if d <= best_distance:
                best = (i64)index
                best_distance = d
        if best >= 0: return best
    return -1

## Points along curve `e` onto `out` (replacing it): a line's ends, a
## circle's or arc's `count` + 1 along it, a free-form curve's `count` + 1
## along its parameter, a text's outline pieces each ended by a NaN pair.
func sample_curve(sketch: const Sketch*, e: SketchEntity, count: usize, out: Growing[f64]*) -> !:
    out.clear()
    if e.kind == EntityKind.line:
        for p in [e.first, e.second]:
            try out.push(sketch.x(p))
            try out.push(sketch.y(p))
    elif e.kind == EntityKind.circle or e.kind == EntityKind.arc:
        let cx = sketch.x(e.first)
        let cy = sketch.y(e.first)
        let r = sketch.params.items[(usize)e.second]
        var start = 0.0
        var sweep = 2.0 * math.pi
        if e.kind == EntityKind.arc:
            let (arc_start, arc_turn) = arc_sweep(sketch, e)
            start = arc_start
            sweep = arc_turn
        for k in 0..<count + 1:
            let angle = start + sweep * (f64)k / (f64)count
            try out.push(cx + r * math.cos(angle))
            try out.push(cy + r * math.sin(angle))
    elif e.kind == EntityKind.text:
        var letters = new_lettering()
        defer letters.close()
        try letter(sketch, e, &letters)
        for piece in 0..<letters.count():
            let steps: usize = 1 if letters.degrees.items[piece] == 1 else 8
            for k in 0..<steps + 1:
                let (x, y) = letters.at(piece, (f64)k / (f64)steps)
                try out.push(x)
                try out.push(y)
            try out.push(math.nan)
            try out.push(math.nan)
    elif e.kind != EntityKind.point:
        var net = new_net()
        defer net.close()
        try net_of(sketch, e, &net)
        try net.sample(count, out)

## How far (`x`, `y`) is from entity `e` (index `at`).
func distance_to(sketch: const Sketch*, e: SketchEntity, at: i64, x: f64, y: f64) -> f64:
    if e.kind == EntityKind.point: return math.hypot(sketch.x(at) - x, sketch.y(at) - y)
    if is_sampled(e.kind):
        # A spline, ellipse, conic or text: its samples as polylines.
        var points = Growing[f64]()
        defer points.close()
        sample_curve(sketch, e, 96, &points) catch failure:
            return 1e300
        var best = 1e300
        for k in 0..<points.count // 2 - 1:
            if math.is_nan(points.items[2 * k]) or math.is_nan(points.items[2 * k + 2]): continue
            best = math.min(best, segment_distance(x, y, points.items[2 * k], points.items[2 * k + 1], points.items[2 * k + 2], points.items[2 * k + 3]))
        return best
    if e.kind == EntityKind.line:
        let ax = sketch.x(e.first)
        let ay = sketch.y(e.first)
        let dx = sketch.x(e.second) - ax
        let dy = sketch.y(e.second) - ay
        let l2 = dx * dx + dy * dy
        let t = math.max(0.0, math.min(1.0, ((x - ax) * dx + (y - ay) * dy) / l2)) if l2 > 0.0 else 0.0
        return math.hypot(ax + t * dx - x, ay + t * dy - y)
    let cx = sketch.x(e.first)
    let cy = sketch.y(e.first)
    let r = sketch.params.items[(usize)e.second]
    let off = math.abs(math.hypot(x - cx, y - cy) - r)
    if e.kind == EntityKind.circle: return off
    # An arc: on its sweep, the distance to its circle; else to its ends.
    let (start, sweep) = arc_sweep(sketch, e)
    var along = math.atan2(y - cy, x - cx) - start
    while along < 0.0: along += 2.0 * math.pi
    if along <= sweep: return off
    return math.min(math.hypot(sketch.x(e.third) - x, sketch.y(e.third) - y), math.hypot(sketch.x(e.fourth) - x, sketch.y(e.fourth) - y))

## How far (`x`, `y`) is from the segment (`ax`, `ay`)-(`bx`, `by`).
func segment_distance(x: f64, y: f64, ax: f64, ay: f64, bx: f64, by: f64) -> f64:
    let dx = bx - ax
    let dy = by - ay
    let l2 = dx * dx + dy * dy
    let t = math.max(0.0, math.min(1.0, ((x - ax) * dx + (y - ay) * dy) / l2)) if l2 > 0.0 else 0.0
    return math.hypot(ax + t * dx - x, ay + t * dy - y)

## The place on curve `curve` closest (`x`, `y`).
func nearest_on(sketch: const Sketch*, curve: i64, x: f64, y: f64) -> (f64, f64):
    let e = sketch.entity(curve)
    if e.kind == EntityKind.line:
        let place = math.max(0.0, math.min(1.0, place_of(sketch, curve, x, y)))
        return at_place(sketch, curve, place)
    if e.kind == EntityKind.circle or e.kind == EntityKind.arc:
        let cx = sketch.x(e.first)
        let cy = sketch.y(e.first)
        let d = math.hypot(x - cx, y - cy)
        if d <= 0.0: return (x, y)
        if e.kind == EntityKind.arc:
            let place = place_of(sketch, curve, x, y)
            if place < 0.0 or place > 1.0: return at_place(sketch, curve, math.max(0.0, math.min(1.0, place)))
        let r = sketch.radius_of(curve)
        return (cx + (x - cx) * r / d, cy + (y - cy) * r / d)
    # A free-form curve: its closest sample.
    var points = Growing[f64]()
    defer points.close()
    sample_curve(sketch, e, 192, &points) catch failure:
        return (x, y)
    var best = 1e300
    var bx = x
    var by = y
    for k in 0..<points.count // 2:
        let d = math.hypot(points.items[2 * k] - x, points.items[2 * k + 1] - y)
        if d < best:
            best = d
            bx = points.items[2 * k]
            by = points.items[2 * k + 1]
    return (bx, by)

## `value` onto `out` unless it is there already.
func add_once(out: Growing[i64]*, value: i64) -> !:
    for v in out.view():
        if v == value: return
    try out.push(value)