SPB Git

Repository Public

ShapeRecognizer.swift 22.2 KB 429 lines swift

1// SP Notes iOS2// File: Core/Ink/ShapeRecognizer.swift3// Description: Smart shapes: recognises a line, an arrow, a rectangle, a triangle or an ellipse / circle in the points of one4//              hand-drawn stroke. Pure geometry (resampling, corner detection, closedness, least-squares fits, a confidence5//              threshold); no machine learning, no UI framework. Anything that is not clearly one of the five shapes is left alone.6//7// Author: Simon-Pierre Boucher8// Contact: contact@spboucher.ai9import CoreGraphics10import Foundation1112/// A clean shape, in the coordinates of the stroke it was recognised from.13enum RecognizedShape: Equatable, Sendable {14    case line(from: CGPoint, to: CGPoint)15    /// The head is at `to`.16    case arrow(from: CGPoint, to: CGPoint)17    /// `rotation` in radians, in (−π/4, π/4]: the angle of the side called `width`.18    case rectangle(center: CGPoint, size: CGSize, rotation: CGFloat)19    /// `radii.width` along the axis at `rotation` (radians), `radii.height` across. A circle has equal radii and rotation 0.20    case ellipse(center: CGPoint, radii: CGSize, rotation: CGFloat)21    case triangle(CGPoint, CGPoint, CGPoint)2223    enum Kind: String, Sendable { case line, arrow, rectangle, ellipse, triangle }2425    var kind: Kind {26        switch self {27        case .line: .line28        case .arrow: .arrow29        case .rectangle: .rectangle30        case .ellipse: .ellipse31        case .triangle: .triangle32        }33    }3435    /// The corners of a rectangle, clockwise on screen from the top-left one of the unrotated box.36    static func corners(center: CGPoint, size: CGSize, rotation: CGFloat) -> [CGPoint] {37        let c = cos(rotation), s = sin(rotation), w = size.width / 2, h = size.height / 238        return [(-w, -h), (w, -h), (w, h), (-w, h)].map { CGPoint(x: center.x + $0.0 * c - $0.1 * s, y: center.y + $0.0 * s + $0.1 * c) }39    }4041    /// The two barbs of an arrow head at `to`.42    static func arrowHead(from: CGPoint, to: CGPoint) -> (CGPoint, CGPoint) {43        let length = hypot(to.x - from.x, to.y - from.y)44        guard length > 0 else { return (to, to) }45        let barb = min(max(length * 0.22, 10), 28), angle = atan2(from.y - to.y, from.x - to.x), spread = CGFloat.pi / 746        return (CGPoint(x: to.x + barb * cos(angle + spread), y: to.y + barb * sin(angle + spread)),47                CGPoint(x: to.x + barb * cos(angle - spread), y: to.y + barb * sin(angle - spread)))48    }4950    /// The outline as polylines whose vertices are the corners of the shape (an ellipse is sampled every few degrees).51    var outlines: [[CGPoint]] {52        switch self {53        case .line(let a, let b): return [[a, b]]54        case .arrow(let a, let b):55            let (l, r) = Self.arrowHead(from: a, to: b)56            return [[a, b], [l, b, r]]57        case .rectangle(let center, let size, let rotation):58            let c = Self.corners(center: center, size: size, rotation: rotation)59            return [c + [c[0]]]60        case .triangle(let a, let b, let c): return [[a, b, c, a]]61        case .ellipse(let center, let radii, let rotation):62            let c = cos(rotation), s = sin(rotation), n = 7263            return [(0...n).map { i -> CGPoint in64                let t = CGFloat(i % n) / CGFloat(n) * 2 * .pi, x = radii.width * cos(t), y = radii.height * sin(t)65                return CGPoint(x: center.x + x * c - y * s, y: center.y + x * s + y * c)66            }]67        }68    }6970    /// True for the outlines whose vertices are sharp corners (everything but the ellipse).71    var hasCorners: Bool { kind != .ellipse }72}7374struct ShapeMatch: Equatable, Sendable {75    var shape: RecognizedShape76    /// 0…1: 1 = the stroke lies exactly on the shape.77    var confidence: Double78}7980enum ShapeRecognizer {81    struct Options: Sendable {82        /// Below this the stroke is left as drawn.83        var minimumConfidence = 0.5584        /// Strokes smaller than this (diagonal of their box, in points) are never shapes: dots, commas, small letters.85        var minimumSize: CGFloat = 2886        /// A rectangle within this angle of the axes is made upright; a line within it is made horizontal / vertical.87        var snapAngle: CGFloat = 5 * .pi / 18088        static let standard = Options()89    }9091    static func recognize(_ raw: [CGPoint], options: Options = .standard) -> ShapeMatch? {92        let input = dedupe(raw.filter { $0.x.isFinite && $0.y.isFinite })93        guard input.count >= 3 else { return nil }94        let box = bounds(input), diagonal = hypot(box.width, box.height)95        guard diagonal >= options.minimumSize else { return nil }96        let length = pathLength(input)97        guard length > 0 else { return nil }9899        var candidates: [ShapeMatch] = []100        if let closed = closedLoop(input, length: length) {101            let loop = resample(closed, count: 128)102            if let polygon = polygon(loop, diagonal: diagonal, options: options) { candidates.append(polygon) }103            if let ellipse = ellipse(loop, options: options) { candidates.append(ellipse) }104        } else {105            let points = resample(input, count: 96)106            if let line = line(points, length: length, options: options) { candidates.append(line) }107            else if let arrow = arrow(points, diagonal: diagonal) { candidates.append(arrow) }108        }109        guard let best = candidates.max(by: { $0.confidence < $1.confidence }), best.confidence >= options.minimumConfidence else { return nil }110        return best111    }112113    // MARK: line114115    private static func line(_ points: [CGPoint], length: CGFloat, options: Options) -> ShapeMatch? {116        guard let first = points.first, let last = points.last else { return nil }117        let chord = distance(first, last)118        // the length of the stroke without the tremor of the hand119        let steady = pathLength(smoothedOpen(points, window: 2))120        guard chord > 0, steady / chord < 1.06 else { return nil }121        let (centroid, direction) = principalAxis(points)122        let normal = CGPoint(x: -direction.y, y: direction.x)123        var worst: CGFloat = 0, sum: CGFloat = 0124        for p in points {125            let d = abs((p.x - centroid.x) * normal.x + (p.y - centroid.y) * normal.y)126            worst = max(worst, d); sum += d127        }128        let mean = sum / CGFloat(points.count)129        let error = max(worst / chord / 0.05, mean / chord / 0.02)130        guard error < 1 else { return nil }131        func project(_ p: CGPoint) -> CGPoint {132            let t = (p.x - centroid.x) * direction.x + (p.y - centroid.y) * direction.y133            return CGPoint(x: centroid.x + t * direction.x, y: centroid.y + t * direction.y)134        }135        var a = project(first), b = project(last)136        let angle = atan2(b.y - a.y, b.x - a.x)137        // nearly horizontal or vertical: made exactly so, around the middle of the line138        let mid = CGPoint(x: (a.x + b.x) / 2, y: (a.y + b.y) / 2), half = distance(a, b) / 2139        for target in [0, CGFloat.pi / 2, .pi, -CGFloat.pi / 2, -.pi] where abs(angle - target) < options.snapAngle {140            a = CGPoint(x: mid.x - half * cos(target), y: mid.y - half * sin(target))141            b = CGPoint(x: mid.x + half * cos(target), y: mid.y + half * sin(target))142        }143        return ShapeMatch(shape: .line(from: a, to: b), confidence: Double(1 - error * 0.5))144    }145146    // MARK: arrow147148    /// A one-stroke arrow: the shaft, then the head drawn without lifting — barb, back to the tip, other barb (`A T B T B`), or149    /// the head closed as a small triangle (`A T B B T`).150    private static func arrow(_ points: [CGPoint], diagonal: CGFloat) -> ShapeMatch? {151        let vertices = mergeClose(simplify(points, tolerance: diagonal * 0.035), minimum: diagonal * 0.05)152        guard vertices.count == 5 else { return nil }153        let tail = vertices[0], tip = vertices[1], shaft = distance(tail, tip)154        guard shaft > diagonal * 0.6 else { return nil }155        let barbs: [CGPoint]156        if distance(vertices[3], tip) < shaft * 0.14 { barbs = [vertices[2], vertices[4]] }          // A T B T B157        else if distance(vertices[4], tip) < shaft * 0.14 { barbs = [vertices[2], vertices[3]] }     // A T B B T158        else { return nil }159        let back = atan2(tail.y - tip.y, tail.x - tip.x)160        var sides: [CGFloat] = [], error: CGFloat = 0161        for barb in barbs {162            let length = distance(barb, tip)163            guard length > shaft * 0.07, length < shaft * 0.6 else { return nil }164            let angle = normalized(atan2(barb.y - tip.y, barb.x - tip.x) - back)165            guard abs(angle) > 10 * .pi / 180, abs(angle) < 75 * .pi / 180 else { return nil }166            sides.append(angle)167            error = max(error, abs(abs(angle) - .pi / 6) / (.pi / 3))168        }169        guard sides[0] * sides[1] < 0 else { return nil } // one barb on each side of the shaft170        // the shaft itself must be straight171        let shaftPoints = points.prefix { distance($0, tip) > shaft * 0.05 }172        let deviation = shaftPoints.map { segmentDistance($0, tail, tip) }.max() ?? 0173        guard deviation / shaft < 0.06 else { return nil }174        error = max(error, deviation / shaft / 0.06)175        return ShapeMatch(shape: .arrow(from: tail, to: tip), confidence: Double(1 - error * 0.45))176    }177178    // MARK: polygons (triangle, rectangle)179180    private static func polygon(_ loop: [CGPoint], diagonal: CGFloat, options: Options) -> ShapeMatch? {181        // start at the point farthest from the centroid — a corner of any polygon — so no corner is split by the closure182        let centroid = mean(loop)183        guard let start = loop.indices.max(by: { distance(loop[$0], centroid) < distance(loop[$1], centroid) }) else { return nil }184        let rotated = Array(loop[start...] + loop[..<start]) + [loop[start]]185        var vertices = mergeClose(simplify(rotated, tolerance: diagonal * 0.045), minimum: diagonal * 0.08)186        while vertices.count > 1, distance(vertices[0], vertices[vertices.count - 1]) < diagonal * 0.08 { vertices.removeLast() }187        vertices = dropFlat(vertices, maximumAngle: 152 * .pi / 180)188        guard vertices.count == 3 || vertices.count == 4 else { return nil }189        // every point of the stroke must lie near the polygon190        var sum: CGFloat = 0, worst: CGFloat = 0191        for p in loop {192            var best = CGFloat.infinity193            for i in vertices.indices { best = min(best, segmentDistance(p, vertices[i], vertices[(i + 1) % vertices.count])) }194            sum += best; worst = max(worst, best)195        }196        let error = max(sum / CGFloat(loop.count) / diagonal / 0.022, worst / diagonal / 0.075)197        guard error < 1 else { return nil }198        let confidence = Double(1 - error * 0.45)199200        if vertices.count == 3 {201            let angles = interiorAngles(vertices)202            guard angles.allSatisfy({ $0 > 14 * .pi / 180 }) else { return nil }203            return ShapeMatch(shape: .triangle(vertices[0], vertices[1], vertices[2]), confidence: confidence)204        }205        let angles = interiorAngles(vertices)206        guard angles.allSatisfy({ abs($0 - .pi / 2) < 20 * .pi / 180 }) else { return nil }207        let sides = (0..<4).map { distance(vertices[$0], vertices[($0 + 1) % 4]) }208        guard min(sides[0], sides[2]) / max(sides[0], sides[2]) > 0.72, min(sides[1], sides[3]) / max(sides[1], sides[3]) > 0.72 else { return nil }209        // orientation: the mean direction of the four sides, modulo a quarter turn210        var sx: CGFloat = 0, sy: CGFloat = 0211        for i in 0..<4 {212            let a = vertices[i], b = vertices[(i + 1) % 4], angle = atan2(b.y - a.y, b.x - a.x) * 4213            sx += cos(angle) * sides[i]; sy += sin(angle) * sides[i]214        }215        var rotation = atan2(sy, sx) / 4 // in (−π/4, π/4]216        if abs(rotation) < options.snapAngle { rotation = 0 }217        let c = cos(-rotation), s = sin(-rotation)218        let local = vertices.map { CGPoint(x: $0.x * c - $0.y * s, y: $0.x * s + $0.y * c) }219        let xs = local.map(\.x).sorted(), ys = local.map(\.y).sorted()220        // each side of the box is the mean of the two corners that define it221        let minX = (xs[0] + xs[1]) / 2, maxX = (xs[2] + xs[3]) / 2, minY = (ys[0] + ys[1]) / 2, maxY = (ys[2] + ys[3]) / 2222        let lc = CGPoint(x: (minX + maxX) / 2, y: (minY + maxY) / 2)223        let center = CGPoint(x: lc.x * cos(rotation) - lc.y * sin(rotation), y: lc.x * sin(rotation) + lc.y * cos(rotation))224        return ShapeMatch(shape: .rectangle(center: center, size: CGSize(width: maxX - minX, height: maxY - minY), rotation: rotation), confidence: confidence)225    }226227    // MARK: ellipse228229    private static func ellipse(_ loop: [CGPoint], options: Options) -> ShapeMatch? {230        // one turn, always the same way231        var winding: CGFloat = 0232        let smooth = smoothed(loop, window: 3)233        // along the stroke as drawn (the closing jump from its end to its start is not a turn of the pen)234        for i in 0..<max(0, smooth.count - 2) {235            let a = smooth[i], b = smooth[i + 1], c = smooth[i + 2]236            winding += normalized(atan2(c.y - b.y, c.x - b.x) - atan2(b.y - a.y, b.x - a.x))237        }238        guard abs(winding) > 1.6 * .pi, abs(winding) < 2.5 * .pi else { return nil }239        let (centroid, direction) = principalAxis(loop)240        let c = direction.x, s = direction.y241        let local = loop.map { CGPoint(x: ($0.x - centroid.x) * c + ($0.y - centroid.y) * s, y: -($0.x - centroid.x) * s + ($0.y - centroid.y) * c) }242        let minX = local.map(\.x).min() ?? 0, maxX = local.map(\.x).max() ?? 0, minY = local.map(\.y).min() ?? 0, maxY = local.map(\.y).max() ?? 0243        var a = (maxX - minX) / 2, b = (maxY - minY) / 2244        guard a > 4, b > 4, b / a > 0.12 else { return nil }245        let lc = CGPoint(x: (minX + maxX) / 2, y: (minY + maxY) / 2)246        var sum: CGFloat = 0, worst: CGFloat = 0247        for p in local {248            let r = sqrt(pow((p.x - lc.x) / a, 2) + pow((p.y - lc.y) / b, 2))249            sum += (r - 1) * (r - 1); worst = max(worst, abs(r - 1))250        }251        let rms = sqrt(sum / CGFloat(local.count))252        let error = max(rms / 0.085, worst / 0.24)253        guard error < 1 else { return nil }254        let center = CGPoint(x: centroid.x + lc.x * c - lc.y * s, y: centroid.y + lc.x * s + lc.y * c)255        var rotation = atan2(s, c)256        if abs(a - b) / max(a, b) < 0.12 {257            // nearly round: a circle258            a = (a + b) / 2; b = a; rotation = 0259        } else {260            rotation = normalizedHalfTurn(rotation)261            for target in [0, CGFloat.pi / 2, -CGFloat.pi / 2] where abs(rotation - target) < options.snapAngle { rotation = target }262        }263        return ShapeMatch(shape: .ellipse(center: center, radii: CGSize(width: a, height: b), rotation: rotation), confidence: Double(1 - error * 0.45))264    }265266    // MARK: closedness267268    /// The stroke as a closed loop (ends trimmed where they overlap), or nil when it is open.269    private static func closedLoop(_ points: [CGPoint], length: CGFloat) -> [CGPoint]? {270        guard let first = points.first, let last = points.last else { return nil }271        // where the end of the stroke comes closest to its start (the pen often goes a little past it)272        let tailStart = Int(Double(points.count) * 0.8)273        guard tailStart > 2, let nearest = (tailStart..<points.count).min(by: { distance(points[$0], first) < distance(points[$1], first) }) else { return nil }274        let closes = distance(first, last) / length < 0.1 || distance(points[nearest], first) / length < 0.05275        guard closes else { return nil }276        var loop = Array(points[...nearest])277        if let end = loop.last, distance(end, first) < 0.5, loop.count > 3 { loop.removeLast() }278        return loop279    }280281    // MARK: geometry282283    static func distance(_ a: CGPoint, _ b: CGPoint) -> CGFloat { hypot(a.x - b.x, a.y - b.y) }284285    static func pathLength(_ points: [CGPoint]) -> CGFloat {286        guard points.count > 1 else { return 0 }287        return (1..<points.count).reduce(0) { $0 + distance(points[$1 - 1], points[$1]) }288    }289290    static func bounds(_ points: [CGPoint]) -> CGRect {291        guard let first = points.first else { return .null }292        var minX = first.x, maxX = first.x, minY = first.y, maxY = first.y293        for p in points { minX = min(minX, p.x); maxX = max(maxX, p.x); minY = min(minY, p.y); maxY = max(maxY, p.y) }294        return CGRect(x: minX, y: minY, width: maxX - minX, height: maxY - minY)295    }296297    private static func dedupe(_ points: [CGPoint]) -> [CGPoint] {298        var out: [CGPoint] = []299        for p in points where out.last.map({ distance($0, p) > 0.01 }) ?? true { out.append(p) }300        return out301    }302303    private static func mean(_ points: [CGPoint]) -> CGPoint {304        let n = CGFloat(max(1, points.count))305        return CGPoint(x: points.reduce(0) { $0 + $1.x } / n, y: points.reduce(0) { $0 + $1.y } / n)306    }307308    /// `count` points at equal distances along the polyline.309    static func resample(_ points: [CGPoint], count: Int) -> [CGPoint] {310        let total = pathLength(points)311        guard points.count > 1, total > 0, count > 1 else { return points }312        let step = total / CGFloat(count - 1)313        var out: [CGPoint] = [points[0]], carried: CGFloat = 0, previous = points[0], i = 1314        while i < points.count, out.count < count - 1 {315            let d = distance(previous, points[i])316            if carried + d >= step, d > 0 {317                let t = (step - carried) / d318                let q = CGPoint(x: previous.x + t * (points[i].x - previous.x), y: previous.y + t * (points[i].y - previous.y))319                out.append(q); previous = q; carried = 0320            } else {321                carried += d; previous = points[i]; i += 1322            }323        }324        out.append(points[points.count - 1])325        return out326    }327328    /// Centroid and unit direction of the largest spread (total least squares).329    private static func principalAxis(_ points: [CGPoint]) -> (CGPoint, CGPoint) {330        let c = mean(points)331        var sxx: CGFloat = 0, sxy: CGFloat = 0, syy: CGFloat = 0332        for p in points { let dx = p.x - c.x, dy = p.y - c.y; sxx += dx * dx; sxy += dx * dy; syy += dy * dy }333        let angle = 0.5 * atan2(2 * sxy, sxx - syy)334        return (c, CGPoint(x: cos(angle), y: sin(angle)))335    }336337    static func segmentDistance(_ p: CGPoint, _ a: CGPoint, _ b: CGPoint) -> CGFloat {338        let dx = b.x - a.x, dy = b.y - a.y, len2 = dx * dx + dy * dy339        let t = len2 > 0 ? min(1, max(0, ((p.x - a.x) * dx + (p.y - a.y) * dy) / len2)) : 0340        return hypot(p.x - (a.x + t * dx), p.y - (a.y + t * dy))341    }342343    /// Ramer–Douglas–Peucker: the corners of a polyline.344    private static func simplify(_ points: [CGPoint], tolerance: CGFloat) -> [CGPoint] {345        guard points.count > 2 else { return points }346        var keep = [Bool](repeating: false, count: points.count)347        keep[0] = true; keep[points.count - 1] = true348        var stack = [(0, points.count - 1)]349        while let (a, b) = stack.popLast() {350            guard b > a + 1 else { continue }351            var worst: CGFloat = 0, index = -1352            for i in (a + 1)..<b {353                let d = segmentDistance(points[i], points[a], points[b])354                if d > worst { worst = d; index = i }355            }356            if worst > tolerance, index > 0 { keep[index] = true; stack.append((a, index)); stack.append((index, b)) }357        }358        return points.indices.filter { keep[$0] }.map { points[$0] }359    }360361    /// Consecutive vertices closer than `minimum` are merged into their middle (a corner drawn as a tiny hook).362    private static func mergeClose(_ vertices: [CGPoint], minimum: CGFloat) -> [CGPoint] {363        var out: [CGPoint] = []364        for (index, v) in vertices.enumerated() {365            if let last = out.last, distance(last, v) < minimum, index != vertices.count - 1, out.count > 1 {366                out[out.count - 1] = CGPoint(x: (last.x + v.x) / 2, y: (last.y + v.y) / 2)367            } else if let last = out.last, distance(last, v) < minimum, index == vertices.count - 1, out.count > 1 {368                out[out.count - 1] = v // the end point is kept exactly369            } else {370                out.append(v)371            }372        }373        return out374    }375376    /// Removes the vertices of a closed polygon where the outline barely turns.377    private static func dropFlat(_ vertices: [CGPoint], maximumAngle: CGFloat) -> [CGPoint] {378        var current = vertices379        while current.count > 3 {380            let angles = interiorAngles(current)381            guard let flattest = angles.indices.max(by: { angles[$0] < angles[$1] }), angles[flattest] > maximumAngle else { break }382            current.remove(at: flattest)383        }384        return current385    }386387    private static func interiorAngles(_ polygon: [CGPoint]) -> [CGFloat] {388        polygon.indices.map { i in389            let p = polygon[i], a = polygon[(i + polygon.count - 1) % polygon.count], b = polygon[(i + 1) % polygon.count]390            return abs(normalized(atan2(a.y - p.y, a.x - p.x) - atan2(b.y - p.y, b.x - p.x)))391        }392    }393394    private static func smoothed(_ loop: [CGPoint], window: Int) -> [CGPoint] {395        let n = loop.count396        guard n > 2 * window + 1 else { return loop }397        return (0..<n).map { i in398            var x: CGFloat = 0, y: CGFloat = 0399            for k in -window...window { let p = loop[(i + k + n) % n]; x += p.x; y += p.y }400            return CGPoint(x: x / CGFloat(2 * window + 1), y: y / CGFloat(2 * window + 1))401        }402    }403404    private static func smoothedOpen(_ points: [CGPoint], window: Int) -> [CGPoint] {405        let n = points.count406        guard n > 2 * window + 1 else { return points }407        return (0..<n).map { i in408            let lo = max(0, i - window), hi = min(n - 1, i + window), count = CGFloat(hi - lo + 1)409            return CGPoint(x: points[lo...hi].reduce(0) { $0 + $1.x } / count, y: points[lo...hi].reduce(0) { $0 + $1.y } / count)410        }411    }412413    /// An angle brought back to (−π, π].414    static func normalized(_ angle: CGFloat) -> CGFloat {415        var a = angle.truncatingRemainder(dividingBy: 2 * .pi)416        if a > .pi { a -= 2 * .pi }417        if a <= -.pi { a += 2 * .pi }418        return a419    }420421    /// The orientation of an axis (no direction), in (−π/2, π/2].422    static func normalizedHalfTurn(_ angle: CGFloat) -> CGFloat {423        var a = normalized(angle)424        if a > .pi / 2 { a -= .pi }425        if a <= -.pi / 2 { a += .pi }426        return a427    }428}429
Files main
Menu

Theme